Olympiad Maths Prep

Library / /3 of 3

Combinatorics Difficulty 7.9 National olympiad, round 2 Prove it Balkan Mathematical Olympiad

Let n3n \ge 3 be a natural number. Anna and Bob play the following game on the vertices of a regular nn-gon: Anna places her token on a vertex of the nn-gon. Afterwards Bob places his token on another vertex of the nn-gon. Then, with Anna playing first, they move their tokens alternately as follows for 2n2n rounds: In Anna's turn on the kk-th round, she moves her token kk positions clockwise or anticlockwise. In Bob's turn on the kk-th round, he moves his token 1 position clockwise or anticlockwise.
If at the end of any person's turn the two tokens are on the same vertex, then Anna wins the game. Otherwise Bob wins. Decide for each value of nn which player has a winning strategy.

Solution

Solution. We will show that Bob wins if and only if 4n4|n and n4n \ne 4. We will often say that Anna and Bob are at a distance dd if we can move one token dd positions clockwise or anticlockwise to reach the other token. Note that the value of this distance is not unique.
We first treat the case 4n4 \nmid n. Given a positive integer rr, we define
mr=r2+r+22andDr={d{1,2,,mr}:dmrmod2} m_r = \frac{r^2 + r + 2}{2} \quad \text{and} \quad D_r = \{d \in \{1, 2, \dots, m_r\} : d \equiv m_r \bmod 2\}
Lemma 1. If it is Anna's turn on round n1r1n - 1 - r \ge 1 or round 2n1r12n - 1 - r \ge 1, and she is at a distance dd from Bob, for some dDrd \in D_r, then she has a winning strategy.
Before proving the Lemma, we show why this implies that Anna has a winning strategy in the case 4n4 \nmid n.
Note that
mn2=n23n+42n m_{n-2} = \frac{n^2 - 3n + 4}{2} \ge n
In particular, Dn2D_{n-2} consists of all odd or of all even numbers in {1,2,,n1}\{1, 2, \dots, n-1\}. If nn is odd, the clockwise and the anti-clockwise distance of Anna from Bob have opposite parities so Anna is at a distance dd from Bob for some dDn2d \in D_{n-2}. Applying the Lemma for r=1r=1 we see that Anna has a winning strategy.
If n2(mod4)n \equiv 2 \pmod 4, then n23n+42(mod4)n^2 - 3n + 4 \equiv 2 \pmod 4, so mn2m_{n-2} is odd. A same argument as above shows that Anna has a winning strategy if dd is also odd. If dd is even then we apply the Lemma in the same way with r=2n2r = 2n - 2 and Anna has a winning strategy since m2n2=2n23n+2m_{2n-2} = 2n^2 - 3n + 2 is even (and m2n2nm_{2n-2} \ge n).
*Proof.* (of Lemma 1) We proceed by induction on rr. For r=1r=1 we have m1=2m_1 = 2 and D1={2}D_1 = \{2\} and since we are in round n2n-2 or 2n22n-2 she has a winning strategy.

---

