The statement was
We have 10 identical bottles of identical pills (each bottle contain hundred of pills). Out of 10 bottles 9 have 1 gram of pills but 1 bottle has pills of weight of 1.1 gram. Given a measurement scale, how would you find the heavy bottle? You can use the scale only once.
And I misunderstood the problem as that the 9 bottles each had 1 gram worth of pills, so each pill in the 9 bottles would weigh in the range [0, 1].
My answer to this problem was like the original problem's solution, but to make it obvious which bottle it was, you needed to add more pills from each bottle.
Let's say we're weighing bottle 1, and we want to add pills from the remaining 9 bottles.
- If the answer is bottle 1, the weight will be in the range [110, 110+]
- If the answer is the last bottle that we don't add pills to the scale from, the weight will be in the range [1, 9]
- If the answer is bottle b and we added x pills from bottle b to the scale, the weight will be in the range [1+b*1.1, 8+b*1.1]
The lower bound is 1+b*1.1 because in the lowest case, all the pills from the bottles will be 0, and the +1 comes from putting the whole bottle of 1 on the scale.
The upper bound is 8+b*1.1 because we only need to add pills from all but 1 bottle since if the last bottle we don't use is the heaviest, the weight will be in the range [1, 9].
To avoid these weight ranges from conflicting so we can uniquely determine the heavier bottle, the number of pills added from each bottle will be in order from 1 to 10:
100, 10, 20, 30, 40, 50, 60, 70, 80, 0
The ranges of the weights for each of these amounts if that bottle is the heaviest will be:
[110, 110+], [12, 19], [23, 29], [34, 41], [45, 52], [56, 63], [67, 74], [78, 85], [89, 96], [1, 9]
No comments:
Post a Comment