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

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.