Maths Olympiad Prep

Library / /363 of 397

Combinatorics Difficulty 7.0 National Olympiad, round 2 Prove it Taiwan

Let nn be a positive integer, and write down 1,2,,n1, 2, \dots, n 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 kk, you cannot choose k1k-1 or k+1k+1.
(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 nn such that Lee has a winning strategy.

Solution

Except for n=1,2,4,6n = 1, 2, 4, 6, Lee always has a winning strategy.
For convenience, let [n]={1,2,,n}[n] = \{1, 2, \dots, n\}. We first prove a lemma:
Lemma: If Lee first chooses nn, and Alpha has already chosen his kk-th number (k2k \ge 2), then Lee can always choose his kk-th number.
Proof: Let a1<a2<<aka_1 < a_2 < \dots < a_k be the first kk numbers chosen by Alpha; note that ak<na_k < n. Since ai+1ai>1a_{i+1} - a_i > 1, for every 1ik1 \le i \le k there must exist bib_i such that ai<bi<ai+1a_i < b_i < a_{i+1}, where ak+1:=na_{k+1} := n. Among these kk values bib_i, Lee has chosen at most k1k-1 of them, so he can always choose one of them as his kk-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 n+12\frac{n+1}{2}, so Lee's first move is to choose nn.

- We first prove that for all n1,2,4,6n \ne 1, 2, 4, 6, Lee has a winning strategy. This splits into two cases:

* nn 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 n+12\frac{n+1}{2} pairwise non-consecutive numbers from [n][n], and this is only possible if these are all the odd numbers in [n][n]; but Lee has already taken the odd number nn at the start, so Alpha will eventually run out of numbers to choose first. In other words, Lee wins.

* nn 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 n2\frac{n}{2} pairwise non-consecutive numbers from [n1][n-1], and this is only possible if these are all the odd numbers in [n1][n-1]. Therefore, as long as Lee, on his second move, chooses any number from {1,3,...,n3}\{1,3,...,n-3\} 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 nn, he cannot choose n1n-1.) In summary, Lee wins.

- We next prove that for all n=1,2,4,6n = 1,2,4,6, Lee has no winning strategy. In fact, we will prove that the game must be a draw.

* n=1,2n = 1,2 are obvious.

* When n=4n = 4, it is easy to see that Alpha's first move must be to choose 11, otherwise Lee chooses 44 and wins. Next, Lee's first move must be to choose 44, otherwise Alpha's second move is to choose 44 and wins. Alpha must then choose 33, Lee must choose 22, and it is a draw.

* When n=6n = 6, Alpha's first move is to choose 11. First consider the two sets {3,5}\{3,5\} and {4,6}\{4,6\}: 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 22, 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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.