Online Course Discussion Forum
Problem 1.10 help on MC II-B Number Theory
It looks that the instructor doesn't have a chance to explain the Problem 1.10 on MC II-B Number Theory in the lecture. Could you let me know why the weights needed are 1,3,9,27,81 in the solution with the base 3, not other bases? Thanks,
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.
社交网络