The Weight Problem of Bachet de Meziriac

I have accumulated a great many mathematical ebooks and I decided that it was high time to make more use of them. To that end, I dusted off (so to speak) an old tome that was first published in 1958. It's titled "100 Great Problems of Elementary Mathematics" by Heinrich Dörrie. I settled on Problem 2 with title and exposition as follows:

The Weight Problem of Bachet de Meziriac

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?

The observation is made by the author that:

This problem stems from the French mathematician Claude Gaspard Bachet de Méziriac (1581-1638), who solved it in his famous book Problèmes plaisants et délectables qui se font par les nombres, published in 1624. We can distinguish the two scales of the balance as the weight scale and the load scale. On the former we will place only pieces of the measuring weight; whereas on the load scale we will place the load and any additional measuring weights. If we are to make do with as few measuring weights as possible it will be necessary to place measur­ing weights on the load scale as well. For example, in order to weigh one pound with a two-pound and a three-pound piece, we place the two-pound piece on the load scale and the three-pound piece on the weight scale. 

Clearly this problem has some history. My first impulse was to devise an algorithm in SageMath that would provide a solution. This is really a brute force approach and does not involve much mathematical reasoning. The text book provides a carefully reasoned solution which I haven't looked at yet. However, I did skip ahead in the book to check that the solution provided by SageMathCell was the correct one. It was.

Here was my approach. The three smallest weights possible are 1, 2 and 3 pounds and so the maximum possible weight is 34 pounds. Thus a possible combination of weights would be 1, 2, 3 and 34 pounds for a total of 40 pounds. There are ${}^{34}{C}_4=297$ ways of choosing four different weights in a range from 1 to 40 in such a way that they total 40. Let's represent these weights by the list items $w[0],w[1],w[2],w[3]$. Because we can place weights on the weight scale and the load scale, this means that weights can be subtracted from one another as well as added to one another. The best way to represent this is by coefficients $a_0,a_1,a_2,a_3$ that can take values of -1, 0, 1. This means the possible weights are given by:$$weight=a_0\times w[0]+a_1\times w[1]+a_2\times w[2]+a_3\times w[3]$$It doesn't matter if some of these possible weights are negative or exceed 40 as this can be taken care of in the algorithm by restricting the range of possibilities. Here is the algorithm that I developed along with its output (permalink):

L=[ ]
N=[n for n in [1..34]]
C=Combinations(N,4)
for c in C:
    if sum(c)==40:
        L.append(c)
a0,a1,a2,a3=var('a0,a1,a2,a3')
for w in L:
    N=[ ]
    for a0 in [-1..1]:
        for a1 in [-1..1]:
            for a2 in [-1..1]:
                for a3 in [-1..1]:
                    weight=a0*w[0]+a1*w[1]+a2*w[2]+a3*w[3]
                    if weight>0 and weight<41:
                        N.append(weight)
    if Set(N).cardinality()==40:
        print(w) 

[1, 3, 9, 27]

It's interesting that only one set of weights covers all the possibilities from 1 to 40. Figure 1 is a plot of the combinations and the numbers from 1 to 40 that they cover. For example, it can be seen only one combination covers just 10 of the possible numbers and that is the combination of 1, 2, 3 and 34. No combination covers 11, 12, 13, 14, 15 or 16 possible numbers but 6, 8, 12 and 14 cover 17 of the numbers. Each blue dot represents a combination. It can be seen that 31 of the possible numbers are covered by a large number of different combinations.

Figure 1: permalink

Now the question that arises is why 1, 3, 9 and 27? What strikes me at first glance is that these weights can be represented as $3^0,3^1,3^2,3^3$. In base 3 we have ${40}_3=1111$ and each 1 represent represents one of the weights and a 0 would represent the absence of that weight. For example ${39}_3=1110$. With 38 however, we have a problem because ${38}_3=1102$ and the 2 would mean that two weights, each of 1 pound, would be needed. The solution is to move the 1 pound weight to the load scale so that:$$\text{weight scale --> }39={1110}_3\equiv {1102}_3+1_3=38+1\text{ <-- load scale }$$Another example is 33 that has a representation of 1020 in base 3.$$\text{weight scale --> }36={1020}_3\equiv {1020}_3+{10}_3=33+3\text{ <-- load scale}$$By moving one or more of the weights to the load scale where necessary, all the possibilities from 1 to 40 can thus be covered. Similarly, if we had five weights of 81, 27, 9, 3 and 1, then all whole-numbered weight from $1={00001}_3$ pound to $121={11111}_3$ pounds could be measured.

At this point, I haven't looked at the solution in the text book and that's what I'll do now. I've cheated a little I know because I worked out the solution by brute force and then sought to justify it. Here is the text book solution:

IF we have a series of measuring weights $A,B,C,...$ which when properly distributed upon the scales enable us to weigh all the integral loads from 1 through $n$ lbs, and if $P$ is a new measuring weight of such nature that its weight $p$ exceeds the total weight $n$ of the old measuring weights by 1 more than that total weight:$$p-n=n+1\text{ or }p=2n+l$$THEN it is then possible to weigh all integral loads from 1 through $p+n=3n+1$ by addition of the weight $P$ to the measuring weights $A,B,C,...$.

In fact, the old pieces are sufficient to weigh all loads from 1 to $n$ lbs. In order to weigh a load of $p+x)\text{ and/or }(p—x)$ lbs, where $x$ is one of the numbers from 1 to $n$, we place the measuring weight $P$ on the weight scale and place weights $A,B,C,...$ on the scales in such a manner that these pieces give either the weight scale or the load scale a preponderance of $x$ lbs. 

This being established, the solution of the problem is easy. In order to carry out the maximum possible number of weighings with two measuring weights, $A$ and $B$, $A$ must weigh 1 lb and $B$ 3 lbs. These two pieces enable us to weigh loads of 1, 2, 3, 4 lbs. If we then choose a third piece $C$ such that its weight $c$ = 2 x 4 + 1 = 9 lbs, it then becomes possible to use the three pieces $A,B,C$ to weigh all integral loads from 1 to $c$+ 4 = 9 + 4= 13.

Finally, if we choose a fourth piece $D$ such that its weight $d$ = 2 x 13 + 1 = 27 lbs, the four weights $A,B,C,D$ then enable us to weigh all loads from 1 to 27 + 13 = 40 lbs. 

Conclusion. The four pieces weigh 1, 3, 9, 27 lbs.

I really can't quite grasp this rather verbose text book explanation and, naturally enough, find my base 3 explanation much simpler to understand. Overall, this has been an interesting exercise and really got me thinking so I'll probably attempt more of these.