Online Course Discussion Forum

Problem 1.10 help on MC II-B Number Theory

 
 
ProfessorAreteem的头像
Re: Problem 1.10 help on MC II-B Number Theory
ProfessorAreteem - 2020年05月27日 Wednesday 12:25
 

The idea is to be able to weight any object of (integer) weight at most $100$ grams by placing the object on one pan (and maybe some weights) and weights on the other pan.

This could be easily done with weights of $1$, $2$, $4$, $8$, $16$, $32$, and $64$ grams by writing the weight in base $2$ and using the corresponding weights for where we have $1$'s. Note this would require $7$ different weights, and we would only use weights on the pan that does not have the object.

If we try the same with base $3$, we would have weights of $1$, $3$, $9$, $27$, and $81$ grams. Using the weights only on the pan that does not have the object would require us to have $2$ of each of the weights, so we would require $2 \times 5 = 10$ weights in total. This can be fixed by using some weights on the same pan that has the object. Say, for example, you have an object that weighs $76$ grams; in base $3$ this number is $2211_3$. Notice that $2211_3 = 10011_3 - 100_3$ ($76 = 85 - 9 = 81 + 3 + 1 - 9$), so we can place weight with weight $9$ in the same pan as the object, and the weights with weight $81$, $3$ and $1$ on the other pan. This can always be done. If a number in base $3$ has a digit $2$ somewhere, it can be written as the difference of two numbers that have only $1$'s and $0$'s. Thus this allows us to use only $5$ weights. 

This trick would not work with other bases, so base $3$ yields the least number of weights.