Saturday, May 01, 2010

Coin Weighing Problem

We are given nine coins. The coins are identical except that one coin is slightly heavier than the others. This can only be detected using a scale (i.e., given two groups of coins, the scale will tell you which group is heavier, or that both groups have equal weight). How many scale weighings are required to isolate the heavy coin?

2 comments:

Mark Reid said...

There's a more difficult version too that you might want to try: exactly the same set up except there are 12 coins and you do not know whether the counterfit is heavier or lighter than the real coins, only that it is a different weight. You are allowed to use the scales three times.

Lev Reyzin said...

2. Divide coins into 3 groups of 3. Test 2 groups against each other -- now you know which of the 3 groups is heaviest. Recurse once on that group. This is also an easy info-theoretic l.b.