Puzzles/Decision puzzles/Weighings Once More/Solution

From Wikibooks, open books for an open world
< Puzzles‎ | Decision puzzles‎ | Weighings Once More
Jump to navigation Jump to search

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 3n combinations possible.
  • Second Observation: A valid weighing for a object of weight x must satisfy the equation
Wl = Wr + x

where Wl and Wr are the sum of all weights on left resp. right side. x has a unique solution for every pair of Wl and Wr.

  • 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 34 = 2 • 40 + 1.


Now, we construct a minimum solution:

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

base3(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