Two Rectangles are Constructable with Tangrams:
An Enumeration Proof using Mathematica

Mathematica in Education
Vol.2 No.4
(October 1993)

by
Joseph Sloan
Department of Mathematics and Computer Science
Lander University
joeslon@hubcap.clemson.edu

Introduction

An enumeration proof is a proof that generates and then
analyzes all possible cases for a problem or some aspect of 
a problem.  If the number of cases is large, computer 
assistance becomes indispensible.  This paper gives an 
example of a proof by enumeration using Mathematica.

Perhaps the best example of a computer generated enumeration
proof is the solution to the four-color map problem by Appel
and Haken [1976].  They demonstrated that four colors are 
sufficient to color any planar map so that no countries 
sharing a border will share the same color.  The technique 
for the proof was suggested by A. B. Kempe in 1879.  But, 
because of the large number of cases that needed to be
considered, the actual proof did not appear until 1976.

While worthy of study, the proof is too complex for 
students to attempt replicating it.  The Appel and Haken 
proof would have taken 300 hours of CPU time on a 
supercomputer of that era.  (Lacking access to such a 
machine, it took closer to 1200 hours [Kolata, 1976].)
Fortunately, there are other enumeration proofs accessible
to students.  Such a proof, based on tangrams and using 
Mathematica, is given here.

The problem

A tangram is an ancient oriental puzzle obtained by cutting
a square into seven pieces [Gardner, 1976a--c]. (See 
Figure 1.)  The pieces are a square, a parallelogram, two 
small triangles, a medium triangle, and two large triangles.
The object of the puzzle is to assemble these pieces into 
various figures, most typically, the original square.  (See
Figure 2.)  It is also possible to construct a second 
rectangle that is twice as long as it is tall.  (See 
Figure 3.)  But can other rectangles be constructed?  None
have been found, but how can we be sure?

We will demonstrate that these are the only two rectangles
that can be constructed.  Our general approach is to 
1) list the lengths of all possible sides with which a 
rectangle can be constructed, 
2) find those combinations that give the correct area, and,
3) analyze each of these rectangles individually.
Because of the number of combinations, this would be too
tedious and error prone for a manual approach.

The Proof

We begin by examining the pieces.  If we take the edge of 
the square piece as our basic unit of length, we can specify 
the dimensions of the other pieces in terms of this unit.
The square is 1 by 1, of course.  The parallelogram has 
adjacent edges of 1 and Sqrt[2] separated by a 45 degree 
angle.  All five triangles are isosceles.  The two small 
triangles have legs of 1 and hypotenuses of Sqrt[2].  The 
medium triangle has legs of Sqrt[2] and a hypotenuse of 2.
The two large triangles have legs of 2 and hypotenuses of
2 Sqrt[2].  Observe that the edges fall into two disjoint 
sets---integers and integer multiples of Sqrt[2], that the 
total area of the pieces is 8 square units, and that the 
total perimeter for all the pieces is 20 + 10 Sqrt[2].

Next, we construct a list of all possible edge combinations
that can be used as a side for a rectangle.  Since pieces 
cannot overlap, each side of a rectangle must be formed by 
joining the edges of individual tangram pieces end-to-end.

We assign to the variable Pieces a list composed of the lists
of edges of each tangram piece.  Thus, the side of our 
rectangle is constructed by using one value from each piece 
(each inner list).  We include 0 in each list since a piece 
may not be used.

Pieces = 
  {{0, 1, 1, Sqrt[2]},            (* small triangle *)
   {0, 1, 1, Sqrt[2]},            (* second small triangle *)
   {0, 1, 1, 1, 1},               (* square *)
   {0, 1, Sqrt[2], 1, Sqrt[2]},   (* parallelogram *) 
   {0, Sqrt[2], Sqrt[2], 2} ,     (* medium triangle *)
   {0, 2, 2, 2 Sqrt[2]},          (* large triangle *)
   {0, 2, 2, 2 Sqrt[2]}};         (* second large triangle *)

Next, we construct a list of all possible sums obtained by
taking one value from each of the inner lists.  This new 
list gives the lengths of all the possible ways we can line 
up edges of our tangram pieces to form the side of a 
rectangle.

This will be clearer if we first consider just two pieces.
Let P1 and P2 be a small triangle and a large triangle
respectively.

P1 = {0,1, 1, Sqrt[2]};
P2 = {0,2, 2, 2 Sqrt[2]};

Outer can be used to construct a list of all possible
combinations drawing one element from each.

Data1 = Flatten[Outer[List, P1, P2],1]

We apply Plus to obtain the lengths for the various
combinations.

Data2 = Apply[Plus, Data1, {1}]

Finally,Union is used next to eliminate duplicates and sort 
the data.

Data3 = Union[Data2]

Thus, there are nine possible ways to line up edges from 
these two pieces to form sides for a rectangle counting
those cases where one or both pieces are omitted.

The function FindCombinations combines these operations.

FindCombinations[Lst1_List, Lst2_List] :=
  Union[
    Apply[Plus, Flatten[Outer[List, Lst1, Lst2], 1], {1}]]

We use a For loop to iterate over all seven tangram pieces.

For[Data=Pieces[[1]]; i=2, 
    i<=7, 
    i++, 
    Data = FindCombinations[Data, Pieces[[i]]]]

