How to color a board such that each square has exactly two neighbors of the opposite color

Solution 1:

If $m=n$, then $m$ and $n$ are both even or both odd; however, the condition requires an even number of black and white squares, so $mn = m^2$ is even; therefore $m=n$ is even. Now let's deal with rectangles that are not squares. Without loss of generality, $n<m$.

Lemma. Assuming $n < m$, the top $n$ rows form an $n\times n$ sub-board symmetric about its main diagonal.

Proof. Induct on the anti-diagonals, looking at them in the following order:

123456
23456
3456
456 .
56   .
6     .

We begin in the middle of each anti-diagonal:

• For the odd anti-diagonals, the middle square can be filled arbitrarily.
• For the even anti-diagonals, the middle two squares are both adjacent to the middle square of the previous anti-diagonal, which (by symmetry) already has two neighbors of one color, so they get the same color.

Then we work outwards, and every step is forced, so the anti-diagonal is symmetric. $\square$

The top $n \times n$ sub-board is symmetric, and its rightmost edge consists of $n$ squares on the edge of the board; its bottom edge (the $n^{\text{th}}$ row of the board), on the other hand, has $n$ squares with more squares below them. However, since the two edges are the same, the coloring condition for them is satisfied just by the $n \times n$ sub-board. Therefore the squares in the $(n+1)^{\text{th}}$ row are identically colored to the squares on the $n^{\text{th}}$ row.

It follows that if we delete the $n \times n$ sub-board, we get an $(m-n)\times n$ board for which the coloring condition also holds.

Now we can finish the claim by induction on the size of the board. The induction hypothesis tells us that both $m-n$ and $n$ must be even; therefore $m$ and $n$ are both even.

Solution 2:

Here's a convenient trick: Flip the color of every other square. I.e. if a square has coordinates $(x,y)\in \mathbb{Z}^2$, flip it's color if $x+y$ is even. Then this modified board will be such that every square has two neighbors of the same color. This means that each square is on a loop of identical color.

Now look at one side of the rectangle, say the bottom. Each square on the bottom has at least one neighbor of the same color also on the bottom (since it has only one neighbor on the board that's not on the bottom). I claim the contiguous blocks of same-colored squares on the bottom can only have even length: If a contiguous block of squares $1, 2, \dots, n$ has the same color, say black, then squares $2, 3, \dots, n-1$ must have white neighbors above them (see picture below; grey squares are undetermined by this argument). Number these white squares $2,3, \dots, n-1$ just like their neighbors below. Then white squares $3,4,\dots,n-2$ must have black neighbors above them. And so on inductively until we are left with just 2 squares at positions $n/2, n/2+1$. This shows you can only have even blocks on the boundary of the board, and hence the boundary itself must have even length, being a sum of possibly several such blocks. Hence the board must have even dimensions $m$ and $n$.