Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Possible Duplicate:
Optimal algorithm for finding the odd spheres

You have 12 balls and you know that they all weigh the same except for 1 which is heavier or lighter than all the others (you don't know which though). How can you make sure you know which ball is the heaviest/lightest in only 3 weighings?

The way I approached it was to split up the 12 balls into three sets of 4 and weigh two of the sets. If the sets balanced the scale, then I know the ball I am looking for must be in the set of 4 balls not weighed, else, I disregard said set and arbitrarily choose the heaviest set of 4 (as opposed to choosing the lightest set). I split the heaviest set of 4 balls into 2 and weigh that... etc.

Repeating this process until all 3 tries have been "used up", even if everything just so happened to be in your favor (the arbitrary choice you have in choosing the heaviest or lightest set happens to be the correct choice) in the end you still end up having to choose between 2 balls. A 50% chance is good, but I am wondering, is there a way to make sure 100%?

share|improve this question
    
Yes, there is a way that guarantees finding the odd-one-out and determining if it's heavier or lighter. Your first step (4 against 4) is good, but you should think harder about the second. –  Alon Amit Apr 9 '12 at 5:15
    
I believe there is a method to find the anomalous ball from 13 in three weighings - but it is not possible to guarantee that you will know whether it is heavier or lighter. –  Mark Bennet Apr 9 '12 at 5:48
    
@Mark: of course there is such a method: just execute a 12-ball protocol leaving one ball aside. If one of the 12 is anomalous, you'll find it, and if not, you'll know it's the 13th. This works assuming you know there's precisely one anomalous ball. –  Alon Amit Apr 9 '12 at 6:00
    
@AlonAmit: and if I can tell the odd one from 13, I can do the same for 14 by your method? - Clearly not, but that depends on the nature of the solution for 13. I need the knowledge that exactly one is different. –  Mark Bennet Apr 9 '12 at 6:06
    
@Mark: Yes, like I said... you need the knowledge that precisely one is different. Maybe I'm misunderstanding what you're trying to say? What, in your view, is wrong with my proposed solution for 13? –  Alon Amit Apr 9 '12 at 6:08
show 1 more comment

marked as duplicate by Aryabhata, Hans Lundmark, Henning Makholm, t.b., Asaf Karagila Apr 9 '12 at 18:52

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

3 Answers

It's hard to believe this classic puzzle isn't already documented in MSE, but FWIW, here's one of the standard "static" solutions. "Static" means that the weighings are fixed in advance - we know which coin (or ball, or whatever) goes on which arm of the balance at each step regardless of the outcomes of previous weighings. This seems like a harder problem to solve, but in fact, it makes the process of finding a solution somewhat easier than the more natural case-by-case analysis.

Create a 3-by-12 matrix. The rows correspond to weighings, the columns correspond to coins. Each entry in the matrix is either L (the coin goes on the left of the scale in this weighing), R (the coin goes on the right) or O (the coin is left out in this weighing).

Now if a coin is heavy, it will make all the weighings in which it has L to be left-heavy, all those in which it is R to be right-heavy, and all the ones where it's O to be balanced. For a light coin it's the other way around. So each pair of (coin, weight bias) creates a sequence of results, and you just need to make sure that all those sequences are different for all the (coin, bias) combinations. In other words, the columns of the matrix must all be different, and moreover, none of them should be inverses of each other (since if coin x is the inverse of coin y, you can't tell a heavy coin x from a light coin y).

Here's an example solution (I use +, - and blanks here instead of R, L and O since it's easier to grasp I think) which has a little bit of structure making it easy to verify the requirements.

1 2 3 4 5 6 7 8 9 A B C
+     + - + -   - +   -
  +   + + - - -   - +
    + - + +   - -   - +

EDIT: to explain once again what all this means, in the first weighing we pit coins 1, 4, 6 and 10 against coins 5, 7, 9 and 12. The second weighing has 2, 4, 5, 11 against 6, 7, 8, 10 and the last one has 3, 5, 6, 12 against 4, 8, 9, 11. So the weighings are always 4 against 4, and as mentioned, the result of weighing #1 don't matter at all for how we choose to handle the other weighings. It's all static.

If coin 1 is heavy, for example, we'll get "Left, balanced, balanced". No other coin can do that by being heavy (there's no other column like this one) and no other coin can do that by being light (since there's no column that goes "- blank blank").

share|improve this answer
1  
The comment on the original post works with this scheme. If we have 13 balls/coins etc then there is one which is unweighed - and if all the others balance we know it is the bad one, but we don't know whether it is heavy or light. –  Mark Bennet Apr 9 '12 at 6:32
    
+1 I had never seen this problem solved this way. Your 3x12 matrix is curious in its own right. If you add a column of pluses (bad for this puzzle, but ignore that) instead of a column of blanks, you get the check matrix of the ternary Hamming code of length 13. If you playing football pools (guess the outcome, win/draw/loss, of 13 matches), then you can use the check matrix (for much the same reasons as in your solution) to generate a system $3^{10}$ 13-tuple guesses with the nice property that you can guarantee that one of the 13-tuples has at least 12 correct guesses. –  Jyrki Lahtonen Apr 9 '12 at 12:26
    
@Jyrki: honored to be the one bringing this to your attention :-) certainly the column condition on the matrix is equivalent to other objects in coding and design theory. –  Alon Amit Apr 9 '12 at 14:38
add comment

Here is the first solution I came up with. There may be a cleaner one to be found.

Weigh four against four to start. If they are equal, you can easily find the odd ball from the remaining four by weighing against two known balls, then one known ball.

If the scales are uneven, let us call the lighter one scale 1 and the heavier scale 2. Keep three balls on scale 1, then exchange the fourth with a ball from scale 2. Remove the remaining three balls on scale 2 and replace them with known balls.

If the scales now balance, you know that the odd ball was removed from scale 2, and is heavier than the others. If scale 1 is still lighter, you know that the odd ball is one of the three kept balls on scale 1, and is lighter than the rest. If scale 2 is lighter, the odd ball must be one exchanged between the two scales.

In all three cases, you can determine the odd ball in one more weighing.

share|improve this answer
add comment

Alon's answer is a good one, but it set me puzzling as to why it is that we can deal with 13 balls and not 14. After all, in three weighings there are 27 possible combinations (the scales can go either way, or be level). The answer for 13 balls allows us to discover the bad ball (13 options) and for twelve of these to say whether it is heavy or light - a total of 25 possibilities - what has happened to the missing two?

The problem is that we are constrained to use eight balls in each weighing - if we could use nine balls we would be able to use all the possibilities. This can be achieved if we have an extra ball, X, which we know to have the correct weight. With balls ABCDEFGHIJKLMN and X weigh as follows:

  1. ABCDX v IJKLM
  2. AEFIX v CDHLM
  3. CGIJL v FHKMX

This scheme enables us to identify whether any of the balls ABCDEFGHIJKLM is the bad one, and if so whether it is heavy or light. If all the weighings come out level, then N is the bad one, but we don't know whether it is heavy or light.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.