Maths Olympiad Prep

Library / /16 of 18

Combinatorics Difficulty 7.7 National olympiad, round 2 Prove it Argentina

Players AA and BB play a game as follows. Initially AA arranges the numbers 1,2,,n1, 2, \dots, n in a row as he wishes; nn is a given positive integer. Next, BB chooses one number and puts a stone on it. Then AA moves the stone to an adjacent number, BB does the same and so on. The stone can be placed on number kk at most kk times, k=1,,nk = 1, \dots, n; the initial move of BB is counted. The one who cannot move loses. For each nn determine who has a winning strategy.

Solution

Player AA has a winning strategy if nn is 00 or 1-1 modulo 44, otherwise BB has one.

Putting the stone on a number can be viewed as subtracting 11 from it. We may assume that BB chooses a number in AA's arrangement and subtracts 11 from it; then AA must subtract 11 from an adjacent number etc. Operating on a number (subtracting 11) is allowed only if the number is positive. Note that each player always moves at positions with the same parity.

Let a1,,ana_1, \dots, a_n be an arrangement of nn nonnegative integers, not necessarily distinct. We call it balanced if there exist nonnegative integers x0,x1,,xnx_0, x_1, \dots, x_n such that
()x0=xn=0andak=xk1+xkfor k=1,,n. (*) \quad x_0 = x_n = 0 \quad \text{and} \quad a_k = x_{k-1} + x_k \quad \text{for } k = 1, \dots, n.

We show that AA can win if and only if his initial arrangement is balanced. This applies not only to 1,,n1, \dots, n but to any given collection of nonnegative integers (zeros and repetitions are allowed).

Suppose that BB has a move in a balanced arrangement a1,,ana_1, \dots, a_n, subtracting 11 from ak=xk1+xka_k = x_{k-1} + x_k. Then xk1>0x_{k-1} > 0 or xk>0x_k > 0 as the move is possible, say xk>0x_k > 0. So AA is able to respond: he can subtract 11 from ak+1a_{k+1} since ak+1=xk+xk+1xk>0a_{k+1} = x_k + x_{k+1} \ge x_k > 0. Moreover the resulting arrangement is balanced. Only aka_k and ak+1a_{k+1} have changed, replaced by ak=xk1+xka'_k = x_{k-1} + x'_k and ak+1=xk+xk+1a'_{k+1} = x'_k + x_{k+1} with xk=xk1x'_k = x_k - 1, and xk0x'_k \ge 0 due to xk>0x_k > 0. Hence if BB has a move in a balanced arrangement then AA has an answering move leading to a balanced arrangement again. Since the game always terminates, it will be therefore BB to end up without a legal move.

Suppose next that AA's initial arrangement a1,,ana_1, \dots, a_n is not balanced. Then BB can win by reducing the game to a balanced case like above where he plays the winning rôle. Define
x0=0andxk=akxk1for k=1,,n. x_0 = 0 \quad \text{and} \quad x_k = a_k - x_{k-1} \quad \text{for } k = 1, \dots, n.
Set an+1=0a_{n+1} = 0 and observe that xk>ak+1x_k > a_{k+1} for some k=1,,nk = 1, \dots, n. Indeed let xjaj+1x_j \le a_{j+1} for all 1jn11 \le j \le n-1. Then x1,x2,,xn0x_1, x_2, \dots, x_n \ge 0 by the definition of the xjx_j. Now notice that xn0x_n \ne 0. Otherwise the equalities ()(*) would hold with nonnegative xjx_j's and the arrangement would be balanced. In conclusion xn>0=an+1x_n > 0 = a_{n+1}.

Let BB start at the first position kk such that xk>ak+1x_k > a_{k+1}, that is, ak>xk1+ak+1a_k > x_{k-1} + a_{k+1}. Note that xj0x_j \ge 0 for j<kj < k by the minimum choice of kk. Since akxk1+ak+1a_k \ge x_{k-1} + a_{k+1} holds after the opening move, BB can play at position kk at least xk1+ak+1x_{k-1} + a_{k+1} more times, regardless of AA's moves on ak1=xk2+xk1a_{k-1} = x_{k-2} + x_{k-1} or ak+1a_{k+1}. (For k=1k=1 assume ak1=xk1=xk2=0a_{k-1} = x_{k-1} = x_{k-2} = 0.) So let BB keep moving at kk until AA has to move at k1k-1 for the (xk1+1)(x_{k-1} + 1)st time. Call such a move of AA move M. It is forced since AA has at most ak+1a_{k+1} moves at k+1k+1.

Right before move M the first k1k-1 positions are occupied by a1,,ak2,xk2a_1, \dots, a_{k-2}, x_{k-2} as ak1=xk2+xk1a_{k-1} = x_{k-2} + x_{k-1} was decreased xk1x_{k-1} times and no moves at previous positions were made. Observe now that a1,,ak2,xk2a_1, \dots, a_{k-2}, x_{k-2} is a balanced arrangement. Indeed it was noted that xj0x_j \ge 0 for all j=0,,k2j = 0, \dots, k-2. So we see that conditions ()(*) hold for the numbers at the first k1k-1 positions: it is enough to redefine ak1a_{k-1} and xk1x_{k-1} as ak1=xk2a_{k-1} = x_{k-2} and xk1=0x_{k-1} = 0.

Consequently AA's move M, if possible, can be regarded as the opening move in a balanced arrangement. So BB can apply the winning strategy of the first player for the balanced case. The only further remark needed is that AA has no escape from positions 1,,k11, \dots, k-1. Wherever BB plays at these positions (following the strategy mentioned), it will be at a position jj with the parity of kk, hence jk2j \le k-2. Thus the game is confined to the first k1k-1 positions and the strategy does apply; so BB wins.

A collection of integers has a balanced arrangement a1,,ana_1, \dots, a_n only if its total sum is even. Indeed j=1naj=2j=0n+1xj\sum_{j=1}^{n} a_j = 2 \sum_{j=0}^{n+1} x_j by the definition. Therefore there is no balanced arrangement of 1,,n1, \dots, n for n1,2(mod4)n \equiv 1, 2 \pmod 4 where 1+2++n1+2+\dots+n is odd. So BB has a winning strategy if nn is 11 or 22 modulo 44. On the other hand a balanced arrangement of 1,,n1, \dots, n exists if n=4kn = 4k or n=4k1n = 4k-1, k1k \ge 1. Write the odd numbers in [1,n][1, n] in ascending order, then the even numbers in descending order. For n=4kn = 4k the arrangement is
1=0+1,3=1+2,5=2+3,,4k1=(2k1)+2k,1 = 0+1, \quad 3 = 1+2, \quad 5 = 2+3, \quad \dots, \quad 4k-1 = (2k-1)+2k,
4k=2k+2k,4k2=2k+(2k2),,4=2+2,2=2+0.4k = 2k+2k, \quad 4k-2 = 2k+(2k-2), \quad \dots, \quad 4 = 2+2, \quad 2 = 2+0.

For n=4k1n = 4k - 1 just ignore 4k4k. Thus AA has a winning strategy if nn is 00 or 1-1 modulo 44.

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.