Can Any Integral Weight Up to 121 Ounces Be Measured with Five Specific Weights?

[nocheesie]

This is a problem from my abstract algebra book written by Ted Shifrin:

A druggist has the five weights of 1, 3, 9, 27, and 81 ounces, and a two-pan balance. Show that he can weigh any integral amount up to and including 121 ounces. How can you generalize this result?

While I see how it's possible to obtain lots of different weights with these 5, I have absolutely no idea how I can generalize my result. Does anyone know the answer to this problem? Thanks a lot in advance.

 

[HallsofIvy]

The first step in generalizing a statement is to be sure you understand what is said. It is not just the case that " it's possible to obtain lots of different weights". The point is that it is possible to obtain every integer from 1 to 121 oz. Did you notice that 1+ 3+ 9+ 27+ 81= 121? Did you notice that 1, 3, 9, 27, and 81 are all powers of 3? How would you use those weights to weigh something that weighed 2 oz? 4 oz?

The second step is trying other special cases. What could you weigh if you had weights of 1, 2, 4, 8, 16 (powers of 2)? What about 1, 4, 16, 64, 256 (powers of 4)? Powers of 5?

 

[matt grime]

there are many generalizations for this,

key thing: 2 is 3-1.

usually you can weigh any amount up to n^(r+1) using n-1 weights each weighing 1,n,..n^r units. this is like taking the expansion of a number in base n.

here we would require two weights of each unit, apparently , but we only have one, so how does it work? cos where as to weigh two units would usually by 1+1, we can use 3-1, the minus meaning put it on the other side to the 3.

if the base were powers of 4 you couldn't weigh 2 units. you can do 1, and 3=4-1... but not two.

 

[robert Ihnot]

If we have two weights we need only to use one side of the scale. In base 2, we just write 1 or 0. So the max for 5 weights, 1, 2, 4, 8, 16 in base two will be written 11111, which is equal to 2^5-1 =31 in its extent. The base 4 as noted will not work because we can not write 2, since we have 1, 4, 16...

In base three, everything is written as 0,1,2. But we have no two in our weights, but we can use both sides of the scale. Example:

Take 210 base 3 = 2x9+1x3 = 21 base 10. We do not have the 2, but we can replace it with -1 (putting it on the other side of the scale) and "bump up" the digits like we would in base 10, getting not 210 base 3, but 1(-1)10 base 3 = 27-9+3 =21 base 10.

Now, 10211 can be bumbed up to 11(-1)11. But the number 10211 = 103 base 10 is less than 11111=121 base 10, and this situation will always happen since 02 =2 is less than 11 =4 base 10.

The problem is limited by the fact that can not "bumb up" on weight 81 because that is the highest of the weights, and so after 11111 base 3, we can go no higher because a 2 anywhere would require a 6th weight. So the max is 11111 = (3^5-1)/(3-1) = 121 base 3.