Two piles, take from one or equally from both

Question

Two piles of stones hold 3 and 5 stones. On each turn a player either removes any positive number of stones from one pile, or removes the same positive number from both piles. The player who takes the last stone (leaving both piles empty) wins. With best play, does the first or the second player win from (3, 5)? Justify it by finding the losing positions with small piles.

Accepted Answer

The second player wins: (3, 5) is a losing position for the player to move. Finding the losing positions. A position is losing if every move from it leads to a winning position, and winning if some move leads to a losing one. - (0, 0): losing (no moves). - Any (0, n), (n, 0) or (n, n) with n at least 1 is winning: empty the one pile, or take n from both. - (1, 2): moves lead to (0, 2), (1, 0), (1, 1) or (0, 1), all winning for the opponent. So (1, 2) is losing. - Any position from which (1, 2) is reachable in one move is winning. That covers (1, n) for n above 2 and (2, n) for n above 2 (redu…

Two piles, take from one or equally from both

Your answer

Discussion

Learn the concepts

Related questions