, 2025

Reformulate the problem as a $n$-string of numbers in $\{0,1\}$ and a position at which the action described in the problem is performed, and add $1$ or $2$ modulo $n$ to the position according to the action. Say that a lap is complete for each time the position resets to $0$ or $1$. We will prove that the statement claim holds after at most two laps, after which the $n$-tuple cycles every three laps.

Say the rooster stops at a position in a certain lap if it performs an action at that position on that lap; otherwise, the rooster bypasses that position. We start with some immediate claims:

- The rooster has to stop at at least one of each two consecutive positions.
- The rooster stops at every position preceded by a $0$. Indeed, if the numbers preceding that position are $00$ then the rooster will definitely stop at the second zero, and if the numbers preceding that position are $10$ then the rooster will either stop at $1$ and go directly to the position or bypass $1$ and stop at the second zero, and then stop at the position.
- Therefore, if the rooster bypasses a position, then it is preceded by a $1$, and that $1$ must be changed to a $0$. This means that the rooster never bypasses a position in two consecutive laps.
- The rooster bypasses every position preceded by $01$. Indeed, the rooster stops at either $1$ or at $0$, after which it will move to $1$; at any rate, it stops at $1$ and bypasses the position.

Our goal is to prove that, eventually, for every three consecutive laps, each position is bypassed exactly once. Then each position changes states exactly twice, so it gets back to its initial state after three laps. The following two lemmata achieve this goal:

Lemma 1. If the rooster stops at a certain position in two laps in a row, it bypasses it on the next lap, except for the $n$-string $1010\ldots10$, for which the problem statement holds.

Proof. If the rooster stopped at a position in lap $t$, then it is preceded by either (A) a $0$ that was changed to $1$, (B) a $11$ that was changed to $01$, or (C) a $10$ in which the rooster stopped at $1$. In case (A), the position must be preceded by $11$ in the lap $t+1$, which becomes $01$, so the rooster will bypass the position in the lap $t+2$. In case (B), the position will be bypassed in lap $t+1$.

Now we deal with case (C): suppose that the position was preceded by $m$ occurrences of $10$, that is, $(10)^{m}$, on lap $t$ and take $m \leq \frac{n}{2}$ maximal. The rooster stopped at the $1$ from each occurrence of $10$, except possibly the first one.

First, suppose that $n \geq 2m+2$. After lap $t$, $(10)^{m}$ becomes either $(00)^{m}$ or $11(00)^{m-1}$ in lap $t+1$. In the latter case, initially we had $1(10)^{m}$, which became $011(00)^{m-1}$. It will then become $a\ 01(11)^{m-1}$ in lap $t+2$, in which the rooster will bypass the position. In the former case, $(10)^{m}$ becomes $(00)^{m}$, so it was either $00(10)^{m}$ or $11(10)^{m}$ in lap $t$, which becomes respectively $a\ 1(00)^{m}$ and $01(00)^{m}$ in lap $t+1$, respectively. In the second sub-case, it becomes $b\ 001(11)^{m-1}$ in lap $t+2$, and the position will be bypassed. In the first sub-case, it must be $11(00)^{m}$ after which it becomes either $01(11)^{m}$ or $1001(11)^{m-1}$. In any case, the position will be bypassed in lap $t+2$.

If $n=2m+1$, the possible configurations are
$$(10)^{m} 0 \rightarrow (00)^{m} 1 \rightarrow (11)^{m} 0 \rightarrow (10)^{m} 0$$
the rooster stops at the $1$ from the first $10$ because it was preceded by a $0$.
$$(10)^{m} 1 \rightarrow (00)^{m} 0 \rightarrow 0(11)^{m} \rightarrow 1(01)^{m}$$
or
$$(10)^{m} 1 \rightarrow 11(00)^{m-1} 0 \rightarrow 01(11)^{m-1} 1 \rightarrow (10)^{m} 1,$$
In any case, the position is bypassed in lap $t+2$.

If $n=2m$, the entire configuration is $(10)^{m}$, $m \geq 2$. If the rooster did not stop at the first $1$, it becomes $11(00)^{m-1}$ in the lap $t+1$, then $01(11)^{m-1}$ in the lap $t+2$, so the position is bypassed in this last lap. If the rooster stopped at the first $1$, it becomes $(00)^{m}$, then $(11)^{m}$, then $(01)^{m}$, then $10(00)^{m-1}$, then $(11)^{m}$, and then it cycles between $(11)^{m}, (01)^{m}$ and $10(00)^{m-1}$.

