I have a question about a mathematical riddle which I already solved but still looking for a shorter/simpler solution:
Following problem: We consider a standard $8 \times 8$ chessboard and we cover it (completely!) with dominos of size $2 \times 1$ (therefore every domino tile cover exactly $2$ fields).
The question is if we can find a cover such that there doesn't exist a $2 \times 2$ subsquare which is covered exactly by two domino tiles or in other words in the cover there don't occure two "direct" neighbour domino tiles from following shape:
I have it already solved in following way: I claim that such covering isn't possible.
Argue via contradiction: Assume that it's possible. Consider the $2 \times 2$ squares of the chess board and consider the partial cover of directly neighboured $2 \times 2$ squares. If a cover as above really exist then up to symmetry on the common edge of the two neighboured squares there could only occure two following cases (here only the vertical pairs; horizontally: analogous):
-
The two neighboured squares share a common domino tile (the orange one)
-
they don't share any domino tile on the common edge
Now there are exactly $24$ such pairings between neighboured $2 \times 2$ squares (note we don't consider the diagonal neighbour pairs).
Now we count all domino tiles in following way:
-each pair of neighbour squares which share a unique common domino tile contribute a $1$ (the orange one)
-each pair of neighbour squares don't share a common domino tile contribute a $1$ with the unique tile beeing fully contained in only one square and intersecting the common edge (the grey one).
That's all. But then we get only $24$ tiles althought there are $32$. Contradiction.
I guess this argument works but I think that it's too cumbersome. Does anybody have an easier / not too circumstaneous way to show it?
Best Answer
How about this:
Let's number the rows $1$ through $8$ from top to bottom, and the columns $1$ through $8$ from left to right. Cell $(x,y)$ means the cell in row $x$ and column $y$
You need a tile to cover cell $(1,1)$.This can be done in two ways, but by symmetry, we only have to consider one of these, so let's consider placing it horizontally, i.e. cover cells $(1,1)$ and $(1,2)$:
Now we need to cover cell $(2,1)$. In order to avoid making a $2\times 2$ subsquare made up of two tiles, there is only way way to place a tile under it, so that will cover cells $(2,1)$ and $(3,1)$:
Now we need to cover $(2,2)$. Again, there is only way way to do this in order to avoid making a $2\times 2$ subsquare made up of two tiles: cover cells $(2,2)$ and $(2,3)$.
OK, and now keep placing tiles along this basic 'diagonal' of the chess-board: you'll find all the placements are forced if you want to avoid a $2\times 2$ subsquare made up of two tiles. But, at the end of the diagonal, you end up having to use one tile to cover $(7,6)$ and $(8,6)$, and another one to cover $(7,7)$ and $(7,8)$:
... and now you are forced to also place one on $(8,7)$ and $(8,8)$, and get a $2\times 2$ subsquare made up of two tiles. (also note that the two parts of the board as of yet uncovered each have an odd number of squares left, so they can no longer be completely covered)
So, it is indeed impossible to do a complete tiling without getting a $2\times 2$ subsquare made up of two tiles.