2
$\begingroup$

One corner of a $(2n - 1) \times (2n - 1)$ chessboard is cut off. For which $n$ can you cover the remaining squares by $2\times 1$ dominoes, so that half of the dominoes are horizontal?

My half-finished solution:

Color the chessboard's rows alternately black and white (so for example when $n=3$, there are 14 black squares and 10 white squares). Each vertical domino covers one white square and one black square, and each horizontal domino covers either two black squares or two white squares. We call a horizontal domino an HB-domino or an HW-domino (H stands for horizontal, B stands for black, W stands for white) based on what color squares it covers. Also let $\#B$ be the number of black squares on the board and $\#W$ be the number of white squares on the board. Then $$\#B=\tfrac{1}{2}(2n-1)(2n-2)+2n-2=(2n+1)(n-1)$$ and $$\#W=4n(n-1)-\#B=(2n-1)(n-1).$$ After the vertical dominoes are placed, since each vertical domino covers exactly one black square, the number of remaining black squares is $\#B-n(n-1)=n^2-1$ and the number of remaining white squares is $\#B-n(n-1)=(n-1)^2$. If $n^2-1$ is odd, there is no way to cover the remaining black squares with only HB-dominoes, since each HB-domino covers exactly two black squares. Similarly, if $(n-1)^2$ is odd, there is no way to cover the remaining white squares with only HW-dominoes. Therefore in order for a valid covering to exist, both $n^2-1$ and $(n-1)^2$ cannot be odd, which means that $n$ cannot be even.

However I have no idea how to prove that when $n$ is odd, a valid covering always exists. Any hints?

$\endgroup$

2 Answers 2

6
$\begingroup$

Let's assume the top left square is cut off. You can fill the rest of the top row with horizontal dominoes, and the rest of the left column with vertical dominoes. Divide what remains into $2\times 2$ squares. Since $n$ is odd you will have an even number of them...

$\endgroup$
0
$\begingroup$

The chessboard has a hamiltonian path, you can use it to extract a tiling.

example of the hamiltonion path for a $5\times 5$ version.

$ \begin{array}{|c|c|c|c|c|} \hline X & 1 & 2 & 3 & 4 \\ \hline 21 & 20 & 13 & 12 & 5 \\ \hline 22 & 19 & 14 & 11 & 6 \\ \hline 23 & 18 & 15 & 10 & 7 \\ \hline 24 & 17 & 16 & 9 & 8 \\ \hline \end{array} $

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.