Smallest Set of Weights for One-Pan Balance

From ProofWiki
Jump to navigation Jump to search

Classic Problem

Consider a set of balance scales for determining the weight of a physical object.

Let this set of scales 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


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