Ken's POTW 040416

Dominos One-by-One

0-4 0-3 0-2 0-1 0-0
1-4 1-3 1-2 1-1
2-4 2-3 2-2
3-4 3-3
4-4

Into a 4x4 grid, place the 15 dominos in this manner: Place one domino in the grid, one digit per square. Place the second domino by overlapping the first by a matching square (the squares that overlap must have the same digit.) Place each successive domino in the same way, overlapping one square and filling an empty square until all 16 squares are filled.

Extension: Is it possible to make this a magic square as well?

Source: Puzzle 09 from the 2003 Puzzle Design Tournament at http://www.otuzoyun.com/puzzledesign/

Solutions were received from Joseph DeVincentis and Alan O'Donnell. Both suggested making a single chain of the dominos and just wrapping it in. Joseph found that a complete magic square couldn't be made in this fashion. [I'm wondering if one could be made if the structure weren't based upon a chain. - KD] Joseph's solution follows.

It is very easy to do this; there are many, many ways. All you need to do is line up all the dominoes end to end, with touching numbers matching, then collapse the row by overlapping touching numbers, and take the resulting string and twist it into the grid in any one of the many possible ways. Since there are 6 occurrences of each number, each number will appear three times in the grid, except the one which starts and ends the sequence (which must be the same) which will appear four times. As an example:

0-0 0-1 1-1 1-2 2-2 2-3 3-3 3-4 4-4 4-0 0-2 2-4 4-1 1-3 3-0

collapse to 0-0-1-1-2-2-3-3-4-4-0-2-4-1-3-0

place in grid (in this case, back and forth across the rows):

Extension: Is it possible to make this a magic square as well?

Since each number appears three times in the grid, plus the end number an extra time, the sum of all the numbers is 3*(1+2+3+4)+n = 30+n where n is the end number. This must be divisible by 4 in a magic square so n must be 2, and the magic sum is 8.

Now we must have the 4-4 somewhere in the grid. This must lie in some row or column, and the other two numbers in that row or column must be 0s. They don't have to be the 0-0 domino, but if they are not, then there is a 0-0 domino somewhere else in the grid which requires two unattached 4s in the row with it. Likewise there is a 4-3 next to 0-1 somewhere.

If these two lines are parallel, then this accounts for all three 4s and all three 0s which can appear in the grid. The other two lines have four 2s, two 3s, and two 1s, and they can appear either with all four 2s in one line, or two 2s, a 3, and a 1 in each line. In the crossing rows, then, the 4-3 must lie in the rows with the 0-0, because otherwise you have 4+3 or 4+4 together in a row which must take two more digits each at least 1. So we end up with 03, 04, 40, 41 contributed to the crossing rows from our first two lines, and the remaining lines must therefore give respectively 23, 22 and 31 in some order, and 12. So the four 2s in a line is impossible, and we must have some permutation of the rows and columns of the following grid:

Note that this means we also have a 4-3-1-0 row crossing the 4-4-0-0. Ignore this for now. But remember that each domino must appear somewhere as an adjacent pair. Since none of the columns have 3-3 or 1-1 in them, we must put these numbers together in the rows. This means we have to have the 3-4-0-1 column between the two 2-2-3-1 columns.

This is a possible solution if we only care about rows and columns. The dominoes can be laid down as follows:

0-3-3-2
|
0 1-4-3
| |   |
4 2 1-1
| | |
4-2 0-2

However, we have a problem making the diagonals work. Each diagonal must contain one digit from each of the 4-4-0-0 and 3-4-0-1 columns, plus two other digits, just like with the rows, so to make them add to 8 requires each diagonal to get one 3 or 4 and one 0 or 1. But since this relationship must also be maintained in the rows, it means we have to split the 0-0 and 4-4 apart, like so:

With the 4s and the 0s forced apart both by rows and by columns, this is impossible.

Alternatively, we can have the 4-4-0-0 and 4-3-1-0 rows cross. Of course, we had such rows crossing above, but now let's consider a case with such crossing rows which does not also have a 4-3-1-0 row parallel to the 4-4-0-0.

This means that one 4 or one 0 will be elsewhere in the grid. But note that the puzzle is 4's-complement symmetric. If you replace every number with 4 minus the number, you still get a solution. So WLOG, let the intersection be at a 4, and thus a 4 appears elsewhere in the grid.

If we put it in a row or column with another 4 or 3, we need a 0 to finish the column and we have none left. So it goes in a line crossing a 0 of 4-4-0-0 (either 4-2-2-0 or another 4-3-0-1 line), and in a line crossing the 0 or 1 or 4-3-1-0 (making either a 4-2-1-1 or 4-2-2-0 line; another 4-3-1-0 in this direction gives the case we already examined).

A second 4-3-0-1 line crossing 4-4-0-0 at a 0 is impossible because of the line crossing the other 0. Since it has no 4, but must add to 8, it must contain 0-2-3-3 in some order. This requires two threes, so we cannot have two other lines in the same direction which both contain a 3. So we must have a 4-2-2-0 line crossing the 4-4-0-0 at a 0.

Putting this 4 on two 4-2-2-0 lines means that all the 2s are occupied in these lines. The unplaced digits are two 1s and two 3s. But now consider the other two lines crossing the 4-3-1-0. Each has a 2, and one has a 3 while the other has a 1. We need to put a total of 3 in one line, and 5 in the other. But with two more digits each either 1 or 3 in each of these lines, this is impossible.

So we have some permutation of this, with 1, 2, 3, 3 in the xs.

0224
0xx2
4xx1
4301

But there are two 0xx2 lines here which must be 0-3-3-2. We don't have enough 3s, so this case is impossible. A 4-3-1-0 row parallel to the 4-4-0-0 is required and leads to the case already described above. So the best we can do is a semi-magic square without magic diagonals.

Mail to Ken