You have 12 coins. They are completely identical except six of them weigh 24g and the other six weigh 25g. You have only a balance scale to sort them out. What is the minimum number of weighings which guarantees all the coins to be sorted?

This method will sort the coins with a minuimum of 5 balances, and a maximum of 12.

Divide the 12 coins into 3 groups of 4 coins each. (Let c indicate a 24g coin, and C a 25g coin).

(1) Do 2-3 preliminary balances to determine the group weight relationships.

(2) If all 3 groups are of equal weight, then the coin distribution can only be (CCcc CCcc CCcc), and 3-9 additional balances will be required. For each of the 3 equal groups: divide it into two 2-coin subgroups, and balance them. If the 2 subgroups are equal, exchange 2 coins and balance them again. If they are still equal, one more coin exchange can produce inequality.

(3) If one group is lighter, and the other 2 are equally heavier, then the coin distribution must be (cccc CCCc CCCc), and 4 additional balances will be required. For each of the 2 equally heavier groups, divide it into two 2-coin subgroups, and balance them. Then balance the 2 coins of the lighter subgroup.

(4) If 1 group is heavier, and the other 2 are equally lighter, then the coin distribution must be (CCCC Cccc Cccc), and 4 additional balances are required. For each of the 2 equally lighter groups, divide it into two 2-coin subgroups, and balance them. Then balance the 2 coins of the heavier subgroup.

(5) If all 3 groups are of different weight, between 2 and 8 additional balances are required. First, divide the heaviest group into two 2-coin subgroups, and balance them. If they are equal, then the coin distribution must be (cccc CCcc CCCC). If not, then the distribution is (Cccc CCcc CCCc). (a) If the distribution is (cccc CCcc CCCC), divide the middle group into two 2-coin subgroups, and balance them. If they are equal, exchange 2 coins and re-balance them. If they are still equal, one more coin exchange will produce inequality. (b) If the distribution is (Cccc CCcc CCCc), first divide the lightest group into two 2-coin subgroups, and balance them. Then balance the 2 coins of the heavier subgroup. Next, divide the middle group into two 2-coin subgroups, and balance them. If the result is equality, exchange 2 coins and re-balance them. If they are still equal, one more coin exchange will produce inequality. Finally, divide the heavier group into two 2-coin subgroups, and balance them. Then balance the 2 coins of the lighter subgroup.















Edited on January 18, 2004, 11:18 pm

Posted by Penny on 2004-01-18 22:37:38