Friday, January 18, 2008

Solving 'Odd Ball'

The riddle goes as follows:


You have 12 balls and a 2 arm balance. With 3 trials on the 2 arm balance you are to tell which one is different of the 12, and how it is different, heavier or lighter, than the others.


Observation 1: There are 24 possible initial conditions, 12 balls x 2 states (heavier or lighter). These will be called 1L through to 12H

Observation 2: For a solution to work in every case each of the 24 initial conditions must have a different outcome of the 3 trials. One possible outcome, for example, could be on trial one the balance tips right, on trial 2 it tips left, and on trial 3 it doesn't tip, encoded as |> < =|. These outcomes will be called 'signatures'.

Observation 3: Each of the 3 trials will contribute one of 3 symbols to the signature. So there are 3x3x3 = 33 = 27 total signatures.

Observation 4: For any given ball, the signatures for it being Light and Heavy must be opposites. Signatures are opposites if all < are changed to > and all > are changed to <. |< > =| is the opposite of |> < =|.

Observation 5: All opposing signatures must be distinct. If 1L had the signature of |= = =| then 1H would have the opposite signature, |= = =|. Therefore |= = =| is an invalid signature. It is the only one of the 27 signatures that does not have a < or a >, so there are 26 remaining valid signatures. (|= = =| would suggest the balance never tipped. This would correspond to if the Odd Ball never went on the balance. And if it was never on the balance you could never know if it was Heavy or Light, so it makes sense to throw this signature away.)


Strategy:
1. What we will do now is assign a signature to each of the 24 initial conditions.
2. We will then have to balance the signatures so that there are an equal amount of balls on each arm for each trial by switching the signatures for Heavy and Light of selected balls.
3. We will then compile the signatures into an algorithm for finding the Odd Ball.

1. Assignment
This is a list of the signatures for Heavy balls. For Sum < is worth 1, = is worth 0, and > is worth -1. A trial is balanced when the sum is 0.
















Balls
Sum
123456789101112
Trials
1
<
<
<
<
<
<
<
<
<
=
=
=
9
2
<
<
<
>
>
>
=
=
=
<
<
=
2
3
<
>
=
<
>
=
<
>
=
<
>
<
1


2. Balance
So here we have to switch the signatures for Heavy and Light and make all the sums equal 0. But this is impossible! Whenever you switch < for > it will change the sum by 2. Since trials 1 and 3 are odd they cannot be balanced.

Remember there are 26 valid signatures. Listed above are 12, and implicitly their opposites, so 24. the signature |= < =| has been left out. We must now substitute this signature for another one. If we are to make all of the Sums even we will have to substitute it for |< < <| or |< < >| or |< > <| or |< > >| . Currently assigned to Balls 1H, 2H, 4H and 5H respectively. Those are all of the signatures (including their opposites) that don't have an equals sign. A quick check agrees there are 23 = 8 = 4x2 signatures with only > and <.

1. Assignment
We will arbitrarily assign |= < =| to Ball 1H and get the following:













Balls
Sum
123456789101112
Trials
1
=
<
<
<
<
<
<
<
<
=
=
=
8
2
<
<
<
>
>
>
=
=
=
<
<
=
2
3
=
>
=
<
>
=
<
>
=
<
>
<
0


2. Balance
Now all of the trials have a sum that is even so we can balance it by switching signatures. Trial 1 has a balance of 8 so you must switch at least 4 signatures. You can balance all sums by switching balls 3, 7, 8 and 9. This gives the following assignments:













Balls
Sum
123456789101112
Trials
1
=
<
>
<
<
<
>
>
>
=
=
=
0
2
<
<
>
>
>
>
=
=
=
<
<
=
0
3
=
>
=
<
>
=
<
>
=
<
>
<
0


3. Compile
We can now use this table to construct our algorithm. We will arbitrarily say that > means the ball is on the left arm and < means it is on the right arm. And we will have the answer!

Trial 1. 3 7 8 9 v. 2 4 5 6
Trial 2. 3 4 5 6 v. 1 2 10 11
Trial 3. 2 5 7 11 v. 4 8 10 12

4. Clean up
Since the numbering is arbitrary we can reassign the numbers so that it goes increasing from the first to show up to the last.

3 -> 1
7 -> 2
8 -> 3
9 -> 4
2 -> 5
4 -> 6
5 -> 7
6 -> 8
1 -> 9
10 -> 10
11 -> 11
12 -> 12

This gives us a more pleasant solution:

Trial 1. 1 2 3 4 v. 5 6 7 8
Trial 2. 1 6 7 8 v. 5 9 10 11
Trial 3. 2 5 7 11 v. 3 6 10 12


Analysis.
The final solution is always the same if you do follow this strategy. All of the arbitrary decisions cancel each other out and settle on what we have produced above.
I find it interesting to note that nowhere along the way did we assume there would be 4 Balls per arm per trial. This effectively proves that it must be done this way.

Step it up.
If you have 5 trials how many balls can you have and still discover the Odd Ball and its state?

Answer:
You will have 35 = 243 total signatures. Minus the |= = =| signature, 243 -1 = 242. One signature for each of the 2 states per ball, 242/2 = 121. Round down to the nearest multiple of 3, 120. With 5 trials you can find the Odd Ball among 120.

Generally with N trials you can find the Odd Ball among B balls (N and B are positive integers):

B = (3N-1)/2 (rounded down to the nearest multiple of 3)

When rounding the Remainder will always be 1 so:

B = [ (3N-1)/2 ] -1
    = (3N-3)/2

No comments:

Post a Comment