Players A and B are playing a game:
Assuming that the players will play optimally, which player can confirm their victory?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Relevant wiki: Invariant Principle - Problem Solving
Lemma: If there are 5 n pieces left for some positive integer n , then the second person to move will win.
Proof: Let's suppose there are 5 n pieces left with some positive integer n . This means that the second player is able to force 5 ( n − 1 ) pieces to be left after their next turn. That is, if the first player picks 3, the second player will pick 2, and if the first player picks 2, the second player will pick 3. Finally, there will be 5 pieces left, and no matter what the first player now picks, the second player will win. □
In this game, there are 29 pieces, that is 5 n + 4 with n = 5 , so player A can't become "the second player" described above with their first turn. If player A now picked 2 pieces, there would be 27 pieces left, giving player B the opportunity to force 25 pieces on the board which is 5 n with n = 5 which would mean player B would become "the second player" and B's victory would be confirmed. For this reason, A picks 3, leaving 26 pieces.
Now, if B picked 3, player A would have the opportunity to confirm his victory by picking 3 and leaving 20 which is 5 n with n = 4 . Instead, player B picks 2 and leaves 24 pieces on the board.
Now the situation is similar to the starting situation: There are 5 n + 4 pieces on the board with a positive integer n and it's player A's turn. The actions described above will repeat themselves until there are 4 pieces and it's A's turn again. As picking 2 now would let player B win by picking 2, player A picks 3, leaving only 1 piece and forcing the game to be tied.
This means, n e i t h e r player can confirm their victory.
Corollary: If there are 5 n + 4 pieces left for some positive integer n , then the game will tie.
Can you figure out what happens for 5 n + 1 , 5 n + 2 , 5 n + 3 pieces?