Problem

Source: 2018 Thailand October Camp 1.1

Tags: combinatorics



Let $2561$ given points on a circle be colored either red or green. In each step, all points are recolored simultaneously in the following way: if both direct neighbors of a point $P$ have the same color as $P$, then the color of $P$ remains unchanged, otherwise $P$ obtains the other color. Starting with the initial coloring $F_1$, we obtain the colorings $F_2, F_3,\dots$ after several recoloring steps. Determine the smallest number $n$ such that, for any initial coloring $F_1$, we must have $F_n = F_{n+2}$.