[Math] every integers from 1 to 121 can be written as 5 powers of 3

number theory

We have a two-pan balance and have 5 integer weights with which it is possible to weight
exactly all the weights integers from 1 to 121 Kg.The weights can be placed all on a plate but you can also put some in a dish and others with the goods to be weighted.

It's asked to find the 5 weights that give us this possibility. It also asks you to prove that the group of five weights is the only one that solves the problem.

Easily i found the 5 weights: 1 , 3 , 9 , 27 , 81

but i can' demonstrate that this group of five weights is the only one that solves the problem.

Can you help me ?

Thanks in advance !

Best Answer

Your five weights add to 121. If there were another set of weights, they would have to sum to at least 121. You can obtain a contradiction. If the lower four weights are the same, you need 81 to hit 121.

Show inductively that with one weight you can get to 1, with two to 4, with three to 13, with four to 40, with five to 121.

It works as follows - there are three possibilities for each weight - in either pan or in neither. There is one possibility for the case where no weights are in either pan, which weighs zero. The remaining cases come in pairs (swap the weights between pans, they weigh the same weight). These are all distinct (the ternary expansion of a number tells you how to allocate the weights) so the maximum number for $n$ weights is $\cfrac {3^n-1}2$.

In response to comment below - now work as follows. The above shows that the set $\{1, 3, 9, 27, 81\}$ works, and that it is efficient (each weight can be weighed in just one way). Suppose we have another set $a \le b \le c \le d \le e$ which does the same. We can immediately replace $\le$ by $\lt$ throughout, because if $a=b$ our set is not efficient, and we can't weigh $121$ distinct weights.

We naturally need $a+b+c+d+e=121$ since this will be the maximum we can weigh. In order to weigh $120$ we need $a=1$. We can't have $b=2$ else we can weigh $1=a=b-a$ (this is inefficient - note, this is where it is useful to have the inductive step in place) but to weigh $118$ we then need $b=3$. This enables us to weigh up to 4. If $c<9$ then $c-a-b \le 4$, and we can weigh the same using just $a$ and $b$ - so we are not efficient (using the inductive step again). If $c>9$ we can't weigh $121-9=112$.