Your boss liked how you solved the Tricky Pearls problem and has now given you a new one.
You have 5 bags of pearls. You are told that each bag contains either all genuine pearls, or all fake pearls. Real pearls weigh 10 grams and fake pearls weigh 9 grams.
Armed with a very precise scale, how can you figure out which bags contains the fake pearls with the fewest number of weighings?
The diference between this problem and the last is that you knew there was only one bag of fakes, but now there can be up to 5 bags of fakes. You can't use triangle numbers this time, you have to use binary notation.
Take one pearl from bag 1, two from bag 2, four from bag 3, eight from bag 4 and 16 from bag 5 [i.e. 2^(n - 1) from bag n.] (Nick - as you takeke them from their bags, you place them in separate baggies, so you can return them to their proper bags after the weighing.)
Weigh the 31 pearls, and subtract 9 * 31 = 279 from that weight. This result is the number of genuine pearls on the scale. Convert this number to a 5 digit binary number. Counting the places right to left, if the digit is a 0, the corresponding bag contains fakes, aand if it is 1, the bag has genuine pearls.
For example: 6 => 00110 would mean that bags 2 and 3 were genuine, and 1,4, and 5 were fakes, while 11 => 01011 means that bags 1,2,and 4 are genuine, and 3 and 5 are fakes.
|
|
Posted by TomM
on 2002-10-08 18:09:56 |
Less bags and more bags
