This king needs therapy if he wants to make new weights which can measure 10^100
King Mathematica of the shining empire of Scientia has had a brainwave. He wishes to remove imperial and standard units of mass out of his empire. Instead, he will create a new type of unit for mass. He calls it margs . He wants to create models for each weight using pure gold, but wants to use as less models as possible but has to have all weights with a model.
Now, this kingdom is not very sophisticated and has no weighing machine but it does have balancing scales. When the king manufactures the new weights (out of lead, of course), he wants to create as less weight types as possible. If he made only a 1 marg weght and a 4 marg weight, then people would be only able to weight 1 marg, 4 margs, 3 margs (by putting a weight on either side of a balancing scale) and 5 margs.
The king asks you, his wise man to tell him what the minimum number of models he needs to make to weigh all weights from 1 to 1 0 1 0 0 margs. You think and reply to him correctly. What did you say?
The answer is 211.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
3 solutions
@Patrick Heebels , we really liked your comment, and have converted it into a solution. If you subscribe to this solution, you will receive notifications about future comments.
This question is similar to an old question . In this case, we are finding the minimum integer n such that 3 n > 1 0 1 0 0 . Apply log to both sides, we get n > 2 0 9 . 5 9 … . So the answer is 2 1 0 .
Dear Pi Han Goh,
I answered that 211 weights are required. My answer was not accepted and the answer of 210 is supposed to be the correct answer.
When I read your solution and reference to the old question "Weighing Trouble" I tried my same strategy on this, essentially the same, problem and got the correct answer.
To me the answers to these both questions are therefore not consistent.
We all agree that using weights that are powers of 3 are to be used, i.e. 3 0 = 1 , 3 1 = 3 , 3 2 = 9 , etc...
We need as many weights such that:
k = 0 ∑ n 3 k ≥ 1 0 1 0 0 ⇒
3 − 1 3 n + 1 − 1 ≥ 1 0 1 0 0 ⇒
n ≥ lo g 3 ( 2 ⋅ 1 0 1 0 0 + 1 ) − 1 ≈ 2 0 9 . 2
Therefore the smallest integer n that satisfies the inequality is n = 2 1 0 .
However that means that we need weights that weigh:
3 0 , 3 1 , 3 2 , … , 3 2 1 0
This means to me that a total of 2 1 0 + 1 = 2 1 1 weights are required.
I reason that with 210 weights you can weigh a maximum of 2 3 2 1 0 − 1 ≈ 7 . 8 4 × 1 0 9 9 which is not sufficient. With 211 weights however we can weigh a maximum of 2 3 2 1 1 − 1 ≈ 2 . 3 5 × 1 0 1 0 0
Can you sir Pi Han Goh or the challenge master, sir Sharky Kesa, point out the flaw in my reasoning?
Log in to reply
I agree. The "correct" answer is in fact wrong. If anyone thinks that n weights can make any number up to 3^n, then please demonstrate how to make the values {1,2,3} with only 1 weight.
Log in to reply
Oh, yes, sorry! Forgot about the 3 0 weight. I'll change the answer.
Log in to reply
@Sharky Kesa – Can someone explain why are we going ahead with powers of 3. (Totally confused) >_< @Sharky Kesa
Log in to reply
@Hrishik Mukherjee – If you want to keep all the weights on one side of the scales, you would use powers of 2. By swapping the weights side to side you can weigh using less weights: To weigh 1: use the "1" To weigh 2: use the "3" with the "1" on the side of the thing you are weighing ... To weigh 40: use the "27", "9", "3" and "1" To weigh 41: use the "81" with the four lower weights on the other side ... ( I won't do all the way up)
Log in to reply
@Chris Cooper – I kinda understood. Thank you :)
Log in to reply
@Hrishik Mukherjee – In response to Sharky Kesa:
Thank you for acknowledging that my solution was in fact the correct one and thank you for changing the answer accordingly.
Kind regards.
Log in to reply
@Patrick Heebels – In response to Hrishik Mukherjee, addendum
What might interest you is the proof that once we have chosen to use powers of 3 as our choice of weights, that with n weights (from 1 up to n ) we are able to make all integer weights from 1 up to 2 3 n − 1 .
Define statement P ( n ) as follows: "With n + 1 weights weighing from 3 0 , 3 1 , … , 3 n we can make all integral values from 1 up to 2 3 n + 1 − 1 .
Proof by induction:
(i) P ( 0 ) means we have 1 weight, namely 3 0 = 1 . And also 2 3 0 + 1 − 1 = 2 3 − 1 = 1 .
Assume P ( n ) to be true for n = m and then take a look at the statement P ( m + 1 ) and proof that it holds.
(ii) We now have weights weighing from 3 0 , 3 1 , … , 3 m , 3 m + 1 . The induction hypothesis tells us we may assume that with the weights from 3 0 , 3 1 , … , 3 m we can weigh all integer values from 1 up to:
2 3 m + 1 − 1 = 2 1 ⋅ 3 m + 1 − 2 1
By subtracting each and every one of these reachable integer values, i.e. 1 , 2 , 3 , … , 2 3 m + 1 − 1 from the biggest weight 3 m + 1 we are able to weigh as low as:
3 m + 1 − 2 3 m + 1 − 1 = 3 m + 1 − 2 1 ⋅ 3 m + 1 + 2 1 =
2 1 ⋅ 3 m + 1 + 2 1 = ( 2 1 ⋅ 3 m + 1 − 2 1 ) + 1
So now we are already able to weigh weights from 1 up to 3 m + 1 .
Finally by adding each and every one of the previously mentioned reachable integer values, i.e. 1 , 2 , 3 , … , 2 3 m + 1 − 1 to the biggest weight 3 m + 1 we are able to weigh as high as:
3 m + 1 + 2 3 m + 1 − 1 = 3 m + 1 + 2 1 ⋅ 3 m + 1 − 2 1 =
2 3 ⋅ 3 m + 1 − 2 1 = 2 3 ⋅ 3 m + 1 − 1 = 2 3 ( m + 1 ) + 1 − 1 = P ( m + 1 ) □
Log in to reply
@Patrick Heebels – Since I haven't learnt mathematical induction yet.. But I kinda understood what u said. Thanks a lot.
Cheers!
For 1,2,3,4 we need 1 and 3 but that means for the next number it has to be (1+3) * 2 + 1 =3 * 3 because if it were only double the total or less so far it would create overlap and thus be inefficient, to have 0 overlap one must double plus one since it would make the lower bound using the largest weight be sum of previous weights + 1
1,3,9 -> sum of geometric (obtained heuristically—I felt that it was geometric) ->
(1-r^n)/(1-r) = (3^n - 1)/2 from sum from 1st term to n-1 term
And from this we can see that if we apply the formula for the next number we get (3^n - 1)/2 * 2 + 1 = 3^n (the nth term), and thus we confirm that the nth term is 3^n.
So we need from 3^0 = 1 to 3^n where 3^n > 10^100
log base 3 both sides: n > 209.5 so n=210
number of terms from 0 to 210 = 210 + 1 = 211
so we need 211 distinct weights
We all agree that using weights that are powers of 3 are to be used, i.e. 3 0 = 1 , 3 1 = 3 , 3 2 = 9 , etc...
We need as many weights such that:
k = 0 ∑ n 3 k ≥ 1 0 1 0 0 ⇒
3 − 1 3 n + 1 − 1 ≥ 1 0 1 0 0 ⇒
n ≥ lo g 3 ( 2 ⋅ 1 0 1 0 0 + 1 ) − 1 ≈ 2 0 9 . 2
Therefore the smallest integer n that satisfies the inequality is n = 2 1 0 .
However that means that we need weights that weigh:
3 0 , 3 1 , 3 2 , … , 3 2 1 0
This means to me that a total of 2 1 0 + 1 = 2 1 1 weights are required.
What might interest you is the proof that once we have chosen to use powers of 3 as our choice of weights, that with n weights (from 1 up to n ) we are able to make all integer weights from 1 up to 2 3 n − 1 .
Define statement P ( n ) as follows: "With n + 1 weights weighing from 3 0 , 3 1 , … , 3 n we can make all integral values from 1 up to 2 3 n + 1 − 1 .
Proof by induction:
(i) P ( 0 ) means we have 1 weight, namely 3 0 = 1 . And also 2 3 0 + 1 − 1 = 2 3 − 1 = 1 .
Assume P ( n ) to be true for n = m and then take a look at the statement P ( m + 1 ) and proof that it holds.
(ii) We now have weights weighing from 3 0 , 3 1 , … , 3 m , 3 m + 1 . The induction hypothesis tells us we may assume that with the weights from 3 0 , 3 1 , … , 3 m we can weigh all integer values from 1 up to:
2 3 m + 1 − 1 = 2 1 ⋅ 3 m + 1 − 2 1
By subtracting each and every one of these reachable integer values, i.e. 1 , 2 , 3 , … , 2 3 m + 1 − 1 from the biggest weight 3 m + 1 we are able to weigh as low as:
3 m + 1 − 2 3 m + 1 − 1 = 3 m + 1 − 2 1 ⋅ 3 m + 1 + 2 1 =
2 1 ⋅ 3 m + 1 + 2 1 = ( 2 1 ⋅ 3 m + 1 − 2 1 ) + 1
So now we are already able to weigh weights from 1 up to 3 m + 1 .
Finally by adding each and every one of the previously mentioned reachable integer values, i.e. 1 , 2 , 3 , … , 2 3 m + 1 − 1 to the biggest weight 3 m + 1 we are able to weigh as high as:
3 m + 1 + 2 3 m + 1 − 1 = 3 m + 1 + 2 1 ⋅ 3 m + 1 − 2 1 =
2 3 ⋅ 3 m + 1 − 2 1 = 2 3 ⋅ 3 m + 1 − 1 = 2 3 ( m + 1 ) + 1 − 1 = P ( m + 1 ) □