Assume the result is true for r=kr = k. For the inductive step suppose it is now Anna's turn on round n1(k+1)=n(k+2)n - 1 - (k+1) = n - (k+2) or round 2n1(k+1)=2n(k+2)2n - 1 - (k+1) = 2n - (k+2) and she is at a distance dd from Bob, for some dDk+1d \in D_{k+1}. By moving her token n(k+2)n - (k+2), or 2n(k+2)2n - (k+2) positions in the opposite direction, she is now at a distance of d(k+2)|d - (k+2)| positions from Bob. After Bob's move they will have a distance of dd' for some d{dk3,dk1,k+3d,k+1d}d' \in \{d-k-3, d-k-1, k+3-d, k+1-d\}. Note that all of these numbers have the same parity as d(k+1)mk+1(k+1)mk(mod2)d - (k+1) \equiv m_{k+1} - (k+1) \equiv m_k \pmod 2. Furthermore,
dk3dk1mk+1(k+1)=mk d - k - 3 \le d - k - 1 \le m_{k+1} - (k + 1) = m_k
and
k+1dk+3dk+2mk+1. k + 1 - d \le k + 3 - d \le k + 2 \le m_k + 1.
(Here we assumed that d1d \ge 1 as otherwise Anna already won.) Since in all cases dmk+1d' \le m_k + 1 and dmk(mod2)d' \equiv m_k \pmod 2, then dmkd' \le m_k. Therefore Anna wins by the induction hypothesis. \Box
We now treat the case 4n4|n, say n=4rn = 4r. If r=1r = 1 it is easy to see that Anna wins in at most two rounds so assume r>1r > 1.
Bob places his token so that d=3d = 3. Note that Anna cannot win on her first move. Let d2k1d_{2k-1} denote the distance after Anna's move on the kk-th round and d2kd_{2k} the distance after Bob's move on the kk-th round. Then modulo 2 the sequence is 0,1,1,0,1,0,0,1,0, 1, 1, 0, 1, 0, 0, 1, \dots which then repeats periodically with period 8.
Bob's strategy consists of two parts. The first part is that he never places his token on Anna's token and also he never moves his token on a position where he will immediately lose on Anna's next step unless he is really forced to do this.
Before explaining the second part of Bob's strategy let us assume for contradiction that Anna has a winning strategy and look at Bob's last move. Due to the first part of his strategy he could perhaps lose only in the following two cases:
(a) Before his last move d=1d = 1 so he is forced to make it d=2d = 2 and then Anna wins.
(b) Before his last move d=2rd = 2r so he is forced to make it d=2r1d = 2r - 1 (d=2r+1d = 2r + 1 is the same) and then Anna wins.
In case (a) Anna wins on a round of the form 2(mod4)2 \pmod 4 which is impossible as on those rounds dd is odd after Anna's move
In case (b) Anna wins on rounds of the form (2r1)(mod4r)(2r-1) \pmod{4r} or (2r+1)(mod4r)(2r+1) \pmod{4r}. Actually rounds of the form (2r+1)(mod4r)(2r+1) \pmod{4r} are rejected since in that case we would have d=2rd = 2r when Bob was playing on round 2r(mod4k)2r \pmod{4k} but that could only be possible if d=0d = 0 when Anna was playing on round 2r(mod4r)2r \pmod{4r}. This is rejected as it means that Anna won on an earlier round.

So in case (b) Anna wins on rounds of the form (2r1)mod4r(2r-1) \bmod 4r. If rr is even, say r=2sr = 2s, this is impossible as on round (2r1)3mod4(2r-1) \equiv 3 \bmod 4 we have that dd is odd after Anna's move.
So we need to show how Bob can avoid case (b) if rr is odd, say r=2s+1r = 2s+1. He needs to avoid d=2rd = 2r when it's his turn to play on rounds of the form (2r2)mod4r(2r-2) \bmod 4r. This can only occur if d=2d=2 when it's Anna's turn to play on rounds of the form (2r2)mod4r(2r-2) \bmod 4r. Bob can avoid this unless d=1d=1 when it's his turn to play on rounds of the form (2r3)mod4r(2r-3) \bmod 4r. This can only occur if d=2r2d=2r-2 or d=2r4d=2r-4 when it's Anna's turn to play on rounds of the form (2r3)mod4r(2r-3) \bmod 4r. Bob can avoid both of these cases unless d=(2r3)d=(2r-3) when it's his turn to play on rounds of the form (2r4)mod4r(2r-4) \bmod 4r. This can only occur if d=1d=1 or d=7d=7 when it's Anna's turn to play on rounds of the form (2r4)mod4r(2r-4) \bmod 4r. But Bob can avoid both of these on his move (on rounds of the form (2r5)mod4r(2r-5) \bmod 4r). The only potential issue would be if n=10n=10 which is not the case here. \square

Looking for a route rather than 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.