Smallest Set of Weights for Two-Pan Balance

From ProofWiki
Jump to navigation Jump to search

Classic Problem

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

Let this balance be such that weights may be placed in either of the two pans.

What is the smallest set of weights needed to weigh any given integer weight up to a given amount?


Solution

A set of weights up to $3^m$ in the sequence $\sequence {3^n}$:

$1, 3, 9, 27, \ldots$

allows one to weigh any given integer weight up to $\dfrac {3^{m + 1} - 1} 2$.


Proof

Place the item to be weighed in the left hand pan of the balance.

Let it weigh $n$.

Let $n$ be expressed in balanced ternary representation.

From Representation of Integers in Balanced Ternary, $n$ can be uniquely so represented.

With $m$ digits, we can count up to $\dfrac {3^{m + 1} - 1} 2$.

We use the balanced ternary representation to model how to place the weights.

Let the digits of $n$ in such a representation be numbered $0, 1, \ldots, m$ from the least significant digit to the most significant digit.

The $k$th digit represents the weight which weighs $3^k$.

When the $k$th digit is $1$, place weight $3^k$ in the right hand pan.

When the $k$th digit is $\underline 1$, place weight $3^k$ in the left hand pan.

When the $k$th digit is $0$, place weight $3^k$ in neither pan.

This will make the balance level.

$\blacksquare$


Examples

Weights up to $40$ Units

Let $S$ be the smallest set of weights needed to weigh any given integer weight up to $40$ units.

Then $\size S = 4$.


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 two-pan balance version of this problem was solved by Claude Gaspard Bachet de Méziriac.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Smallest_Set_of_Weights_for_Two-Pan_Balance&oldid=594599"