For which values of $~n~$can we end this process?

Question

A circle is divided into $~n~$ sectors$~(n \ge 3)$. Each sector can be filled in with either $~1~$ or $~0~$. Choose any sector $C$ occupied by $~0~$, change it into a $~1~$ and simultaneously change the symbols $~x,~ y~$ in the two sectors adjacent to $~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?

I noticed that every move adds $~1~$ to the total sum of $~1$s $~\mod 2~$ and every move is reversible therefore the question is the same as asking for which values of $~n~$ can we start with only $~1$s in every sector and end with a single $~0~$.

I'm not sure if this is even helpful but I don't have any idea how to solve this, hints suggestions and solutions would be appreciated.

Taken from the 2018 Pan-African Maths Olympiad

Answer 1

If $n$ is a multiple of $3$, you cannot always succeed. Color the sectors red, green and blue in so that every three adjacent sectors have all three colors. Let $r,g,b$ be the total number of zeroes in each corresponding color. Each move changes the parity of $r$ by $1$, and the same goes for $g$ and $b$. Therefore, if $r$ and $b$ have different parities initially, then they will continue to do so. Since the parities of $r$ and $b$ will both be zero when the process is over, the process cannot end in this case.

If $n$ is a not a multiple of $3$, you can always succeed. This solution is more complicated, but here is the general idea.

• As long as there are two adjacent zeroes, toggle one of them. This decreases the number of zeroes by at least one, so eventually, all zeroes will be isolated.

• Pick two zeroes, and "move" one of them towards the other until there are at most two ones between them, using this pattern:

10111
01011
00101
11001
11110

• There are now three cases:

  • If the two zeroes are now adjacent, then a single move turns them into a single 0.
  • If the two zeroes have a single 1 between them, then there is a sequence of moves which turns them into a single 0 (how?).
  • If there are two ones between them, then there is a sequence of moves which eliminate both zeroes (how?).

• Either way, we can reduce the number of zeroes. Continue this process until there is exactly one zero, and then toggle it so there are now two zeroes separated by a $1$. There are again two cases.

  • If $n$ is two more than a multiple of $3$, then move one of the zeroes around the circle the long way until it is two spaces away from the other zero. Then, eliminate both zeroes.

  • If $n$ is one more than a multiple of $3$, then you can still succeed, but I leave finding this to the reader.

Answer 2

Partial answer: Every $n$ that is not a multiple of $3$ works.

Let's start with the vector $[\underbrace{1,...,1}_{n-1\text{ times}},0]$.
Our strategy is simple: We push the zero to the front. For $n=4$ it'd look like this:

$[1,1,1,\color{red}{0}] \rightarrow [0,1,\color{red}0,1] \rightarrow [0,0,1,0]$

For our general vector, it works the same way, only describing it is a little more difficult:

• Each move we push the $0$ one index to the left.
• Therefore, in the $i$-th move, we invert the cells $i-1,i,i+1$

We'll have to handle the first move exclusively, as it skips around the bounds. If we let $c(\cdot)$ be the invertion-operation, then in the $i$-the move the vector looks like this: $$ [c(1),1,1...,1,c(1),c^2(1),c^3(1),c^3(1),...,c^3(1),c^2(0)] = [0,1,1,...,1,0,1,0,0,...,0,0] $$ Right before we flip the second element it looks like this $$ [0,0,1,0,0,...,0,0] $$ , and flipping the second element gives us $$ [1,1,0,0,0,...,0,0] $$ . So we have either a contiguous array of $n-1$ or $n-2$ zeros, and as we flip 3 zeros per turn, as long $n-1$ or $n-2$ are divisible by $3$, this approach lets us reach the final state.