Problem

Source: 2022 China TST, Test 4 P1

Tags: combinatorics, Coloring



Initially, each unit square of an $n \times n$ grid is colored red, yellow or blue. In each round, perform the following operation for every unit square simultaneously: For a red square, if there is a yellow square that has a common edge with it, then color it yellow. For a yellow square, if there is a blue square that has a common edge with it, then color it blue. For a blue square, if there is a red square that has a common edge with it, then color it red. It is known that after several rounds, all unit squares of this $n \times n$ grid have the same color. Prove that the grid has became monochromatic no later than the end of the $(2n-2)$-th round.