CSC 477/677 Hint for Thirteen-Coins Puzzle
On this web page ,
an explanation is given on how to find a solution to the twelve-coins puzzle,
using the base 3 logarithm. (3, because the balance scale has 3 possible
outputs at each weighing.)
As explained on that web page, if A is a decision model algorithm
that has d possible outcomes for each decision (in most problems, d = 2, but
for the coin balance problem, d = 3), and if there are N possible
configurations of the data, and if A decides which configuration is
true, then A must, in the worst case, make logdN decisions.
The proof that you can't do it with 13 coins is not
so simple, because there are 26 possible configurations (any of the 13
coins is the bad one, and it could be either heavy or light),
and log3(26) < 3, so it looks like an algorithm could exist!
What you need to prove is
that, regardless of what you decide to do in the first weighing, there
is a possible outcome of the first weighing such that there are more
than 9 possible remaining configurations. (Why 9?)
Back to
Course Page