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

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 ?

This seems like a variation on the Frobenius coin problem, which in general is NP-hard. Fortunately, this specific instance is not.

As before, here’s Chirico’s *The Mathematicians* for you to look at
while you try to solve this. Solution below.

## The Solution #

The four weights are (1, 3, 9, 27). Before we confirm this computationally, let’s compute the solution using induction.

Let’s rephrase the problem as

You have

weights… such that you can weigh any number of pounds in the range `1:m`

….

where

Then for the case

### 1. The weights can weigh any object from 1 to 4 pounds. #

I’ll use

is weighed as

is weighed as

is weighed as

is weighed as

You can see from the above that the general form of the solution is

where

Let’s just see what that looks like in R:

```
library(poorman)
signs = c(-1, 0, 1)
S = expand.grid (s1 = signs,
s2 = signs)
knitr::kable(S)
```

s1 | s2 |
---|---|

-1 | -1 |

0 | -1 |

1 | -1 |

-1 | 0 |

0 | 0 |

1 | 0 |

-1 | 1 |

0 | 1 |

1 | 1 |

Let’s take the linear combination of `s1`

and `s2`

, using the weights
(1, 3).

```
S = S |>
mutate(x = 1 * s1 + 3 *s2)
knitr::kable(S)
```

s1 | s2 | x |
---|---|---|

-1 | -1 | -4 |

0 | -1 | -3 |

1 | -1 | -2 |

-1 | 0 | -1 |

0 | 0 | 0 |

1 | 0 | 1 |

-1 | 1 | 2 |

0 | 1 | 3 |

1 | 1 | 4 |

You can confirm for yourself that using another pair of weights won’t necessarily give you 9 unique values.

We are only interested in the positive values for our problem. We can calculate that the number of positive values is

In other words, the weights (1, 3) can weigh the values `1:4`

.

### 2. The case of three weights #

How many values can we weigh with three weights, and what are they? It’s
clear that `1:4`

can be represented as

We know that

### 3. Finally, the case of four weights #

We can calculate that

Now let’s confirm it.

```
S = expand.grid (s1 = signs,
s2 = signs,
s3 = signs,
s4 = signs) |>
mutate(x = 1*s1 + 3*s2 + 9*s3 + 27*s4) |>
filter(x > 0)
# confirm we have the values 1:40
stopifnot(S$x == 1:40)
knitr::kable(S)
```

s1 | s2 | s3 | s4 | x | |
---|---|---|---|---|---|

42 | 1 | 0 | 0 | 0 | 1 |

43 | -1 | 1 | 0 | 0 | 2 |

44 | 0 | 1 | 0 | 0 | 3 |

45 | 1 | 1 | 0 | 0 | 4 |

46 | -1 | -1 | 1 | 0 | 5 |

47 | 0 | -1 | 1 | 0 | 6 |

48 | 1 | -1 | 1 | 0 | 7 |

49 | -1 | 0 | 1 | 0 | 8 |

50 | 0 | 0 | 1 | 0 | 9 |

51 | 1 | 0 | 1 | 0 | 10 |

52 | -1 | 1 | 1 | 0 | 11 |

53 | 0 | 1 | 1 | 0 | 12 |

54 | 1 | 1 | 1 | 0 | 13 |

55 | -1 | -1 | -1 | 1 | 14 |

56 | 0 | -1 | -1 | 1 | 15 |

57 | 1 | -1 | -1 | 1 | 16 |

58 | -1 | 0 | -1 | 1 | 17 |

59 | 0 | 0 | -1 | 1 | 18 |

60 | 1 | 0 | -1 | 1 | 19 |

61 | -1 | 1 | -1 | 1 | 20 |

62 | 0 | 1 | -1 | 1 | 21 |

63 | 1 | 1 | -1 | 1 | 22 |

64 | -1 | -1 | 0 | 1 | 23 |

65 | 0 | -1 | 0 | 1 | 24 |

66 | 1 | -1 | 0 | 1 | 25 |

67 | -1 | 0 | 0 | 1 | 26 |

68 | 0 | 0 | 0 | 1 | 27 |

69 | 1 | 0 | 0 | 1 | 28 |

70 | -1 | 1 | 0 | 1 | 29 |

71 | 0 | 1 | 0 | 1 | 30 |

72 | 1 | 1 | 0 | 1 | 31 |

73 | -1 | -1 | 1 | 1 | 32 |

74 | 0 | -1 | 1 | 1 | 33 |

75 | 1 | -1 | 1 | 1 | 34 |

76 | -1 | 0 | 1 | 1 | 35 |

77 | 0 | 0 | 1 | 1 | 36 |

78 | 1 | 0 | 1 | 1 | 37 |

79 | -1 | 1 | 1 | 1 | 38 |

80 | 0 | 1 | 1 | 1 | 39 |

81 | 1 | 1 | 1 | 1 | 40 |

And we are done. At this point, I’ll note that we’ve just re-invented a
signed base-3 number system: digit

Among Bachet’s accomplishments are a method of constructing magic squares; a way of solving indeterminate equations with continued fractions; the proof of Bézout’s Identity; and a Latin translation of

*Arithmetica*by Diophantus (he of the Diophantine equations). Famously, Fermat’s last theorem was a scribbled margin note on his copy of this very translation. ↩︎