While this is a familiar problem, I never spent time to think about it. Yesterday this problem was tossed in an Information Theory class.

Given 12 coins, possibly 1 fake coin (heavier/lighter). Using a scale to weigh at most 3 times, find out if there is a fake coin. If there is, find it, and find out if it’s heavier or lighter than the real coins.

So the common way to solve think about this is trial and errors. But this is an Information Theory class. So I wanted something more systematic.

We want to find out such a solution, and then prove that there’s no solution using 1 or 2 times. Then we can prove that 3 is the optimal number. It turns out that the second part is easier to prove.

Suppose we label coins from 1-12. Then there’ll be 25 possible inputs: no fake coin, or (fake coin=1..12)x(fake coin heavier/lighter). With a decision tree having at most 3 branches per node (scale returning heavier/lighter/balanced), we need a depth of 3 to cover those inputs. Moreover, when the depth is 3, the first and second levels all have full degrees of 3.

This helps a lot in pruning the invalid solutions. For example, we may consider weighing 3vs3 in the first step. Suppose 3A=3B (3 is the number of coins, A/B is to denote their side). Then we have 6 coins left with 2 steps. 6 coins -> 13 possibilities, and clearly there is no solution in 2 steps.

It boils down to 4Avs4B.

If 4A>4B (similarly for 4B>4A), there are 8 possible cases (each coin can be fake). 2 steps might be able to cover (3*3>8). We weighs 2A+B vs 2A+B.

  • 2A+B=2A+B–> the fake coin is among the two unweighed Bs. Just compare them will work.
  • 2A+B>2A+B–> the fake one is among the left 2A and the right B. Just compare 2A’s will work.

If 4A=4B, we have 4 coins left, there are 9 possible inputs for those 4 coins. Hmm, tight bound indeed, because with 2 steps left we can only cover as much as 9 possible inputs as well. Here we weighs 1 real + A vs. 2B.

  • ‘=’, test the left over coin
  • ‘>’, compare the Bs
  • ‘<‘, compare the Bs, too.

The fun thing about this solution is that it is still found through brute force, but with guidance from the bounds we proved at the beginning.

Advertisements