Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University or The Math Forum.



Re: 12 billiard ball problem
Posted:
Nov 19, 1997 11:33 AM


In article <m2wwi58as5.fsf@mailhost.neuroinformatik.ruhrunibochum.de>, David Kastrup <dak@mailhost.neuroinformatik.ruhrunibochum.de> wrote: > > 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?
To construct the following solution I borrowed part of the notation and weighing scheme posted by Samuel HOCEVAR <sammy@chez.com> in message <3471E604.7310BDD5@chez.com>. The balls are 123456789ABC, an X stands for a "normal" ball, i+ means that ball i is heavier, i means that ball i is lighter. Sentences between braces are comments.
1. If 1234=5678 then {12345678 are of normal weight}
1.1. If 9AB=XXX then
1.1.1. If C<X then C 1.1.2. If C>X then C+ 1.1.2. If C=X then all the balls are equal
1.2. If 9AB<XXX then {the unchecked ball is in 9AB and it is lighter}
1.2.1. If 9=A then B 1.2.2. If 9<A then 9 1.2.3. If 9>A then A
1.3. If 9AB>XXX then {the unchecked ball is in 9AB and it is heavier}
1.2.1. If 9=A then B+ 1.2.2. If 9<A then A+ 1.2.3. If 9>A then 9+
2. If 1234>5678 then {the unchecked ball either is in 1234 and it is heavier or it is in 5678 and it is lighter; 9ABC are normal}
3.1. If 1235=4XXX {Sammy's "special trick"} then {the unchecked ball is in 678 and it is lighter}
3.1.1. If 6=7 then 8 3.1.2. If 6<7 then 6 3.1.3. If 6>7 then 7
3.2. If 1235<4XXX then {the unchecked ball is 4+ or 5}
3.2.2. If 4=X then 5 3.2.2. If 4>X then 4+ {4>X is impossible}
3.3. If 1235>4XXX then {the unchecked ball is in 123 and it is heavier}
3.3.1. If 1=2 then 3+ 3.3.2. If 1<2 then 2+ 3.3.3. If 1>2 then 1+
3. If 1234<5678 then 5678>1234 and we may proceed, mutatis mutandis, as in 2 above.
In this scheme there are two impossible weighing outcomes, accounting for the redundancy.
JosÃÂÃÂ© H. Nieto
==== Posted via Deja News ==== http://www.dejanews.com/ Search, Read, Post to Usenet



