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.
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
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):
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 !