An $8 \times 8$ grid is covered with 32 dominoes (each square on a
domino equals one square in the grid). Show that the number of
dominoes lying horizontally is an even number.
Hint: Color all the squares in every other column black. How many black squares cover a vertical domino? Are the number of black squares covered by vertical tiles together an even or an odd number? How many black squares cover a horizontal tile? Can the number of horizontal tiles be an odd number?
My answer is:
Let the number of squares in the $x$ direction be $8$, and let the number of squares in the $y$ direction be $8$. Let every other column be colored black, thus $4$ columns are colored black. For each black column, we can arrange $\frac{8}{2}=4$ vertical dominoes, which is an even number. For this specific case, we then obtain the total number of black squares covered by vertical tiles to be $8\times4=32$, which is also an even number. For the horizontal dominoes, we have the following: Every horizontal domino covers one black square. Since we have the total number of black squares being 32, the remaining maximum number of horizontal dominoes is $\frac{32}{2}=16$, which is an even number. But since one can not place any horizontal dominoes on the board if all the black squares are covered by vertical ones, then the maximum number of dominoes lying horizontally is $16$, which is an even number.
But unfortunately, this is not correct. Any hints?
Thanks
Best Answer
Colour the entire 1st, 3rd, 5th and 7th rows of the board black and the others white. Clearly, every domino lying horizontally covers $2$ squares of the same colour and every domino lying vertically covers $1$ black square and $1$ white square. Now, suppose there are $x$ dominoes lying horizontally along the black rows and $y$ dominoes lying horizontally along the white rows. Then, the number of black squares is
$$ 2x+0y+1(32-x-y)=32 \\ x+32-y=32 \\ x=y $$
Hence, the total number of dominoes lying horizontal is $x+y=2x$ is even.