Smallest Set of Weights for One-Pan Balance
Classic Problem
Consider a balance for determining the weight of a physical object.
Let this balance be such that weights may be placed in one of the pans.
What is the smallest set of weights needed to weigh any given integer weight up to a given amount?
Solution
A set of $m$ weights in the sequence $\sequence {2^n}$:
- $1, 2, 4, 8, 16, \ldots$
allows one to weigh any given integer weight up to $2^m - 1$.
Proof
This is equivalent to the statement that every positive integer can be expressed uniquely in binary notation.
This in turn is an application of the Basis Representation Theorem.
$\blacksquare$
Examples
Weights up to $63$ Units
Let $S$ be the smallest set of weights needed to weigh any given integer weight up to $63$ units.
Then $\size S = 6$.
Also see
Historical Note
The question of how many weights are needed to weigh any given integer weight up to a given amount was considered by Leonardo Fibonacci.
The one-pan balance version of this problem was solved by Niccolò Fontana Tartaglia.
Sources
- 1974: W.W. Rouse Ball and H.S.M. Coxeter: Mathematical Recreations and Essays (12th ed.)
- 1986: David Wells: Curious and Interesting Numbers ... (previous) ... (next): $31$
- 1992: David Wells: Curious and Interesting Puzzles ... (previous) ... (next): Bachet: $108$
- 1997: David Wells: Curious and Interesting Numbers (2nd ed.) ... (previous) ... (next): $31$