#7 Coloring and Board Problems

The board has area \(25\), while each domino has area \(2\). The total area covered by dominoes is always even, so an area of \(25\) cannot be tiled.

The full \(6\times6\) board has equal numbers of black and white cells. Removing two cells of the same color destroys this equality. But every domino covers one black and one white cell, so any domino tiling would cover equal numbers of the two colors. Contradiction.

On a \(7\times7\) board, the corner color occurs \(25\) times and the other color \(24\) times. Dominoes cover equal numbers of the two colors. Hence the remaining cell must have the color that occurred one more time, the corner color.

Every knight move changes the square color. After an odd number of moves the color is opposite to the initial one. Since \(9\) is odd, the knight is on a white square. It cannot be on black after \(9\) moves.

Under the coloring by \(i+j\pmod3\), every straight tromino covers one cell of each color. On the \(5\times5\) board, colors \(0,1,2\) occur \(9,8,8\) times. The cell \((1,1)\) has color \(2\), so after removing it the counts become \(9,8,7\). They are not equal, so no tiling exists.

In chessboard coloring, opposite corners of an \(8\times8\) board have the same color. After removing them, one color has two fewer cells than the other. Each domino covers one cell of each color, so the remaining region cannot be tiled.

In chessboard coloring, cell \((i,i)\) always has the same color because \(i+i\) is even. Thus \(8\) cells of one color are removed. The full board had equal color counts, and after removal they are unequal. Dominoes cover colors equally, so tiling is impossible.

Color the columns alternately in two colors. A horizontal domino covers one cell of each column color, while a vertical domino covers two cells of one column color. The board has \(18\) cells of each color. Horizontal dominoes keep the balance, so vertical dominoes must contribute equal numbers of cells of the two colors. Thus the number of vertical dominoes in the two types of columns must be equal. But their total is \(5\), impossible.

Under the coloring \((i,j)\mapsto i+j\pmod3\), every straight tromino covers one cell of each color. On a \(7\times7\) board, colors \(0,1,2\) occur \(16,16,17\) times. The cell \((1,2)\) has color \(0\), so after removal the counts are \(15,16,17\). They are not equal, so the remaining region cannot be tiled by straight trominoes.

Under coloring by \(i+j\pmod4\), each straight tetromino covers one cell of each of the four colors. On the \(5\times5\) board, colors \(0,1,2,3\) occur \(6,6,7,6\) times. The cell \((1,2)\) has color \(3\), so after removing it the counts are \(6,6,7,5\). They are not equal, so no tiling exists.

Opposite corners of a \(4\times4\) board have the same color. But every knight move changes color, so after \(15\) moves, an odd number, the knight must be on the opposite color. Therefore it cannot finish in the opposite corner.

Since \(mn\) is odd, one color occurs one more time in chessboard coloring. Dominoes cover one cell of each color. Hence after all domino-covered cells are removed, the remaining cell must have the majority color.

In chessboard coloring, all cells on the main diagonal have the same color. The full \(10\times10\) board has equal color counts, and after removing \(10\) cells of one color the equality is broken. A domino always covers one cell of each color, so tiling is impossible.

Under the coloring \((i,j)\mapsto i+j\pmod3\), every tromino covers one cell of each color. Thus \(21\) trominoes cover \(21\) cells of each color. On the \(8\times8\) board, colors \(0,1,2\) occur \(22,21,21\) times. Therefore the single cell must have color \(0\). But \((1,1)\) has color \(2\), and \((8,8)\) has color \(16\equiv1\pmod3\). Neither can be the single cell.

Color the columns alternately. A horizontal domino always covers one cell of each column color. A vertical domino covers two cells of one color. Since the board has equal color counts, vertical dominoes must be split equally between the two types of columns. Their number must be even. Since \(17\) is odd, such a tiling is impossible.

Color the board as a chessboard. Every knight move changes color, so the knight graph is bipartite: all edges go between the two colors. A closed tour through \(25\) cells would be a cycle of length \(25\). But every cycle in a bipartite graph has even length, because colors alternate. Contradiction.

On a \(9\times9\) board, the corner color occurs \(41\) times and the other color \(40\) times. All dominoes together cover equal numbers of the two colors. The one remaining cell, covered by the monomino, must have the majority color, the corner color.

Color cell \((i,j)\) by \(i+j\pmod4\). A straight tetromino covers one cell of each color. On the full \(8\times8\) board each color occurs \(16\) times. On the main diagonal the colors alternate only between \(0\) and \(2\): four cells of color \(0\) and four of color \(2\) are removed, while colors \(1\) and \(3\) are not removed. The remaining counts are \(12,16,12,16\), not all equal. Hence no tiling exists.

Under coloring by \(i+j\pmod3\), every straight tromino covers one cell of each color. Thus \(16\) trominoes cover \(16\) cells of each color. On the \(7\times7\) board the color counts are \(16,16,17\), with the extra color being \(2\). Therefore the monomino must stand on a cell of color \(2\), meaning \(i+j\equiv2\pmod3\).

The full \(8\times8\) board has \(32\) cells of each color. Dominoes cover equal numbers of black and white cells. If one uncovered cell were black and the other white, the covered cells would include \(31\) black and \(31\) white cells, which is consistent. Thus the proposed statement is false: the two uncovered cells may have different colors. For example, leave two adjacent cells and tile the rest. Therefore the correct conclusion is that coloring does not force the two cells to have the same color.

Color cell \((i,j)\) by \(i+j\pmod4\). Each straight tetromino covers one cell of each color. On the full \(8\times8\) board each color occurs \(16\) times. The corners have colors \(2,1,1,0\), so after removal the counts are \(15,14,15,16\). These are not equal, so the region cannot be split into pieces each taking one cell of each color.

Color cell \((i,j)\) by \(i+j\pmod4\). Each straight tetromino covers one cell of each color, so \(20\) tetrominoes cover \(20\) cells of each color. On the \(9\times9\) board, the counts of colors \(0,1,2,3\) are \(20,20,21,20\). Hence the single monomino must cover the extra cell of color \(2\).

Color the columns alternately. As before, horizontal dominoes cover one cell of each color, while vertical dominoes cover two cells of one color. Since the whole board has equal color counts, vertical dominoes must be split equally between the two types of columns. Hence their total number is even. Thus an odd number of vertical dominoes is impossible. Example with \(16\): tile the first four columns entirely by vertical dominoes, giving \(16\) vertical dominoes; tile the remaining four columns by horizontal dominoes along rows.

Color cell \((i,j)\) by the residue \(i+j\pmod4\). Any straight tetromino covers one cell of each of the four colors. On the full \(10\times10\) board, the counts of colors \(0,1,2,3\) are \(25,24,25,26\). On the main diagonal \((i,i)\), colors alternate between \(2\) and \(0\), so \(5\) cells of color \(0\) and \(5\) cells of color \(2\) are removed. On the other diagonal \((i,11-i)\), the sum of indices is \(11\), so all these \(10\) cells have color \(3\). After removal the counts are \(20,24,20,16\). They are not equal. But a tiling by straight tetrominoes would require equal numbers of all four colors. Contradiction.