Figure 1. A balance (Richard via Picassa Web)

There aren’t many mathematics blogs that are either interesting or accessible enough (meaning “easy to understand”)  to attract my attention. However, one that I do take a peak at on occasion is The Math Less Traveled by Brent Yorgey,  a PhD student in programming languages at the University of Pennsylvania. Brent is also a former math teacher at Woodrow Wilson SHS in Washington DC.

The Math Less Traveled offers various musings on mathematics and programming and an occasional interesting problem. One such problem appeared there recently. It is known as the broken weight problem. As Yorkey points out, it’s an old problem (circa 1612!) and it appears in an interesting book called 100 Great Problems in Elementary Mathematics: Their History and Solution by Heinrich Dorrie (which also happens to be available at the Pikes Peak Library in Colorado Springs).

According to Yorkey, it goes like this:

A merchant had a forty pound measuring weight that broke into four pieces as the result of a fall. When the pieces were subsequently weighed, it was found that the weight of each piece was a whole number of pounds and that the four pieces could be used to weigh every integral weight between 1 and 40 pounds. What were the weights of the pieces?

Okay, I said to myself, I can probably figure that out. It might not be pretty, but I can figure it out!

My Thinking on the Broken Weight Problem

My first thought was that the sum of the eights must equal 40. That seems useful. Then I got thinking that some addition and subtraction was going to be used to generate the combinations required to weigh every integral value from 1 to 40. Uh-huh.

Next, I realized all the numbers were probably all odd, since only even numbers can be generated by adding and subtracting even numbers, but both odd and even numbers can be made by addition and subtraction of odd numbers. So far so good!

My next thought is that the average of  the 4 numbers was 10. So I figured the required numbers would probably lie on either side of 10 and be not too far from 10.

To summarize: sum of 40, not far from 10, all odd.

So 9 and 11 are in play, and so are 7 and 13. HOWEVER the difference of 9 and 11 is 2 and so is the difference of 11 and 13. I got to figured that each consecutive pair would have to have a difference different from any other pair so as the maximum number of sums and differences would be obtainable. I had a hunch that prime numbers would be involved in some way (I am not sure why, it was just a hunch). What the heck, I’ll try 1, 9, 13 and 17. They have differences of 8, 4, and 4 respectively and their sum is 40 (but I didn’t check the differences or else I probably would have tried something else). I avoided 15 for no other reason than it isn’t prime.

Does that work? Nope, you can’t set up a scale to measure a weight of 2! Choosing 1 was probably fairly limiting also. Try again.  I’ll pull the 13 down to an 11 and push the one up to a 3, thus preserving the sum of 40. So I’m working with 3, 9, 11 and 17. The sum is 40, they are on either side of 10, they are all odd, and I’ve got a couple primes in there to boot.

Unfortunately, try as I might (using this admittedly ugly method) I cannot get a weight of 4 to balance (nor 7 for that matter). Must. Think…

Three Weeks Later

I finally got it. I’d say I spent an additional 2-3 hours on it overall. I posed the problem to a colleague at school and he had in a few days! He almost showed me his result but I stopped him before I could see it. I wanted to figure it out on my own. But, I did run my reasoning by him to see if I was on the right track.

• The 4 weights sum to 40. Check.
• Since the average is ten, they must be close to 10. Not exactly.
• They must all be odd. Check.
• I forgot to ask if they were all prime.

He let slip that three of them were in fact less than ten. Oh well I guess I’ll take that clue.

The breakthrough came when I realized hat one of them must be 1. Because, when all four pieces are on one side to balance an object of weight = 40, the only way to measure a weight of 39, would be to remove one piece and that piece had to be 1.

So I made a list of all combinations of three odd numbers (including 1) less than ten, plus one other to add up to 40. This led to

• 1, 3, 7, 29
• 1, 5, 7, 27
• 1, 3, 9, 27
• 1, 5, 9, 25

At this point the answer was staring me right in the face but I still didn’t see it.  I ruled out 1, 5, 9, 25 because it had two differences equal to 4 (5 – 1 and 9 – 5), and I had previously decided  it would be advantageous to have the differences between all four numbers to be not the same. On a hunch, I then chose the one that had the smallest difference  between 9 and the largest number and this was 1, 3, 9, 27 (27 – 9 = 18). Then I started testing, working my way down from 40. It worked!

Then I saw the pattern. To find the correct N number of pieces, choose weights with values of (N-1)⁰, (N – 1)¹, … (N-1)^n-1. In this case N = 4 pieces and 3⁰ = 1, 3¹ = 3, 3² = 9 and 3³ = 27.

I tested this idea with N = 3 and this works for finding 3 weights that can weigh any integral value up to 7. I assume it would work for N = 5 with weights of 1, 4, 16, 64 and 256 to weigh any integral weight up to 341. Perhaps I’ll try to write a computer program to test it.

Note added in addendum: As Brent points out in a comment, integral values from 1 – 341 cannot be weighed with weights of 1, 4, 16, 64 and 256. Obviously! There is no way to balance a weight of 2 (or 6, and many others).

A New Pattern Discovered

As it turns out, my colleague hit on that (N-1)⁰, (N – 1)¹, … (N-1)^n-1 idea pretty quickly. Smart! But before I saw that for my self I actually found another pattern that works, at least for the one case for which I tried it.

Figure 2. Testing from 121 to 41 with 5 weights (1, 3, 9, 27, 81)

What if? I thought, I added another term to the sequence 3⁰ = 1, 3¹ = 3, 3² = 9 and 3³ = 27? That would be 3⁴ = 81, which would give five weights with a sum of 121. I worked it down for each weight from 121 to 41 (since I already knew it would work from 40 on down) and sure enough it could be done (See Figure 2 which shows the work from 80 to 41).

So it appears that one could perhaps sometimes find two different total weights that could be weighed with N pieces. Even though 341 fails with 1, 4, 16, 64 and 256, 15 can be done with 1, 2, 4, and 8 (using a similar idea to find that 121 can be done with 1, 3, 9, 27, 81). And guess what? Integral weights from 1-31 can be weighed with weights of 1, 2, 4, 8 and 16.

I have come to think that no base greater than 3 can be used to generate a sequence that works. This is because there is no way to combine the resulting pieces to balance a weight of 2.

There are probably some other interesting things to investigate along these lines.