So, apart from this specific string, the rooster will stop at most two laps in a row at each position.

Lemma 2. If the rooster bypasses one position on a lap, then it stops at that position on the next two laps, with the same exception as lemma 1.

Proof. The position must be preceded by $1$ in lap $t$. If it is preceded by $11$, it changes to $10$ in lap $t+1$. Then it becomes $00$ because the $1$ was already skipped in the previous lap, and the rooster will stop at the position in the lap $t+2$.

Now suppose that the position was preceded by $(01)^{m}$ on lap $t$ and take $m \leq \frac{n}{2}$ maximal. It becomes $10(00)^{m-1}$ or $(00)^{m}$ in lap $t+1$. In the former case, in lap $t+2$ it becomes either $00(11)^{m-1}$, after which the rooster stops at the position again, or $(11)^{m}$, which we'll study later. In the former case, $(00)^{m}$ becomes $(11)^{m}$ or $01(11)^{m-1}$. In the latter case, the $0$ was bypassed, so it must be stopped in the next lap, becoming $(10)^{m}$. In the $(11)^{m}$ case, in order to bypass the position in lap $t+2$, it must become $(10)^{m}$. All in all, the preceding terms are $(01)^{m}$. Then, either $10(00)^{m-1}$ or $(00)^{m}$, then either $(11)^{m}$ or $01(11)^{m-1}$, then $(10)^{m}$. Then the second term in $(01)^{m}$ is $1$, then $0$, then $1$, and then $0$, that is, it changed three times. So we fall under the exception to lemma 1.

The result then immediately follows from lemmata 1 and 2.

Define positions, laps, stoppings, and bypassing as in Solution 1. This other pair of lemmata also solves the problem.

Lemma 3. There is a position and a lap in which the rooster stops twice and bypasses once (in some order) in the next three laps.

Proof. There is a position $j$ the rooster stops for infinitely many times. Each time it stops at $j$, it changes between stopping and bypassing $j+1$. So the rooster stops and bypasses $j+1$ infinitely many times. Then there is a lap in which the rooster stops at $j+1$, and bypasses it in the next. As in solution 1, it cannot bypass $j+1$ two times in a row, so it stops at $j+1$ in the next lap.

Lemma 4. If the rooster stops twice and bypasses once (in some order) at some position in three consecutive laps, it also stops twice and bypasses once at the next position (in some order) in the same laps (or in the next laps, in case the lap changes from one position to the other).

Proof. When the rooster bypasses the position, it must stop at the next one. In the two times it stops at the position, the cell has different numbers on it, so the rooster will stop once and bypass once at the next position.

By lemmata 3 and 4, there would be a moment that the rooster stops twice and bypasses once (in some order) at any position after this moment. After this moment, if the rooster is in a cell $C$ in lap $t$, we know that it stopped; stopped-bypassed; and bypassed-stopped at $C$ in laps $t, t+1, t+2$. Since it stopped twice and bypassed once (in some order) in laps $t+1, t+2, t+3$, it must stop at $C$ in lap $t+3$. Moreover, the rooster stopped twice and bypassed once (in some order) each cell between stopping at $C$ in laps $t$ and $t+3$, so every cell has the same assigned number before and after going around the circle three times.

Let us reformulate the problem in terms of Graphs: we have a directed graph $G$ with $V= \{v_{1}, v_{2}, \ldots, v_{n}\}$ representing positions and $E=\{v_{i} \rightarrow v_{i+1}, v_{i} \rightarrow v_{i+2} \mid 1 \leq i \leq n\}$ representing moves. Indices are taken $\bmod n$. Note that each vertex has in-degree and out-degree both equal to $2$. We say that the edge $v_{i} \rightarrow v_{i+1}$ is active and $v_{i} \rightarrow v_{i+2}$ is inactive if the number on $v_{i}$ is $0$, or the edge $v_{i} \rightarrow v_{i+2}$ is active and $v_{i} \rightarrow v_{i+1}$ is inactive if the number on $v_{i}$ is $1$. The rooster then traces an infinite trail on the graph in the following manner;
- it starts at $v_{1}$;
- if the rooster is at $v_{i}$, it uses the active edge going out of $v_{i}$ to continue the path, and changes the number on $v_{i}$.

Take the first vertex that appears $3$ times on the rooster's trail, and suppose without any loss of generality that it is $v_{1}$ (otherwise, just ignore the path before the first time that this vertex appears). Consider the sub-trail from the first to the third time $v_{1}$ appears: $C=v_{1} \rightarrow \cdots \rightarrow v_{1} \rightarrow \cdots \rightarrow v_{1}$. Trail $C$ induces a circuit $C^{*}$ on $G$ that passes through $v_{1}$ twice.

