Algebraic solution to the Broken Weight Problem

Here is a problem I was sent, which it turns out was first posed by Claude Gaspard Bachet de Méziriac in a book of arithmetic problems. The problem is as follows:

A few years ago, a King's mathematics professor purchased a small farm, a place where he could unwind on the weekends and grow some fruit and vegetables. The farm came with all kinds of tools and various implements, including a large balance scale. Next to the scale was an old (pre-metric) 40 lbs stone with some initials carved into it: apparently, a previous owner had used it to weight 40 lbs of feed.

One morning, while cleaning out his barn, the professor dropped the stone and it broke into four pieces.

The professor was a bit sad about his carelessness, as he had liked that curious old stone. But he soon discovered something interesting: He could use the four pieces of the broken stone to weigh items on the balance scale - as long as these items were in one pound increments, between 1 and 40 pounds.

How much did each of the four pieces weigh?

Note that since this was a 17th-century merchant, he of course used the balance scale to weigh things. So, for example, he could use a 1 lb weight and a 4 lb weight to weigh a 3 lb object, by placing the 3 lb object and 1 lb weight on one side of the scale, and the 4 lb weight on the other side.

I won't post the solution as maybe some of you would like to give this a go. For anyone reading this and wanting to try it themselves, DON'T SCROLL DOWN! People will be posting their solutions there.

I did this using an intuitive method but my question I am asking is in two parts:

1) Is there an algebraic solution to this without first solving it intuitively and then finding the logic

2) Is there therefore a general form you can take to solve any problem of this type?

Good luck!

If you can weigh $1,2,3,\ldots,40$, you can also automatically weigh $-1,-2,-3,\ldots,-40$ and trivially $0$. That is, you can determine $81=3^4$ different weights by putting each of the four weights into either of the pans or not use it. This means that the condition is "sharp" - any distinct distribution of pieces results in a distinct (integer) weight as difference between the two pans. If the pieces are $a\le b\le c\le d$, then the largest possible weights are $a+b+c+d=40$ (of course) and then $b+c+d$, which must be $39$, hence $a=1$. The next smallest weight is $b+c+d-a=38$, followed by $a+c+d$, which must be $37$, hence $b=3$. Then we already know that the sequence continues with $c+d=36$, $c+d-a=35$, $c+d-b+a=34$, $c+d-b=33$, $c+d-b-a=32$. Then the next smallest (i.e., the largest not having $+c$ and $+d$) is $a+b+d$ and must equal $31$, so that $c=9$ and finally $d=27$ (as we might have guessed meanwhile).

• I don't understand how $b + c + d = 39$? – Kaish Dec 27 '14 at 20:28
• Actually, I do understand. I didn't read it properly. I do have another question though: What was the reason behind stating there is $81$ different weights? – Kaish Dec 27 '14 at 20:35
• @Kaish With four weights, we can distinguish at most 81 weights (including negatives) because there are 81 ways to place the weights. If there were less than $40+1+40=81$ weights that can be distingished, it might be the case that different combinations lead to the same weight, for example it might be the case that $b+c+d-a = a+c+d$ (i.e., $b=2a=2$); or it might even be the case that the largest weight (in continuous sequence) is less than $a+b+c+d$. By counting the $81$ weights, I know that all $\epsilon_aa+\epsilon_bb+\epsilon_cc+\epsilon_dd$ with $\epsilon_x\in\{-1,0,1\}$ are different. – Hagen von Eitzen Dec 28 '14 at 15:22

For a "fair" balance scale, in order to be able to weigh an object of weight 1 you need a 1 stone. Then to weigh an object of weight 2 you need either a 2 stone or a 3 stone. The key point is that there is no weight achievable with stones of $(1,2)$ that is not achievable with $(1,3)$ (while $(1,3)$ can also weigh a 4 stone), so $(1,3)$ dominates over $(1,2)$ in the sense that it is always better.

Now to weigh a 3-stone you do need either $(1,2)$ or $(1,3)$ so any best solution must include $(1,3)$. Now apply the same reasoning to 5 and you find that you need a 5, 6, 7, 8, or 9-stone, and that $(1,3,9)$ dominates. It is easy to create an induction proof that to weigh all numbers up to $N$ with the minimum number of stones, a minimal solution is always of the form $\{3^k\} | 0 \leq k \leq \log_3 (3N/2)$; in the present case, $N=40$ so $k$ goes up to 3 so 4 stones suffice.

A related problem is that of the "unfair" scale, where it balances if the total weight on the left is exactly twice that on the right.

• You do not need a 1 stone to weigh 1. For example $2, 3, 7$ allow you to weigh $1,2,3,4,5$. – Hagen von Eitzen Dec 27 '14 at 18:56

$1,3,9,27$ are the numbers that make up to $1-40\;lb$ because....

\begin{align} 1&=1\\ 1-3&=2\\ 3&=3\\ 1+3&=4\\ 1+3-9&=5\\ 3-9&=6\\ 9-1&=8\\ 9&=9\\ 1+9&=10\\ 1-3=2+9&=11\\ \end{align} and so one until you get to $40$ its quite simple once you get the $4$ numbers.