You have 11 coins, fewer than half of them bogus, and a balance scale; can you find for sure a good coin in...

Original problem (each bogus coin has its own weight):

Yes.

Weigh two coins.  If they balance, both must be good.  Otherwise,
set them aside, knowing that at least one of them is bogus.

Weigh two more coins.  Again, if they balance, both must good;
otherwise at least one is bogus.

Keep on weighing two at a time until the five weighings are up.
If no pair balance, five pairs containing at least five bogus coins
have been set aside; but since there are no more than five bogus
coins, the eleventh coin must be good.

-- Fred W. Helenius <fredh@ix.netcom.com>

----------------------------------------------------------------------

Warm-up (5 coins, two weighings):

Label the coins 1 - 5

Weigh coins 1 & 2 against 3 & 4.

If the pans balance weigh 1 & 2 against each other.
   If the pans balance 5 is the only bogus coin.
   If the pans don't balance 5 is a good coin.

If the pans don't balance switch coins 1 & 3
   If the pans balance 5 is a good coin
   If the pans don't balance and the heavy pan is still heavy
   1 & 3 are good coins.
   If the pans don't balance and the heavy pan is now light
   2 & 4 are good coins.

-- Kevin Green <kdg977t@cnas.smsu.edu>

[ Editor: in the first case (both weighings balance) coins 1-4 must all
be good, since two bogus coins among them would make four; coin 5 may
then be good or bogus, so "5 is the only bogus coin" is not certain, but
a good coin is still found. ]

----------------------------------------------------------------------

Harder variant (11 coins, all bogus coins of one weight):

To look at the problem another way, each coin can be either heavy or
light, and we must find a coin that is in the majority.

Weigh A+B against C+D.
  If they do not balance, see Case I below.
  If they balance, weigh E+F against G+H.
    If they do not balance, see Case II below.
    If they balance, see Case III below.

Case I:  A+B does not balance C+D.

  Weigh A+C against B+D.

    If they balance:
      A and C must be a heavy and a light.
      Weigh A+C against each of E+F, G+H, I+J.  This tells us how many
      heavy and how many light coins are in each pair (A+B, C+D, E+F,
      G+H, I+J).  If there are 6 or more coins of one weight in those
      10 coins, we will have identified one of the pairs as being both
      of that weight, so the coins in that pair are both good.
      Otherwise, there are 5 heavy and 5 light coins in the first 10,
      and the 11th coin (K) is good.

    If they (A+C and B+D) do not balance:
      The coin that was on the heavy side (HH, say) in both weighings
      must be heavy; the coin that was on the light side (LL, say) in
      both weighings must be light; the other two coins (X1 and X2,
      say) must have the same weight as each other.  Weigh HH+LL
      against each of E+F and G+H.  This tells us how many heavy and
      how many light coins are in each of those two pairs.  We
      distinguish five cases:

        Ia:  E, F, G, H are all heavy.
          Weigh LL+X1+X2 against I+J+K.  (The other 5 coins are heavy.)
          If they balance, X1 and X2 are good; otherwise HH, E, F, G,
          H are good.

        Ib:  E, F, G, H are all light.
          Same as Ia, with obvious modifications.

        Ic:  Three of E, F, G, H are heavy and one is light.
          One of the pairs E+F and G+H consists of a heavy coin and a
          light coin: assume it is E+F.  (Otherwise, just relabel.)
          Weigh E+F+LL (two lights and a heavy) against I+J+K.
          If the latter is heavier, there are at least 6 heavies (HH,
          G, H, one of E and F, and two of I and J and K), so HH, G,
          and H are good.
          Otherwise (I+J+K no heavier than two lights and a heavy), we
          know that HH, LL, E, F, G, H, I, J, K contain at least 4
          heavies and 4 lights, so X1 and X2 must be good.

        Id:  Three of E, F, G, H are light and one is heavy.
          Same as Ic, with obvious modifications.

        Ie:  Two of E, F, G, H are light and two are heavy.
          Weigh E+F+G+H against any four of I, J, K, X1, X2.  If they
          balance, the remaining one of I, J, K, X1, X2 is good; if
          E+F+G+H is lighter, then HH is good; if E+F+G+H is heavier,
          then LL is good.

Case II:  A+B balances C+D; E+F does not balance G+H.

  Relabel, exchanging (A,B,C,D) with (E,F,G,H).  Now A+B does not
  balance C+D, but E+F balances G+H.  Now proceed as in Case I, except
  that when we come to weigh two of A, B, C, D against each of E+F and
  G+H (as we always do) we only need one of the two weighings, since
  we know they will give the same result.

Case III:  A+B balances C+D; E+F balances G+H.

  We know that A+B+E+F weighs the same as C+D+G+H; in fact, this fact
  is all we need.  For in two weighings we can either identify a coin
  in the majority among A, B, E, F, which must be in the majority
  overall (since there are at least 3 of its weight among A, B, E, F
  and so at least 3 among C, D, G, H, and so at least 6 overall), or
  else determine that A, B, E, F contain two heavies and two lights;
  in the latter case we weigh I against J, and if they balance then
  they are both good, and if they don't balance then K is good.

  To make this determination about A, B, E, F in two weighings, start
  by weighing A+B against E+F.  If they balance, weigh A against B: if
  those balance, then A, B, E, F are all the same weight and hence all
  good; if A does not balance B then A, B, E, F contain two heavies
  and two lights.  If A+B does not balance E+F, weigh A+E against B+F:
  if they balance, then A, B, E, F contain two heavies and two lights;
  if they do not balance, then the two coins of A, B, E, F that were
  on the heavy side in one weighing and the light side in the other
  are both in the majority.

Phew!  That's it.  You may notice that one theme, the testing of four
coins with two weighings as described in the last paragraph of Case 3,
occurs several times with slight variations.

-- John Rickard <jrr@atml.co.uk>