, 2013

We shall prove that this can be done if and only if at least one of the numbers $n$ and $m$ is even.

First observe the case when one of the numbers is even. Without loss of generality, suppose $m$ is even. We divide a table of size $n \times m$ ($n$ rows, $m$ columns) into quadrilaterals of size $1 \times 2$ and color them white and black in turn, in the form of a chessboard, as shown in the figure below. Since $m$ is even, each row can be divided into exactly $\frac{m}{2}$ such quadrilaterals, which makes the coloring possible. It also holds that each cell has exactly one neighbouring cell of the same color. The table-coloring problem is solved.

Now observe the case when both numbers are odd. Suppose the table is colored in the desired way. We search for a contradiction. Because the number of all cells in the table is odd, there must be an odd number of cells of one of the two colors, say black. Number the black cells with numbers $1$ to $2z-1$ for some natural number $z$. Let the number of all black neighbours of the cell numbered $i$ be $k_i \in \mathbb{N}$. The number of all unordered pairs of neighbouring black-colored cells must then be equal to
$$\frac{k_1 + k_2 + \dots + k_{2z-1}}{2}$$
This holds due to the following reasoning: if we count the number of all black neighbours of all the cells in the table, we count every pair of neighbouring black cells twice. We have assumed that the table is colored in the desired way, hence all the numbers $k_i$ are even. The numerator of the above fraction thus contains a sum of an odd number of odd numbers, which again is an odd number. From this we conclude that the number of all pairs of neighbouring black cells is not an integer, which is an obvious contradiction. Hence, if numbers $m$ and $n$ are odd, the table cannot be colored in the desired way.