Problem: Initially we have an $m\times n$ board with all unit squares white. As a result, we want to paint any two squares with a common edge, one black and one white. (That is, we want to get it like a chessboard pattern after the final step.)
In each step of the painting process, a $2\times 2$ square is selected on the board and its white unit squares are painted black and its black unit squares painted white. For which $(m, n)$ pairs can the board be painted as desired?
Note: I solved some parts of the problem. I'm adding them to the post. Remaining part of the problem is at the bottom of the page. Thanks.
My attempts and some parts about the solution:
- For $4\mid m$ and $4 \mid n$, it is possible. Firstly, let's take $m=4, n=4$.
$
\begin{array}{|c|c|c|c|c|}
\hline
\text{ } & \text{ } & \text{ } & \text{ } \\ \hline
\text{ } & \text{ } & \text{ } & \text{ } \\ \hline
\text{ } & \text{ } & \text{ } & \text{ } \\ \hline
\text{ } & \text{ } & \text{ } & \text{ } \\ \hline
\end{array}
\to
\begin{array}{|c|c|c|c|c|}
\hline
\blacksquare & \blacksquare & \text{ } & \text{ } \\ \hline
\blacksquare & \blacksquare & \text{ } & \text{ } \\ \hline
\text{ } & \text{ } & \blacksquare & \blacksquare \\ \hline
\text{ } & \text{ } & \blacksquare & \blacksquare \\ \hline
\end{array}
\to
\begin{array}{|c|c|c|c|c|}
\hline
\blacksquare & \text{ } & \blacksquare & \text{ } \\ \hline
\blacksquare& \text{ } & \blacksquare & \text{ } \\ \hline
\text{ } & \blacksquare & \text{ } & \blacksquare \\ \hline
\text{ } & \blacksquare & \text{ } & \blacksquare \\ \hline
\end{array}
\to
\begin{array}{|c|c|c|c|c|}
\hline
\blacksquare & \text{ } & \blacksquare & \text{ } \\ \hline
\text{ } & \blacksquare & \text{ } & \blacksquare \\ \hline
\blacksquare & \text{ } & \blacksquare & \text{ } \\ \hline
\text{ } & \blacksquare & \text{ } & \blacksquare \\ \hline
\end{array}
$
That is, a $4 \times 4$ board can be paint as desired. Easily, we expand that, if $4\mid m$ and $4\mid n$ then a $m \times n$ board can be paint as desired.
- If $m=2$ or $n=2$, $m \times n$ board can not be paint as desired. Let $m=2$.
\begin{array}{|c|c|c|c|c|}
\hline
\text{x} & \text{ } & \text{ } & \text{ }& \text{ } & \text{ } \\ \hline
\text{x} & \text{ } & \text{ } & \text{ }& \text{ } & \text{ } \\ \hline
\end{array}
Let's examine the first column of the $2\times n$ table (Cells with x in them). Since the colors of these cells will always be the same, a desired format cannot be done.
- If $m$ or $n$ is an odd number, a painting in the desired format can not be done. Suppose that $m \geq 3$ odd number. Let's examine difference of number of white squares and number of black squares in the first two columns. Let $w, b$ be number of white squares and number of black squares in the first two columns. Difference of they is $D = w- b$.
$
\begin{array}{|c|c|c|c|c|}
\hline
\text{ } & \text{ } \\ \hline
\text{ } & \text{ } \\ \hline
\text{ } & \text{ } \\ \hline
\text{ } & \text{ } \\ \hline
\text{ } & \text{ } \\ \hline
\end{array}
$
Initially $D = 2m – 0 = 2m$.
$
\begin{array}{|c|c|c|c|c|}
\hline
\text{ } & \blacksquare \\ \hline
\blacksquare & \text{ } \\ \hline
\text{ } & \blacksquare \\ \hline
\blacksquare & \text{ } \\ \hline
\text{ } & \blacksquare \\ \hline
\end{array}
$
After the final step $D= m – m = 0$.
We will prove that $D$ is an invariant in $\mod 4$. Because,
$
\begin{array}{|c|c|c|c|c|}
\hline
\text{ } & \text{ } \\ \hline
\text{ } & \text{ } \\ \hline
\end{array}
\to
\begin{array}{|c|c|c|c|c|}
\hline
\blacksquare & \blacksquare \\ \hline
\blacksquare & \blacksquare \\ \hline
\end{array}
$
After the step, $D$ will decrease $8$.
$
\begin{array}{|c|c|c|c|c|}
\hline
\blacksquare & \text{ } \\ \hline
\text{ } & \text{ } \\ \hline
\end{array}
\to
\begin{array}{|c|c|c|c|c|}
\hline
\text{ } & \blacksquare \\ \hline
\blacksquare & \blacksquare \\ \hline
\end{array}
$
After the step, $D$ will decrease $4$.
$
\begin{array}{|c|c|c|c|c|}
\hline
\blacksquare & \blacksquare \\ \hline
\text{ } & \text{ } \\ \hline
\end{array}
\to
\begin{array}{|c|c|c|c|c|}
\hline
\text{ } & \text{ } \\ \hline
\blacksquare & \blacksquare \\ \hline
\end{array}
$
After the step, $D$ will same…etc.
Thus, $D$ is an invariant in $\mod 4$.
When $m\geq 3$ odd number, initially $D = 2m \equiv 2 \pmod{4}$ and after the final step $D\equiv 0 \pmod{4}$. Since $2\not\equiv 0 \pmod{4}$, there is a contradiction. That is, when $m$ or $n$ is an odd number, a painting in the desired format can not be done.
Remaining Problem: Let $m,n>2$ even numbers.
(a) If $m\equiv 2 \pmod{4}$ and $n\equiv 2 \pmod{4}$, can we paint in the desired format?
(b) If $m\equiv 2 \pmod{4}$ and $n\equiv 0 \pmod{4}$, can we paint in the desired format?
Best Answer
Hint As you noticed, you need some sort of invariant to prove you cannot succeed. You used the difference $b-w$ for the squares in two columns. Instead, find a modulo invariant for the number of black squares alone in a single column.