Maths Olympiad Prep

Library / /27 of 30

Combinatorics Difficulty 6.9 National olympiad Prove it Ireland

n3n \ge 3 people seated at a round table play a game as follows. Initially each player is dealt a green or orange card. Game play then takes place in a series of rounds. In each round,
(i) Each player notes the colours of the cards held by the two players to his/her immediate right. If these are different, the player raises his/her hand.
(ii) Each player with a raised hand replaces his/her card with one of the opposite colour.
The game ends when each player holds the same colour as he/she did initially. A value of nn is called playable if game play must end after a finite number of rounds, regardless of the initial cards dealt to the players.
(a) Prove that there are infinitely many values of nn which are playable.
(b) Prove that there are infinitely many values of nn which are not playable.

Solution

(a) Denote the configuration of cards after round k0k \ge 0 by a binary sequence a1(k),a2(k),a3(k),,an(k)a_1^{(k)}, a_2^{(k)}, a_3^{(k)}, \dots, a_n^{(k)}, where the subscripts are interpreted modulo nn (here k=0k=0 corresponds to the initial cards dealt to the players). The outcome of each round may then be computed recursively by
ai(k+1)=ai(k)+ai1(k)+ai2(k)i=1,2,,n(1) a_i^{(k+1)} = a_i^{(k)} + a_{i-1}^{(k)} + a_{i-2}^{(k)} \quad \forall i = 1, 2, \dots, n \quad (1)
for k0k \ge 0, where addition is modulo 2. Next, by induction on rr we show that for all r0r \ge 0 and all k0k \ge 0,
ai(k+2r)=ai(k)+ai2r(k)+ai2r+1(k)i=1,2,,n. a_i^{(k+2r)} = a_i^{(k)} + a_{i-2r}^{(k)} + a_{i-2^{r+1}}^{(k)} \quad \forall i = 1, 2, \dots, n.
This is obviously true for r=0r=0, as it matches (1). Assuming this equation holds for a fixed r0r \ge 0, we have, for all i=1,2,,ni=1, 2, \dots, n and all m0m \ge 0,
ai(m+2r)=ai(m)+ai2r(m)+ai2r+1(m). a_i^{(m+2r)} = a_i^{(m)} + a_{i-2r}^{(m)} + a_{i-2^{r+1}}^{(m)}.
With m=k+2rm = k + 2^r it follows that for all i=1,2,,ni = 1, 2, \dots, n and all k0k \ge 0,
ai(k+2r+1)=ai(k+2r+2r)=ai(k+2r)+ai2r(k+2r)+ai2r+1(k+2r)=(ai(k)+ai2r(k)+ai2r+1(k))+(ai2r(k)+ai2r+1(k)+ai2r2r+1(k))+(ai2r+1(k)+ai2r2r+1(k)+ai2r+2(k))=ai(k)+ai2r+1(k)+ai2r+2(k) \begin{align*} a_i^{(k+2^{r+1})} &= a_i^{(k+2^r+2^r)} = a_i^{(k+2^r)} + a_{i-2^r}^{(k+2^r)} + a_{i-2^{r+1}}^{(k+2^r)} \\ &= (a_i^{(k)} + a_{i-2^r}^{(k)} + a_{i-2^{r+1}}^{(k)}) \\ &\quad + (a_{i-2^r}^{(k)} + a_{i-2^{r+1}}^{(k)} + a_{i-2^{r-2^{r+1}}}^{(k)}) \\ &\quad + (a_{i-2^{r+1}}^{(k)} + a_{i-2^{r-2^{r+1}}}^{(k)} + a_{i-2^{r+2}}^{(k)}) \\ &= a_i^{(k)} + a_{i-2^{r+1}}^{(k)} + a_{i-2^{r+2}}^{(k)} \end{align*}
and the results follows by the principle of induction.
Therefore, if n=2rn = 2^r for any r2r \ge 2, after nn rounds we have ai(n)=ai(0)+ain(0)a_i^{(n)} = a_i^{(0)} + a_{i-n}^{(0)} and ai2n(0)=ai(0)a_{i-2n}^{(0)} = a_i^{(0)} for all ii; we conclude that each such nn is playable.

(b) For any nn divisible by 3, we may set the initial configuration of cards to
ai(0)={1if i0(mod3)0otherwise. a_i^{(0)} = \begin{cases} 1 & \text{if } i \equiv 0 \pmod 3 \\ 0 & \text{otherwise.} \end{cases}
Then it is easily shown that the next round yields the all-ones sequence, and this configuration will not change thereafter, i.e. ai(k)=1a_i^{(k)} = 1 for all i=1,2,,ni = 1, 2, \dots, n and for all k1k \ge 1. Therefore every nn divisible by 3 is not playable.

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.