2
$\begingroup$

Fifteen $2 \times 1$ dominoes can be used to tile a $5 \times 6$ rectangle. In tiling the rectangle we might generate what are known as fault-lines. A fault-line is any horizontal or vertical line that divides a tiling, without cutting through any of the domino pieces, so as to form a tiling consisting of two sub-rectangular tilings. A fault-free tiling is thus one that has no such fault-lines.

One example of a fault-free $2 \times 1$ domino tiling on a $5 \times 6$ rectangle is shown below. shown below

My question is:

How many different fault-free $2 \times 1$ domino tilings of a $5 \times 6$ rectangle are possible? Here rotations and reflections are not considered to be different.

So far I have managed to find 2 (Edit: not 3 as I initially thought) different fault-free tilings using trial-and-error but honestly have no idea how one ought to proceed in general.

$\endgroup$
4
$\begingroup$

I enumerated all $1183$ tilings (not considering symmetry, and not necessarily fault-free). Of those only $6$ were fault-free, and these are in two symmetry classes.

enter image description here

enter image description here

What's your third one?

$\endgroup$
  • 1
    $\begingroup$ What did you use to enumerate the tilings? $\endgroup$ – DanielV Mar 21 at 19:08
  • $\begingroup$ I have just realised what I initially thought to be a third different arrangement is just a rotation of one of the other two I found. $\endgroup$ – omegadot Mar 22 at 1:15
  • $\begingroup$ @DanielV I wrote a program in Maple. $\endgroup$ – Robert Israel Mar 22 at 3:23
4
$\begingroup$

For each of the four horizontal grid lines passing through the interior, there certainly needs to be a domino crossing that line. In fact, there must be at least two such dominoes, because having exactly one domino is impossible for parity reasons (why?).

Similarly, of the five vertical interior grid lines, the leftmost, middle and rightmost need one domino across them, and the other two need two dominoes crossing them. Since there are only $15$ dominoes to go around, and the number of required dominoes on each of these grid lines adds to $4\cdot 2+3\cdot 1+2\cdot 2=15$, the requirements are met exactly.

This gives you a starting point for how to place the dominoes, as each line has one or two distinguished dominos which must cross it. Start with the unique dominos crossing the outer vertical lines; these can a priori go in one of five places each, but a little thought shows that they only have three possibilities each, and in fact you can rule out $2$ of the $3\times 3$ possibilities. You may find that many dominoes afterwards are forced... or maybe more insight is required to make this countable by a human.

Edit: I also made a program which loops through all domino tilings of the $5\times 6$ board (using Knuth's Algorithm X) and checks to see if they are fault free. Only $6$ are fault free, and they fall in two symmetry classes.

╺━╸ ╻ ╺━╸ ╻
╻ ╻ ╹ ╺━╸ ╹
╹ ╹ ╺━╸ ╻ ╻
╻ ╺━╸ ╻ ╹ ╹
╹ ╺━╸ ╹ ╺━╸

 ╻ ╺━╸ ╻ ╺━╸
 ╹ ╺━╸ ╹ ╻ ╻
 ╻ ╻ ╺━╸ ╹ ╹
 ╹ ╹ ╻ ╺━╸ ╻
 ╺━╸ ╹ ╺━╸ ╹

╻ ╺━╸ ╺━╸ ╻
╹ ╺━╸ ╻ ╻ ╹
╺━╸ ╻ ╹ ╹ ╻
╻ ╻ ╹ ╺━╸ ╹
╹ ╹ ╺━╸ ╺━╸

 ╻ ╺━╸ ╺━╸ ╻
 ╹ ╻ ╻ ╺━╸ ╹
 ╻ ╹ ╹ ╻ ╺━╸
 ╹ ╺━╸ ╹ ╻ ╻
 ╺━╸ ╺━╸ ╹ ╹

 ╺━╸ ╺━╸ ╻ ╻
 ╻ ╺━╸ ╻ ╹ ╹
 ╹ ╻ ╻ ╹ ╺━╸
 ╻ ╹ ╹ ╺━╸ ╻
 ╹ ╺━╸ ╺━╸ ╹

 ╻ ╻ ╺━╸ ╺━╸
 ╹ ╹ ╻ ╺━╸ ╻
 ╺━╸ ╹ ╻ ╻ ╹
 ╻ ╺━╸ ╹ ╹ ╻
 ╹ ╺━╸ ╺━╸ ╹
$\endgroup$

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.