Here’s a fantastic problem I recently heard. Apparently it was first posed by Claude Gaspard Bachet de Méziriac in a book of arithmetic problems published in 1612, and can also be found in Heinrich Dorrie’s 100 Great Problems of Elementary Mathematics.
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?
Note that since this was a 17th-century merchant, he of course used a balance scale to weigh things. So, for example, he could use a 1-pound weight and a 4-pound weight to weigh a 3-pound object, by placing the 3-pound object and 1-pound weight on one side of the scale, and the 4-pound weight on the other side.
The solution to this puzzle is really fascinating and leads into all sorts of fun generalizations and other topics; I’ll write more later. For now, as always, feel free to leave questions, observations, and solutions in the comments (so don’t look at the comments before you’ve solved it if you don’t want to see the answer!).
The Math Less Traveled 
What fun!
Without solving, I am looking at a few sub-problems.
How many ways could the four weights be combined?
1 at a time (4)
1 – 1 (12, of which 6 are negative, so 6)
2 at a time (6)
2 – 1 (12, and if some are negative, convert to 1 – 2)
2 – 2 (6 of which 3 are positive)
3 at a time (4)
3 – 1 (4. If one is negative, take 1 -3 instead)
4 (1)
So I see potential for 46 weights, meaning precious little repetition.
Next, how many ways can we divide 40 into 4 natural numbers? 39C3. But how many of those have no repeated elements? I’m going to give this problem some thought, and either let it suggest a third problem, or move on to the original.
Hmm, so I thought of 1,3,9,27.
Now i have to prove given k, does there exist a pair (k+a, b) such that k+a = b. where a and b expressed in ternary should only contain 0 and 1’s, and a+b have the same property. and 1<=a+b<=40
not a rigorous proof,
If I express k in ternary, then then there can be at most 5 digits, if it's 5 digits, it has to be 10000, which is 1+3+9+27.
If it's already all 1 and 0, then it can be expressed by sum of 1,3,9,27 easily.
If there exist a 2 in 3^n'th place, then one can add a 1 in a's 3^n'th place. b will have a 0 in 3^n'th place.
It could create a new 2. if it happens, do it again until all 2 are removed.
There can be at most 4 carries.
so this will always work.
My solution:
I had cast the question as that each integer in [1,40] could be expressed (not necessarily uniquely) as a_1*W_1 + a_2*W_2 + a_3*W_3 + a_4*W_4, where w.l.o.g. we had that W_1 <= W_2 <= W_3 <= W_4, and for which each a_i is taken from {-1,0,1}. After deducing that W_1 = 1, and staring at it for a while, I suddenly realized that it looked awfully like a ternary expansion. I made the guess that W_2 = 3, W_3 = 9 and W_4 = 27, and verified that it is indeed the answer.
It sure seemed more obvious after the fact given the form that I had put it in!
The fact that 40 = 3^0 + 3^1 + 3^2 + 3^3 seemed to be essential to the existence of a solution. Is it true in general that a stone of M = 1+3 + … + 3^n pounds could be broken into n+1 pieces such that those pieces could weigh all integral weights up to M?
1,3,9,27.
I’m just sitting down to dinner, so I don’t have time to explain in detail,
but roughly, represent every weight in base 3, where 2 digits are realized as the ‘2’ digit weight on the other side of the scale and a heavier weight on the main side. It can also be thought of as sort of a base 3 with 1,0, and -1 digits.
It would seem that each piece can add, subtraction or have no effect on the total weight. That’s 3 states which leads to an obvious conclusion.
What a great hint!
It was NOT obvious to me. But after about 30 seconds thought, it all became clear (including the actual answer, and the extension).
Thank you.
What a fun problem, but I think I found one solution. Still not sure however what we can learn from the special solution.
First, I think we need to consider what happens at the edges. Obviously needing a way to represent 39 lead to the conclusion that one of the weights has to be 1. Then we have found a solutions for 38 too, because we can just put 39 on one side and 1 on the other, representing 38. Thus 37 is the next problem. As Jonathan mentions it’s probably a bad idea to use more repeat elements then necessary it seems reasonable to choose 3 as the second weight. Now by choosing 1 and 3 you can represent the numbers 1 to 4 and 32 to 40.
Now the problem becomes somehow trivial as we realize that we can represent +/- 4 for of each number we can represent with each combination of the two remaining weight and we have 28 numbers left to cover. Choosing the most obvious solutions with 9 as the third weight and consequently 25 (after all the sum of the four weights has to be 40) as the fourth we see that due to 25-9=16 and 25+9=34 the remaining numbers can be represented by those particular weights.
Quite interestingly the only numbers we are able to present in more than one way are 12, 13, 36, 37, 38. In order to fulfill the 46 potential weights computed by Jonathan some number has to be represented in 3 ways, but I cannot find the number.
Uh, I shoud have read what I was writing and realize that the 25 is actually a 27 and now even the extension begins to make sense
Given the clue in the problem statement about putting weights on the other side of the scale to subtract weight, it is possible to derive the answer before you have figured out the underlying logic.
First guess that you probably have to have a 1-pound weight. This seems like a reasonable place to start. At this point the only amount I can successfully weigh is 1 pound.
So, what’s the smallest weight I can’t yet weigh? 2 pounds. What weight (other than a 2-pound weight) would let me weigh 2 pounds? A 3-pound weight would do the job. So I add that to my arsenal. Now I can weigh anything up to 4 pounds with my 1-pound and 3-pound weights.
Now the small weight I can’t yet weigh is 5 pounds. Given that I can weigh anything up to 4 pounds, if I now add a 9-pound weight, I can now weigh anything between 5 and 9 pounds by using the 9-pound weight and subtracting between 0 and 4 pounds as appropriate.
One more iteration, using my 1-, 3-, and 9- pound weights, yields the 27 pound weight using the same logic.
It’s then fairly straightforward to verify that I can do all the weights from 28 to 40 pounds, and that my 1-, 3-, 9-, and 27- pound weights add up to the original 40 pounds.
Solution! Stop reading now if you don’t want to know! I’m not sure that my method is really the most straightforward but it seems to work =)
Call the pieces A, B, C, and D. Each piece will either be on the left side of the scale, the right side of the scale, or off the scale. In any given setup, then, each of the four pieces can be labeled with a -1, 1, or 0, respectively. Now you can describe the entire scale with four trinary bits (trits? maybe?) That is, any combination of pieces can be described with four values, each of -1, 1, or 0.
This leads to the following observations (and this is something like what my thought process looked like):
– There are 81 possible combinations: 3 ^ 4 = 81.
– BUT: Many of these combinations are reflections of other equivalent combinations. That is, -1 0 0 0 symbolizes piece A on the left side of the scale and nothing else present; this is really the same thing as 1 0 0 0, with piece A on the right side of the scale. Or, more precisely, the two configurations would allow you to measure a single weight.
– Furthermore, every combination is exactly the same as the configuration reached by just swapping the left and right sides of the scales. So we can throw out half of those 81 combinations.
– …also, we can throw out 0 0 0 0, because having none of the weights on the scale makes for a pretty useless scale. Which means we’re down to forty combinations. That’s convenient.
– So, forty combinations of trinary bits, each of which equals a configuration that we know adds up to the values 1 through 40. …Let’s try the powers of three, just to see. (A = twenty-seven, B = nine, C = three, D = one.) Hey, look, those add up to forty also! How about that!
– I was pretty sure that was right at this point but I wrote a quick program to check all the combinations. It’s right. =)
Haha, this is an absolute classic.
I’m wondering though just how much this has to do with mathematics and how much it has to do with inspiration and trial and error. Just out of curiosity, does anyone know what area of mathematics, if any, would cover questions like this and have techniques to solve them?
Thanks
Ironically, I calculated the number of ways to put the weights down as a summation involving binomial coefficients, before putting it into Mathematica, which spit out a very simple answer, which immediately suggested MathPhan’s hint.
The combinatorial problem suggests that we have one redundant weight, that can be measured out in two ways (or three if you count “negative” weights as another way to get the same weight). Does anyone know which one it is?
MattPhan, I love that thought. I’ve seen a number of problems like this one, and something in them usually gives me the hint I need. But I had never framed it in quite that way. So nicely condensed.
Given a broadcast I think Sue pointed some of us to elsewhere, I immediately went from my first impulse (that this would be powers of 2) to thinking of the notion of logarithmic growth and geometric means. So trying 1, 3, 9, and 27 was a natural. I was sure that if it added to 40 it would be correct. I haven’t worked on generalizing or extending, but it’s interesting where “intuitions” come from when someone points you to a seemingly unrelated issue within a short time before you see a certain problem. I’m not read through all the comments above so that I can work on this more later when I have time (and paper). 😉
Hihi,
I used this problem a few months ago to test my “how do I teach problem solving skills.” It’s a great one! Thanks for posting this. Here’s my thoughts on how to teach something like this:
Best,
Sam
Great problem! I had fun solving it.
Steve-O
Your comment got me thinking…
Is the fact that (3^4-1)/2=1+3+9+27 a coincidence? I’m pretty sure that can be generalized as:
((k^n)-1)/(k-1)=k+k^2+…+k^(n-1)
Does this have anything to do with solving the problem? Or similar problems like it?
Revised generalization:
((k^n)-1)/(k-1)=1+k+k^2+…+k^(n-1)
I had a private bet with myself that the solution would involve a Golomb Ruler. Then I read the comments and thought “oh bother”. Then I read the whole thing again and slapped myself, having obviously not learnt the first lesson that I was taught in maths classes, which is “read the whole question before you answer it”!
Pingback: The broken weight problem: solutions and further exploration « The Math Less Traveled
I enjoy your blog Brent and I enjoyed this problem. I am no a mathematician, but I do like math enough to teach it middle schoolers. I took a shot at this problem using a more or less heuristic approach with an element of brute force. I finally did discover the pattern behind it. I wrote up my experience at my blog at http://mistermcintoshsays.org/2010/06/06/the-broken-weight-problem/
Please explain the underlying message in what Mattphan said, which i was suppose to concieve
I’M GOING TO START THIS OFF WITH… I AM NOT A STUPID PERSON. I AM AN SE NURSE AND AM VERY GOOD AT WHAT I DO. HOWEVER I JUST DO NOT GET THIS. MY SON IS IN SEVENTH GRADE AND THIS IS AN EXTRA CREDIT THING. I WILL NOT LET HIM JUST PUT THE ANSWER DOWN WITHOUT HIM KNOWING HOW WE CAME TO THIS CONCLUSION… BUT THE PROBLEM IS I DON’T EVEN KNOW HOW TO EXPLAIN THE ANSWER. THANKS FOR YOUR HELP. MANDI