Tom painted round fence which consists of $2n \ge6$ sections in such way that every section is painted in one of four colours. Then he repeats the following while it is possible: he chooses three neighbouring sections of distinct colours and repaints them into the fourth colour. For which $n$ Tom can repaint the fence in such way infinitely many times?
Problem
Source: Kyiv mathematical festival 2015
Tags: Kyiv mathematical festival, combinatorics
junioragd
10.05.2015 12:20
If I understand the problem correctly,we have $2n$ points on a circle and each is coloured with one of four colours and in every move we pick $3$ consecutive points of different colors and repaint them in to fourth colour,then the answer is no for all $n$.Suppose opposite. Let $S$ be the number pairs of points which are consecutive or have at most one point beetwen them which have distinct colours.It is easy to prove that $S$ is decrasing by at least one per move and since $S$ is finite(at most $4n$),we will have that $S$ is zero after a finite number of moves,which means that all numbers will be the same,which is a contradiction.
dgrozev
13.05.2015 00:37
junioragd wrote: ...Let $S$ be the number pairs of points which are consecutive or have at most one point beetwen them which have distinct colours.It is easy to prove that $S$ is decrasing by at least one per move... There is a question here: well, if so, why did the author impose the sections of the fence to be $2n$, instead just $n$. Secondly, consider $1,1,|1,2,3|,3,3\to 1,1,|4,4,4|,3,3$ and see that the value of $S$ is not decreasing, but increasing by 1. Moreover, this idea can not be fixed, just because for example we can repaint the fence $1,1,1,2,2,3$ (the first and the last elements are glued)infinitely many times. This is also true, I suppose, when $n$ is odd, which can be checked easily.