Source

I got this problem from Rustan Leino, who got it or a slight variation of it from Matthew Parkinson.

I solved it and wrote up my solution.

Problem

You are given a balance (that is, a weighing machine with two trays) and a
positive integer $N.$ You are then to request a number of weights. You pick
which denominations of weights you want and how many of each you want.
After you receive the weights you requested, you are given a *thing*
whose weight is an integer between $1$ and $N,$ inclusive. Using the
balance and the weights you requested, you must now determine the exact
weight of the *thing*.

As a function of $N,$ how few weights can you get by requesting?

Solution
Reveal

You need exactly $n = \lceil \log_3 N \rceil$ weights. We now show that this number of weights is both necessary and sufficient.

It's sufficent because you can use the weights $w_0, w_1, \ldots, w_{n-1}$ where each weight $w_i$ weighs $2 \cdot 3^i.$ We'll assume $N > 1$ and thus $n > 0,$ since the case $N=1$ is obvious.

With those weights, you can use the following procedure to compare the thing's weight to any weight $W$ that's positive, even, and less than $3^n$.

Let $D = (W + 3^n - 1) / 2.$ Because of $W$'s properties, $D$ is a positive integer less than $3^n$, so its ternary representation has fewer than $n$ digits. So, we can find $n$ ternary digits $d_0, d_1, \ldots, d_{n-1}$ such that $D = \sum_{i=0}^{n-1} d_i 3^i.$ Now, for each $j \in \{0, 1, 2\},$ let $I_j$ be the set $\{ i \mid d_i = j \}.$

On the left side of the balance, put the thing and, for each $i \in I_0,$ weight $w_i.$ On the right side, put, for each $i \in I_2,$ weight $w_i.$ Call the thing's weight $T.$ The total weight of the left side will be $T + \sum_{i \in I_0} 2 \cdot 3^i$ and the total weight of the right side will be $\sum_{i \in I_2} 2 \cdot 3^i.$ Thus, we are effectively comparing $T$ to \[ \left(\sum_{i \in I_2} 2 \cdot 3^i\right) - \left(\sum_{i \in I_0} 2 \cdot 3^i\right). \] This is equal to \[ 2 \left[\left(\sum_{i \in I_2} 2 \cdot 3^i\right) + \left(\sum_{i \in I_1} 1 \cdot 3^i\right) + \left(\sum_{i \in I_0} 0 \cdot 3^i\right) \right] - \left[\left(\sum_{i \in I_2} 2 \cdot 3^i\right) + \left(\sum_{i \in I_1} 2 \cdot 3^i \right) + \left(\sum_{i \in I_0} 2 \cdot 3^i\right)\right]. \] Since $I_0 \cup I_1 \cup I_2 = [0, n-1],$ the quantity in the first set of brackets is $D$ and the quantity in the right set of brackets is $\sum_{i=0}^{n-1} 2 \cdot 3^i = 3^n - 1.$ So, we are effectively comparing $T$ to $2D - (3^n - 1).$ This equals $W.$

So now we see we can use the above procedure repeatedly to compare the thing's weight to every even weight less than $3^n.$ Since $3^n$ is odd, that means we'll compare it to every even weight less than $3^n + 1.$ Since $N \leq 3^n$, we know $N < 3^n+1,$ so we know we'll compare $T$ to every even weight $\leq N.$ We now show that this is sufficient to determine $T.$ There are two cases to consider: $T$ is even and $T$ is odd.

If $T$ is even, then $T$ is one of the weights we'll compare against since $T \leq N.$ When we compare $T$ to $T,$ the balance will show the weights are equal and we'll learn the thing's weight.

We split the case of $T$ odd into three subcases: $T = 1$, $T = N$, and $1 < T < N.$ If $T = 1,$ then when we compare $T$ to $2,$ we'll see it's less than $2$ and conclude it must be $1.$ We know we can compare to $2$ since $2$ is even and $n > 0$ means $2 < 3^n.$ If $T = N,$ then when we compare $T$ to $N-1$, we'll see it's more than $N-1$ and conclude it must be $N.$ We know we can compare to $N-1$ because $T$ being odd makes $N-1$ even, and $N-1 \leq N.$ Finally, if $1 < T < N$, then when we compare $T$ to $T-1$ and $T+1$ we'll find it weighs more than the former and less than the latter, making its weight definitively $T.$ We know we can compare against both those weights because they're both even and $\leq N.$

Suppose you can get by with only $n-1$ weights. Then, there are only
$3^{n-1}$ ways you can arrange the items on the balance, since for each
weight you can either put it on the same side as the thing, put it on the
other side from the thing, or leave it off the balance entirely. We call two
arrangements *opposites* if they leave off the same weights and put the
remaining ones on opposite sides as each other with respect to the thing.

One of these arrangements is useless because it leaves all the weights off the balance, effectively comparing $T$ to $0.$ Furthermore, the other $3^{n-1} - 1$ arrangements can be partitioned into pairs of opposites. If one element of a pair is useful, comparing $T$ to some positive number $p,$ the other one is useless, comparing it to $-p.$ So, there are at most $(3^{n-1} - 1)/2$ useful arrangements.

For each $a$ such that $1 \leq a \leq N-1,$ if there's no arrangement comparing $T$ to $a$ and there's also no arrangement comparing $T$ to $a+1,$ then the weighings cannot distinguish between the cases $T=a$ and $T=a+1.$ Thus, for every adjacent pair of possible weights, at least one arrangement must cover one element of that pair. Thus, we must have at least $\lfloor N/2 \rfloor$ arrangements.

So, we must have $(3^{n-1} - 1)/2 \geq \lfloor N/2 \rfloor \geq (N-1)/2.$ This means $3^{n-1} \geq N,$ so $n \geq 1 + \log_3 N.$ However, this isn't possible since $n = \lceil \log_3 N \rceil.$ Thus, we need at least $n$ weights.