#### 3.5 Problem 5: The Fake Coin Puzzle I

Two weighings are sufficient! That is astonishing. First, the coins are
numbered from 1 to 8. Of course, the first idea would be to weight all coins: 4
on one side of the balance and 4 on the other side. The fake coin is then at
the lighter side, this is repeated with the four on the lighter side, etc. This
method would lead to 3 weighings. But what if we only weight 6 coins
initially? Coins 1,2,3 on one side of the balance and 4,5,6 on the other side?
Because then we know: if the left side is lighter, the fake coin is there, if
the right side is lighter, then it is on the right side, and if they are
equal, then the face coin must be 7 or 8. Bingo! That is the key idea:
to separate the coins into three groups. This key idea is repeated in
the second weighing. Suppose the left side with the coins 1, 2, 3 is
lighter, then we know the fake coin is there. Now we weight only coin 1
against coin 2. If the left is lighter then the fake coin is 1, of the right is
lighter then the fake coin is 2, otherwise the fake coin is 3, which was
not weighted! The whole weighings process is best shown in a Figure
5.