Let $2001$ given points on a circle be coloured either red or green. In one step all points are recoloured simultaneously in the following way: If both direct neighbours of a point $P$ have the same colour as $P$, then the colour of $P$ remains unchanged, otherwise $P$ obtains the other colour. Starting with the first colouring $F_1$, we obtain the colourings $F_2,F_3 ,\ldots .$ after several recolouring steps. Prove that there is a number $n_0\le 1000$ such that $F_{n_0}=F_{n_0 +2}$. Is the assertion also true if $1000$ is replaced by $999$?
Problem
Source: Baltic Way 2001
Tags: combinatorics proposed, combinatorics
KRIS17
12.04.2019 07:28
Lemma 1: Any segment $S$ of the cirlce having no $3$ consecutive points of the same color keeps alternating, in other words: $S_{n}=S_{n +2}$ for all $n\ge 1$. Proof: Clearly, any point in $S$ is surrounded by atleast $1$ point of different color. So this point must change its color. Thus each point changes its color to the other color in each step. Thus after $2$ colorings each point obtains the original color, there by the entire segment $S$ returns to its original state after $2$ colorings. Lemma 2: Any Segment $C$ of the circle having all points of same color keeps getting reduced in size by $2$ after each step until no $3$ points of the same color remain in the segment. Proof: Consider the end points of the segment. They are surrounded by an opposite colored point. So after one step, these $2$ end points change their colors to the opposite color while the rest of the points remain unchanged in segment $C$. This process continues in each recoloring until we are left with no $3$ points of the same color in segment $C$. From lemma 1 we infer that in order to attain a state $F_{n_0}$ where $F_{n_0}=F_{n_0 +2}$ we require that no $3$ consecutive points of the same color exist in the circle. From Lemma 2, the maximum number of steps needed to reach a state $F_{n_0}$ depends on the size of the longest segment $C$ containing points of the same color. Case 1: All $2001$ points of the circle are of the same color: This is a degenerate case. Here none of the points change colors at each step so $F_{n_0}=F_{n_0 +2}$ for all $n_0\ge 1$. So lets ignore this case. Case 2: Exactly $2000$ points of the circle are of the same color. So starting from this initial position $F_1$, from lemma 2, after exactly $(2000/2) - 1 = 999$ recolorings i.e at $F_{1000}$ we are left with no $3$ consecutive points of the same color. So from lemma 1, we have $F_{1000}=F_{1000 +2}$. In fact $F_{n_0}=F_{n_0 +2}$ for all $n_0\ge 1000$. Since we need atleast $999$ recolorings after initial coloring $F_1$ in the above case, the assertion fails for $n_0\le 999$.