You have ten coins, but two are fake, and weigh a little less. How many times do you have to use a two arm scale, in order to pick out the two fakes?
There are C(10,2) = 45 possibilities as to which might be the two fake coins. Each weighing on a balance scale has three possible outcomes: left light, both equal, right light. So with two weighings you'd have 9 possible pairs of outcomes. With three weighings you'd have 27 possible sequences of outcomes. With four weighings you'd have 81 possible sequences of outcome--theoretically enough to distinguish the 45 possible combinations of two of the ten coins being light. You certainly can't do it in fewer weighings than four.
The first weighing can't be of 1 coin against another, as there are 29 of the 45 possibilities that would result in a balanced pair of pans, so that if that happened, youd have 29 possibilities to check in only the three remaining weighings, which have only 27 possible sequences of outcomes.
The following table shows, for a given number of coins in each pan, the number of combinations of light coins that would result in an equal weighing (balanced pans), and the number that would tip the scale in a particular direction. The number that would tip the scale in the opposite direction is the same as that and is not shown:
number equal pan tips
in each possible left (same # as pan tips right)
1 29 8
2 19 13
3 15 15
4 17 14
5 25 10
Weighing three coins against another three seems a good bet for the first weighing, so as to separate the possibilities into three groups of 15 each.
Posted by Charlie
on 2005-03-25 20:30:57