Algebraic solution to the Broken Weight Problem

Question

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!

Answer 1

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.

Answer 2

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).

Answer 3

$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.