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?
