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?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
8
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
-
4$\begingroup$ 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. $\endgroup$– GamowFeb 23, 2016 at 12:32
-
2$\begingroup$ @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). $\endgroup$ Feb 23, 2016 at 21:50
-
1$\begingroup$ 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. $\endgroup$ Feb 23, 2016 at 22:11
-
1$\begingroup$ Thanks again, @Gamow, laying out your proof with pictures was more satisfying than the solution $\endgroup$– humnFeb 23, 2016 at 22:31
-
1$\begingroup$ Which app did you use in order to make the pictures @humn? $\endgroup$ Jan 3, 2019 at 10:15