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

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!

• Is there only one weight of each kind? If there are 2 weights of each kind, then it is possible. Because it will become a base 3 number system and hence any number can be written in that form. May 31 '20 at 14:55
• @JohnBrookfields Yeah that's exactly what I thought! like base 6 or 5 ... but nope you have only 1 of each May 31 '20 at 14:57
• Yes, @PeterForeman, I thought the same too. I was just editing that comment for that and working on the math May 31 '20 at 14:58

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

• Thank you for the comment! Is it possible to prove using induction? or the way you specified is easier? Thanks! May 31 '20 at 15:01
• @PeterForeman Sorry I still dont understand... I have only 1 weight of each size, so base 3 cannot exist with 1 weight May 31 '20 at 18:37
• @Remember1312 Two things. Firstly, sorry for responding to a comment you wrote on the other answer; that was a mistake. I've added an inductive argument to my answer. Secondly, the original coefficients from $-1$ to $1$ indicate whether you place a weight on one side, neither or the other, whereas coefficients from $0$ to $2$ are one more than such a $-1$-to-$1$ coefficient, not an overall number of copies needed. So even a $2$ doesn't mean you need two identical weights.
– J.G.
May 31 '20 at 18:40
• @Remember1312 An $n=2$ example: to weigh $11$ add $(3^3-1)/2=13$, then note $24$ becomes $220$ in base $3$, so $a_0=-1,\,a_1=a_2=1$. Therefore, balance the $11$ and $1$ against $3$ and $9$.
– J.G.
May 31 '20 at 18:44

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.

• Thank you for the comment! Is it possible to prove using induction? or the way you specified is easier? Thanks! May 31 '20 at 15:02
• @Remember1312 I use the fact that integers from $0$ to $3^{n+1}-1$ have at most $n+1$ digits in base $3$. You could prove that by induction.
– J.G.
May 31 '20 at 15:21
• @J.G. I am still stuck on the proof, can you please give me a clue on where to start? I would prefer if it was using induction (complete or regular) May 31 '20 at 18:35