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 ..
    ..
..
[download]

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.)