Prove you can weigh any number between 1 and $\frac{3^{n+1} -1}{2}$ using $n+1$ weights - Discrete

Question

You have $n+1$ weights, with each weighing $1,3,9, \dots, 3^n$ (one of each)

Prove that you can weigh with a traditional scale ( The one with two bowls) each integer weight between $$1 ~~~~~\text{And }~~~~~\frac{3^{n+1} -1}{2}$$

My go:
This was very confusing to me because I did not understand well how you can possibly weigh, let's say $4$ (Maybe it's just putting $1+3$ ?)

I tried proving using induction:

1. If $n=0$ then we have $1$ weight weighing 1, and so we can weigh $\frac{3^1 -1}{2} ~~~ \text{And} ~~~ 1 = 1$ which is obvious.

2. Assume you have $n+1$ weights and you can weigh each integer between $1$ and $\frac{3^{k+1} -1}{2}$

3. Now we prove for $n = k+1$ so: $1$ to $\frac{3^{k+2}-1}{2}$ using the fact we can weigh $\frac{3^{k+1} -1}{2}$
   However I am stuck from here, I am clueless on how to use the fact we now have a weight of $1,3,9,\dots,3^k,3^{k+1}$

This seems like a known question, but I could not find anything on the web!
Thank you!

Answer 1

You need to prove each such integer is of the form $\sum_{j=0}^na_j3^j$ with $a_j\in\{-1,\,0,\,1\}$. Equivalently, adding $\sum_j3^j=\frac{3^{n+1}-1}{2}$ to the integer, we wish to prove every integer from $\frac{3^{n+1}+1}{2}$ to $3^{n+1}-1$ is of the form $\sum_{j=0}^na_j3^j$ with $a_j\in\{0,\,1,\,2\}$. But that's trivial; just write it in base $3$.

For an inductive variant, note the case $n=0$ is trivial, and to go from $n=k$ to $n=k+1$ write each integer from $0$ to $\frac{3^{k+2}-1}{2}$ as $3m+j$ with $-1\le j\le1,\,0\le m\le\frac{3^{k+1}-1}{2}$. By the inductive hypothesis, $m$ is of the form $\sum_{j=0}^ka_j3^j$, so $3m+j$ is of the same form but with the upper limit changed to $k+1$.

Answer 2

This is a well known problem.

One solution: write $n$ in base $3$ using the digits $0, \pm 1$ instead of the digits $0,1,2$. That's balanced ternary. Then use the coefficients to determine which weights go on which side of the balance. For example, $$ 16 = 27 - 9 - 3 + 1 $$ tells you that a weight of $16$ together with a $9$ and a $3$ will balance a $27$ and a $1$.

See https://www.cs.umb.edu/~eb/weighing.pdf for a paper on this topic in recreational mathematics, to appear in Mathematics Magazine.