Subtract a square
A pile holds 20 stones. On each turn a player removes a number of stones that is a perfect square: 1, 4, 9 or 16 (or 25 and beyond, if the pile is big enough). The player who takes the last stone wins.
Who wins from a pile of 20 with best play? Work out the losing positions from 0 upwards and describe the pattern you find, or the lack of one.
Show a hint
Call a pile size "losing" if the player about to move from it loses with best play. Zero is losing. A size is losing exactly when every square you could remove leads to a winning size.
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
Sign in to join the discussion · reading is open to everyone
💡 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.
Related questions
Twenty coins in a circleGuess each other's coinPlacing knights so that none attackNim where the last stone losesRacing a rook to the corner
All questions →