Here’s a series of puzzles, in increasing difficulty. This is a common type of puzzle, and I’ve heard the first three many times before, but the last one is one that I came up with. It’s meant to be extremely difficult - it just might be the hardest of its kind ever posed.

Version 1: Easy

You are given a set of nine balls, one of which is very slightly heavier than the others, and a balance scale. The scale allows you to weigh two sets of balls at a time, and will tell you which set is heavier, or if they weight the same. Using the scale only twice, how can you figure out which is the heavier ball?

Version 2: Medium

You are given four balls, one of which is either heavier or lighter, and a fifth ball, which is known to be a normal weight. Using the scale only twice, how can you determine which ball is different, and whether it is heavier or lighter?

Version 3: Hard

You are given twelve balls, one of which is either heavier or lighter. Using the scale three times, how can you determine which ball is different, and whether it is heavier or lighter?

Version 4: Impossible

You are given 39 balls, one of which is either heavier or lighter. Using the scale four times, how can you determine which ball is different, and whether it is heavier or lighter? For an added challenge, how can you do the same with the restriction that you can’t change which balls you weigh based on the outcome of previous weighings. I.e. you can’t say “if the first weighing comes out one way, I’ll then weigh A vs B, and if it goes the other, I’ll weigh C vs D.” You must decide on all four of your weighings before actually doing any of them.

I’ll post the answers to all of these in a little while.

Update:

How about with 120 balls and 5 weighings? 363 and 6? If you haven’t guessed by now, solving these bigger problems might be easier if you know some programming. In general, I think it’s possible to do \((3^n-3)/2\) with \(n\) weighings, although I haven’t proved it yet.

Update 2:

Solutions have been posted here.