# Puzzles/Decision puzzles/Weighings Once More/Solution

Pathetic drawing following

/|\ / | \ / | \# ---- | ---- | -------

Weight to be measured is #.

We prove, that 4 is the minimum size of a weighing set to measure the numbers from 1 to 40.

- First Observation: each weight of your weighing set can be in three states. It can be on the left side, on the right side or not on the scale at all. So, for n weights, there is a maximum of 3
^{n}combinations possible.

- Second Observation: A valid weighing for a object of weight x must satisfy the equation

W_{l}= W_{r}+ x

where W_{l} and W_{r} are the sum of all weights on left resp. right side. x has a unique solution for every pair of W_{l} and W_{r}.

- Third observation: if there is a valid weighing for a positive x, there must be a valid weighing for -x. For every weighing set there is a trivial solution for 0. If we want a solution for all numbers from 1 to 40, n must be at least 4, because 3
^{4}= 2 • 40 + 1.

Now, we construct a minimum solution:

Lemma: The weighing set S(n) = {1, 3, ..., 3^{n}} can measure all weights between 1 and |S(n)|.

Proof by induction:
For S(0) the lemma trivially holds.
Assume that the lemma holds for S(n). We will now prove that it holds for S(n+1).
Because S(n) is a subset of S(n+1), we can surely measure all weighs between 1 and |S(n)| = (3^{n + 1})/2 without using the weight 3^{n+1}. By adding this weight on the left side, we can reach all solutions between 3^{n+1} - (3^{n+1})/2 = |S(n)| + 1 and 3^{n+1} + (3^{n+1})/2 = 3^{n+2}/2 = |S(n+1)|. QED.

Because of |S(3)| = 40, a solution to the problem is the weighing set {1,3,9,27}, which is minimal.

Questions:

- Prove that this is a unique solution.
- Can somebody think about an extension to a "fourth dimension" ?

Algorithm for finding how to weigh a particular integer weight from 1 to S(n):

1 - Let x be the weight you want to find weighing set for it.

2 - Subtract x from S(n) and convert the result to base 3. Then zero pad to make the size of resulting string equal to the size of weighting set.

3 - Subtract one from each bit. Since the string is in base three, the result after subtraction is -1, 0, or 1. Reverse the sign of each number.

4 - Each digit determine where to use its corresponding positional weight in reverse order (i.e. 81, 27, 9, 3, 1). Zero means the corresponding weight not on the scale, +1 means on the right, and -1 on the left resp.

As an example suppose we want to know how to place each of 5 weights (1, 3, 9, 27, 81) to weigh 51.

S(n) = 121

121 - 51 = 70

base_{3}(70) = 2121, zero pad => 02121, subtract one from each digit => -1, 1, 0, 1, 0, reverse the signs => 1, -1, 0, -1, 0 => (+1 x 81) + (-1 x 27) + (0 x 9) + (-1 x 3) + (0 x 1) = 51

These digits determines the placing of weights: 81 on right resp, 27 on left, 9 out, 3 on left, and 1 out