8
$\begingroup$

Mary has a box with special $2\times1$ dominoes. Each dominoe has two red corners and two blue corners, and these dominoes come in two different types: The first type has the lower left and the upper right corner in red, while the second type has the upper left and the lower right corner in red. In other words, the second type is the mirror image of the first type. The box contains $20$ dominoes of the first type and $12$ dominoes of the second type.

Question: Is it possible to tile a standard $8\times8$ chessboard with Mary's dominoes, so that no red dominoe corner touches any red corner of another dominoe?

(The dominoes may be rotated in the tiling, but they must not be flipped over. Two dominoe corners may touch horizontally, vertically, or diagonally.)

$\endgroup$
  • $\begingroup$ That would be a lot of cases to consider... $\endgroup$ – the4seasons Mar 22 '15 at 14:21
  • $\begingroup$ You're talking about a chessboard but tagging with [checkerboard] $\endgroup$ – Marco Bonelli Mar 22 '15 at 14:40
9
$\begingroup$

Yes, it is possible. One configuration is as follows. The 20 horizontally oriented are all of one type; the 12 lowercase dominos are the other type. With these orientations, all upper-left and lower-right corners (in absolute terms) are red, and all lower-left and upper-right corners are blue. Also, there are no four-corners intersections in the configuration; so a lower-left corner can never touch an upper-right corner, not a lower-right an upper-left. This ensures that no two corners of the same colour touch.

 ___ ___ ___ ___
|___|___|___|___|
| |___|___|___| |
|_| |___|___| |_|
| |_| |___| |_| |
|_| |_|___|_| |_|
| |_|___|___|_| |
|_|___|___|___|_|
|___|___|___|___|

I suspect this is the only possible solution. I can’t quite show that, but I can show: in any suitable arrangement, all the dominos of one type must be vertical, and all those of the other type horizontal, or equivalently, all the UL and BR corners in the arrangement must be one colour, all the UR and BL corners another colour. (Proof: if not, look for the upper-most left-most domino whose UL corner is not the same as the UL corner of the whole board. What could happen around the UL corner of this domino? There are no valid possibilities.)

Now that this is fixed, an arrangement will have no clashing corner colours precisely if it has no “four-corners” intersections.

$\endgroup$
  • $\begingroup$ This ASCII picture doesn't show which dominos are of one type and which of the other. $\endgroup$ – leoll2 Mar 22 '15 at 14:52
  • 1
    $\begingroup$ @leoll2: yes, I left that to the text — I couldn’t think of a nice way to show it in the ascii diagram. $\endgroup$ – Peter LeFanu Lumsdaine Mar 22 '15 at 14:59
  • 1
    $\begingroup$ Are you sure this ASCII art is right? It doesn't seem to be tall enough. $\endgroup$ – user2357112 supports Monica Mar 22 '15 at 22:44
  • $\begingroup$ @user2357112: oops, thanks, yes — bottom row was missing! Fixed. $\endgroup$ – Peter LeFanu Lumsdaine Mar 23 '15 at 3:21
8
$\begingroup$

Here's an ugly paint drawing of a working pattern. enter image description here

$\endgroup$
  • $\begingroup$ Ugly? Much prettier than my ASCII-art version! $\endgroup$ – Peter LeFanu Lumsdaine Mar 22 '15 at 14:56

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.