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.

An Improved Solution to the Probability Problem

My last blog gave a labored explanation of why given R red balls and W white balls in a bowl, if they are removed one at a time randomly until one color has been totally removed, what is the probability that White will be exhausted first.

Joshua Zucker gave much more elegant expalantion for the reason the probability of white being exhausted first is red/(red + white)

His solution, in my words.. forget everything except the last ball in the bowl... whatever color it is is Not the color that was exhausted. So All we have to do to know the probability that White is exhausted, is find the probability that the last ball drawn if we emptied the bowl would be red. But if we look at all the possible orders of drawing all the balls, 4/7 of the first balls drawn are red, 4/7 of the second balls drawn are red..and the same continues all the way to the end; 4/7 of the final balls drawn will be red, meaning that in 4/7 of the trials, the white balls were exhausted first.

Now I'm thinking about the case of three colors, red, white and blue. I haven't started, so if you have an easy explanation, lay it on me.... otherwise, more later.

-------------- edited afterward...
ask and you shall receive... Joshua does what he does best, thinking and explaining his thoughts on the fly... see the comment and learn ....