There are $N\ge3$ letters arranged in a circle, and each letter is one of $L$, $T$ and $F$. For a letter, we can do the following operation: if its neighbors are the same, then change it to the same letter too; otherwise, change it so that it is different from both its neighbors. Show that for any initial state, one can perform finitely many operations to achieve a stable state. Here, a stable state means that any operation does not change any of the $N$ letters. (ltf0501)
Problem
Source: IMOC 2020 C2
Tags: combinatorics
Prod55
23.10.2021 20:12
For any initial state $S$ let $a_S$ the maximum possible length of a block $AA...A$ that we can make with finitely many moves , where $A$ is someone of $F,L,T$. It's easy to show that the stable stases are of the form $ABCABC...ABC(1)$, $AAA...AA (2)$. If $a_S=1$ then obviously we have the first form and we are done. Now let $N>a_S\geq 2$, then we can make a block of the form $\underset{a_S\,\,times}{\underbrace{AA..A}}B$ . Now for the next two letters we have $9$ cases: $(1)AABAC\rightarrow AAAAC$ contradiction.(we have a block $AA..AA$ of leght $a_S+2$)) $(2)AABAA\rightarrow AAAAA$ contradiction. $(3)AABCA\rightarrow ACBCA\rightarrow ACCCA\rightarrow ACCBA\rightarrow ACABA\rightarrow AAAAA$, contradiction. $(4)AABCC\rightarrow AABAC\rightarrow AAAAC$ contradiction. $(5)AABBA\rightarrow AABCA=(3)\rightarrow ...$ contradiction. $(6)AABAB\rightarrow AAAAB$ contradiction. $(7)AABBC\rightarrow AABAC=(1)\rightarrow ..$ contradiction. $(8)AABCB\rightarrow AABAB=(6)\rightarrow ..$ contradiction. $(9) AABBB\rightarrow ACBBB\rightarrow ACABB\rightarrow AAABB$ contradiction. So $a_S=N$ and we are done.