6
$\begingroup$

We have a balance scale, where can determine whether two quantities $a$ and $b$ satisfy $a>b$, $a=b$ or $a<b$.

Given an integer $w_n$, we want to be able to distinguish between weights of $1,2,\dots,w_n$ with some set of $n$ weights.

What is the maximum value of $w_n$ for each $n$?

Note: it is not $\displaystyle\sum_{i=0}^{n-1}3^i$, for example take the following (not necessarily maximal) configuration for $n=2$:

Weights are 1 and 4, maximum is 6:

  1. 1=1
  2. 2>1, 2+1<4
  3. 3+1=4
  4. 4=4
  5. 5=4+1
  6. 6>4+1
$\endgroup$
  • $\begingroup$ @Oray is that clearer? $\endgroup$ – boboquack Sep 17 '17 at 22:04
  • $\begingroup$ thanks! it is clear now... gonna check if it is not solved yet tomorrow, good night :) $\endgroup$ – Oray Sep 17 '17 at 22:06
  • $\begingroup$ @Lawrence I've gone for 'some set', does that clear things up? $\endgroup$ – boboquack Sep 18 '17 at 0:04
  • $\begingroup$ As written, since you don't constrain $n$, $w_n$ could be anything. E.g. suppose we're given $w_n = 1000$. Choosing $n=1000$ and $w_i = i$ gives a trivial solution. Suggested wording: Given integer $n$ and the freedom to pick any $n$ weights $w_1, ..., w_n$ so that you can distinguish any given integer weight from 1 to $w_n$ using the scale, what is the maximum value of $w_n$? $\endgroup$ – Lawrence Sep 18 '17 at 8:04
  • $\begingroup$ @Lawrence I'm afraid a recent edit might have turned the question on its head. Does this clear things up? $\endgroup$ – boboquack Sep 18 '17 at 8:30
9
$\begingroup$

The maximum value of $w_n$ is

$w_n = 3^n$

To see this, first note that

If we want to distinguish between $x$ and $x+1$, some combination of weights has to form a value in the interval $[x, x+1]$, otherwise those two values would give the same result for any weighing.

Generalizing for all $w_n$ values...

We need to be able to weigh exactly a value in $[1, 2]$, a value in $[2,3]$, a value in $[3,4]$,...

And the way to accomplish this with the least amount of weight combinations is

to cover two intervals with each single possible weighing combination, i.e. be able to weigh exactly $2$, $4$, $6$, ...

Knowing all of this, the biggest we can get is

With $n$ weights, we can weigh exactly at most $\displaystyle\sum_{i=0}^{n-1}3^i$ distinct positive values (as mentioned in the question).

This is because each weight has 3 possibilities: either it's used in the same pan as the weight we want to measure, or in the opposite pan or not at all, giving us $3^n$ possibilities. One of those is zero (from not placing any weight), and for each positive weight we can measure we can also measure a corresponding negative weight by swapping all weights from one pan to the other, so the total of distinct positive weights is $\frac{3^n-1}{2}$.

This means we can weigh at most $2$, $4$, ..., $2 \times \displaystyle\sum_{i=0}^{n-1}3^i$ exactly (by using the weights $2$, $6$, ... $2 \times 3^{n-1}$), being able to distinguish up to $w_n = 2 \times \displaystyle\sum_{i=0}^{n-1}3^i + 1 = 3^n$.

$\endgroup$
  • $\begingroup$ I'll accept this some time in the next 10 hours. $\endgroup$ – boboquack Sep 17 '17 at 23:03
  • $\begingroup$ ^vote with a note: Any chance of adding at least a link to explain how "with $n$ weights, we can weigh exactly $\displaystyle\sum_{i=0}^{n-1}3^i$ distinct values"? $\endgroup$ – humn Sep 17 '17 at 23:06
  • 1
    $\begingroup$ I added an explanation @humn, though as even this question itself takes this as a given, I assume elaborating 100% on that would be better left to a different question :) $\endgroup$ – ffao Sep 17 '17 at 23:23
5
$\begingroup$

It's easy to show the number of measurements which can be made exactly with $n$ weights is $\tfrac12(3^n-1)$, which is achieved by having weights of size 1, 3, 9, ... , 3n-1. Say the object to be measured is placed in the left pan. There are 3n – 1 ways to place weights on the scale, excluding the empty placement. However, if one placement allows you to measure $x$, then reversing the pans of all the weights (while keeping the target object in the left pan) would measure $-x$, so half of these placements are useless for positive measurements.

When you don't need an exact measurement, then

whenever you are able to measure $n$ and $n+2$, you are also able to measure $n+1$. That is, you can also measure one value in each of the gaps, including the gap above and below all the values you can measure. The number of gaps is equal to the number of exact measurements plus one, so you at most hope to measure $2\cdot (\tfrac12(3^n-1))+1 = 3^n$ values. This is achieved by using weights 2, 6, 18, 54, ... , 2·3n-1.

$\endgroup$
  • $\begingroup$ Oh dear, looks like ffao ninja'd you :P $\endgroup$ – boboquack Sep 17 '17 at 23:08
  • 1
    $\begingroup$ Oh yeah, he beat me by quite a lot! But I took the time to come up with an answer and figured I might as well post it $\endgroup$ – Mike Earnest Sep 17 '17 at 23:09

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.