The Coin Problem

Here is a problem: You have 10 coins. One of these coins is heavier than the others, but they are all otherwise identical. You have a balance scale which you can use to compare the weights of any two sets of coins. You must devise a strategy to find the heavier coin in the minimum number of weighs (in the worst case).

The solution is simple. Split into two groups of 5 and compare those two. Select the heavier of the two sets and compare two sets of two in there. If they are equal, it must’ve been the one you didn’t compare. If they are not, you compare the two on the heavier side to finally find the heaviest. So it takes only 3 weighs.

Now, what if the odd coin out is either heavier than the others or lighter than the others but you don’t know which? In fact, it is still possible to do it in three goes. The following diagram shows you how.

 

 

The ten coins are labelled as shown at the top. ‘A’ is short for A1 + A2 + A3, and similarly for ‘B’ and ‘C’. The underlines denote that the coin is a known reference (i.e. known to be neither heavier nor lighter). If A and B are not the same weight, we assume A is heavier (as otherwise you can just relabel them).

Note that in every path except for the first, which ends in D, you know not just which coin it is, but if the coin is heavier or lighter than the others.

Advertisements

One Response to The Coin Problem

  1. Nir says:

    As an extension, try 12 coins with 3 weighings.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: