The Weight Problem of Bachet de Meziriac

image

I will dedicate my this week's Torque group post to the discussion of the famous weighing problem of the French Mathematician Claude Gaspard Bachet de Meziriac (1581-1638), who solved it in his famous book Problemes plaisants et dilectables qui se font par les nombres, published in 1624.

$$\textbf{Problem.}$$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?

$$\textbf{Solution.}$$We separate the two scales of the balance as the weight scale and the load scale.On the former we will only place pieces of the measuring weight and on the latter we will place load and any additional measuring weights(This gives us greater flexibility).

For example,in order to weigh 2 pounds with a five pound and a three pound piece,we will place the five pound piece on the weight scale and the three pound on the load scale.

We define "preponderance" as the positive difference between sum of the weights placed on each scale.For example,if we place two weights 5 lbs and 10 lbs on one scale and three pieces weighing 1,3,4 lbs on the second scale,then this gives the first scale a preponderance of $$(10+5)-(1+3+4) = 7$$ lbs.

We will approach the problem with an idea reminiscent of Mathematical induction.

Let us suppose ,we have a series of weights A,B,C,..... which when properly distributed on the two pans,enable us to weigh all integral loads from $$1$$ to $$n$$ lbs.We take a new measuring weight X,such that it's weight (say p) exceeds the sum of the weights of the old measuring weights(say n) by $$n+1$$.

That is, $p - n = n+1$ $p = 2n+1$

Now let us understand the motivation of this choice of p.If X weighs more than $$2n+1$$,then clearly it is impossible to measure the weight $$n+1$$ using this system! On the other hand if it is less than $$2n+1$$,then not only will we be not able to measure the weight $$3n+1$$,but also some of the lower values of weight will overlap (can be constructed with or without using X) leading to an inefficient system.So $$p= 2n+1$$ is the most appropriate choice of $$p$$.

So now it is possible to weigh all integer loads from $$p+n = 3n+1$$,by addition of the weight P to the other weights.Clearly the old pieces can be used to weigh all values from $$1$$ to $$n$$ lbs.In order to weigh a load of $$p+x$$ lbs or (p-x) lbs,where x is a number between 1 to n,we place the measuring weight P on the weight scale,and the other weights in such a way that it gives the weight sacle a preponderance of x lbs.

It is quite intuitive that to measure the maximum number of weights using 2 measuring weights say A and B ,A must weigh 1 lb and B must weigh 3 lbs.These two pieces can be used to measure weight loads of 1,2,3,4. $1= 1$ $3-1=2$ $3=3$ $3+1=4$

By our discussion the third pieces should weigh $$c = 2*4+1=9$$ , then it becomes possible to measure all possible weights from $$1$$ to $$3*4+1 = 13$$!!

$1= 1$ $3-1=2$ $3=3$ $3+1=4$ $9-(3+1) = 5$ $9-3=6$ $9-(3-1)=7$ $9-1=8$ $9=9$ $9+1=10$ $(9+3)-(1)=11$ $9+3=12$ $9+3+1=13$

Finally we choose a 4th piece D,such that it's weight $$d = 2*13+1=27$$lbs.This choice of A,B,C and D can be used to measure all weights from 1 to 40 .

Hence the four pieces should be $$1,3,9,27$$!!

Bachet's weight problem was generalized by the English mathematician MacMahon. In Volume 21 of the Quarterly Journal of Mathematics (1886) MacMahon determined all the conceivable sets of integral weights with which all loads of 1 to n lbs can be weighed .

So I hope you all learnt a little some thing today...Stay tuned for my next note!!

$$\textbf{ARCHIVE:-}$$ Here are some of my previous notes

Cryptography:RSA Cipher

Cryptography:Diffie-Hellman Key Exchange

Fermat's Method of Infinite descent

Stacking problems

Partitioning of integers

4 years, 4 months ago

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$...$$ or $...$ to ensure proper formatting.
2 \times 3 $$2 \times 3$$
2^{34} $$2^{34}$$
a_{i-1} $$a_{i-1}$$
\frac{2}{3} $$\frac{2}{3}$$
\sqrt{2} $$\sqrt{2}$$
\sum_{i=1}^3 $$\sum_{i=1}^3$$
\sin \theta $$\sin \theta$$
\boxed{123} $$\boxed{123}$$

Sort by:

A slightly better approach (sketched below) would be to consider weights $$w_1, w_2, \ldots w_n$$ and linear combinations $$\epsilon_i \in \{ -1, 0, 1 \}$$:

$\epsilon_1 w_1 + \epsilon_2 w_2 + \ldots \epsilon_n w_n.$

Then, we can weigh up to $$3^n$$ linear combinations. However, we must ignore the single combination of all 0's, and also combinations which yield a negative value (they pair up nicely with combinations which yield a positive value). Hence, there are at most $$\frac{3^n-1}{2}$$ such combinations.

It remains to find a set of $$n$$ weights, which allow us to weight from 1 up to $$\frac{3^n-1} { 2}$$. This is easy if you motivate it according to the above (or just realize that the weights are of the form $$3^{i-1}$$).

Staff - 4 years, 4 months ago

I was wondering if any other combination of weights would work....

- 4 years, 4 months ago

{23,9,6,2} match 36 weigths; {24,9,4,3} , {25,7,6,2} , {26,10,3,1}, {28,8,3,1} match 37weights; {26,9,3,2} match 38 weights;

- 1 year, 9 months ago

That's awesome!!! o_o

- 4 years, 4 months ago

Can you please explain why you took $$p-n=n-1$$ and the next two paragraphs in more layman terms?

Thanks

- 4 years, 4 months ago

I took $$p-n = n+1$$,

Think of it this way,using the weights other than X we can measure any value from 1 to n and the minimum weight that can be measured using p is $$p-n$$ and if this equals $$n+1$$ then we can use the maximum number of load weights using the minimum number of measuring weights....

- 4 years, 4 months ago