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?

(In reply to thoughts by Charlie)

We must assume the two fakes weigh the same! Following this, if the scale ever tips, we know that all of the coins in the heavy group are keepers. We are then interested in reducing the possible equal outcomes. I'll use * to denote keepers.

Let us use Charlie and Kardo's strategy for step one since it minimizes the number of equal possible weighings. Set the first four aside and weigh the remaining three vs. three.

Case I: the scale is equal. The possibilities are:
6 variations of both fakes left out.
e.g. FFRR RRR RRR
9 variations of each fake in a group of 3
e.g. RRRR FRR FRR
I will return to Case I

If the scale tips one way or the other. We simply eliminate the three coins in the heavy group altogether and we also know that both fakes are not in the first group of four. This reduces the problem to:
3 variations of both fakes in the light group of three:
RRRR FFR ***
12 variations of one fake in each group:
FRRR FRR ***

Let us number the remaining coins 1-7. Let's try weighing coins 1 and 2 from the group of four against 3 and 5.

This gives five equal scenarios (and coin 3 must be real):
RR*R RFF ***
RR*F RRF ***
RR*F RFR ***
RF*R FRR ***
FR*R FRR ***
We can easily solve in two more weighings - done in four steps.

Scale tips Left means the first two are genuine and can be eliminated and the following 6 scenarios remain:
**RR FRF ***
**RR FFR ***
**RF FRR ***
**FR RRF ***
**FR RFR ***
**FR FRR ***
Then we just compare 6 and 7 and we are down to two scenarios each - done in 4 steps.

Scale tips right means we have identified 3, 5 and 4 as keepers and only the following 4 scenarios remain:
RF** *RF ***
RF** *FR ***
FR** *RF ***
FR** *FR ***
It will still take two more weighings to solve - done in 4 steps.

Returning to Case I: (if the coins were numbered we have compared 5,6,7 to 8,9,10 and found them to be equal) let us now weigh 1,2,5 against 3,8,9. - Yes this is confusing.

If Equal only 6 scenarios remain (and 4 is real):
RRR* RRF RRF
RRR* RFR RRF
RRR* FRR RFR
RRR* FRR FRR
RFF* RRR RRR
FRF* RRR RRR
Then we simply compare 3 and 10 and we are down to two possibilities for each outcome - done in four steps.

If scale tips left, we know 1,2, 5 (and 10) are keepers and only the following 5 scenarios remain:
**RR *RF RF*
**RR *RF FR*
**RR *FR RF*
**RR *FR FR*
**FF *RR RR*
Again, we can easily solve in two more weighings - done in four steps.

Should the scale tip right, we know that 3,8,9 (and 6 & 7) are keepers and only the following 4 scenarios remain:
RR*R F** **F
RF*F R** **R
FR*F R** **R
FF*R R** **R
This will take two more weighings - done in 4 steps.

The answer is 4 Weighings across the board.

Posted by Eric on 2005-03-26 18:31:13