The strategy you list is adaptive, i.e, depending on the outcome of a weighing, you do different things. An interesting special class of solutions is fixed strategies, where you just have 3 fixed weighings such that no matter how the one ball is odd, you will detect it. Unfortunately, I know that my analysis is not complete, and I'm not sure that any such strategies exist (I suppose I could google, but I haven't yet). I wrote some very basic brute search code to look for a fixed strategy, but came up cold.

The reason I am drawn towards fixed strategies is that, if they exist, they have the benefit of having a much simpler representation. You can look at a fixed strategy as a 12 x 3 table, filled with L, R and - (or L, R, and ~ if you like), to denote whether a ball is on the left or right side of the scale, or not weighed in a certain round. Example: 

  L L L L R R R R - - - -
  L L - - R R - - L R - -
  L - L - L - R - R - R -

[download]
This strategy says to weigh balls 1-4 vs balls 5-8. Then weigh 1,2,9 vs 5,6,10. Then weigh 1,3,5 vs 7,9,11.

It's easy to check whether this gives a real solution. First of all, in order to give you any information about ball weight, each round has to have the same number of balls on the LHS and RHS of the scale. Then, you have to pretend the odd ball is each of the 12 balls and see whether all other candidates would get logically eliminated. If the odd ball is one that is measured, then the scale tips so you can throw out the ones that weren't measured. If the odd ball is not measured, the scale balances, so you can throw out the ones that were measured. In code, that looks like this (with the table being represented as a 2d, 3x12 array): 

sub check_scheme {
    my @scheme = @_;

    ## check that each round measures the same amount of balls
    for my $round (0 .. 2) {
        my $lhs = grep { $scheme[$round][$_] eq "L" } 0 .. 11;
        my $rhs = grep { $scheme[$round][$_] eq "R" } 0 .. 11;
        return 0 if $lhs != $rhs
    }

    ## simulate the scheme with each of the balls being the odd one
    for my $item (0 .. 11) {
        my @candidates = (0 .. 11);

        for my $round (0 .. 2) {
            if ($scheme[$round][$item] eq "-") {
                @candidates = grep { $scheme[$round][$_] ne "-" } @can
+didates;
            } else {
                @candidates = grep { $scheme[$round][$_] eq "-" } @can
+didates;
            }
        }

        ## by this point we should have eliminated all but one ball!
        return 0 if @candidates != 1;
    }
    return 1
}

[download]
Unfortunately, I know that this analysis is incomplete, because (depending on the statement of the problem) you may be able to use information about the direction of the scale and keep track of which balls were on sides of the scale that went up and down. The only information I assume we use here is whether or not the two sides were equal. In fact, now that I'm writing this, I think a basic counting argument shows that there is no fixed strategy that works unless you use information about whether balls were in the heavy or light side of the scale (Update: Indeed, look at the "L" or "R" entries as 1s and the "-" entries as 0. For two balls to be distinguished, they must at some point have mismatched 0/1's in their column. There are 8 ways a ball can have an assignment of 0/1's, but there are 12 balls. Conclusion: some pair of balls must be indistinguishable in this very simple scheme).

Oh well, it was a nice attempt at a simple analysis, but it was too simple to yield any solutions. My feeling is that this analysis could be extended by keeping a two lists of candidates (the possibly heavy balls and the possibly light balls), seeing which way the scale swings, and making the logical deductions. Feel free to expand on it, but unfortunately I need to go get other work done this morning ;)

blokhead

In reply to Re: Odd Ball Challenge by blokhead
in thread Odd Ball Challenge by Limbic~Region

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • 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! —
  • 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:
    & &amp;
    < &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.