Saturday, December 30, 2006

New Year's Brain Teaser

Here's a good brain teaser to give you some entertainment for the new year.

You have 12 balls, identical in every way except that one of them has a different weight from all the others. You also have a balance scale. In 3 rounds, in each of which you can compare the weights of any 2 groups of balls, you have to ascertain which is the ball with the different weight and whether this ball is heavier or lighter than the other balls.

This is not a trick question in any way. I solved part of this puzzle after I got a significant hint. I wish I had tried a bit harder to solve it by myself, but it's too late now. If you want a hint, you can email me, but you'll feel greater satisfaction if you solve it by yourself.

Happy new year!


David Bergman said...

Ok, it took me 2 minutes to find the solution, in broad strokes, and some 5 minutes more to formalize it. Will formalize it as a Ruby app (or Erlang?) and hide it somewhere.


John Goodwin said...

There is actually an algebra for solving problems like this. It is formally equivalent to fractional design of experiments with three levels. The three levels are left side, right side, and not weighed. Each of the 12 balls is a 'main effect' and the null hypothesis to be tested is that all the balls weigh the same. You want an experimental design (a set of three contrasts) in which the 12 main effects are not aliased to each other, and which can detect deviations from the null hypothesis and their sign.

I mention these details because it allows one to design similar problems easily.

Ankit Verma said...

hey good one. Took me around 15min. really amazing. Can be easily put to search algorithms. thanks.

Valentin Dinu said...

Hey, this is cool! Nice one! - Valentin Dinu