"Toy" Puzzle #1

Wow, it's been a long time since I said anything here. Just have been too busy and I can't bring myself to post filler material. Hopefully the next few posts will be interesting.

Some people love to solve mathematical brainteasers, but most consider it a silly waste of time. There is something really inefficient (and even dumb) about allocating so much time and toil on these mental boondoggles! Yet sometimes brainteasers can serve as "toy" versions of much more important problems. Since they have a small number of variables, you can "play" with these problems and subsequently make headway on more involved ones. Most great scientists have used toy problems that somehow captured the essence of a bigger problem to make significant discoveries. In this post I will look at such an "impractical" problem and show that it can actually instruct. This is an old teaser but I actually have a twist to the solution that I think is new. I'll present that in my next post. Today all I will do is pose the problem and give some hints.

The Oddball Problem: You are given n identical looking balls. n-1 of them weigh the same, but one of them is either heavier or lighter than the others (you don't know which). Given a two pan weighing machine what is the minimum number of weighings you need to do to be sure that you have identified that odd ball? You can only use the weighing pan as follows: put some balls in the left pan, some in the right pan and observe one of three possible outcomes: either the left pan is heavy or the right pan is heavy, or they are even.

Since you don't know if the odd ball is heavier or lighter things get a bit tricky. This problem is often posed with 12 balls. Here's a problem worth working on:

Show that for 12 balls you can always identify the oddball in 3 weighings!

A few hints: Every time you do a weighing, you want to learn something new, i.e. you want to gain information that allows you to eliminate as many possibilities as possible. Initially, there are 2*12=24 different possibilities since each of the 12 balls can be the odd ball and an odd ball could be heavier or lighter. But you have to plan your weighings carefully! Think of each weighing as an experiment with an uncertain outcome. Suppose you start out by weighing ball 1 against ball 2. If the pan is heavy either to left or the right that's great news since you now know that the oddball is either ball 1 or 2. But it is far more likely that the pans will come up even. In fact this chance is 5/6. Under this predictable outcome we just eliminate 2 of the 12 balls from consideration, i.e. only 4 out of a possible 24 hypotheses. The way the problem is stated we've got to be sure we can nail the oddball after 3 weighing so you can't count on getting lucky. This tells us that the strategy for getting to 3 weighings has to be a bit more clever.

The next post will have a simple solution for the n ball problem....