Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math.independent

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
jhnieto@luz.ve

Posts: 91
Registered: 12/12/04
Re: 12 billiard ball problem
Posted: Nov 19, 1997 11:22 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply



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 *

José H. Nieto

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







Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.