Proof player 2 always wins by mirroring (Nim)

One version of a game called Nim is played as follows. There are two players and two piles consisting of the same natural number of objects; for this example, suppose the objects are nickels. At each turn, a player removes some number of nickels from either one of the piles. Then the other player removes some number of nickels from either of the piles. The players continue playing alternately until the last nickel is removed. The winner is the player who removes the last nickel.

Prove: If the second player always removes the same number of nickels that the first player last removed and does so from the other pile (thus making the piles equal in number after the second player’s turn), then the second player will win.

Here’s a clean “mirror”‐strategy proof that the second player (P₂) will always win.

---

Setup. – Two piles, each of size $n$. – Players alternate: P₁ goes first, then P₂, etc. – On your turn you remove any positive number of nickels from exactly one pile. – Whoever takes the very last nickel (i.e. empties the last nonempty pile) wins.

---

1. The Mirror Strategy

P₂’s rule. On each of P₁’s moves, say P₁ removes $k$ nickels from one of the piles. Then P₂ immediately removes $k$ nickels from the other pile.

Because the two piles were equal just before P₁’s move, removing $k$ from one leaves one pile of size $n-k$ and the other still size $n$. Then P₂ can legally remove $k$ from that size-$n$ pile (since $k\le n$), restoring both piles to size $n-k$.

Thus:

Invariant. At the end of each of P₂’s turns, the two piles are the same size.

---

2. Why This Guarantees a Win

1. Base case (start of play). Before anyone moves, both piles are size $n$. So the invariant holds.

2. Preservation. If at the end of one of P₂’s turns both piles are size $m$, then:

   1. P₁ removes $k$ from one pile (with $1\le k\le m$), leaving piles $(m-k,m)$.
   2. P₂ then removes $k$ from the other pile, leaving $(m-k,m-k)$.
   3. Hence after P₂’s turn both piles are again the same size ($m-k$).

3. Termination & win. Eventually the piles shrink down. The first time P₁ empties a pile, say he takes all $m$ remaining nickels from one pile, we have:

   $$ \text{After P₁’s move: piles } (0,\,m). $$

   By the invariant $m$ is exactly how many are in the “other” pile. P₂ then removes those last $m$ nickels from that other pile—legally and wholly—leaving $(0,0)$ and thus taking the very last coin.

Since P₂ never violates the rules (he always takes at most what’s available), and since this mirror‐move process ensures he makes the final removal, P₂ is guaranteed to win. ∎