Re^3: Odd Ball Challenge

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?

Comment on Re^3: Odd Ball Challenge

Replies are listed 'Best First'.

Re^4: Odd Ball Challenge
by kaif (Friar) on Jun 28, 2005 at 17:11 UTC

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

[reply]
[d/l]
[select]


Welcome to the Monastery
	PerlMonks