Maths Olympiad Prep

Library / /14 of 18

Combinatorics Difficulty 7.4 National olympiad, round 2 Prove it Argentina

Let N4N \ge 4 be a fixed integer. Two players AA and BB write down numbers, each number in continuation to the previous expression. First AA writes +1+1 or 1-1, then BB writes +2+2 or 2-2, then AA writes +3+3 or 3-3 etc.; at step kk the player to move must write +k+k or k-k. The objective of each one is that after a move of his several consecutive numbers in the obtained expression, taken with their signs, have sum divisible by NN. For each NN determine which of the players has a winning strategy, if any.

Solution

The first player AA has a winning strategy if NN is congruent to 00 or 11 modulo 44, otherwise the second player BB has one.

Let N=4k+rN = 4k + r where k1k \ge 1 and r{0,1}r \in \{0, 1\}. Then AA starts with +1+1 and in the sequel negates all moves of BB until BB writes ±2k\pm 2k. Here "negates" means that AA writes (2j+1)-(2j+1) or (2j+1)(2j+1) according as BB writes (2j)(2j) or (2j)-(2j). We may assume that the first move of BB is 2-2 or else AA wins by writing 3-3 (1+23=01+2-3=0 is divisible by NN for all NN). Moreover we may assume that BB also negates each move of AA up to step 2k2k. If BB does not do so at step 2j2j then the expression ends (2j2)+(2j1)+(2j)-(2j-2)+(2j-1)+(2j) or +(2j2)(2j1)(2j)+(2j-2)-(2j-1)-(2j) after step 2j2j. So AA wins at step 2j+12j+1 by writing (2j+1)-(2j+1) or (2j+1)(2j+1) respectively, because m(m+1)(m+2)+(m+3)=0m-(m+1)-(m+2)+(m+3)=0 for all mm. Thus the sum 12+3+(2k1)(2k)1-2+3-\cdots+(2k-1)-(2k) is obtained at step 2k2k, after a move of BB.

Neither player has won the game by that moment. Indeed denote Sn=12++(1)n1nS_n = 1 - 2 + \cdots + (-1)^{n-1}n, then Sn=n+12S_n = \frac{n+1}{2} for nn odd and Sn=n2S_n = -\frac{n}{2} for nn even. It follows that if 1i<jn1 \le i < j \le n then SiSj=ji2|S_i - S_j| = \frac{j-i}{2} for i,ji, j of the same parity and SiSj=i+j+12|S_i - S_j| = \frac{i+j+1}{2} for i,ji, j of different parity. In particular 0<SiSjn0 < |S_i - S_j| \le n. So there is no winner yet if N>nN > n. This is the case here, with N=4k+r4kN = 4k + r \ge 4k and n=2kn = 2k. Note that the argument works for k=1k=1 (N=4N=4) where 2k2=02k-2=0 is not present in the sum but can be assumed.

Now AA wins by writing (2k+1)-(2k+1). If N=4k+1N = 4k + 1 then the sum of the last two numbers (2k)(2k+1)=N-(2k) - (2k+1) = -N is divisible by NN; if N=4kN = 4k then so is the sum of the last four numbers (2k2)+(2k1)(2k)(2k+1)=4k=N-(2k-2) + (2k-1) - (2k) - (2k+1) = -4k = -N.

Player BB has an analogous winning strategy for N=4k+rN = 4k + r where k1k \ge 1 and r{2,3}r \in \{2, 3\}. Without loss of generality AA starts the game with +1+1 (if BB has a winning strategy for a game starting +1+1, he can just negate his moves in this strategy if AA's opening move is 1-1). Now BB answers 2-2 and in general negates AA's moves up to step 2k+12k+1. One may suppose again that AA also negates BB's moves, due to the identity m(m+1)(m+2)+(m+3)=0m - (m+1) - (m+2) + (m+3) = 0. Thus the sum 12++(2k1)(2k)+(2k+1)1 - 2 + \cdots + (2k-1) - (2k) + (2k+1) is obtained at step 2k+12k+1, after a move of AA. It was shown above that 0<SiSj2k+1<N0 < |S_i - S_j| \le 2k+1 < N whenever 1i<j2k+11 \le i < j \le 2k+1, so that there is no winner yet by that time. The next move +(2k+2)+(2k + 2) of BB is winning. If N=4k+3N = 4k+3 then +(2k+1)+(2k+2)=N+(2k+1)+(2k+2) = N; if N=4k+2N = 4k+2 then +(2k1)(2k)+(2k+1)+(2k+2)=4k+2=N+(2k-1)-(2k)+(2k+1)+(2k+2) = 4k+2 = N.

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.