The puzzle goes like this:
A set of 12 coins of similar shape and size contains one counterfeit coin, whose weight is different from that of the other coins. Find the coin using a balance and minimum number of weighing.
The catch of the problem is that it is not mentioned whether the counterfeit coin is lighter or heavier than the rest of the normal coins.
Lower Bound
Let us first examine what is the minimum number of weighing required to find the coin. We use information theory based approach for getting this.
Each weighing can have three different outcomes,
- left_side < right_side
- left_side = right_side
- left_side > right_side
Thus min number of weighing >= ceiling (log 12 base 3) = ceiling ( log(12)/log(3) ) = 3
Solution
Well, as it turns out, we need exactly 3 weighing. The method is kind of confusing to describe, so I drew a flowchart (PDF) for the same (click on the image for the full sized image):
Background
Campus recruitments were about to commence so I was in hunt for good puzzles to hone my problem solving skills. A friend of mine sent me this gem. I was used to tackling coin puzzles, but this was unique as the weight of the counterfeit coin was not given. I tried it and getting the 4 weighing solution was quite easy to get.
Next I gave this problem to my friends at IISc, Dyut, Abhiskek and Arghya. After a lot of attempts Dyut and Abhiskek could not improve upon my solution. After a few days I tried it again. Particularly the case where the first two groups were unequal. After a couple of attempts with a fresh mind, I cracked it. Later I found out that my friends had also figured out the solution from some other friend, who solved it at the very first go. Well there are no dearth of brilliant guys IISc !
how would you solve this problem in 3 weighings, if you were to find whether the odd-man-out is heavier or lighter than the rest?
ReplyDeleteBigyan,
ReplyDeleteAn excellent puzzle, and a good flowchart to go with.
However, I did not understand the case of (A, B, E) v (C, D, F). if you consider (A, B, E) < (C, D, F), couldn't it be that 'E' is the lighter coin, or one of C or D are heavier and not 'F', as you've considered while weighing 'A' and 'B'. In that case, would not another weighing be required, if 'A', B' and 'F' all turn out to have the same weights?
@ Igor
ReplyDeleteE cannot be the lighter coin as in the last weighing we have ensured G1<G2, i.e. {A,B,C,D} < {E,F,G,H}.
Similarly all your questions would be answered. Just follow the flowchart carefully.
@ doodlesandmusings
ReplyDeleteOut here, most of the cases also gives this additional information, so my guess would be that we can modify some parts of the flowchart to get the heavier or lighter answer also.