|
|
Re: 12 billiard ball problem
Posted:
Nov 19, 1997 4:59 AM
|
|
hpa@transmeta.com (H. Peter Anvin) writes:
> Followup to: <01bcf44e$fef00320$8de52ac2@jon>
> By author: "Jonathan Pearce" <jvpearce@classic.msn.com>
> In newsgroup: sci.math
> >
> > Does anybody know of an elegant solution to the twelve billiard ball
> > problem?
> >
> > (Twelve apparently identical billiard balls, one of which is slightly
> > heavier than the rest, determine which is the heavier one making only three
> > weighings.)
> >
> > I would be very grateful for a reply.
> >
> > JVP.
>
> Why make it so easy? Twelve billiard balls (gold bars, whatever...);
> exactly one is *either* lighter *or* heavier than the others;
Why make it so easy? Twelve billiard balls (...); exactly one is
unchecked, and is either lighter or heavier or equal to the others.
> find which one it is *and* if it is lighter or heavier, in three
> weighings by a balance scale.
Let's see how much redundancy we have: three weighings of that kind
deliver three trits of information. The number of cases we have to
distinguish is all equal, one heavier, one lighter, all in all 25
cases.
This means we have a redundancy of about 0.07 trits, or 0.111 bits.
Pretty slim.
But this also means that in a perfect weighing scheme, there will be
two weighing combinations that turn out to be impossible, or one case
where we arrive at our decision after just two weighings.
Which is it?
--
David Kastrup Phone: +49-234-700-5570
Email: dak@neuroinformatik.ruhr-uni-bochum.de Fax: +49-234-709-4209
Institut fÃÂür Neuroinformatik, UniversitÃÂätsstr. 150, 44780 Bochum, Germany
|
|
