Question

Show that if a game of nim begins with two piles containing different numbers of stones, the first player wins when both players follow optimal strategies.

Short answer

One can infer that player-1 wins always in the above two cases.

Step-by-step solution

Step 1: 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 a game of nim begins with two piles containing different numbers of stones, the first player wins when both players follow optimal strategies.

If the player-1 starts with two piles of a different number of stones, the position may be either of the cases:

1) The smaller pile contains one stone and the larger pile contains a greater number of stones. In this case, player-1 can remove the entire greater pile and can win the game.

2) The smaller pile contains stones equal to or greater than \({\bf{2}}\) and the larger pile contains stones greater than the smaller pile.

Final conclusion

Therefore, player-1 can remove stones in such a way that the two piles are equal. The player-2 starts the next move with two piles of an equal number of stones.

Since the player who plays first with an equal number of stones in the pile loses, player-2 loses in such a path.

Hence, one can infer that player-1 wins always in the above two cases.