Question

Rachel and Regina are playing a variation of the game Nim, in which they take turns removing 1, 2, 4, or 5 matches from the pile of n matches in the center. The person who takes the last match wins. Given that Rachel starts, and both players play optimally, what is the 6th smallest value of n that guarantees Regina the win?

Answer 1

18

Answer 2

We analyze game positions (n matches) as winning (W) if the current player can force a win and losing (L) if any move leaves a winning position for the opponent.

1. Base: n = 0 is losing.

2. For n = 1 and n = 2, the current player can remove 1 or 2 matches respectively to leave 0 (L) so these are winning.

3. For n = 3, the possible moves are:

   • Remove 1 → n = 2 (W)
   • Remove 2 → n = 1 (W)
   • Removing 4 or 5 is not possible.

   Thus, n = 3 is losing.

4. Continuing this process shows that every move from n = 3k (where k is an integer) leaves a position with n not divisible by 3 which is winning. Hence, the losing positions are n = 3, 6, 9, 12, 15, 18, …

Since Rachel starts, if the total number of matches is a losing position (i.e. a multiple of 3), Regina can force a win by playing optimally. The 6th smallest such n (excluding 0) is:

n = 3, 6, 9, 12, 15, 18 → 18