13
$\begingroup$

Here's a shape that could be tiled by dominoes. Without the fault line there are 64 tilings. With fault line how many possible tilings are there?

     _ _
   _|  _|_
 _|  _|   |_
|   |       |
|_ _|      _|
  |_     _|
    |_ _|
$\endgroup$
  • $\begingroup$ this is my first time posting a problem on here... $\endgroup$ – john mangual Apr 18 '18 at 19:54
7
$\begingroup$

the answer is

16

There are mendatory dominoes with the line :

           _ _
         _|_ _|_
       _|_ _|   |_
      |   |       |
      |_ _|_     _|
        |_ _|_ _|
          |_ _|
 
This leave 2 parts to tile. the left square has 2 possibilities, the right one is a little bite more complicated.
An easy way to do it to group the tiling by count of vertical dominoes among the 6 :

0 vertical -> 1 tiling
   _ _
 _|_ _|_
|_ _|_ _|
|_ _|_ _|
  |_ _|
2 vertical-> 3 tilings (they always are in the middle column)
   _ _       _ _       _ _
 _|_ _|_   _|_ _|_   _|_ _|_
| | |_ _| | |_ _| | |_ _| | | 
|_|_|_ _| |_|_ _|_| |_ _|_|_|
  |_ _|     |_ _|     |_ _| 
 
4 vertical -> 3 tilings
   _ _       _ _       _ _
 _|_ _|_   _| | |_   _|_ _|_
| | | | | | |_|_| | | |_ _| | 
|_|_|_|_| |_|_ _|_| |_| | |_|
  |_ _|     |_ _|     |_|_|
  
6 vertical -> 1 tiling
   _ _ 
 _| | |_ 
| |_|_| |
|_| | |_| 
  |_|_|
This gives 8 tilings for the right part.
The two part are independant so there is a total of 16 tilings for the cross.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ i like how you drew each tiling $\endgroup$ – john mangual Apr 21 '18 at 12:37
10
$\begingroup$

I count:

16

reasoning:

4 tiles in the original are forced (a square w/ 3 edges has only 1 place to extend a domino into), leaving 2 mutually exclusive subgraphs.

         _ _
       _|_ _|_
     _|_ _|a c|_
    |   |e b d g|
    |_ _|f     h|
      |_ _|_ _|
        |_ _|

The left area clearly has 2 subgraphs.

The right area: Based on placing on labeled squares ab, you force dominoes cd ef and gh. Filling in the remaining gives 2 unique tilings, which becomes 6 after you take into account reflections/rotations of the starting position. 2 more tilings are obtained by having the inital placement not present, which forces dominoes onto ac, ef, gh, and the bottom 2 squares which leaves another 2x2 square which has 2 tilings, giving a total of 6+2=8 graphs on the right section.

mutually exclusive -> multiply the results ->2x8=16

| improve this answer | |
$\endgroup$
4
$\begingroup$

The top left part can be tiled in

2 ways; the top two dominoes are fixed and you have 2 options for the bottom 2x2 square.

Near the bottom, we have

a single tile which is left-most; this determines the position of two horizontal dominoes.

We're left with

a 12-tile shape in the form of a plus. If the top two tiles are covered by one horizontal domino, and the bottom two as well, there are five options for the remaining 4x2 rectangle (4 where the rectangle is split in half, 1 where it isn't). If the bottom one is done by two vertical dominoes, the rest is fixed, so that's one other option. If the top two tiles are covered by two vertical dominoes, we have two options depending on whether the bottom two tiles are covered by one or two dominoes. So that makes eight total.

Multiplying the independent shapes, we see that there are

16 total possibilities.

| improve this answer | |
$\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.