A Graphic Solution to the 25 Stones Problem

I recently wrote a blog about the problem below from the Gazette from the Australian Mathematical Society. I started out not knowing how to solve it, figured out how to solve it, but had to have Joshua Zucker give me the proof... a good learning experience, but it is such a nice problem that I wanted to see if I could explain it in terms that would make it clear to my students, so here is the problem, and a hopefully understandable solution:

Piles of stones

There are 25 stones sitting in a pile next to a blackboard.
You are allowed to take a pile and divide it into two smaller piles of size
a and b,
but then you must write the number a×b on the blackboard. You continue to do this until you are left with 25 piles, each with one stone.

What is the maximum possible sum of the numbers written on the blackboard?


I figured out pretty quickly by experimentation that it didn't matter how you divide the piles, you ended up with the same total on the board, 300.

One of the classic ways of exploring a problem like this is to make it smaller, so I reduced the pile to two, then three, etc and realized that each time the solution was equal to the number of ways of choosing two things from a collection of n things; $\dbinom{n}{2}$
n ____2_______3________4_______5______6_____________________25____________n

sum ___1______3_________6______10_____15____________________300__________(n)(n+1_/2

But why??? Enter Joshua with an explanation. He illustrated the solution with an analogy to a well known type of problem, the handshake problem. I will try to use basic Graph Theory...

To begin with, we reduce the problem to eight stones, a more manageable number to graph... the extension to any other number should be reasonably easy...
Visualize each stone as a node of a graph and lines connecting each pair, as in the complete graph of K₈ shown at the top.

If we count the number of line segments we will get 8 choose two, $\dbinom{8}{2}$ = 28 segments, as we would expect, since each segment is formed by selecting two of the eight points to be endpoints in every possible way.

Now what happens if we divide the eight points into two groups. We illustrate that by drawing a line to divide the eight points into two sets. In this example we have chosen to divide them into sets of five and three as shown here.



If we count, we notice that 5x3=15 segments are cut by the line, that is, the number of connections between the separated groups is equal to the product of the size of the two groups. Eliminating these 15 segments, we get two separate groups, each of which can be subdivided again.



If we now subdivide any of the other groups, we will cut another set of line segments. In this example we cut the five group.


This cut will eliminate another 6 of the segments, and now there are three groups. At each stage as we reduce the groups toward one in each set, we eliminate one or more of the 28 line segments, until at the end we have eight isolated points, and all 28 line segments have been cut.

Thanks Joshua, a great approach.

A Different Look at an Old Puzzle

Reading through a paper on Public Key Cryptography (yeah, I know how to live), by Shai Simonson of Stonehill College, I was reintroduced to an old problem from my youth. "In the 1995 movie Die Hard: With a Vengeance (aka Die Hard III), Bruce Willis and Samuel L.Jackson play a bomber's deadly game as they race around New York trying to prevent explosions.In order to stop one explosion, they need to solve the following puzzle:

Provided with an unlimited water supply, a 5-gallon jug, and a 3-gallon jug, measure outprecisely 4 gallons, by filling and emptying the jugs." If you have never tried this problem, you might pull out the pencil and paper and have a go before you read on.

In a graph theory variant of this problem, the unlimited supply is often replaced with an eight gallon jug, but the problems are equivalent. I had just hours before read the same problem in reviewing Nets, Puzzles, and Postmen by Peter M. Higgins.

Simonson goes on to describe a little history of the problem, "Of course this puzzle was not invented for this movie. Most references attribute the puzzle and its variations to Tartaglia [Tweedie, M.C.K., A Graphical method of Solving Tartaglian Measuring Puzzles, Mathematical Gazette, 23, (1939) 278-282.], but the earliest known version of the problem occurs in the "Annales Stadenses" compiled by Abbot Albert of the convent of the Blessed Virgin Mary in Stade. Stade is a small city on the west side of the Elbe estuary a bit downriver from Hamburg. The date of compilation is uncertain, but seems to be 1240."

"The puzzle is also discussed in detail at the wonderful educational mathematics site cut the knot created by Alex Bogolmony ".

Knowing you would be interested, I copied a short clip from Bogolmony's site where he retells the story of how, “Siméon Denis Poisson (1781-1840) was a famous French mathematician of the last century. He worked in celestial mechanics, probability, calculus, electricity and magnetism. He is known to be designated for a medical carreer by his family. Edward Kasner and James Newman Mathematics and the Imagination refer to Poisson's biographer, Arago:
“Siméon Poisson's family tried to make him everything from a surgeon to a lawyer, the last on the theory that he was fit for nothing better. One or two of these professions he tackled with singular ineptitude, but at last he found his métier. It was on a journey that someone posed to him a problem similar to the one below (above on this page - AB). Solving it immediately, he realized his true calling and thereafter devoted himself to mathematics, becoming one of the greatest mathematicians of the nineteenth century." ahhhh now you wonder how many young people discovered their love for mathematics in a darkened theater as they shouted out help to Willis and Jackson, "No, Fill the three and dump it into the five!".

The graphic NET for the problem is in the photo at the top. Imagine the points x,y as giving the amount in each of the two jugs. The x-coordinate shows how much is in the five-gallon jug and the y-coordinate shows how much is in the three-gallon jug. Each of the paths on the graph shows a possible move. For instance, if we start at (0,0) nothing in the two jugs, there are two paths we may follow, rigth out the x-axis to the point (5,0), or vertically up the y-axis to (0,3). The object is to end up at (4,0) or (4,1) or (4,2) or (4,3) since each of these will have a jug containing four gallons. To solve it, just move along the lines from point to point and if you get stuck, go back a point and take a different path. In the language of the graph-theory people, this is called a breadth first search (I think).

Have fun, but keep in mind you may be learning important math along the way. Simonson points out the reason for his including the puzzle in his work, "This puzzle is useful for studying public-key cryptography, because the solution embodies the two major related number-theoretic results: Euclid’s algorithm [I just realized I have never written up anything on this, perhaps because so much has been done so well in other places, like this page ] and Fermat’s Little Theorem.

I found a post by David Singmaster, one of the foremost experts on Recreational Mathematics, who provides some additional history of the problem, and an incentive for young mathematicians (see the bold below)...
" Measuring With Jugs.... I have reorganised the notation of these problems. Tweedie, MG 23 (1939) 278-282, is the source of the triangular graphical method of solution. Halving 8 using 5 and 3 is in Abbot Albert which seems to be the earliest version. Pacioli, De Viribus,
seems to be the first to use any other values, e.g. halving 12 using 7 and 5. Tartaglia seems to be the first to divide in thirds, e.g. divide 24 in thirds using 5, 11, 13. The general problem of what can be obtained from a, b, c with c full to start seems to be first treated by A. Labosne is his 5th ed. of Bachet's Problemes and appears to still be unsolved when c < a+b." So have a go children!!!