マツシタのお勉強

Find the heavy bottle

Problem

You have 20 bottles of pills. 19 bottles have 1.0 gram pills, but one has pills, but one has pills of weight 1.1 grams. Given a scale that provides an exact measurement, how would you find the heavy bottle? You can only use the scale once.

Approach

Firstly we think about only two bottles. One of the bottles is heavy bottle and another is not. Then I take one pill from bottle1 and two pills from bottle2. If bottle1 was heavy bottle, the sum of the weight is 2.1 grams. Other hand if bottle2 was heavy bottle, the sum of the weight is 2.2 grams. That's because, the numbers of taking pills are different. Therefore if we take different count of pills from each bottles, we can find out the heavy bottle.

How to Solve

This problem can be solved by the following steps.

  1. name bottle each bottle the number from 1 to 20
  2. take number of pills from each bottle
  3. weigh the sum of the pills
  4. figure out the heavy bottle

Let's see the detail of the step 4. If all pills were same weight, the sum of the weight will be 210 (1+2+ 3+ ... + 20). But actually real sum value is different from 210. Taking remainder by subtracting 210 from real sum, we can figure out the heavy bottle.

(weight - 210) / 0.1 => bottle number