
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: +492347005570 Email: dak@neuroinformatik.ruhrunibochum.de Fax: +492347094209 Institut fÃÂÃÂ¼r Neuroinformatik, UniversitÃÂÃÂ¤tsstr. 150, 44780 Bochum, Germany

