Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: 12 billiard ball problem
Replies: 15   Last Post: Jan 4, 2013 12:07 PM

 Messages: [ Previous | Next ]
 jhnieto@luz.ve Posts: 91 Registered: 12/12/04
Re: 12 billiard ball problem
Posted: Nov 19, 1997 11:33 AM

In article <m2wwi58as5.fsf@mailhost.neuroinformatik.ruhr-uni-bochum.de>,
David Kastrup <dak@mailhost.neuroinformatik.ruhr-uni-bochum.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.

-------------------==== Posted via Deja News ====-----------------------
http://www.dejanews.com/ Search, Read, Post to Usenet

Date Subject Author
11/18/97 Jonathan Pearce
11/18/97 Sam @ The NIMP Team
11/19/97 jhnieto@luz.ve
11/19/97 Sam @ The NIMP Team
11/18/97 Pat (Jedi In Training)
11/18/97 H. Peter Anvin
11/19/97 David Kastrup
11/19/97 jhnieto@luz.ve
3/3/99 bob vanderbrink
3/3/99 David Kastrup
11/20/97 Jeff Erickson
11/20/97 Brian Hutchings
1/7/98 Rosa Guia
11/10/98 James W.
10/27/03 Bill Bridges
1/4/13 Raymond C Phillips, LT USN Retired