Strike a number and all its divisors
The numbers 1 to N are written on a board. Two players alternate. On your turn you choose a number still on the board and strike it out together with every divisor of it that is still on the board (a number's divisors include 1 and itself). The player who strikes out the last remaining number wins.
For which N does the first player have a winning strategy? You are not asked to describe the strategy, only to prove who wins.
Show a hint
Consider the modest first move "strike out 1". It removes only the number 1. Ask what the second player's best reply to that would be, and whether the first player could have made that reply as an opening move.
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.