Bachet’s Four Weights Problem
Here’s another puzzle from Henry Dudeney’s article “The World’s Best Puzzles”, The Strand Magazine, December 1908. According to Dudeney, this puzzle is originally from Problèmes plaisans et délectables qui se font par les nombres (Pleasant and delectable number problems), by French mathematician Claude Gaspar Bachet de Méziriac (1551-1636).[1]
You have four (integral) weights w1,w2,w3,w4 and a balance scale such that you can weigh any object weighing from 1 lb to 40 lbs (no fractions). The weights may go on either side of the scale (eg, with the object, or in the opposite pan). What are the wi?
This seems like a variation on the Frobenius coin problem, which in general is NP-hard. Fortunately, this specific instance is not.
where m depends on how many weights you have. We can also observe that the sum of all the weights must equal the weight of the heaviest object you can measure, and that object must weigh m pounds.
Then for the case n=1, you have a single weight w1=1, and you can weigh any object that weighs one pound (the interval 1:1). Now let’s look at the case n=2.