Length[Data]

This gives a total of 62 possible sides for our rectangles.
Since candidate rectangles must have both their length and
width taken from this list, this gives 3844 possible
rectangles.  Fortunately, we can easily reduce the number.

First, we eliminate the first length, 0.

Data = Rest[Data];

Since the shortest edge is now 1 and the total area is 8,
we can exclude all sides longer than 8 because the area of
any rectangle using one of these edges would be greater
than 8.

Data = Select[Data,N[#]<=8&];

Length[Data]

We have reduced the number of possible rectangles to 29^2 or
841.

Our next step is to enumerate all possible edge pairs for 
rectangles.  First, we pair each possible edge with every 
other possible edge in PossibleShapes.  Sort and Union are
used to remove duplicates.

PossibleShapes = Flatten[Outer[List, Data, Data],1];

PossibleShapes = Union[Map[Sort, PossibleShapes]];

Once we have our candidate shapes, we look to see which pairs
give an area of 8 by calculating the area for each pair.

ViableRectangles = 
  Select[PossibleShapes, (#[[1]] * #[[2]] == 8)&] // 
    TableForm

We now have only four candidates.  Each row gives the 
dimensions of a possible rectangle.  The last row, 
2 Sqrt[2] by 2 Sqrt[2], is the original square.  The second 
row, 2 by 4, is the other known rectangle.  That the other 
two rectangles cannot be formed is clear when we compare
their dimensions to the individual pieces.

A 1 by 8 rectangle simply could not contain either of the 
large triangles since their minimum height is the Sqrt[2].
The Sqrt[2] by 4 Sqrt[2] rectangle must have a perimeter 
of 10 Sqrt[2].  Thus, all of the edges that are multiples 
of Sqrt[2] must lie on the perimeter of the rectangle.
Moreover, none of the integer edges can be used in the
perimeter since the sum of a nonzero integer and a nonzero 
integer multiple of Sqrt[2] will never be an integer multiple
of Sqrt[2].  But the edges that are multiples of Sqrt[2] on 
the parallelogram are on parallel sides separated by 
Sqrt[2]/2.  To use both would require that they be on 
opposite sides of the rectangle.  This is impossible since 
their separation does not match either dimension of the 
rectangle.

Efficiency

For a proof, efficiency is only an issue if the code fails
to produce an answer.  As long as the memory requirements
of the code does not exceed the memory of the computer used
and as long as the time required does not exceed the user's
patience, the code is "efficient enough."

If the code is not acceptable, the place to start is with 
the basic algorithm.  This particular proof works because 
it enumerates, not all possible shapes, but one aspect of
the shape in question.  That is, it enumerates possible edge
lengths for rectangles.  This choice reduces both space and 
time complexity.  Additional reductions in space complexity 
were given in In[10], and In[11] to satisfy the memory 
constraints of the computer used.  Another such reduction,
not needed here, would be to reduce the number of sides 
considered by eliminating duplicate edges for each piece.
The following statement could be added after In[1]:

Pieces = Map[Union, Pieces];

Although not necessary, the space requirements could have 
been considerably reduced by combining the generation and
selection processes.  In In[1] Outer is used to generate 
all edge pairs at once.  This could have been replaced with 
two nested loops, both over Data, generating candidates
one at a time.  Then, by testing within the inner loop, the
collection of data could have been restricted to just the
dimensions of viable rectangles.

Shapes = {};

For[i=1, i < Length[Data], i++,
  For[j=1, j < Length[Data], j++,
    If[(Data[[i]] * Data[[j]]) == 8,
       Shapes =
         Union[Append[Shapes, 
                      Sort[{Data[[i]], Data[[j]]}]]]]]]

The list Shapes contains the dimensions of candidate 
rectangles.

Discussion

I have used this proof as a demonstration in a course in
Mathematica programming with good results.  The class was
composed of junior and senior mathematics, computer science,
and engineering students.  Since the proof requires only 
elementary high school mathematics, students were able to
focus on the proof technique and the programming style.  The
proof was easily followed and served as a useful example
of both exploratory mathematics and functional programming
constructs.

Considering the number of edge combinations involved, trying
to solve this manually would be tedious at best and highly
error prone.  By using Mathematica, we were able to construct
all possible combinations and then reduce the problem to one 
that was easily analyzed.  I do not wish to suggest that this
could not have been done without Mathematica.  Nonetheless, 
this particular proof was the result of explorations with
Mathematica.

References

Apple, K. and W. Haken, "Every Planar Map is Four Colorable,"
Bulletin of the American Mathematical Society, 82:5, 
711--712.

Gardner, Martin. 1974. "Mathematical Games", Scientific
American, 231:2, 98--103.

Gardner, Martin. 1974. "Mathematical Games", Scientific
American, 231:3, 187--191.

Gardner, Martin. 1974. "Mathematical Games", Scientific
American, 231:4, 124--125.

Kolata, G. B. 1976. "Four-color Conjecture: A Computer
Aided Proof", Science, 193:564--5.

About the Author

Joseph Sloan is Assistant Professor of Mathematics and
Computer Science at Lander University.  He received a M.S. 
in Mathematics from Duke University in 1981.  In 1987 he 
received a Ph.D in Biomedical Engineering from Duke
University for his work on computer modeling of the 
electrical properties of the heart.