15
$\begingroup$

Suppose you want to create a set of weights so that any object with an integer weight from 1 to 40 pounds can be balanced on a two-sided scale by placing a certain combination of these weights onto that scale.

What is the fewest number of weights you need, and what are their weights?

$\endgroup$
24
$\begingroup$

It turns out that you need four weights, measuring 1, 3, 9, and 27 pounds.

The trick here is that you can put weights on both sides of the scale. If you have an object of 2 pounds on the left side, you can place the 3-lb. weight on the right side and the 1-lb. weight on the left side for the scale to balance.

Similarly, if the object weighs 5 pounds, you put the 9-lb. weight on the right side and the 3-lb. and 1-lb. on the left side.


If you have a set of weights that can balance any weight from $1$ to $N$ pounds, then they can also balance any weight from $-1$ to $-N$ pounds just by switching the sides of the scale that you place them on. So the next weight you'd want to add would weigh $2N + 1$ pounds, and then you can balance any weight from $1$ to $3N + 1$ pounds on the scale.

So, starting with the 1-lb. weight, which can balance any weight from $1$ to $1$ pounds, we get $2(1) + 1 = 3$ pounds for the next weight, and they can balance anything up to $1 + 3 = 4$ pounds.

Then, for those two weights, we get $2(4) + 1 = 9$, and they can balance up to $1 + 3 + 9 = 13$ pounds.

And finally, for all three of those weights, we get $2(13) + 1 = 27$, and they can balance up to $1 + 3 + 9 + 27 = 40$ pounds, as required.

In general, to measure any weight up to $n$ pounds, you will need at least $\lceil\log_3(2n)\rceil$ weights due to the above formula.

$\endgroup$
  • 2
    $\begingroup$ This has an interesting tie-in to base 3. Notice each weight is a power of 3. It turns out you can represent any number as the difference of two base 3 numbers whose digits are only 0s or ones... For example, 5 in decimal is 12 in base 3, which can be rewritten as 100 - 11 (9 - 4). The next important detail is that you won't have a "1" in the same "place" in both numbers. So if you convert the number to this representation, you can put the weights corresponding to the positive number on the empty side, and the weights corresponding to the negative number on the side with the mystery weight. $\endgroup$ – TheRubberDuck Sep 19 '14 at 20:59
  • $\begingroup$ Well, @EnvisionAndDevelop, that's just a consequence of each weight having three possible states, either on the left side, on the right side, or off the scale. If you have $k$ weights with $n$ possible positions, then the total possible number of output is naturally going to be $n^k$. In the case of numbers in base 3, it's each place value either being 1 on the first number only, 1 on the second number only, or 1 on both/neither. $\endgroup$ – Joe Z. Sep 20 '14 at 1:16
  • $\begingroup$ While "3 states" tends to correspond directly to "base 3", it's not necessarily true that arithmetic in base 3 will mean anything. I'm not just talking about arbitrarily assigning 0/1/2 to different states and different "places" to the known weights; I'm taking it further by also representing the act of weighing as an equation. I don't think that's a natural consequence of having k objects with n states. $\endgroup$ – TheRubberDuck Sep 22 '14 at 14:14
  • 2
    $\begingroup$ You can think of the solution as base 3 except where the digits are not 0, 1, or 2 but rather 0, 1, or -1. $\endgroup$ – Ben Millwood May 23 '15 at 16:43
3
$\begingroup$

The minimum is still four weights for up to 40 pounds, but you can do it a bit more efficiently than the previous answer. Assuming you can also tell if a set of weights is heavier/lighter than another set and not just if they are equal, we can also find out the weight of an object through comparisons with other weights. For example, with a single weight weighing $2$ pounds, we can find weights within the range of $1$ to $3$. Using $x$ as our mystery weight, we can find all values as:

  • $1: x < 2$
  • $2: x = 2$
  • $3: x > 2$

Using two weights, the new one being size $6$, we can find the values of mystery weights up to $9$ pounds.

  • $1$ and $2$ are the same as the above
  • $3:$ $x > 2$ and $x + 2 < 6 $
  • $4:$ $x + 2 = 6 $
  • $5:$ $x + 2 > 6$ and $x < 6 $
  • $6:$ $x = 6 $
  • $7:$ $x > 6 $ and $ x < 6+2 $
  • $8:$ $x = 6 + 2 $
  • $9:$ $x > 6 + 2 $

Utilising this, the maximum values for any integer weight up to $n$ pounds is only $\lceil\log_3(n)\rceil$ rather than $\lceil\log_3(2n)\rceil$. The four weights we need for $n=40$ are 2, 6, 18 and 54. This will also allow you to find weights up to a $(2 + 6 + 18 + 54) + 1 = 81$ pounds.

$\endgroup$
  • 1
    $\begingroup$ @user477343 I"m new to the Puzzling exchange, but are all the spoiler tags really neccesary, especially as the current accepted answer doesn't have any? $\endgroup$ – Jo King Oct 13 '18 at 6:04
  • 1
    $\begingroup$ At PuzzlingSE it is customary to use spoilers as a step-by-step reveal mechanism. One could possibly combine some of the above into single ones (i.e. the bullet list as one single spoiler) though. Generally it is considered good formatting to have some clear text between each spoiler. I see it as ‘have a break and think if you can get the next piece by yourself’ opportunity. So for me, the above is also fine. $\endgroup$ – BmyGuest Oct 13 '18 at 6:11
  • 1
    $\begingroup$ Looking around, I haven't found any site policies on spoiler tags. I've also found a lot of debate over spoiler tag only edits on Meta with no clear winners. As such, due to the fact that this is an old question and the currently accepted answer already spoils a majority of the puzzle, I've decided to revert the edit. $\endgroup$ – Jo King Oct 13 '18 at 6:31
  • 2
    $\begingroup$ @JoKing very smart! I believe this is another very effective valid solution and a very smart one! I like it a lot... $\endgroup$ – Oray Oct 13 '18 at 9:29
  • 2
    $\begingroup$ Unfortunately I don't believe this is valid (@Oray) since the question specifically asks about "balancing" weights, not measuring them. Clearly an inequality is not balanced. $\endgroup$ – boboquack Oct 13 '18 at 10:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.