The Impossible Tetrahex Triangle: Torsten Sillke, FRA, May 1994
written up: Apr 1997
S. W. Golomb (and Martin Gardner as well) asked
in 'Polyominoes' 2nd Ed. (1994) on page 125 excercise 4:
Did anyone find a simpler proof of impossibility [of the triangle]?
I show there is no simple proof using maximizing weighting functions.
There is no LP-proof (Linear Programming) by fractional relaxation.
This shows the worth of near-solutions.
(For the impossiblity of the 5 times 2*2*5 pentacube problem
(see the pentacube tower project) I used near-solutions too.)
It seems unlikely to find a proof using weighting functions
and a partition of the figure giving congruence conditions.
(Examples of this aproach are: rectangles with L4, rectangles
with hexominoes, tetrahedra with 3-bones.)
Averaging-tiling-problems are a special form of count-tiling-problems.
The points of a orbit of a given symmetry subgroup are identified and so
counted. By averaging a solution of a count-tiling-problems over its
group we get an averaging-solution. Each point is meet fractional one
time. Let us call an averaging-solution a near-solutions if only few
points must be covered by averaging.
If there excists a weighting function which proofs the impossibility,
then the average weighting function (averaging over the symmetry group
of the figure) proofs the impossibility too. In fact the defect can
only grow by averaging.
So we can restrict our search to symmetric weighting functions.
But if there is an averaging-tiling-solution there can not be a
weighting function which proofs the impossibility.
I give several near-solutions (all with one defect?) for the triangle of size 7.
C2 and C3 near-solutions:
J I I I I O O N P P P C O O
J J J Y O O N N P C O O
N C C Y Y I N Y C C
+ N Y - + Y J -
C N P I Y J
P P I J
+=CN P J-B +=IY J P-B <- 'P' is not maximal for function B
C2 near-solutions:
O O C C P P P J N N I I I I
O O Y C P I J Y N N P P
Y + C - I J + Y - P
J Y N I Y C C P
J N I C O C
J N (IP) O O
+=JY N P-B +=JY O P-B
P P C C Y O O
P C Y Y O O
P C J Y N
I - + N
I N J
I J
+=JN I J-B
P P - C + J I P P - C + N I
P N C J C I P Y N N C I
P N J Y I P Y Y C I
N Y Y I Y O J I
N O Y O O J
O O (JO) O J
+=CJ O J-B +=CN J O-J
P P N N C C I
P Y - + N I
P Y Y C I
Y O J I
O O J
(JO) O J
+=CN J O-B
P P P J J J I
P N J C C I
- N C Y +
N Y Y I
N O Y
O O
+=CI O C-B
C3 near-solutions:
N N J J J P P
I N N C J P
I - C Y P
I Y + C
I O Y
O O
+=CY O C-B
C2 near-solutions: (propeller position: center)
P P P I I I I
P C C Y O O X X
C Y Y O O X X
C J Y N = Y and 3 times X X X X
J N N
+ -
+=JN J nice but illegal as N is in an illegal position
C3 near-solutions: (propeller position: center)
P P - - J J J
P N Y J C I
P N Y Y +
N Y C +
N O I
O O
+=CI O the center is perfect
P P C C J J J
P + Y J - I
P + Y Y I
N Y - I
N O I
O O
+=CN O the border is perfect
later we will see, that the C3-counting solution is unique
in the center case.
Some good weighting Functions:
1 1 1 1 1 1 1
1 0 0 0 0 1
1 0 0 0 1
1 0 0 1
1 0 1
1 1
1
B(oarder)-Function
C I J N O P Y : tetrahexes
012 0124 0123 012 0123 0-4 01 : B-Function values (legal positions)
2 4 3 2 3 4 1 : maximal B-Function values
The sum of the maximal B-Function values is 19.
The sum of the B-Function values of the figure is 18.
The excess (the difference) is 1.
It follows: Piece I must have weight 4 and must therefore be on the border.
1 0 1 0 1 0 1
0 0 0 0 0 0
1 0 1 0 1
0 0 0 0
1 0 1
0 0
1
D(istance 2)-Function
C I J N O P Y : tetrahexes
012 02 012 1 1 012 1 : D-Function values (legal positions)
2 2 2 1 1 2 1 : maximal D-Function values
The sum of the maximal D-Function values is 11.
The sum of the D-Function values of the figure is 10.
The excess (the difference) is 1.
It follows: Piece I must have weight 2.
What are legal positions?
If a placement of a piece results in parts of the figure,
which have not a multiple of 4 free positions, it is called illegal.
If a placement of a piece results in a free position of the figure,
which can not be covered by any other piece, it is called illegal.
Analysis of case: The propeller in central posiotion:
-----------------------------------------------------
After placing the Y the remaining configuration has C3 symmetry only.
The two weighting functions B and D can be combined into one in the
following way:
a b a b a b a
b 0 . 0 0 b
a 0 . . a
b . 0 b
a 0 a
b b
a
AB-Function
This function has excess=0 for a>=b.
C I J N O P Y : tetrahexes
a+b 2a+2b 2a+b a+b a+2b 2a+2b - : maximal AB-Function values
The sum of the maximal AB-Function values is 9a+9b.
The sum of the AB-Function values of the figure is 9a+9b.
The excess (the difference) is 0.
Note, that the C weighting has become smaller in this case, as
2a is illegal.
This weighting-function is optimal as no function can proof the
impossibility in this case, as near solutions excists in this case.
But this function helps in construction of a short proof for this case.
- The piece O must be in a corner to get its maximal weight.
- The remaining figure (triangle - {Y,O}) has no legal position for C.
- Therefore this case is impossible.
Appendix:
---------
The C3 counting-solution for the triangle without the center Y unique:
a b c a b c a
c a b c a b
b c a b c
a b c a
c a b
b c
a a three-partition of the triangle
Count: (a,b,c) = (10,9,9)
C I J N O P Y : tetrahexes
2 2 1 1 2 1 2 2 1 1 1 : a-count
0 1 2 1 1 1 0 1 2 1 3 : b-count
2 1 1 2 1 2 2 1 1 2 0 : c-count
After placement of Y there is only one position of C in the C3-counting
problem. The O is fixed too as the B-function is sharp. So only few
(a,b,c) vectors are possible. Let us subtract the pieces with a unique
vector. It remains (3,5,4) to be filled by I, J, and P. As the a-count
is 3 and all pieces give at least one, all variants with a-count 2 can
be eliminated. So J is (1,1,2) which gives the a remaining (2,4,2) for
I and P. They must be now both (1,2,1). The (a,b,c) solution is unique
if the AB-function constraints hold.
Now we can refine the (a,b,c)-counting solution to C3-counting solutions.
Only J and N have two placements in the C3-problem, the rest remain unique.
One point can be covered by one of the J placements. And so there is only
one solution for the C3-counting problem.
One example of averaging a weighting function of lower symmetry:
1 1 1 1 1 1 1
0 0 0 0 0 0
1 1 1 1 1
0 0 0 0
1 1 1
0 0
1
S(trips)-Function
C I J N O P Y : tetrahexes
123 024 123 2 2 123 2 : S-Function values (legal positions)
3 4 3 2 2 3 2 : maximal S-Function values
The sum of the maximal S-Function values is 19.
The sum of the S-Function values of the figure is 16.
The excess (the difference) is 3.
averaging of the S-function over D3 gives:
2 1 2 1 2 1 2
1 1 1 1 1 1
2 1 2 1 2
1 1 1 1 / 3
2 1 2
1 1
2
This function has the power of the D-function.
Weighting function with lower symmetry may help in finding
a short proof. Assume we can conclude from such a function
that a piece must lay on some positions. If intersection
of the possibilities for all conjugated groups is empty
the figure is impossible.
Example: Assume we know that the piece O must be in one
of two corner but not in the third.
All D3-averaging-solutions for the triangle:
a b c e c b a
b d f f d b
c f g f c
e f f e
c d c
b b
a
Counts for legal positions of the tetrahexes.
Positions marked with '+' have a suboptimal value for the B-function.
a b c d e f g
---------------------
0) C 0 0 0 0 1 2 1 +
1) C 0 0 1 0 1 1 1
2) C 0 0 1 1 0 1 1 +
3) C 0 0 1 1 1 1 0
4) C 0 0 2 0 0 2 0
5) C 0 1 1 0 0 2 0
6) I 0 1 2 0 1 0 0
7) I 1 1 1 0 1 0 0
8) J 0 0 1 0 1 2 0 +
9) J 0 0 2 1 1 0 0
10) J 0 1 1 0 0 1 1 +
11) J 0 1 1 0 1 1 0
12) J 1 1 0 1 0 1 0 +
13) J 1 1 1 0 0 1 0
14) N 0 0 1 0 0 3 0 +
15) N 0 0 1 1 1 1 0
16) N 0 1 0 1 0 1 1 +
17) N 0 1 1 0 0 2 0
18) N 1 1 0 1 0 1 0
19) O 0 0 1 0 1 2 0 +
20) O 0 0 1 1 1 1 0 +
21) O 0 1 1 1 0 1 0 +
22) O 1 2 0 1 0 0 0
23) P 0 0 2 0 1 1 0 +
24) P 0 1 1 0 1 1 0 +
25) P 0 1 1 1 1 0 0 +
26) P 1 1 1 1 0 0 0 +
27) P 1 2 1 0 0 0 0
28) Y 0 0 0 0 0 3 1 +
29) Y 0 0 0 1 1 1 1
30) Y 0 0 1 0 0 3 0
The 20 solutions for the D3-averaging-problem:
C00+ I06 J09 N18 O22 P27 Y30
C02+ I07 J11 N15 O22 P27 Y30
C01 I06 J12+ N15 O22 P27 Y30
C03 I07 J10+ N15 O22 P27 Y30
C04 I06 J08+ N18 O22 P27 Y29
C03 I06 J13 N14+ O22 P27 Y29
C05 I07 J09 N14+ O22 P27 Y29
C04 I07 J11 N18 O21+ P27 Y29
C03 I07 J13 N17 O21+ P27 Y29
C05 I07 J13 N15 O21+ P27 Y29
C05 I06 J13 N18 O20+ P27 Y29
C01 I06 J11 N18 O22 P26+ Y30
C01 I06 J13 N18 O22 P25+ Y30
C04 I07 J11 N17 O22 P26+ Y29
C04 I07 J13 N17 O22 P25+ Y29
C04 I06 J13 N18 O22 P24+ Y29
C05 I06 J13 N18 O22 P23+ Y29
C03 I07 J09 N17 O22 P27 Y28+
C03 I06 J13 N15 O22 P27 Y28+
C05 I07 J09 N15 O22 P27 Y28+
The solutions can be classified with the '+' marked piece.
Every solution must contain exectly one such piece.
From these D3-averaging-solutions one can try to construct
all near-solutions with only one defect pair. I made this
by hand and found the near-solutions given above. Later
I checked this table by a program.
References:
- Martin Gardner;
Mathematical Magic Show,
Alfred A. Knopf (1977) New York.
chapter 11: Polyhexes and Polyaboloes
- Solomon W. Golomb;
Polyominoes,
2nd Edition (1994) Pricton Univ. Press.
page 125 excercise 4:
Did anyone find a simpler proof of impossibility?
- Herman Riele, J. J. te Winter, D. T. Winter;
The Tetrahexes Puzzle,
CWI Newsletter (Amsterdam) 10 (March 1986) 33-39