This question already has an answer here:
- N balls and a scale 4 answers
Most people are familiar with the following problem:
A well-known example has nine (or fewer) items, say coins (or balls), that are identical in weight save for one, which in this example is lighter than the other —a counterfeit (an oddball). The difference is only perceptible by weighing them on scale—but only the coins themselves can be weighed. Is it possible to isolate the counterfeit coin with only two weighings?
To find a solution, we first consider the maximum number of items from which one can find the lighter one in just one weighing. The maximum number possible is three. To find the lighter one we can compare any two coins, leaving the third out. If the two coins tested weigh the same, then the lighter coin must be one of those not on the balance. Otherwise, it is the one indicated as lighter by the balance.
Now, imagine the nine coins in three stacks of three coins each. In one move we can find which of the three stacks is lighter (i.e. the one containing the lighter coin). It then takes only one more move to identify the light coin from within that lighter stack. So in two weighings we can find a single light coin from a set of 3 X 3 = 9.
By extension, it would take only three weighings to find the odd light coin among 27 coins, and four weighings to find it from 81 coins.
But what if you have an unknown number of coins, one being lighter than the other, and you want to know the minimum number of times you will have to use the scale to find the odd one out.
Does anyone know of a formula to calculate it?