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:22 AM

In article <3471E604.7310BDD5@chez.com>,
Sam H <sammy@chez.com> wrote:
>
> Jonathan Pearce wrote:

> > 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.)

>
> Are you sure it is 'heavier' ? The original problem only states
> the odd ball is lighter or heavier?

If you knew beforehand that the odd ball is heavier then three
weighings would suffice for as much as 27 balls.

>
> Anyway here is my solution:
>
> Let's call the marbles 123456789ABC.
> I'll call X a normal marble when
> we know there are some and it is
> possible to choose one.
>
> I put a '*' when we know which marble is
> the odd one AND if it is lighter or heavier.
> Note that we don't know it only if it is marble C.
> *** note: another solution would fix that, but do you need it ?
> ******* Begin of hideous solution ********
>
> 1. If 1234=5678
>
> we know that the odd one is in 9ABC
>
> 1.1. If 9A=XX
>
> we know that the odd one is in BC
>
> 1.1.1. If B=X
>
> the odd one is C
>
> 1.1.2. If B<>X
>
> the odd one is B *
>
> 1.2. If 9A<>XX
>
> we know that the odd one is in 9A
>
> 1.2.1. If 9=X
>
> the odd one is A *
>
> 1.2.2. If 9<>X
>
> the odd one is 9 *
>
> 2. If 1234<5678
>
> then let's invert 1234 and 5678
> and let's say 1234>5678
> (just a re-indexation)
>
> 3. If 1234>5678
>
> then the odd one is in 12345678
> and 9ABC are normal
>
> 3.1. If 1235=4XXX (my special trick)
>
> then the odd one is not in 12354
> then it is in 678
> so we know it is lighter since 1234>5678
>
> 3.1.1. If 6=7
>
> then the odd one is 8 *
>
> 3.1.2. If 6<7
>
> then the odd one is 6 *
>
> 3.1.3. If 6>7
>
> then the odd one is 7 *
>
> 3.2. If 1235<4XXX
>
> then if the odd one is lighter
> it is in 1235 and 5678 > it's 5
> and if it is heavier it is
> in 4XXX and 1234 > it's 4
> so it is in 45
>
> 3.2.2. If 4=X
>
> then the odd one is 5 *
>
> 3.2.2. If 4<X
>
> then there is a bug somewhere :)
>
> 3.2.3. If 4>X
>
> then the odd one is 4 *
>
> 3.3. If 1235>4XXX
>
> then if it is heavier it is in
> 1235 and in 1234 so it's in 123
> if it's lighter it's in 4XXX and
> in 6789: impossible
> so it's heavier and it's in 123
>
> 3.3.1. If 1=2
>
> then it's 3 *
>
> 3.3.2. If 1<2
>
> then it's 2 *
>
> 3.3.3. If 1>2
>
> then it's 1 *
>
> ******* End of hideous solution ********

If you want to know if the odd ball is heavier or lighter in all
cases, fix the subtree beginning at 1.1. as follows:

1.1. If 9AB=XXX

1.1.1. If C<>X the odd one is C *

1.2. If 9AB<XXX

the odd one is in 9AB and it is lighter

1.2.1. If 9=A the odd one is B *
1.2.2. If 9<A the odd one is 9 *
1.2.3. If 9>A the odd one is A *

1.3. If 9AB>XXX

the odd one is in 9AB and it is heavier

1.2.1. If 9=A the odd one is B *
1.2.2. If 9<A the odd one is A *
1.2.3. If 9>A the odd one is 9 *

-------------------==== 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