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

Friday, January 4, 2008

Category Feeds

Typically I try not to do blogs about blogging but I went through quite a bit of work to get my category feeds going and nobody seems to be using them. Most things that I want to write about end up here. That is to say it is far from a specialized blog. I put in some personal stories, I write about some little tech hacks I found or trends in the open source world. I write about stupid riddles and how fascinating they are to me because of what happens when you look at them in certain ways. There is no way any other one person could find even most of this interesting. I get that. Enter categories and category feeds.

Now in that all of my content could not be interesting to any one person, my blog is not special. Most blogs I find have certain domains that I find useful and the rest is written for somebody who is not me. Rather than subscribing to the blog as a whole, I subscribe to the category feed. This is especially important for high volume blog. If you publish daily or more I consider you a high volume blog. Normally I have to do some digging to find the feed I want. Typically, Blogger included, you merely have to click on the category link and type /feed at the end of the url.

But some blogs, namely Wordpress, I still don't know how to get a category feed. And that keeps me from subscribing to a few blogs that I really want to, because I don't want all the other crap I have to take to get the stuff I want.

So if you want to help me out and maybe your readers too, here is how you can get links to your category feeds.

You may want to run your category feeds through feed burner. Here's how to do that.

Then you can put links to your category feeds as explained here.

If everybody did this the world would be a lot more linkable. That and if Blogger automatically attached an anchor name to every <p> tag. That way you could link to any paragraph, like the way you can link to any part of a video on Googlevideo.

Thursday, January 3, 2008

Back to UPEI

I can hardly believe it. Today I took in my first university class in over 2 years. Yes, I am back at UPEI after this, and this, and this. I don't know exactly what it means that I am back. Mainly I would think it means I have learned how to use it more wisely, and its need is more important.

That is to say I am trying to exploit the things that UPEI and I agree on, and I have found an end that I have found an end for which I am willing to be subjected to the modern torture mechanism known as formal education.

I would like to be a teacher. What age, I don't know yet. What subject, same deal. Rather I'll take what I can get.

So I am currently pursuing a BA in political studies. I'm flirting with the idea of a dual minor in math and economics. Then a post BA in education. There are still more people to talk to before it all gets inked.