On a circle, $n \geq 3$ points are marked. Each marked point is coloured red, green or blue. In one step, one can erase two neighbouring marked points of different colours and mark a new point between the locations of the erased points with the third colour. In a final state, all marked points have the same colour which is called the colour of the final state. Find all $n$ for which there exists an initial state of $n$ marked points with one missing colour, from which one can reach a final state of any of the three colours by applying a suitable sequence of steps.
Problem
Source: Baltic Way 2023/10
Tags: combinatorics
11.11.2023 22:31
Denote the colours as $1,2,3$. Claim: If $n$ is even, then we can do this operation. If there exists $1,2,3$ in a moment, then we can do this. The arc $1,2,1,1,...,1,1$ which has $2k-2$ numbers can be turned into $3$ by doing operations from left to right. If we choose the other $2$ colours as $1$ and $2$, we can get all $3$ colours at the final position. Let's prove that we can't reach all $3$ colours for odd $n'$s. Assume contrary. Assume that the colour which doesn't exist in the initial position is $2$. The operations are $1,2\rightarrow 3$ $1,3\rightarrow 2$ $2,3\rightarrow 1$ So the total numbers of $1$ and $3$ changes $0$ or $2$ in a move. There exists odd number of $1$ and $3$ so at any position, there should be odd number of $1$ and $3$. It results in a contradiction because there will be at least one $1$ or $3$ at any position which gives us that the circle won't contain just $2'$s.
15.06.2024 10:29
Denote $r$ = red, $b$ = blue, $g$ = green. For $n$ even, consider the arrangement $rrbb\cdots bb$, where the amount of $b$-s is $n-2$. Replacing $rb$ with $g$ leads to $rgb\cdots bb$ with $n-3$ $b$-s, then $gb$ with $r$ - to $rrbb\cdots bb$ with $n-4$ $b$-s, etc, we continue in the same fashion until reaching only one $b$, i.e. the configuration $rgb$. From here replacing two points with a third leads to all of $rr$, $gg$, $bb$. For $n$ odd, suppose without loss of generality that green is missing, and note that the total amount of blue and red changes by $0$ or $2$ in one move, i.e. its parity is preserved. Initially this amount is odd, hence also at the end; in particular, reaching a configuration with green points only is impossible, since it contains zero red and blue points.