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: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 *
JosÃÂé H. Nieto
-------------------==== Posted via Deja News ====-----------------------
http://www.dejanews.com/ Search, Read, Post to Usenet
|
|
|
|
