Re: Puzzle

scot@moosilauke.cs.dartmouth.edu
Mon, 28 Dec 1998 14:35:30 -0500 (EST)


Chick Tiberio writes:

> Duncan,
>
> This problem rang a very familiar bell with me. After a little research, I
> found it.
>
> Suppose you are given 13 objects, 12 of which are the same, but one is
> either heavier or lighter than the others. Show that, with 3 weighings using
> a pan balance, it is possible to identify the odd object.
>
> This appears in my 1962 edition of Kemeny, Schleifer, Snell, and Thompson's
> book "Finite Mathematics with Business Applications" as problem 14 on page
> 89. I seem to remember solving this problem for some guy on my dorm floor
> back in the 60's!! The catch in using 13 marbles instead of 12 is that at
> the end of the process you can identify the marble but cannot tell whether
> it is heavier or lighter.

The problem also appears in _Combinatorial Algorithms_ by Reingold,
Nievergelt, and Deo. pp. 14-23. They give a general solution for determining
a bad coin from among (3^k - 1)/2 unknown coins, at most one of which is bad,
in k weighings. They also assume an extra coin known to be good, so are
able to tell whether the bad coin is heavy or light. So they do 1 coin in
a single weighing, 4 coins in 2, 13 coins in 3, etc.

They also prove that it is impossible to handle more coins or to determine
the solution for that number without the good coin. It is very pretty -
given n coins there are 2n + 1 possible outcomes (each coin could be heavy
or light, for 2n outcomes, and all could be good, the final possible
outcome). There are 3^k leaves of a decision tree after k weighings, and
they get every one of the leaves to represent a different possible outcome.

Scot Drysdale