After figuring out the Trickier pearls problem you've just realized something. Being a pearl expert you know there are two types of oysters which each produce pearls exactly the same in every aspect except for weight. The pearls produced by the blue oysters weigh 10 grams and the ones produced by the black oysters weigh 11 grams, and of course fake pearls weigh 9 grams.

You have 5 bags and each of them either contains all fake pearls, all black oyster pearls or all blue oyster pearls. You have to find out which bags contain which kinds of pearls in the least amount of weighings possible. Assume every bag of pearls has an infinite amount of pearls.

On the scale, place 1 from bag 1, 3 from bag 2, 9 from bag 3, 27 from bag 4 and 81 from bag 5. From the total weight, subtract the 1089 that the total would be if they were all fake.

Express the result in base 3 numbers. The first position on the right contains a 0, 1 or 2 depending on whether bag 1 contained fake pearls or pearls from blue or black oysters respectively. The next position to the left (the 3's position) has the same significance for the second bag. The next position to the left (the 9's position) does so for the third bag, etc.

To convert a number to base-3 (ternary), divide the number by 3 and place the remainder on the extreme right of your answer. Take the quotient and divide it by 3. Place the remainder just to the left of the preceding remainder, and continue with the new quotient. Keep repeating until you get a quotient of zero (of course place the corresponding remainder on the left of the answer).

For example, if the total weight were 1300 grams, you'd subtract 1089, giving 211. Convert this to ternary: 211/3 = 70 w/rem 1; 70/3 = 23 w/rem 1; 23/3 = 7 w/rem 2; 7/3 = 2 rem 1; 2/3 = 0 w/rem 2. Thus the ternary representation is 21211, and the 5th and 3rd bags contain pearls from black oysters and the rest contain pearls from blue oysters, and there were no fakes.

Posted by Charlie on 2003-04-02 09:12:36