Maths Olympiad Prep

Library / /35 of 36

Combinatorics Difficulty 7.7 National Olympiad, round 2 Prove it Saudi Arabia

Let NN be a positive integer. Ali and Hadi play a game in which they start by writing the numbers 1,2,,N1, 2, \dots, N on a board. They then take turns to make a move, starting with Ali. Each move consists of choosing a pair of integers (k,n)(k, n), where k0k \ge 0 and nn is one of the integers on the board, and then erasing every integer ss on the board such that 2kns2^k|n - s. The game continues until the board is empty. The player who erases the last integer on the board loses.
Determine all values of NN for which Ali can ensure that he wins, no matter how Hadi plays.

Solution

The answer is that Geoff wins when NN is of the form 2n2^n for nn odd or of the form t2nt2^n for nn even and t>1t > 1 odd.

Common remarks. We will say that a set SS wins if the current player wins given SS as the current set of integers on the board. Otherwise, we will say that SS loses. We will let J(S,T)=(2S1)(2T)J(S, \mathcal{T}) = (2S - 1) \cup (2\mathcal{T}). Note that every subset of Z\mathbb{Z} can be written as J(S,T)J(S, \mathcal{T}) for some unique pair (S,T)(S, \mathcal{T}) of subsets of Z\mathbb{Z}. We will let [n][n] denote the set {1,2,,n}\{1, 2, \dots, n\}.

Lemma 1. For any set S,TS, \mathcal{T} wins if and only if J(S,)J(S, \emptyset) wins. Similarly, SS wins if and only if J(,S)J(\emptyset, S) wins.
Proof. Let (k,m)(k, m) be a move on SS, and let T\mathcal{T} be the result of applying the move. Then we can reduce J(S,)J(S, \emptyset) to J(T,)J(\mathcal{T}, \emptyset) by applying the move (k+1,2m1)(k + 1, 2m - 1).
Conversely, let (k,m)(k, m) be a move on J(S,)J(S, \emptyset). We can express the result of this move as J(T,)J(\mathcal{T}, \emptyset) for some T\mathcal{T}. Then we can reduce SS to T\mathcal{T} by applying the move (max(k1,0),(k+1)/2)(\max(k - 1, 0), (k + 1)/2).
This gives us a natural bijection between games starting with SS and games starting with J(S,)J(S, \emptyset) and thus proves the first part of the lemma. The second part follows by a similar argument.

Lemma 2. If S,TS, \mathcal{T} are nonempty and at least one of them loses, then J(S,T)J(S, \mathcal{T}) wins.
Proof. If SS is losing, then we can delete J(,T)J(\emptyset, \mathcal{T}) using the move (1,t)(1, t) for some tJ(,T)t \in J(\emptyset, \mathcal{T}), which leaves the losing set J(S,)J(S, \emptyset). Similarly, if T\mathcal{T} is losing, then we can delete J(S,)J(S, \emptyset) using the move (1,s)(1, s) for some sJ(S,)s \in J(S, \emptyset), leaving the losing set J(,T)J(\emptyset, \mathcal{T}).

Lemma 3. If SS is nonempty and wins, then J(S,S)J(S, S) loses.
Proof. From this position, we can convert any sequence of moves into another valid sequence of moves by replacing (k,2n1)(k, 2n - 1) with (k,2n)(k, 2n), and vice versa. Thus we may assume that the initial move (k,m)(k, m) has mm odd. We want to show that any such move results in a winning position for the other player.
The move (0,m)(0, m) loses immediately. Otherwise, the move results in the set J(T,S)J(\mathcal{T}, S) for some set T\mathcal{T}. There are three cases. If T\mathcal{T} is empty then the other player gets the winning set J(,S)J(\emptyset, S). If T\mathcal{T} is losing then the other player can choose the move (1,s)(1, s) for some sJ(,S)s \in J(\emptyset, S), which leaves the losing set J(T,)J(\mathcal{T}, \emptyset). If T\mathcal{T} is nonempty winning then the other player can choose the move (k,m+1)(k, m + 1), which results in the position J(T,T)J(\mathcal{T}, \mathcal{T}). We can do induction on S|S| to show that this is a losing set.

Lemma 4. [2n][2n] wins if and only if [n][n] loses.
Proof. Note that [2n]=J([n],[n])[2n] = J([n], [n]), the result follows directly from Lemma 2, 3.

Lemma 5. For any integer n1n \ge 1, [2n+1][2n + 1] wins.
Proof. By Lemma 4, either [n][n] or [2n][2n] loses. If [n][n] loses, then by Lemma 2 we have that [2n+1]=J([n+1],[n])[2n+1] = J([n+1], [n]) wins. Otherwise, [2n][2n] loses, and therefore [2n+1][2n+1] wins by choosing the move (k,2n+1)(k, 2n+1) for kk big enough so only 2n+12n+1 is eliminated.

It remains to verify the original answer. We have two cases to consider:
* Suppose N=2nN = 2^n for some nn. For N=1N = 1, every move is an instant loss for Geoff. Then by Lemma 4, Geoff wins for N=2nN = 2^n if and only if Geoff loses for N=2n1N = 2^{n-1}, and thus by induction we have that Geoff wins for N=2nN = 2^n if and only if nn is odd.
* Otherwise, N=t2nN = t2^n, for some nn and some t>1t > 1 with tt odd. By Lemma 5, Geoff wins when n=0n = 0. Then by Lemma 4, Geoff wins for N=t2nN = t2^n if and only if Geoff loses for N=t2n1N = t2^{n-1}, and thus by induction on nn we have that Geoff wins for N=t2nN = t2^n if and only if nn is even.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.