This is in continuation of Sorting Coins.

You have 18 coins. They are completely identical in every other respect except five of them weigh 24g, six of them weigh 25g and, the remaining seven weigh 26g. 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?

There are 18!/(5!*6!*7!) = 14,702,688 possible states from which one is to be identified. The balance scale can have 3 possible outcomes. The base-3 log of the number of possible states is just over 15.02, so at least 16 weighings would be required, and depending on logistics, maybe more, as we don't know if a scheme that guarantees only 16 can be worked out.

Posted by Charlie on 2012-03-28 09:44:53