A logic puzzle involving a balance.

Question

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%?

Answer 1

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.

Answer 2

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

Answer 3

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.