A pile has 100 stones. Players alternately remove 1, 2 or 4 stones, and whoever takes the last stone wins. Who wins with correct play and what is the first move?

A pile has 100 stones. Players alternately remove 1, 2 or 4 stones, and whoever takes the last stone wins. Who wins with correct play and what is the first move?

Approach: Work upward from zero, marking each count as winning or losing for the player to move, and look for the residue class that repeats.

The first player wins by taking 1 stone. Zero is losing for the player to move. Counts 1, 2 and 4 are winning because they reach 0 in one move, and 3 is losing because 1 and 2 are the only reachable counts and both are winning. Continuing upward, 6 is losing as well, and the pattern is that a count is losing exactly when it is a multiple of 3, since every legal take of 1, 2 or 4 moves the residue away from 0 and the opponent can always restore it. Because 100 leaves a remainder of 1 on division by 3, removing 1 leaves 99. After that use a mirroring strategy: answer a take of 1 with 2, a take of 2 with 1, and a take of 4 with 2, so each round removes 3 or 6 and 99 stays a multiple of 3.

Follow-up: With the allowed takes changed to 1, 3 and 4, which counts are losing for the player to move?

Key concepts: losing position, residue mod 3, mirroring strategy.