Determining integral weights

Question

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

Answer 1

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$.

Answer 2

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, ... , 3^n-1. Say the object to be measured is placed in the left pan. There are 3ⁿ – 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·3^n-1.