comment on

Good thinking. As djohnston concluded, such a strategy does exist. As you say, it does and must use the information of which side of the scale went up. My solution above uses a fixed strategy, actually. Try it out! Here's a detailed explanation of the strategy it uses:

Label your balls as follows:

001 (221)
011 (211)
012 (210)
022 (200)
100 (122)
110 (112)
120 (102)
121 (101)
201 (021)
202 (020)
212 (010)
220 (002)
[download]

where the first number is the primary label of the ball and the second is the secondary label (to be used later). Now use the following weighings, focusing on the primary labels only:

(balls labelled with 0 in the first position) vs (balls labelled with 2 in the first position)
... the second position ...
... the third position ...

(Note: for reasons of golfing, my program runs the weighings in backwards order.) Now, for the result of each weighing, write 0 if the left side was heavier, 1 if it was a tie, and 2 if the right side was heavier. You should have a three-digit number. If the number is one of the primary labels above, then that ball was the unique heavier ball, and if it was one of the secondary labels, it was the unique lighter ball.

This method can be generalized (that is, with 4 weighings you can solve the same problem for 39 == (3**4 - 3) / 2 balls)! If you notice above that the primary and secondary labels are "dual" in a sense (in base 3 they sum to 26 --- i.e., 0s are replaced with 2s and vice-versa), then the problem actually comes down to finding a way of choosing the primary/secondary distinction in such a way that the weighings I described above each lead to (4 ball) vs (4 ball) comparisons. It so happens that the above labelling accomplishes the task. In general, this is a problem of coding theory.

I hope that my explanation was helpful. If anyone would like for me to do so, I can explain the code for my solution above in more detail.

In reply to Re^2: Odd Ball Challenge by kaif
in thread Odd Ball Challenge by Limbic~Region

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


Do you know where your variables are?
	PerlMonks