Discrete Math In the parlour game Nim there are two players

Discrete Math:

In the parlour game Nim, there are two players and two piles of matches. At each turn, a player removes some (non-zero) number of matches from one of the piles. The player who removes the last match wins.

Prove that if the two piles contain the same number of matches at the start of the game, then the second player can always win.

Solution

A winning strategy for the second player is that if first player removes: m matches from one pile second player in his turn must remove m matches from the other pile.

We prove this by induction on number of matches, n

Base case : n=1

Each pile has 1 match.

Only one move for first player ie to remove 1 match from either pile. Then second player can also remove the last remaining match and win the game. So base case is true.

Inductive Step (Using strong induction)

Suppose it is true for:

1<=n<=k

We will show it is also true for n=k+1

Suppose we have two piles with : k+1 matches in each.

First player removes: R matches from one pile. No we are left with two piles:

One with k+1 matches and other with: k+1-R

If k+1=R ,one pile is empty and second player wins after removing k+1 matches from the other pile.

Else, second player removes: R matches from the pile with k+1 matches.

Now it is first player\'s turn with: k+1-R matches in each pile.

By our assumption: second player wins in this case ie for: n<=k

Hence, second player wins for n=k+1

Hence second player always wins for all values of n.