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ⁿ combinations possible.

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

Wl = Wr + 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⁴ = 2 • 40 + 1.

Now, we construct a minimum solution:

Lemma: The weighing set S(n) = {1, 3, ..., 3ⁿ} 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ⁿ⁺¹. By adding this weight on the left side, we can reach all solutions between 3ⁿ⁺¹ - (3ⁿ⁺¹)/2 = |S(n)| + 1 and 3ⁿ⁺¹ + (3ⁿ⁺¹)/2 = 3ⁿ⁺²/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₃(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