2
$\begingroup$

A standard set of double-six dominoes has 28 tiles with 2 numbers on each side from 0 to 6. Tiles can be placed next to each other if all the touching numbers match (from all 3 adjacent sides). Can you place all the 28 tiles into a 7x8 rectangle? If this is not possible, then what is the maximum number of tiles you can place within such a rectangle?

Good luck!

Improve this question
$\endgroup$
0

3 Answers 3

Reset to default
3
$\begingroup$

Here's my first attempt.

There are very few ways to fill a 2x2 square, and none of those can be extended to allow a 3x3 square to be filled completely. The only way to fill a 2x2 square that does not involve a double is to arrange 4 dominoes like a windmill. I have tried to do that as often as possible in this solution. It contains all non-doubles except for 0-3, so 20 dominoes and 16 empty squares.

  --- --- --- ------- --- --- --- 
 | . | . | 1 | 1   4 | . | . | 0 |
  -------|   |------- -------|   |
 | 6   5 | 5 | . | 4 | 4   6 | 6 |
  ------- -------|   |------- --- 
 | . | 5 | 5   0 | 0 | . | 6 | . |
  ---|   |------- -------|   |--- 
 | . | 4 | . | 0 | 0   1 | 1 | . |
  --- -------|   |------- ------- 
 | 4 | 4   2 | 2 | . | 1 | 1   2 |
 |   |------- -------|   |------- 
 | 3 | . | 2 | 2   3 | 3 | . | 2 |
  -------|   |------- -------|   |
 | 3   6 | 6 | . | . | 3   5 | 5 |
  ------- --- --- --- ------- ---

I have little doubt this can be improved by using doubles.

Edit:
I have now used a computer to find a better solution. The search was not exhaustive, but I suspect this is optimal.

This uses 23 dominos. The unused ones are: 1-6, 2-5, 3-3, 3-0, 4-0.

   ------- ------- ------- ---
  | 1   1 | 1   2 | 2   2 | 2 |
   ------- ------- -------|   |
  | 1 | . | 1 | . | 2 | . | 3 |
  |   |---|   |---|   |--- --- 
  | 3 | . | 4 | 4 | 4 | 4   3 |
   --- --- ---|   |--- ------- 
  | 3 | . | 4 | 4 | 4 | . | 3 |
  |   |---|   |---|   |---|   |
  | 5 | 5 | 5 | . | 6 | 6 | 6 |
   ---|   |-------|---|   |---|
  | 5 | 5 | 5   6 | 6 | 6 | 6 |
  |   |--- -------|   |---|   |
  | 1 | . | 5 | . | 0 | . | 2 |
   -------|   |------- -------|
  | 1   0 | 0 | 0   0 | 0   2 |
   ------- --- ------- -------

Edit 2:
I have now done an exhaustive computer search, and if my program is correct then this is an optimal solution.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Nice solution. I believe I can match it by using a few doubles. $\endgroup$
    – Dmitry Kamenetsky
    Oct 24, 2019 at 6:03
  • 1
    $\begingroup$ With minor adjustments you can fit the 5/5 in for 21 dominoes. I have solutions with 22 dominoes, trying for 23 before posting. $\endgroup$
    – Daniel Mathias
    Oct 24, 2019 at 21:26
  • 1
    $\begingroup$ @DanielMathias I have found a 23 piece solution with the help of a computer. $\endgroup$
    – Jaap Scherphuis
    Oct 24, 2019 at 23:33
  • $\begingroup$ Nice. That will save me the trouble of posting 22. I gave up the manual search, would have done the coding next and likely found the same 23. $\endgroup$
    – Daniel Mathias
    Oct 25, 2019 at 0:50
  • 1
    $\begingroup$ @DmitryKamenetsky: I can't find the program right now, but it was fairly straightforward search with back tracking. It just visits each cell of the board in left to right, top to bottom order. If the square is already full, it skips over it. If it's an empty square, it tries to place a valid domino horizontally to the right or vertically down, or else leaves it empty. For each of those possibilities it tries filling the rest of the board recursively, and when it's done all of them it backtracks to the previous square. To speed up the search I assumed the first number used was 1, second 2 etc. $\endgroup$
    – Jaap Scherphuis
    Nov 8, 2019 at 13:30
4
$\begingroup$

An answer for the first part of the question:

1. Note that all dominoes are different, so they cannot be placed long-edge-to-long-edge (since they must then have 2 pairs of numbers matched, which implies that both dominoes contain same pairs of numbers, but all our dominoes are different).
2. That means that the line segments which cut each domino in half (1x1 squares) cannot share a point (in which one segment begins and the other ends). From now, we proceed from placing the dominoes themselves to placing line segments which cuts them into 2 1x1 squares.
3. Such a line segment obviously cannot begin or end in a corner of the rectangle (since it would mean that a half of a domino is outside the rectangle).
4. For the same reason, such a line segment cannot connect two points at the edge.
5. We have 26 possible points (with integer coordinates, excluding the corners) on the edge to place these line segments (of length 1), and no 2 consecutive (including those which "surround" a corner) can be used, so the number of possible locations for placing these points on the edge is no more than 26/2 = 13.
6. On the other hand, we have 6x7=42 different possible locations to place the points inside the rectangle (all points having both integer coordinates).
7. So, the number of possible locations for placing points in which the segments begin and end is no more than 42+13=55.
8. But we have 28 dominoes to place, so the 28 segments must connect 28x2=56 different points. As we have only 55 locations to do so, that means that at least 2 segments will share a point, so placing 28 dominoes in a 7x8 rectangle which involves no long-edge-to-long-edge touching (and so, having all sides matching) is impossible.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ That's a really nice proof. I think it generalises to any size rectangle, and doesn't even require the set of dominoes to be complete (just no duplicates). $\endgroup$
    – Jaap Scherphuis
    Oct 24, 2019 at 10:02
  • 1
    $\begingroup$ @JaapScherphuis Probably yes. For an $m\times n$ rectangle, we get $(m-1)+(n-1)+(m-1)\times(n-1)=mn-1\leqslant mn$. With $m=8$ and $n=7$, we get this answer. $\endgroup$
    – trolley813
    Oct 24, 2019 at 10:37
1
$\begingroup$

This just answers one part: "Can you place all the tiles onto a 7x8 rectangle"

No because: At some point you need to place a double. Let's say it is 1-1. Let's look at filling a long edge of the 1-1 domino. If it's up against the edge, look at the other side of the domino. You have to put two '1' squares in there, and they can't both belong to dominoes perpendicular to the 1-1 because that would require them both to be another 1-1. So at least one of them is parallel to the 1-1, and because it has to match the domino adjacent to the short edge of the 1-1, it must also be a 1-1. So you simply can't build around any double without more of that double. Lots more.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.