Re^2: Odd Ball Challenge

[kaif]

No, it is not. Here's an information theory approach: by asking three questions which have three possible answers each (left side goes down, right side goes down, or equal), there are only 3**3 == 27 possible "inputs". Suppose there were 15 balls --- then there would be 15 * 2 == 30 (each ball can be heavier or lighter than the rest) possible "outputs". There are more outputs than inputs, so it is impossible. (This is the same approach as analyzing the "game tree".)

In fact, this argument shows that it is not possible to do the same for more than 13 balls; a slightly more sophisticated argument shows that 12 is actually the maximum. The best that is possible for 13 balls is determining which ball is different, but not necessarily whether it is heavier or lighter; this is not possible for 14 or more balls.

[jimX11]

You use "outputs" the way I'd use "inputs."

While thinking more about the algorithm, I see I assumed that we'd know if the odd ball was heavier or lighter than the others. My bad.

If we know that the odd ball is, say, heavier, then we can find in in 3 weighings even if there are 14 other balls.

I don't follow your informational theory argument, do you think the argument shows that what I claim in the paragraph above is not possible?

[kaif]

Here's a try at my information theory argument again, attempting to explain my notion of "input" and "output". Assume you have 15 balls, all of the same weight, except for one which is different, but you don't if it is heavier or lighter. We want to find this ball, and whether it is heavier or lighter, with three weighings. Then our algorithm should look something like

compare {1,2,..} vs {6,7,..}  # the return value here is my notion of 
+"input"
if they are equal
    compare .. vs ..
    if left is heavier
        compare .. vs ..
        if they are equal, print ".. is heavier"  # this is my "output
+"
        if right is heavier, print ".. is lighter"
        ..
    ..
if right is heavier
    compare .. vs ..
    ..
..

Notice that our code can branch into three at most three times (because there are three weighings and each can either be equal, left-heavy, or right-heavy), and so it will have at most 27 print statements. But this is a contradiction! It should be possible, under some input, for there to be 30 possible "outputs": "1 is heavier", "1 is lighter", ..., "15 is heavier", "15 is lighter".

If we do know that the "foreign" ball is heavier, then it is possible to solve the problem for up to 27 balls (which is what the analogous information theory argument yields there). The algorithm is similar to jpeg's above, except you split into groups of 9, 3, and 1:

• Split the balls into three groups of 9. Weigh two of them against each other. You now know which of these groups contains the foreign ball. (It's either the heavier group or the unweighed group if the balance was equal.)
• Split that group into three groups of 3. Do the same to determine a group of 3 balls.
• Split that group into three groups of 1. Do the same to determine which ball it is. (That is, weigh one of the three balls against another.)