16
$\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$
25
$\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.

| improve this answer | |
$\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
  • 3
    $\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.

| improve this answer | |
$\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$ – user53152 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$ – user53152 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
2
$\begingroup$

Each of the 4 weights has 3 possibilities. It can be in the left pan, right pan or off the scale. That gives 3 to the fourth = 81 possibilities. Ignoring the case where all the weights are off the scale, the same weight is represented twice, once with the left side tipping and once with the right side tipping, giving 80/2 = 40 possibilities. We need at least 4 weights. We need to show that 4 weights suffices.

Let us designate the left pan as negative and the right pan as positive. Each weight placement w on the scale is multiplied by a coefficient of -1, 0 or 1, depending on whether the weight is on the left pan, off the scale, or in the right pan. We know that if the coefficients were instead 0, 1 and 2, we could represent the number in base 3 by assigning powers of 3 to the weights - 1, 3, 9 , and 27. The highest base 3 number = 2222 = 80 base ten.

Suppose we take a base 3 representation of the weight and subtract 1 from each of the coefficients. That would give a weight with coefficients -1, 0 and 1. Of course, subtracting 1 from each coefficient is equivalent to subtracting 1111 base 3 = 40 base 10. We adopt the following strategy. For any weight w from 0 to 40, add 40, then convert to base 3, and finally subtract 40 by subtracting 1 from each base 3 coefficient. Since w is at most 40 = 1111 base 3, w + 40 is between 1111 and 2222 base 3, giving the base 3 numbers with 4 columns from 40 to 80. Subtracting one from each column gives the four column numbers for 0 to 40 using -1, 0, and 1 as coefficients.

Here is an example. Let w = 17. w + 40 = 57 = 2010 base 3. Subtracting 1 from each column gives 1 -1 0 -1. We get 17 by placing 9 and 1 in the left pan and 27 in the right pan.

| improve this answer | |
$\endgroup$
  • $\begingroup$ This answer seems to be extending the already known and accepted solution with a different explanation (apparently motivated by @Ben Millwood's observation in this comment) and a useful "built-in" way to tell how to place the weights. I feel like it's still not exactly a solution to the problem, but more like a proof that the solution works, and a nice way to apply it. But much better than your earlier post; thanks for giving it another go! $\endgroup$ – Rubio Mar 10 at 7:17

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.