6
$\begingroup$

We have a 5x5 grid:

5x5 Grid

We also have some dominoes, 1 of each type with numbers 1 to 6 on each side. So we have the dominoes

1 | 1
1 | 22 | 2
1 | 32 | 33 | 3
1 | 42 | 43 | 44 | 4
1 | 52 | 53 | 54 | 55 | 5
1 | 62 | 63 | 64 | 65 | 66 | 6

How many ways are there to place the dominoes so

A: There are 7 spaces left uncovered and
B: No domino touches a number adjacent to it in the number line, or touches its own number?

Clarifications:

  • Not all dominoes have to be used
  • The dominoes must be in the grid
  • There seems some confusion about the 'touching dominoes' part. I'll make it clearer:

1 | 35 | 4 Fine

1 | 33 | 1 Not Fine

And another example:

2 | 31 | 3 Fine

1 | 34 | 3 Not fine

And if they're on top of each other:

2 | 3
4 | 1 Fine

3 | 2
4 | 1 Not Fine

I hope this makes sense. I would also advice using a computer here

$\endgroup$
  • 1
    $\begingroup$ How are you putting 21 dominoes into 25 squares and leaving 7 spaces uncovered? $\endgroup$ – f'' Apr 29 '16 at 19:13
  • 3
    $\begingroup$ Do you know that there's a "nice" solution to this? If not, this would be best solved by computer. $\endgroup$ – Deusovi Apr 29 '16 at 20:37
  • 2
    $\begingroup$ For your [1|3][2|3] example, wouldn't 3 being adjacent to 2 on the number line make this not fine? Or have I misunderstood what you meant by that? $\endgroup$ – Zandar Apr 30 '16 at 8:18
  • 6
    $\begingroup$ I'm currently running a program that enumerates all possible solutions. It's currently at over 50 million, and it hasn't even started placing any dominoes vertically (they're all horizontal). In fact, every one of the solutions so far has [1|1] in the top-left corner and [1|2] in the top-right corner. I suspect that the number of solutions is in the billions. $\endgroup$ – GentlePurpleRain Jul 15 '16 at 15:27
  • 2
    $\begingroup$ I realized I never followed up on my last comment. My program got to around 50 billion before I shut it down, and it wasn't even close to complete. The are literally trillions of solutions. To my mind, that makes this a very poor question, since there's no hope of solving it by hand, and all you're asking for is someone to write a computer program to answer your question. There is no puzzle involved here. $\endgroup$ – GentlePurpleRain Sep 2 '16 at 22:39
3
$\begingroup$

How many ways are there to place the dominoes?

Too many.

It is close to, and likely over, 1.232 * 10^16, or 12.3 Quadrillion for 9 dominoes.

I thought we should get an approximate bound on the size of this question. I set up a program to run a few calculations.

First I am going to cover physical locations of the dominoes, not their faces.

We are leaving 7 spaces uncovered, so we are only placing 9 dominoes on the board.

But, how many ways can we place the dominoes on a 5x5 board? For the first domino the are 40 pairs of tiles it could cover (20 horizontal and 20 vertical).

I had hoped to do this mathematically, unfortunately the options for the subsequent dominoes varies by the position of the first. If the first is placed in the corner of the board, the second has 36 possibilities. If it placed adjacent and parallel to a board edge, 35. Adjacent and perpendicular gives 34, and not adjacent to any edge gives 33. So I got a program to run some calculations.

The first number is how many dominoes you are placing, the second is the total number of ways to place the dominoes:

     1 40
     2 1,372
     3 39,792
     4 959,496
     5 18,840,000
     6 293,486,400
     7 3,507,073,920
     8 30,731,097,600
     9 185,341,685,760

To help establish a bound we are going to look at the number of ways the faces could appear in a sample domino layout. This should give an approximation but will not give an exact answer as some layouts will likely have a different number of possibilities.

      1 1 2 2 9
      3 3 4 4 9
      5 5 6 6 0
      7 7 8 8 0
      0 0 0 0 0

Here the numbers are used to identify the distinct dominoes. How many ways can dominoes in these positions appear? The first domino has 36 options (6 options where the domino is a double, 15 options where it has the smaller number on the left, and 15 options where it has the smaller number on the right).

A second program was set to run with the specific restrictions of this puzzle.

      1 36
      2 1,040
      3 37,440
      4 258,880
      5 2,210,388
      6 21,445,228
      7 242,916,980
      8 2,235,646,272
      9 24,113,835,232

An astute reader may have noticed that both my calculations included some overlap. The both are allowing for all the permutations. Dividing my first results by nPn (to prevent counting of permutations in both results) gives:

     1  40
     2  686
     3  6632
     4  39979
     5  157000
     6  407620
     7  695848
     8  762180
     9  510752

And now multiplying the previous two results together gives:

     1  1,440
     2  713,440
     3  248,302,080
     4  1.035 * 10^10
     5  3.470 * 10^11
     6  8.742 * 10^12
     7  1.690 * 10^14
     8  1.704 * 10^15
     9  1.232 * 10^16

But this is all based on the representive domino layout shown previously. Using this alternative layout, where the dominoes are separated into two 'islands':

      1 1 2 2 9
      3 3 4 4 9
      0 0 0 0 0
      5 5 6 6 0
      7 7 8 8 0

Gives 6.24 * 10^10 ways of having the dominoes, and gives a larger final value of 3.19 * 10^16. If someone can establish, definitively, the most and least complex domino layouts, these could be used to establish a proper bound on the number of possibilities.

$\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.