A $9\times9$ checkerboard is colored with 2 colors. If we choose any $3\times1$ region on the checkerboard we can paint all of the squares in that region with the color that is in the majority in that region. Show that with a finite number of these operations, we can paint the checkerboard all in the same color.
Problem
Source: Puerto Rico 2013 TST #6
Tags: combinatorics
AdithyaBhaskar
01.05.2015 09:38
My solution: Let us number the squares $a1,a2,...,a9,....,i9$. We first apply the operation on $a1,a2,a3;a4,a5,a6;,a7,a8,a9,...,i7,i8,i9$. Now, by using this technique on $a2,a3,a4; $ then $a3,a4,a5$ etc., we can colour each of $a1,...,a9$ in the same color and the same applies to $b1,...,b9,$ etc. Next, we apply this to $a1,b1,c1;a2,b2,c2$ etc., so that all of $a1,...,a9,b1,....,b9,c1,...,c9$ are of the same colour. Then using $b1,c1,d1;b2,c2,d2 $ etc. we can colour the cells $a1,...a9,....,d9 $ in the same colour. Following in a similar manner, we colour all of the cells in the same colour.
programmeruser
24.09.2022 04:06
Let $(x,y)$ denote the square in the $x$th column and $y$th row.
Also, let the operation in the problem statement be denoted as flipping.
We can paint the checkboard in the same color with this method:
First, make it so that each column has uniform color. Let the column number be $c$. We can do this by flipping $(c, 1)$, $(c, 2)$, and $(c, 3)$, then flipping $(c, 2)$, $(c, 3)$, $(c,4)$, and so on until the column is of uniform color.
Once the columns are of uniform color, we can make the whole board uniform color with a similar process. For every row $r$, we flip $(0, r)$, $(1, r)$, and $(2, r)$, then we flip $(1, r)$, $(2, r)$, and $(3, r)$ and so on until the entire board is of uniform color.