A circle is divided into $n$ sectors ($n \geq 3$). Each sector can be filled in with either $1$ or $0$. Choose any sector $\mathcal{C}$ occupied by $0$, change it into a $1$ and simultaneously change the symbols $x, y$ in the two sectors adjacent to $\mathcal{C}$ to their complements $1-x$, $1-y$. We repeat this process as long as there exists a zero in some sector. In the initial configuration there is a $0$ in one sector and $1$s elsewhere. For which values of $n$ can we end this process?
Problem
Source: 2018 Pan-African Mathematics Olympiad
Tags: combinatorics
03.07.2018 23:26
Let the numbers in the sectors be $x_1, x_2, \dots, x_n$, and suppose that initially $x_1 = 0$, while $x_i = 1$ for $i > 0$. After choosing the only zero available, we have that $x_n = x_2 = 0$, and $x_i = 1$ otherwise. Suppose that we are in the position where $x_n = 0$, $x_1 = x_2 = \dots = x_k = 0$, $x_{k+1} = 1$, and $x_{k+2} = 0$. By choosing the $0$ in position $k+2$, we then obtain the configuration where $x_n = 0$, $x_1 = x_2 = \dots = x_{k + 1} = 0$, $x_{k+2} = 1$ and $x_{k + 3} = 0$. Thus continuing in this way, we obtain the configuration where $x_{n-2} = 1$, and $x_i = 0$ otherwise. If $n \equiv 1 \pmod 3$, then at this point we can divide the $0$ into groups of $3$ and apply the procedure to the $0$ in the middle of each group to contain a configuration where each sector contains a $1$. If $n \equiv 2 \pmod 3$, then we apply the procedure to the $0$ in sector $n-1$ to obtain the configuration where $x_{n-1} = x_n = 1$, and $x_i = 0$ otherwise. We can then again divide the remaining $0$s into groups of $3$ and apply the procedure to the $0$ in the middle of each group. Finally, we show that if $n \equiv 0 \pmod 3$, then the procedure never terminates. Let $A = x_1 + x_4 + \dots + x_{n-2}$, $B = x_2 + x_5 + \dots + x_{n-1}$, and $C = x_3 + x_6 + \dots + x_n$. We note that we initially have that $A = \frac{n}{3} - 1$, and $B = C = \frac{n}{3}$, while in the configuration where every sector contains a $1$ we have that $A = B = C = \frac{n}{3}$. We now note that the allowed operation changes the parity of $A$, $B$, and $C$. In particular, we always have that $A$, $B$, and $C$ do not all have the same parity, and so it is not possible to obtain a configuration where $A = B = C$.