Let be a positive integer, and write down on the blackboard. Alpha and Lee take turn choosing a number from the board according to the following rules:
(i) You cannot choose any number that was previous selected by either player.
(ii) If you have chosen , you cannot choose or .
(iii) The game is a draw if all numbers are chosen. Otherwise, the player who cannot choose any number first loses the game.
Suppose Alpha chooses first. Determine all such that Lee has a winning strategy.
Solution
Except for , Lee always has a winning strategy.
For convenience, let . We first prove a lemma:
Lemma: If Lee first chooses , and Alpha has already chosen his -th number (), then Lee can always choose his -th number.
Proof: Let be the first numbers chosen by Alpha; note that . Since , for every there must exist such that , where . Among these values , Lee has chosen at most of them, so he can always choose one of them as his -th number. Q.E.D.
Back to the original problem. Without loss of generality, we assume that Alpha's first move is a number not exceeding , so Lee's first move is to choose .
- We first prove that for all , Lee has a winning strategy. This splits into two cases:
* is an odd number greater than or equal to 3: By the lemma, as long as Alpha can choose, Lee can also choose. Moreover, if the game is a draw, Alpha must choose pairwise non-consecutive numbers from , and this is only possible if these are all the odd numbers in ; but Lee has already taken the odd number at the start, so Alpha will eventually run out of numbers to choose first. In other words, Lee wins.
* is an even number greater than or equal to 8: Similar to the previous case, the lemma tells us that Lee can never lose, and for the game to be a draw, Alpha must choose pairwise non-consecutive numbers from , and this is only possible if these are all the odd numbers in . Therefore, as long as Lee, on his second move, chooses any number from that Alpha has not yet chosen, Alpha must lose (note that at this point Alpha has only chosen two numbers, so Lee must have such a number available to choose. Since Lee's first move was to choose , he cannot choose .) In summary, Lee wins.
- We next prove that for all , Lee has no winning strategy. In fact, we will prove that the game must be a draw.
* are obvious.
* When , it is easy to see that Alpha's first move must be to choose , otherwise Lee chooses and wins. Next, Lee's first move must be to choose , otherwise Alpha's second move is to choose and wins. Alpha must then choose , Lee must choose , and it is a draw.
* When , Alpha's first move is to choose . First consider the two sets and : if Lee chooses the smaller (larger) one from one of these sets, Alpha then chooses the larger (smaller) one from the other set. And if Lee chooses , Alpha chooses the remaining number from the two sets above. From this we see that Alpha can force at least a draw, and by the lemma Lee can also force at least a draw, so the game must be a draw.