Online Course Discussion Forum

Problem 1.10 help on MC II-B Number Theory

 
 
Picture of Cory Li
Problem 1.10 help on MC II-B Number Theory
by Cory Li - Saturday, May 23, 2020, 1:35 PM
 

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,

 
Picture of Areteem Professor
Re: Problem 1.10 help on MC II-B Number Theory
by Areteem Professor - Wednesday, May 27, 2020, 12:25 PM
 

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.