Ken's POTW


Triominos
      A-----B-----C
     / \   / \   / \
    /   \ /   \ /   \
   D-----E-----F-----G
  / \   / \   / \   / \
 /   \ /   \ /   \ /   \
H-----I-----J-----K-----L
 \   / \   / \   / \   /
  \ /   \ /   \ /   \ /
   M-----N-----O-----P
    \   / \   / \   /
     \ /   \ /   \ /
      Q-----R-----S
Take a set of 24 triominos (dominos with three sides, a number at each corner), consisting of all possible configurations of the values 0, 1, 2, and 3, and place them into a hexagon, two units on a side, such that each adjacent side matches correctly. Or, show why it can't be done.

(Note that 1-2-3 is a different triomino than 1-3-2, since neither can be rotated to create the other; while 1-1-2 would be the same as 1-2-1, since the latter can be rotated to obtain the former.)

Here is a list of the 24 triminos, numbered clockwise:
a. 0-0-0b. 0-0-1c. 0-1-1d. 1-1-1e. 0-0-2f. 0-2-2
g. 2-2-2h. 0-0-3i. 0-3-3j. 3-3-3k. 1-1-2l. 1-2-2
m. 1-1-3n. 1-3-3o. 2-2-3p. 2-3-3q. 0-1-2r. 0-2-1
s. 0-1-3t. 0-3-1u. 0-2-3v. 0-3-2w. 1-2-3x. 1-3-2
If it is possible, send your solution as a labeled copy of the above diagram.

Source: Original.


I recevied the following solution from Philippe Fondanaiche, Paris, France. It agrees with my own solution (below) that the triominos can't be placed. (I'll admit that I don't completely understand his solution, but I get the idea.) The next question, of course, is how close can you get, and I try to address that in my solution. Correct answers were also received from Yaacov Yoseph Weiss and from Kirk Bresniker, who wrote a computer program to exhaust all of the possibilities after a logical determination of a few locations.
>From Philippe Fondanaiche Paris France

Triominos

I think that it is not possible to place the 24 triominos into the hexagon.

24 triominos with 3 digits for each of them represent a total number of 72
digits. We can easily check that each of the digit 0,1,2 and 3 appears 18
times.
For all the letters A,B,C,D... as mentioned in the hexagon, we calculate the
number of triominos starting from each of them. So we obtain the following
chart:
        
                           2       3      2
                       3       6       6      3
                    2      6       6      6      2
                       3       6       6      3
                            2       3      2

We observe that the index 2 appears 6 times, the index 3 appears 6 times too
and the index 6 appears 7 times and we verify that 2x6 + 3x6 + 6x7 = 72 which
 is the total number of digits above mentioned.

For each digit i = 0,1,2,3 let consider the numbers:
     a(i) = how many times i is on a letter with the index 2
     b(i) = how many times i is on a letter with the index 3
     c(i) = how many times i is on a letter with the index 6

We have the following relations:
  2xa(i) + 3xb(i) + 6xc(i) = 18 whatever i = 0,1,2,3
  sum [a(i)] = 6
  sum [b(i)] = 6
  sum [c(i)] = 7

>From the first identity,we infer thatwhatever i a(i) is a multiple of 3 and
b(i) is even.
As it is impossible to have one digit with the same index 2, we infer from
the second identity that there are necessarily 2 digits and 2 only with the
index 2. For example i = 0 and i = 1.
Therefore 3xb(0) + 6xc(0) = 12 or b(0) + 2xc(0) = 4.
We can check that b(0) = 2 is the one solution with b(i) even.If not with
b(0) = 0 or b(0) = 4 ,it is impossible to set a triomino with the 3 same
digits.So c(0) = 1.
Same solutions for i = 1.

Concerning the digits 2 and 3, we have the following identities:
b(2) + b(3) = 2
c(2) + c(3) = 5
3xb(2) + 6xc(2) = 18 or b(2) + 2xc(2) = 6
3xb(3) + 6xc(3) = 18 or b(3) + 2xc(3) = 6
There is one solution of this set of equations excluding the symmetry between
2 and 3:
b(2) = 2     b(3) = 0     c(2) = 2     c(3) = 3

Hence we have the following sheet:

        digit   I    0           1           2            3
________________I__________________________________________
index    2      I    3           3
index    3      I    2           2           2
index    6      I    1           1           2            3

Starting from the digit 3 placed for example on E,F,J and from the digit 2
placed on N,O,R , we have to place the triomino 0,0,0 on K,L,P and the
triomino 1,1,1 on D,H,I or H,I,M .Quickly we observe that it is impossible to
place the remaining digits 0 and 1. Same observation if 2,2,2 is on K,L,P and
so on .....

Best regards. 

Ken's solution:
      A-----B-----C
     / \   / \   / \
    /   \ /   \ /   \
   D-----E-----F-----G
  / \   / \   / \   / \
 /   \ /   \ /   \ /   \
