## Thursday, 6 December 2012

### Some History of a Weighty Problem

A while back my blog got a nice mention on Gary Antonick’s “Numberplay” in the New York Times. That seems only fair as I was in the process of writing this post about one of the problems in his column which relates back to a nice old recreational problem from way back.

Gary’s version of the problem reads like this:

You have a balance scale and a single chain with thirteen links.
Each link of the chain weighs one ounce. How many links of the chain
do you need to break in order to be able to weigh items from 1 to 13 ounces
in 1-ounce increments?

This is a complication of the ancient problem in two ways, first by having to divide up the chain to get links, but also because it does not say how the weighing is to be performed.

In recreational history such “balance scale” problems have two basic forms, one in which all the weights have to go on one side to balance the unknown object, and a more clever approach (my bias) that allows known weights to be on both pans of the balance. In the end Gary’s solution goes for the both-sides solution which allows the chain to be cleverly cut in only one place (producing three sections of one, three, and nine lengths) allowing the weighing of any integer weight as requested.(Cut the fourth link and remove it for the one, leaving three on one end of it, and nine on the other)

Searching for older versions of the problem, I quickly found a post in the Problem of the Week section of a 1961 Popular Science.

This one particularly allows the weights to be placed on both pans of the balance.
The solution a month later not only provides the same solution approach as Gary’s column, but also gives a bit of (not quite correct) history of the problem.

The credits to Tartaglia and Bachet are not wrong, they are just not complete. This is understandable because the attributions probably came from one of the outstanding recreational mathematics books of the early 20th century, Mathematical Recreations and Essays by W.W.Rouse BALL, in which he also credits Bachet and Tartaglia:

Both solutions were given over three hundred years earlier than Tartaglia, by Leonardo of Pisa, often known now as Fibonacci. From Sigler’s translation of the famous Liber Abaci I find:

Fibonacci also posted a version avoiding the use of weights in both pans by requiring that the total weight for each increment must be presented on a given day, in this case where each ounce was represented in a valuable metal, requiring the powers of two solution.

From David Singmaster's notes on the Chronology of Recreational Mathematics I found an earlier reference, but do could find no more about the subject named there

"c1075 Tabar_: Mift_h al-mu`_mal_t - first Use of 1,3,9,... as Weights."

Even among those whose historical education has fully informed them of the earlier usages, the use of Bachet’s name is still common, as illustrated in a relatively new article which suggests a newer version of the problem from Edwin O’Shea’s BACHET’S PROBLEM: AS FEW WEIGHTS TO WEIGH THEM ALL
The generalized Bachet’s problem that we will explore here is that of finding appropriate weights when one replaces 40 with any positive integer. The full generalization, due to Park and studied further by Rødseth, not only tells us the minimum number of parts needed when 40 is replaced by any m but all possible ways to accordingly break up a given m. Furthermore, we can also count the number of distinct ways to break up such an m. For example, when we replace 40 by m = 25 we’ll still need no more than four parts but there are now nine ways to break up 25 to solve Bachet’s problem. Written as partitions with four parts, these are:
25 = 1 + 3 + 9 + 12 = 1 + 3 + 8 + 13 = 1 + 3 + 7 + 14
= 1 + 3 + 6 + 15 = 1 + 3 + 5 + 16 = 1 + 3 + 4 + 17
= 1 + 2 + 7 + 15 = 1 + 2 + 6 + 16 = 1 + 2 + 5 + 17

This brings us back to the NY Times version of the problem, but we might ask, how would you split the 13 link chain if you had to be able to pay any amount from 1 to 13 ounces of gold on a given day, as in the Fibonacci's second version of the problem?