Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

What's the maximal number of dominos (2x1 tiles) that can be placed on a checkerboard (8x8 square) so that every domino covers exactly 2 squares of the checkerboard and no two dominos form a 2x2 square?

share|improve this question
up vote 30 down vote accepted

Looks like:

  31 dominos can be placed  


Thanks to @Gamow's comment, this number's maximality can be proved by self-contradiction of the assumption that it is not maximal. Any more dominos would cover all 64 squares.

Assumption to be disproved: All squares can be covered with dominos.

   A. As the top left corner must be covered, start with a horizontal domino there. (Every other possible corner domino is equivalent to this by rotation and reflection.) From here on:

Successive placements of a diagonal series of dominos are forced to form a descending herringbone staircase in order to prevent a 2x2 square from being formed in combination with each previous domino.
B. The domino that neighbors A along the left edge must be vertical.
C. The inside corner formed by A and B must be covered by a horizontal domino.
D −  M. Likewise, until a horizontal domino-shaped hole at the bottom right corner, if filled, would form a 2x2 square with M.

Therefore the top left corner cannot be covered, which negates the assumption and proves that a 32-domino solution is impossible.


Further reading, courtesy of @Fimpellizieri's comment:
Conway's Tiling Groups PDF [and height functions] – W. P. Thurston
Tiling with Polyominoes and Combinatorial Group Theory PDF – J. H. Conway & J. C. Lagarias
Domino Tilings of the Torus PDF [and the plane] Abstract – F. de Souza Lima Impellizieri

share|improve this answer
4  
I think that 31 cannot be beaten: Suppose that there is a solution with 32, and consider the domino in the upper left corner. Then the position of the two dominoes directly below it is enforced. You may continue like this, and argue that there is a staircase going towards the lower right corner. In the very end, you generate a 2x2 square. Contradiction. – Gamow Feb 23 at 12:32
    
Posted an answer with this and then saw your comments. Mine doesn't have very nice graphics, so I've deleted it to let one of you make a prettier one. – Trenin Feb 23 at 12:57
2  
@Gamow This is correct! My MSc dissertation is on domino tilings of the torus. In fact, any two distinct tilings of a finite simply-connected planar region can be joined by a sequence of flips, where a flip is a move that exchanges two dominos forming a $2\times 2$ square by the only other configuration. In particular, if a simply-connected planar region admits more than one domino tiling (and the checkerboard admits many of them), than each of its tilings necessarily admits a flip (and thus contains a tiled $2 \times 2$ square). – Fimpellizieri Feb 23 at 21:50
1  
If you're into domino tilings, you can learn some more about height functions (introduced by Thurston here). Coincidentally, with the missing domino the tiling you chose is the 'highest' (or 'lowest'). I'll shamelessly plug my MSc dissertation here: it's on domino tilings of the torus, but it also discusses the planar case. For more general tilings, Conway wrote a nice paper involving group theory here. – Fimpellizieri Feb 23 at 22:11
1  
Thanks again, @Gamow, laying out your proof with pictures was more satisfying than the solution – humn Feb 23 at 22:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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