Counterfeit coin problem
A balance puzzle or weighing puzzle is one of a number of logic puzzles based on the balancing of similar-looking items—often coins—to determine which holds a different value within a limited number of uses of the balance scales. These differ from puzzles that assign weights to items, in that only the relative mass of these items is relevant. n weighings are sufficient to find a bad coin among 3n − 1/2 coins.
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 others—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 .
...
Wikipedia