Question

Show that if a game of nim begins with two piles containing the same number of stones, as long as this number is at least two, then the second player wins when both players follow optimal strategies.

Short answer

One can conclude that when a nim game starts with an equal number of stones in two piles, always the winner will be player-2 if he plays in an optimal way.

Step-by-step solution

The value of a vertex of a game tree tells us the payoff to the first player if both players follow the minmax strategy and play starts from the position represented by this vertex.

If the vertex is a leaf, by definition the value assigned to this vertex is the payoff to the first player.

One shall show that if two piles of an equal number of stones is the initial position for a nim game, then always the second player will win if he follows an optimal path.

Player-1 has the following options to remove the stones from an equal number of 17 stones in two piles:

1) Remove one entire pile, in which player-2 will remove the \({\bf{n - 1}}\) stones from the second pile and wins.

2) Remove \({\bf{n - 1}}\) stones from a pile and in this case, also the player-2 will win the game by removing entire another pile of stones.

3) Remove an equal number of stones from the piles which again results in an equal number of piles.

4) If player-1 removes an unequal number of stones and makes the pile unequal, player-2 can remove the stones in the next move in such a way that again the piles should contain an equal number of stones.

Final conclusion

Therefore, it is clear that always player-2 can make two piles of equal numbers.

So, player-2 can make the piles \(\left( {{\bf{2 2}}} \right)\). If player-1 plays with \(\left( {{\bf{2 2}}} \right)\) position the results of the possible moves are: \(\left( {{\bf{1 1}}} \right){\bf{ }}\left( {{\bf{1 2}}} \right){\bf{ }}\left( {\bf{2}} \right)\) and in any of these cases player-2 will win the game.

Therefore, one can conclude that when a nim game starts with an equal number of stones in two piles, always the winner will be player-2 if he plays in an optimal way.