In article <3471E604.7310BDD5@chez.com>, Sam H <firstname.lastname@example.org> 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 *