Finding the counterfeit coin from a list of 9 coins

Question

Just came across this simple algorithm here to find the odd coin (which weighs heavy) from a list of identical weighing coins.

I can understand that if we take 3 coins at a time, then the minimum number of weighings is just two.

How did I find the answer ?

I manually tried weighing 4 sets of coins at a time, weighing 3 sets of coin at a time, weighing two coins at a time, weighing one coins at a time.

Ofcourse, only if we take 3 coins at a time then the minimum number of steps (two) is achievable.

The question is, how do you know that we have to take 3 coins ?

I am just trying to understand how to approach this puzzle instead of doing all possible combinations and then telling the answer as 2.

1 http://en.wikipedia.org/wiki/Balance_puzzle

Answer 1

The base-case is this:

How do you know that we should take three coins at a time ?

The approach :

1. First find the base-case.

Here the base-case would be to find the maximum number of coins from which you can find the counterfeit coins in just one-weighing. You can either take two or three coins from which you can find the counterfeit one. So, maximum(two, three) = three.

So, the base-case for this approach would be dividing the available coins by taking three at a time.

2. The generalized formula is 3^n - 3 = (X*2) where X is the available number of coins and n is the number of weighing's required. (Remember n should be floored not ceiled).

Consider X = 9 balls. 3^n = 21 and n is ceiled to 2.

So, the algorithm to tell the minimum number of weighing's would something be similar to:

algo_Min_Weight[int num_Balls]
{
   return log base 3 ([num_Balls * 2] + 3);
}

Answer 2

In each weighings, exactly three different things can happen, so with two weightings you can only see nine different overall things happening. So with each weighing, you need to be guaranteed of eliminating at least two thirds of the (remaining) possibilities. Weighing three coins on each side is guaranteed to do this. Weighing four coins on each side could maybe eliminate eight coins, but could also eliminate only five.

Answer 3

It can be strictly proved on the ground of Information Theory -- a very beautiful subject, that builds the very foundations of computer science.

There is a proof in those excellent lectures of David MacKay. (sorry but do not remember in which one exactly: probably one of the first five).