Maths Olympiad Prep

Library / /57 of 63

Combinatorics Difficulty 7.6 National olympiad, round 2 Prove it Japan

Let kk be a positive integer. Players AA and BB play a game according to the following rule: Initially, a chess piece is placed at the origin (0,0)(0, 0) of the xyxy-plane. The player AA will start the game followed by BB and repeat, each choosing a strategy among those specified by the following rules:
* Possible strategies for AA: Choose a lattice point, which is not occupied by the chess piece and mark the point by a ✓.
(Here, by a lattice point we mean a point in the xyxy-plane whose xx-coordinate and yy-coordinate are both integers).
* Possible strategies for BB: Repeat the process of moving the chess piece located at (x,y)(x, y) to either (x+1,y)(x+1, y) or (x,y+1)(x, y+1) jj times where 1jk1 \le j \le k. However, in each move of the process he is not allowed to move the chess piece into a lattice point marked by a ✓.
AA wins the game if BB gets into the situation where he cannot move the chess piece. Determine all possible values for kk for which AA can win the game after a finite number of steps no matter how BB chooses his strategies.

Solution

We will show that for any positive integer kk AA has strategies to win the game no matter how BB chooses his strategies.
In the sequel, we restrict the possibilities for AA to mark only those lattice points in the set J={(x,y):x+y=2k+1k}J = \{(x, y) : x + y = 2^{k+1}k\}. Also, we allow AA not to choose any lattice point to mark in his action. We will show that it is possible for AA to choose a correct strategy at each stage in such a way to prevent for BB to move the chess piece into the set JJ no matter how BB chooses his strategies.
Let us set Ii={(x,y):ikx+y<(i+1)k}I_i = \{(x, y) : ik \le x + y < (i+1)k\}. If the chess piece lies in the region IiI_i, it stays in IiI_i or moves into Ii+1I_{i+1} after the next action by BB. This implies

that in order for the chess piece to reach the set JJ, it is necessary that for each ii (i=1,2,,2k+1i = 1, 2, \dots, 2^{k+1}) BB must end his action at least once in the set IiI_i. Now, for each ss (s=k+1,k,k1,,2s = k+1, k, k-1, \dots, 2) take note of the consecutive actions starting with the time of the first action by BB after the chess piece reached the set I2k+12sI_{2^{k+1}-2^s} for the first time and ending with the action by AA taken immediately after the chess piece reached the set I2k+12s1I_{2^{k+1}-2^{s-1}}, and call its listing the ss-phase of the listing of consecutive actions taken during a game played.
Let us investigate the situation in an ss-phase more in detail. For tt (t=1,2,,2s1t = 1, 2, \dots, 2^{s-1}), suppose that the chess piece was moved to a point (x,y)(x', y') of the set {(x,y):x+y=(2k+12s+t)k}\{(x, y) : x+y = (2^{k+1}-2^s+t)k\} during or at the end of an action by BB, then define the set Xs,tX_{s,t} by
Xs,t={(x,y):x+y=2k+1k,(2s1t)k+xx2s1k+x}, X_{s,t} = \{(x,y) : x+y = 2^{k+1}k, (2^{s-1}-t)k+x' \le x \le 2^{s-1}k+x'\},
It is easy to check that the inclusion relations Xs,1Xs,2Xs,2s1X_{s,1} \subset X_{s,2} \subset \dots \subset X_{s,2^{s-1}} hold.
Let hsh_s be an integer satisfying 0hs<k0 \le h_s < k. Then there are exactly tt or t+1t+1 elements (x,y)(x, y) of the set Xs,tX_{s,t} for which xhs(modk)x \equiv h_s \pmod k holds. (t+1t+1 such elements exist only when 2s1k+xhs(modk)2^{s-1}k+x' \equiv h_s \pmod k). Now, consider the following strategy for the player AA:
If at the first time of the arrival of the chess piece in the set I2k+12s+tI_{2^{k+1}-2^{s+t}} there is an element in Xs,tX_{s,t} which is unmarked and for which xhs(modk)x \equiv h_s \pmod k is satisfied, then mark this element. If there are 2 or more such elements, then choose an element to be marked in such a way that one of the elements of the form ((2s1t)k+x,(2k+12s1)k+x)((2^{s-1}-t)k+x', (2^{k+1}-2^{s-1})k+x') or (2s1k+x,(2k+12s1)k+x)(2^{s-1}k+x', (2^{k+1}-2^{s-1})k+x') remains unmarked.
Do not mark any point if there are no such elements.
By using the induction on tt, the following facts can be established:
* Immediately after the action by AA using the strategy stated above, there are tt or more elements (x,y)(x, y) in the set Xs,tX_{s,t} which are marked and for which xhs(modk)x \equiv h_s \pmod k hold.
* If there is an unmarked element of the set Xs,tX_{s,t} satisfying xhs(modk)x \equiv h_s \pmod k, then this element must be either ((2s1t)k+x,(2k+12s1)kx)((2^{s-1}-t)k+x', (2^{k+1}-2^{s-1})k-x') or (2s1k+x,(2k+12s1)kx)(2^{s-1}k+x', (2^{k+1}-2^{s-1})k-x').
By definition the set Xs,2s1X_{s,2^s-1} is precisely the set of points lying in the set JJ that can be reached by the chess piece if BB can make moves ignoring \checkmark's after the time it reaches the set {(x,y):x+y=(2k+12s)k}\{(x, y) : x+y = (2^{k+1}-2^s)k\} for the first time. Hence, we have the inclusion relations Xk+1,2kXk,2k1X2,2X_{k+1,2^k} \supset X_{k,2^{k-1}} \supset \dots \supset X_{2,2}. Therefore, if AA chooses strategies in such a way that for each ss (s=k+1,k,,2s = k+1, k, \dots, 2) he picks distinct hsh_s and performs the action for the ss-phase using the strategy with the picked hsh_s specified above, then AA can end up with the situation where X2,2X_{2,2} has at most one element unmarked. At this stage the only points on the set JJ that the chess piece can move into must belong to the set X2,2X_{2,2}. But since the chess piece at this stage lies in the set I2k+12I_{2^{k+1}-2}, BB has to take at least 2 more actions in order to move the chess piece into the set JJ, which means that AA can take an action at least once before the chess piece can reach the set JJ, and therefore, AA can mark the unmarked point in X2,2X_{2,2}.

(if there is an unmarked point) to prevent BB to move the chess piece into the set JJ.
Thus we have established the assertion that for any positive integer kk there are strategies that AA can follow to win the game regardless of how BB chooses his strategies.

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 and solution reproduced as published; topic and difficulty added by this site.