0
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ May 31 '20 at 14:55
  • $\begingroup$ @JohnBrookfields Yeah that's exactly what I thought! like base 6 or 5 ... but nope you have only 1 of each $\endgroup$
    – CSch of x
    May 31 '20 at 14:57
  • $\begingroup$ Yes, @PeterForeman, I thought the same too. I was just editing that comment for that and working on the math $\endgroup$ May 31 '20 at 14:58
2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Thank you for the comment! Is it possible to prove using induction? or the way you specified is easier? Thanks! $\endgroup$
    – CSch of x
    May 31 '20 at 15:01
  • $\begingroup$ @PeterForeman Sorry I still dont understand... I have only 1 weight of each size, so base 3 cannot exist with 1 weight $\endgroup$
    – CSch of x
    May 31 '20 at 18:37
  • $\begingroup$ @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. $\endgroup$
    – J.G.
    May 31 '20 at 18:40
  • $\begingroup$ @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$. $\endgroup$
    – J.G.
    May 31 '20 at 18:44
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thank you for the comment! Is it possible to prove using induction? or the way you specified is easier? Thanks! $\endgroup$
    – CSch of x
    May 31 '20 at 15:02
  • $\begingroup$ @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. $\endgroup$
    – J.G.
    May 31 '20 at 15:21
  • $\begingroup$ @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) $\endgroup$
    – CSch of x
    May 31 '20 at 18:35

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.