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:

enter image description here

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):

enter image description here

  1. The two neighboured squares share a common domino tile (the orange one)

  2. 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?

  • 2
    $\begingroup$ This is part of an ongoing contest! (Bundeswettbewerb Mathematik) $\endgroup$ – Hagen von Eitzen Dec 26 '18 at 19:44
  • $\begingroup$ @HagenvonEitzen: Hi, sorry, I wasn't conscious about it. I just accidentally encountered encountered this problem made me curious. Generally, I would suggest to delete the question but I think that it would not be ok towards the author or the excellent answer below. $\endgroup$ – KarlPeter Dec 26 '18 at 21:32
  • $\begingroup$ This problem has the same answer (very similar to the accepted answer) for whatever rectangle size board. $\endgroup$ – Santropedro Apr 18 at 3:17

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)$:

enter image description here

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)$:

enter image description here

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)$.

enter image description here

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)$:

enter image description here

... 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.


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.