In between two occurrences of $v_{1}$, the rooster must have completed at least one lap. Vertex $v_{1}$ appears three times at $C$, so $C$ contains at least two laps. Since (as per Solution 1) no vertex is bypassed twice in a row, $C^{*}$ must contain every vertex. Moreover, $v_{1}$ is the first (and only) vertex that appeared three times on the rooster's path, so each vertex appear at most twice on $C^{*}$.

Lemma 5. Take $V^{\prime}$ to be the subset of $V$ containing the vertices that only appears once on $C^{*}$ and $E^{\prime}$ to be the edges of $G$ that don't appear on $C^{*}$. So $G^{\prime}=(V^{\prime}, E^{\prime})$ is a simple cycle or $V^{\prime}=E^{\prime}=\emptyset$.

Proof. We will first prove that each edge in $C^{*}$ appears exactly once. Suppose, for the sake of contradiction, that there is an edge $u \rightarrow v$ that appears twice on $C^{*}$. So $u$ must appear times in $C$, because the active edge going out of $u$ changes at each visit to it. So $u=v_{1}$, but the rooster only goes out of $v_{1}$ twice in $C$, which is a contradiction.

Now, since $C^{*}$ does not have repeated edges, all four edges through $v$ are in $C^{*}$ if $v$ is visited twice in this cycle. So the edges on $E^{\prime}$ cannot pass through vertices in $V \backslash V^{\prime}$, then $G^{\prime}$ is well-defined.

Since $v \in V^{\prime}$ is visited once on $C^{*}$, it has $\operatorname{deg}_{\text{in}}(v)=\operatorname{deg}_{\text{out}}(v)=1$ in $G^{\prime}$, so $G^{\prime}$ is a union of disjoint simple cycles. Each of these cycles completes at least one lap, and $v_{1}$ is skipped on these laps, so all cycles must use the edge $v_{n} \rightarrow v_{2}$. But the cycles are disjoint, so there is at most one cycle.

Lemma 6. The rooster eventually traverses a contiguous Eulerian circuit of $G$.

Proof. If $V^{\prime}=E^{\prime}=\emptyset, C^{*}$ is already an Eulerian circuit traversed in $C$. If not, take $u_{1}$ to be the first vertex of $C$ that is in $V^{\prime}$. Let $U=u_{1} \rightarrow \cdots \rightarrow u_{k} \rightarrow u_{1}$ be the cycle determined by $G^{\prime}$ by Lemma 5, $C_{1}=v_{1} \rightarrow \cdots \rightarrow u_{1}$ be the sub-path of $C$ from the first $v_{1}$ to $u_{1}$, and $C_{2}=u_{1} \rightarrow \cdots \rightarrow v_{1}$ be the rest of $C$.

Each vertex on $V \backslash V^{\prime}$ has been changed twice, so they would be in their initial states after $C$; every vertex on $V^{\prime}$ has been changed only once, and therefore are not on their initial states. Let us trace the rooster's trail after it traversed $C$. By the minimality of $u_{1}$, all the edges of $C_{1}$ are active after $C$, so the rooster traverses $C_{1}$ after $C$. Moreover, each $u_{i}$ was visited exactly once in $C$ and has not yet used the edge $u_{i} \rightarrow u_{i+1}$. Since all their states have changed, all edges of $U$ are active after $C$. Therefore, the rooster traverse $U$ after $C_{1}$, flipping all the vertices in $U$ to their initial states. Then, since every state in $U$ was changed, the rooster traverses $C_{2}$ instead of $U$. The trail is then $C \rightarrow C_{1} \rightarrow U \rightarrow C_{2}$, and then $C_{1} \rightarrow U \rightarrow C_{2}$ is an Eulerian circuit.

Having this in mind, after the rooster completes an Eulerian circuit, it has passed through each vertex twice and returned to its initial vertex, so the state of the rooster and of the edges are the same before and after the Eulerian cycle. The rooster will then traverse the Eulerian circuit repeatedly.

The edges $v_{i} \rightarrow v_{i+1}$ move forward by one position and the edges $v_{i} \rightarrow v_{i+2}$ move forward by two positions. Since all edges are used, each time the rooster traverses the Eulerian circuit, it moves forward a total of $n(1+2)=3n$ positions, which corresponds to three laps. The proof is now complete.