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" ?