In the beginning, there is a circle with three points on it. The points are colored (clockwise): Green, blue, red. Jonathan may perform the following actions, as many times as he wants, in any order: Choose two adjacent points with different colors, and add a point between them with one of the two colors only. Choose two adjacent points with the same color, and add a point between them with any of the three colors. Choose three adjacent points, at least two of them having the same color, and delete the middle point. Can Jonathan reach a state where only three points remain on the circle, colored (clockwise): Blue, green, red?
Problem
Source: Israel National Olympiad 2016 Q4
Tags: combinatorics, colorings, points
Pathological
28.08.2019 19:33
Let's keep track of the contiguous blocks of points of the same color. For instance, if the points on the circle are $G, G, R, B, B, R, G, R, B, G, G, R, B, G, G, R, B, B, B, B$ in clockwise order, we only care about the sequence $G, R, B, R, G, R, B, G, R, B, G, R, B$. The first operation does nothing, the second operation does either nothing to the sequence or one of the following six things: $$B \rightarrow BRB, B \rightarrow BGB, R \rightarrow RBR, R \rightarrow RGR, G \rightarrow GRG, G \rightarrow GBG.$$The third operation simply reverses one of the above operations, which is to say it either does nothing or does one of the following six things: $$BRB \rightarrow B, BGB \rightarrow B, RBR \rightarrow R, RGR \rightarrow R, GRG \rightarrow G, GBG \rightarrow G.$$We will say that an operation is meaningful if it does not do nothing. So there are $12$ possible meaningful operations. We will say that an operation is additive if it augments the size of the sequence by $2$ letters, and subtractive if it decreases the sequence by $2$ letters. So there are $6$ additive operations and $6$ subtractive operations. We will call an arc of the sequence to be a pair of consecutive colors in the sequence. We will call a $GR-$arc on in which the two points are $G$ and $R$, in clockwise order. Define $GB-, BR-, BG-, RB-, RG-$arcs similarly. Let $a, b, c$ be variables corresponding to the number of $GB-, BR-, RG-$arcs respectively. Notice that each move either does nothing or toggles the parity of precisely one of $a, b, c.$ Furthermore, every move preserves the parity of each of $a, b, c$ iff it is not meaningful, and toggles the parity of precisely one of $a, b, c$ if and only if it is additive or subtractive. Observe that since the size of the sequence is $3$ at the beginning and end (goes from $G, B, R \rightarrow B, G, R$), the number of additive moves and number of subtractive moves are the same. Hence, the parities of $a, b, c$ are toggled an even number of times in total, and so hence $a+b+c$'s parity should be the same in the end as it was in the beginning. However, this is not the case, as $a+b+c = 3$ initially, and it is $0$ at the end. Hence Jonathan cannot reach the desired state. $\square$