Take one, two or four stones
Two players face a pile of 20 stones. On each turn a player removes 1, 2 or 4 stones (never 3). The player who takes the last stone wins.
Who wins with best play, the first or the second player? What is the winning first move, and what is the rule for every move after that?
Notice that the allowed moves skip the number 3, so the usual "leave a multiple of 5" pattern from the take-1-to-4 game will not be right.
Show a hint
Work backwards from small piles. A pile of 0 is a loss for the player to move. Mark each pile size as a win or a loss and look for the pattern.
Your answer
Solving needs a free account
Answers, streaks and solutions unlock when you are signed in. Reading the question and the hint stays free.
Discussion
💡 Discussion rules
- No full solutions here. Hints and approaches only.
- Complexity, edge cases and intuition are the point.
- Interview experiences are welcome. Respect your NDAs.
Loading discussion…
Learn the concepts
The theory behind this question.