One of my longtime friends (from my undergraduate days at Johns Hopkins), and sometime writer at 3QD, is Abhay Parekh. He has started his own blog:
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!