H-----I-----J-----K-----L
 \   / \   / \   / \   /
  \ /   \ /   \ /   \ /
   M-----N-----O-----P
    \   / \   / \   /
     \ /   \ /   \ /
      Q-----R-----S

For each digit (0-3), there are 13 triominos that contain that digit. The controlling pieces to place are the trios (0-0-0, 1-1-1, 2-2-2, 3-3-3), and there are only three different places for each piece, after symmetry.

If a trio (say 0-0-0) is placed in AEB, then 7 of the 13 triominos must be placed around those vertices, including two of the duos (001, 002, or 003). Another 6 triominos must be placed with that digit (0) elsewhere in the hexagon, with no 0 in adjacent locations. In other words, no 0 may be placed in C, F, J, I, D.

Aside: Why Not Adjacent? Quickly inspect what would exist if any of the adjacent locations held the same digit (0) as the trio. Either a new trio would be formed (but only one can exist) or a diamond would be formed, with three identical digits on one long edge, all next to one remaining digit. This effectively makes the two triominos in that diamond identical. Therefore, the remaining digits must not be adjacent to the first ones.

If a trio is placed in BEF, then 10 of the 13 triominos must be placed around these vertices, including all duos, and the remaining 3 must be placed elsewhere in the hexagon. Again, no 0 can be in A, D, I, J, K, G, or C.

This exercise was simply to show that one trio MUST have a vertex on the center point, J. Any trio on the edge forces all identical digits away from that point, so at least one trio must occupy that point.

      A-----1-----C
     / \   / \   / \
    /   \ /   \ /   \
   D-----0-----0-----G
    \   / \   / \   /  
     \ /   \ /   \ /    
      3-----0-----2
       \   / \   /
        \ /   \ /
         N-----O
A trio in the center forces all 13 triominos with that digit to be placed around the trio (12 triangles border on each center triangle.) With 000 as the trio, the three duos (001, 002, 003) must be placed adjacent to the trio.

Next consider the 011 triomino. If N=O=1, then 013 is placed, and C must be 2. To place the 033 triomino, D must be 3, but then there is no spot for 022. So 011 in not in JON. It must be next to the existing 1, in EAB or FBC. Similarly, the 022 and 033 must be next to their respctive existing digits.

Placing 011 in the two possible locations leads to six possible completions of the diagram. Through rotation and substitution, these are equivalent to two unique solutions. Through mirror symmetry, these are also identical. The result is at the right.

This leaves three final configurations to try for the hexagon, one each for the three long sides being completed sides of the final hexagon. These three options are below, followed by their analyses.

      1-----1-----3
     / \   / \   / \
    /   \ /   \ /   \
   3-----0-----0-----2
    \   / \   / \   /
     \ /   \ /   \ /
      3-----0-----2
       \   / \   /
        \ /   \ /
         2-----1
      1-----1-----3
     / \   / \   / \
    /   \ /   \ /   \
   3-----0-----0-----2
  / \   / \   / \   / \
 /   \ /   \ /   \ /   \
H-----3-----0-----2-----L
 \   / \   / \   / \   /
  \ /   \ /   \ /   \ /
   M-----2-----1-----P
    \   / \   / \   /
     \ /   \ /   \ /
      Q-----R-----S

            |
            v
      A-----B-----C
     / \   / \   / \
    /   \ /   \ /   \
   1-----1-----3-----G
  / \   / \   / \   / \
 /   \ /   \ /   \ /   \
3-----0-----0-----2-----L
 \   / \   / \   / \   /
  \ /   \ /   \ /   \ /
   3-----0-----2-----P
    \   / \   / \   /
     \ /   \ /   \ /
      2-----1-----S

            |
            v
      A-----B-----C
     / \   / \   / \
    /   \ /   \ /   \
   D-----1-----1-----3
  / \   / \   / \   / \
 /   \ /   \ /   \ /   \
H-----3-----0-----0-----2
 \   / \   / \   / \   /
  \ /   \ /   \ /   \ /
   M-----3-----0-----2
    \   / \   / \   /
     \ /   \ /   \ /
      Q-----2-----1

            |
            v
H must be 3. S must be 1. M is either 1 or 2. Another duo (133 or 233) is still needed. Either (P=L=3 and R=1) or (Q=R=3 and P=1). Only the latter allows 222 to be placed, so Q=3, R=3, P=1, L=2.

Now, if M=1, 132 is duplicated and 223 is lost. If M=2, 223 is duplicated and 133 is lost. So this placement doesn't solve the problem, but gets as close as possible.

A must be 1. C must be 3. P must be 2. B is either 2 or 3. Another duo (112 or 113) is still needed, so S must be 1, and B must be 3.

G can't be 3 (333 is already placed) or 1 (133 is already placed) or 2 (LKG and LPK would be identical). So this hexagon also does not solve the problem.

In this diagram, there is no place to put the 222 triomino.
So there is no configuration that meets the requirements of the puzzle. The closest that can be found duplicates/omits a single triomino.


Mail to Ken