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