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.