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?
(In reply to
re: Simple approach by John)
John -- good idea!
I think I can take this further, and get down to 8:
Take the master, and weigh against the first 5 other coins. If they are all the same, one more weighing will finish the problem. If not, then those 6 are fully known. Here is how to get the other 6 done in 3 weighings.
Case 1: we know there are 1 heavy and 5 light (or the other way around). Weigh them in three sets of two. As soon as one is not balanced we are done. This takes at most 3 weighings.
Case 2: we know there are 2 of one kind and 4 of the other (we know which). Label the coins A,B,C,D,E,F. Weigh A vs B and C vs D. If either pair is unbalanced, then weigh E vs F which will also be unbalanced, and the 2 of a kind will be known. If A==B and C==D, then we don't have to weigh E and F, they will match. Weigh A vs C. If they match, A==B==C==D, if they don't, we know which are the 2 and which are the 4. In either case, we can do it in 3 weighings.
Case 3: a split 3/3 distribution. Again, label them A,B,C,D,E,F. Weigh A vs B. Sorry, more cases:
A != B: then we know which is which, and we have 4 coins, split 2/2, and 2 weighings left. Weigh C vs D. If they balance, we know E==F and we can weigh C vs E. If C != D, then we know which is which, and can weigh E vs F and be done.
A == B: Weigh A vs C. If A == C, we know D==E==F and one more weighing will tell us which set is light. If A != C, we know everything about A, B, C. We can then handle D, E, F using your trick: weigh D vs E and we know everything.
In all cases, 8 weighings will suffice.
re(2): Simple approach
