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?
Answer
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
No comments:
Post a Comment