Thursday, February 18, 2016

triangle games: three jugs and the towers of hanoi

I was prompted to pull  "Geometry Revisited" (GR) by Coxeter and Greitzer off the shelf after reading John Conway and Alex Ryba's "The Stiener-Lehmus Theorem" (from The Best Writing on Mathematics, 2015, edited by Mircea Pitici). 

GR includes a very short section on "trilinear coordinates" which were used to in drawing up the triangle of triangles. As Coxeter and Grietzer explain,

As a welcome relief from the ordinary squared paper, used for plotting points with given Cartesian coordinates, one can sometimes buy "triangulated" paper, ruled with three systems of parallel lines, dividing the plane into a tessellation of small equilateral triangles. Such paper is convenient for plotting points that have given trilinear coordinates with respect to a (large) equilateral triangle.... These coordinates are ideal for representing any situation in which three variable quantities have a constant sum.

Representing shapes of triangles qualifies nicely as "a situation in which three variable quantities have a constant sum," as does the "three jug problem," which Coxeter and Grietzer use to show off the fun and usefulness of trilinears.

A Three Jug Problem

Suppose you have a three ungraduated jugs that hold 8 pints, 5 pints and 3 pints of liquid, respectively. You know the total volume that each jug can hold, but since they have no other measurements written on them, you can't use individual jugs to measure out quantities other than their full amount. Now suppose that the 8 pint jug is full and the others are empty; without loosing any liquid, how can you measure out 4 pints?

So, this problem fits nicely into the trilinear coordinate case: the total amount of liquid shared among the three jugs stays the same (8 pints), and each point (a, b, c), will represent the amount in the 8 pint, 5 pint, and 3 pint jug respectively. However, because of the different sizes of the jugs, not all of the trilinear points are accessible: The point (0,0,8) would represent all 8 pints in the 3 pint jug, so we draw solid lines on the triangle at (a, 5, c) and (a, b, 3) that cut off the 5 and 3 pint jugs. leaving us a parallelogram inside the triangle that represents all possible states of the jugs.

Our goal is to get one of the jugs to have just 4 pints in it. There are three solutions: (4,1,3), where there are 4 pints in the 8 pint jug 1 in the 5 pint jug and 3 in the 3 pint jug; (4,4,0), where there are 4 pints in the 8 pint jug and 4 in the 5 pint jug; and (1, 4, 3), where there is 1 pint in the 8 pint jug, 4 in the 5 pint jug, and 3 in the 3 pint jug.

A pour from one jug to another is shown by traveling from one edge of the parallelogram to another. So for example, starting with 8 pints in the large jug (8,0,0), we can pour 3 pints into the smallest jug and end up at (5,0,3).

Continuing along, bouncing from one side of the parallelogram to another, we have the first solution: (8,0,0), (5,0,3), (5,3,0), (2,3,3), (2,5,1), (7,0,1), (7,1,0), (4,1,3).

Starting off in the other direction, pouring from the 8 pint jug into the 5 pint jug leads to another solution: (8,0,0), (3,5,0), (3,2,3), (6,2,0), (6,0,2), (1,5,2), (1,4,3).

The Towers of Hanoi

The Three Jug problem reminded me of the Towers of Hanoi puzzle, where disks are exchanged between three rods.

The Towers of Hanoi consists of three rods onto which disks can be slid. A stack of disks of different sizes is on the first rod, stacked from largest to smallest, so that they form a cone. Your goal is to move all the disks onto another rod such that that a disk can never sit on top of a smaller disk and disks can only move one at a time.

Just as with the volume of liquid shared among the jugs, we can think of total weight of the disks as remaining constant as they shift between the rods. Movement between the jugs was restricted to either a complete filling or complete emptying of a jug, which gave the solution on the triangle the effect of bouncing from one side to the other. That is not the same situation as in the Hanoi problem, where movement between the rods is restricted by the stacking rules - but this rule might also lead to interesting patterns.

There are a number of ways of solving the Towers of Hanoi, but here is the one I like: if the rods are labeled a, b, c, to move the tower of disks from a to c, first move the tower without the last disk to b, move the last disk to c, and then move the tower back on top of the last disk already on c. If you are not familiar with recursion, you'll maybe not be convinced that this is a solution. Rest assured that by changing the problem of moving n disks into a problem of moving n-1 disks (twice), the problem is solved: You just need to keep applying the solution to each of the smaller sets of disks until the problem vanishes completely.

Lets imagine that for the n disk version, we have disks of weight 1, 2, 3, ... n. For n=3, we have disks of weight 1, 2, and 3, so we can play the game on a triangle with lengths of 6 (the total weight of all the disks).

Suppose that for rods a, b, c we use the coordinates (a,b,c) where the value of the letter represents the weight of the disks on that rod. Lets say we are trying to move the disks from a to c, which would require us to move from (6,0,0) to (0,0,6). If we follow the recursive solution above, we get a pattern like this:

If we had been playing with only two disks, we would have had a smaller triangle, and a simpler solution, You can see that the two disk solution appears twice in the three disk solution, but rotated, and these two copies of the smaller solution are linked by a move of largest disk. This is just as what you would expect from our algorithm (move the n-1 stack onto the 'spare' rod, move the n disk onto the target rod, then move the n-1 stack onto the target rod).

Here is the pattern up to n = 6.

Instead measuring the weight of the disks on the triangle, we could have just used each axis to count the number of disks - so for the 3 disk problem, we would have just has a triangle of sides length 3. This means that each move will have the same length (length 1), and some points that were distinct in the triangles above will now be the same.

The patterns look different, but they still exhibit the same recursive structure - each solution contains two copies of the previous solution joined by the move of the last disk.

So. trilinear coordinates provide a fun way of displaying triangle families, a helpful way of representing the classic 3 jug problem, and provide a way of seeing the "recursiveness" of the Towers of Hanoi solution. By the way, when I was manually trying to draw out solutions to the jug and Hanoi problems, I found the triangular graph paper here helpful.

Note: Trilinear coordinates are sometimes called triangluar coordinates, and sometimes barycentric - there are actually various types of these coordinate systems that are sometimes distinguished: see this note from the math forum.