You are given twelve identical-looking balls and a two-sided scale. One of the balls is of a different weight, although you don't know whether it's lighter or heavier. How can you use just three weighings of the scale to determine not only what the different ball is, but also whether it's lighter or heavier?
Split this into three groups of four, A1, A2, A3, A4; B1, B2...; C1, C2... Each step here corresponds to one weighing.
- Weigh A against B.
- If A > B, then weigh A1, B1, and B2 against B3, B4, and C1.
- If the weights are equal, then one of A2...4 is heavier; weigh A2 and A3. If they are equal, A4 is heavier. If one is heavier, then that ball is heaviest.
- If the first group is heavier, then either A1 is heavier, or B3-4 is lighter. Compare B3 and B4; if they are equal, A1 is heavier; if they are different, the lightest is the lightest ball.
- If the first group is lighter, then either B1 or B2 is lighter. Weigh them and see.
- If A < B, renumber all A-balls to B-balls, and perform the above steps.
- If A = B, weigh A1, A2, A3 against C1, C2, C3
- If they are equal, then weigh A1 against C4. If A1 is lighter, then C4 is the odd ball and it is heavy. If A1 is heavier, then C4 is the odd ball and it is light.
- If A is heavier than C, weigh C1 against C2. If they are equal, then C3 is the odd ball and it is lighter. If they are not equal, then the lighter of the two balls is the lightest ball
- If A is lighter than C, weigh C1 against C2. If they are equal, then C3 is the odd ball and it is heavier. If they are not equal, then the heavier of the two balls is the heaviest ball.
- If A > B, then weigh A1, B1, and B2 against B3, B4, and C1.
We can work backwards from the third step to see, approximately, why this works. At the third weighing, the options need to be reduced to either two or three balls. This means that the second weighing must reduce to either two or three possible balls.
We know that the first step will remove either 1/3 or 2/3 of the possible solutions, no matter what you do. This means that, in the 1/3 case, you need to split the possibilities down from 8 into a group of 3, a group of 3, and a group of 2. From this, the third weighing points to the odd ball out. Because this case implies one set of balls is heavier, by virtue of finding the odd ball out, we know whether it's heavier or lighter, so we actually don't need to worry about this piece of information at all.
In the 2/3 case, you need to reduce the possibilities into a group of 3 and a group of 1, which is easy enough to do intuitively. Because we actually don't know the relative weight of the odd ball in this case, the information from the third weighing must be used to determine whether the ball is heavier or lighter.
There is another way to do this problem, that doesn't involve any sort of conditional branching at all. It is in fact possible to set a fixed weighing schedule beforehand and still determine which ball is lighter or heavier in just 3 weighings. I'll explain how below.
The gist of problems like these is, how much information can you get from the procedure you're allowed to undertake? With each weighing, the scale can either tip to the left, tip to the right, or stay balanced. This gives you a total of 33 = 27 possible outcomes, and in this case you need to discern 24 results from them (one of 12 balls is either light or heavy, which is 12 × 2 = 24).
So, we need to begin the tedious task of mapping each result to an outcome.
One of the things we can immediately notice is that there are also three states each ball can be in during each weighing - on the left side of the scale, on the right side of the scale, or off the scale. Naturally, this maps to the states of the scale in a way that's intuitively analogous:
If the odd ball out is heavier...
- and the ball is placed on the left side, the scale will tip to the left.
- and the ball is placed on the right side, the scale will tip to the right.
- and the ball is off the scale, the scale will remain balanced.
If the ball is lighter, the first two cases are inverted.
There are 27 possible ways to place each ball in all three weighings, each corresponding to a different outcome if that ball is the odd one out. We need to find an arrangement of balls where each possible set of placements and its inverse (for the heavy and light cases) is distinct.
Here's a preliminary arrangement that satisfies the distinctness property:
Ball 1 2 3 4 5 6 7 8 9 10 11 12 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10-11-12 W1 L L L L L L L R R R R R R R R L W2 L R L L L L R L R L R R R R L R W3 L R R L L R L L R L L R R L R R L = place it on the left This second table lists the inverses. R = place it on the right Notice that no possible arrangement = leave it off appears more than once in both tables.
Right away, we run into the problem that we're not putting the same number of balls onto each scale. If you have seven balls on one side and one on the other, of course the scale is going to tip to the side with seven balls (unless your odd ball out is ridiculously heavy, but let's not entertain that scenario). So we need to invert a few of these configurations so that we're putting four on each side for each weighing. With some trial and error, we can get something like this:
Ball 1 2 3 4 5 6 7 8 9 10 11 12 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10-11-12 W1 L L R R L R R L R R L L R L L R W2 L R L R L R L R R L R L R L R L W3 R L R L L L R R L R L R R R L L
So our final weighing schedule of balls is as follows:
Weighing 1: 1 4 8 12 / 5 7 10 11 Weighing 2: 2 6 9 11 / 4 7 10 12 Weighing 3: 5 8 9 10 / 3 6 11 12
And the outcomes are interpreted as such:
= = L : 3L L = = : 1H R = = : 1L = = R : 3H L = L : 8H R = L : 5H = L = : 2H L = R : 5L R = R : 8L = L L : 9H L L = : 7L R L = : 4L = L R : 6H L L R : 10L R L L : 12L = R = : 2L L R = : 4H R L R : 11H = R L : 6L L R L : 11L R R = : 7H = R R : 9L L R R : 12H R R L : 10H = : scale balanced L : scale tipped to the left R : scale tipped to the right nL : ball n is light nH : ball n is heavy
And thus, we've created a weighing scheme where each weighing is completely predetermined beforehand, that still manages to determine which ball is the odd one out, and whether it's lighter or heavier.
You might notice that we didn't use
=== in our arrangements.
We can't use
RRR as a 13th pair for a 13th ball, because then we'd end up having to put nine balls onto the scale, and there's no way to do that since nine is odd. We could probably use it in place of one of the
LLR/RRL pairs, but leaving
RRR out makes for a symmetry in the result chart that I rather like.
However, what's interesting is that you can have a 13th ball that you never place on any scale, and if your scales balance out in all three weighings, the 13th ball you never weighed is the odd ball out (although you obviously can't tell without a fourth weighing whether it's lighter or heavier).
Some of the existing answers to this ancient question are excellent, but there's one famous answer that I think deserves mention here. It comes from an article in Eureka, the annual magazine of the University of Cambridge's student mathematical society, written by C A B Smith under the pseudonym of "Blanche Descartes".
It has two very nice features. The first is that it's an "unbranching" solution: you don't need to change what you do on later weighings depending on the results of earlier ones. The second is that once you've seen it it's almost impossible to forget.
Smith's solution is written entirely in verse and includes an explanation of how it all works, but I shall quote only the actual answer. "F" here is our protagonist Professor Felix Fiddlesticks, whose mother has asked him for help with the puzzle. I have made some trifling changes to the original formatting.
F set the coins out in a row
And chalked on each a letter, so,
To form the words:
F AM NOT LICKED
(An idea in his brain had clicked.)
And now his mother he'll enjoin:
"MA, DO / LIKE
ME TO / FIND
FAKE / COIN!"
Each of the three lines of F's injunction describes one weighing. When you've done them all, the results uniquely determine which coin is fake and in which way.
I spent some time working on this puzzle after it appeared on "Brooklyn Nine-Nine" (if you want, you can watch Captain Holt describe the puzzle here) and I wrote a detailed, illustrated solution here: Island of Tyreses Solution. In this particular version I am attempting to find an islander, Diffy, who is either heavier or lighter than the other 11 islanders.
The final solution takes into account two things I learned from previous attempts:
In a group of four, I can identify Diffy in two weighings.
A. First, I set two islanders from the group against two known non-Diffys. If the see-saw tilts, I know that Diffy is one of these two. If the see-saw remains even, I know that Diffy is one of the other two.
B. Now, I select one of the remaining two possible-Diffys and set him against a known non-Diffy. If the scale tilts, I have found Diffy. If the board remains even, I know that Diffy is that last remaining islander.
C. Alternatively, if the see-saw tilts in Step A, and you want to know whether DIffy is heavy or light, you could note the direction from Step A and put the two remaining possible-Diffys on the scale opposite one another. If the see-saw tilts in the same direction as Step A, then Diffy is the one still on the same side as he was during Step A. Otherwise, if the orientation of the see-saw changes, Diffy is on the other side.
- In a group of three I can identify Diffy in one weighing, as long as I have directional information. I will describe this in further detail under Use #3.
Because of lesson #1, I can split off four islanders before checking the rest. If Diffy is in that group of four, the first weighing will come out even, and I can now identify him from among those four with my two remaining moves. If Diffy is not in that group of four, I now have four islanders whom I can rule out and also use to tare my see-saw.
So, for my first use of the see-saw, I weigh the eight remaining islanders against each other with four on each side.
I’ve already outlined my plan if this first see-saw usage turns out even, so what’s next if it turns out odd? This is where the genius comes in.
I now have some “directional information.” I will henceforth call whichever direction the see-saw tilted in Use 1 “Direction 1″ or “D1″ for short. I know that if Diffy is heavy, he is on the part of the see-saw that went down, and if if Diffy is light, he’s on the part of the see-saw that went up. If I move Diffy, the see-saw will change orientation! It has no choice because Diffy, and only Diffy, causes the see-saw to tilt. Also, remember lesson #2, I have directional information and one move after the current one, so I can totally take out three possible Diffys before the next use of the see-saw. I’ll need to use one of the islanders I ruled out in Use 1 in order to keep three islanders on each side.
If Use #2 gives us an even see-saw we can find Diffy in the three we removed, but if it doesn’t, we need to pay attention to the direction that the see-saw moves. Did it move the same way as before, Direction 1, or did it change orientation to Direction 2? Our next choice will be based on the answer! If it moved in Direction 1, then we know that Diffy is not one of the islanders who switched sides for Use #2. If the see-saw moved in Direction 2, then Diffy is one of the side-switchers. Either way, we have got him down to being one of three or two. Use #3 is a little hard to generalize since it is different for each possibility.
In the case where I have a group of three possible-Diffy islanders, two of those islanders were on the same side during Use #1, when the see-saw moved into D1. If I put one of these islanders on each side of the see-saw and the see-saw again moves into D1, then we know that Diffy is the islander on the original side. If the see-saw moves into D2, then we know that Diffy is on the opposite side of the see-saw. If the see-saw remains even, we know that Diffy is the third member of the group.
All Mapped Out
This is a rewriting by R. Allen Gilliam of Jared Anderson's solution from another version of this puzzle on this site. Perhaps it's just how my mind works, but this seems much easier to understand.
Number the men (or coins, or balls) 1 through 12.
Weigh 1 2 3 4 against 5 6 7 8.
If they're the same, then the different man is 9 10 11 or 12. Skip to I below.
If they're different, make note of whether 1 2 3 4 is heavier or lighter.
Weigh 1 2 3 5 against 4 10 11 12. (Notice that we know 10 11 and 12 are not the different one.) There are three possibilities:
(1) If 1235 has the same difference (heavier or lighter) as 1234, then the different one must be 1 2 or 3 and has the same difference (heavier or lighter) as 1234. Skip to II below.
(2) If 1235 balances 4 10 11 12, then the different one must be 6 7 or 8 (the ones we removed) and has the same difference (heavier or lighter) as 5678. Skip to II below.
(3) If 1235 now has the opposite difference (heavier or lighter) as 1234, then either 4 or 5 is the different one. Either 4 has the same difference as 1234 (heavier or lighter) or 5 has the same difference as 5678 (heavier or lighter). So we simply weigh 4 against 1. If they're the same, then 5 is the different one. If they're different, then 4 is the different one.
I. Finding which of 9 10 11 12 is different with two weighings when you don't know whether the different one is heavier or lighter:
Weigh 9 against 10. Two possibilities:
(1) If they're different, then it has to be 9 or 10. Weigh 9 and 11. If they're the same, 10 is the different one. If they're different, it's 9.
(2) If they're the same, then it has to be 11 or 12. Weigh 9 and 11. If they're the same, 12 is the different one. If they're different, it's 11.
(If it's 12, we won't know whether he was heavier or lighter since we never weighed him. We found him by process of elimination. He must be the different one since all the others weigh the same.)
II. Finding which of three men is different with one weighing when you know whether the different one is heavier or lighter:
Rename the three men 1 2 3. Weigh 1 against 2. Two possibilities:
(1) If they're the same, 3 is the different one.
(2) If they're different, whichever one has the correct difference (heavier or lighter) is the different one.
This seems to be the simplest solution for 12 items if you only must find the item of different weight, as some versions of the puzzle ask. Joe Z's solution can find the item and the difference with 12 items, and the different item with 13 items. Finding the different item and the difference with 14 items seems mathematically impossible with 3 weighings because there are only 27 possible outcomes with 3 weighings and there are 28 possibilities with 14 items. But could a variation of Joe Z's solution find the different item out of 13, and whether it's heavier or lighter? If so, then finding the different one but not the difference with 14 items would be possible. Finding the different one but not the difference out of 15 would be impossible because you can leave only one item out of the weighings while still being able to identify the different one, and if you weigh the item then you'll know whether it's lighter or heavier which we know is mathematically impossible with 14 items.
This solution is similar to the one provided by R Gilliam but differs in the second step. Divide the balls into 3 groups of 4 balls each. Let's call them g1 g2 and g3 pick any two groups and weigh them against each other. One of two scenarios is true. The pans are balanced: the 8 balls you just weighed all have the correct weight. The pans are unbalanced: The 4 balls you did not weigh all have the correct weight.
Either way at the end of the first weighing you have at least 4 balls of the correct weight.
For the second weighing one side of the pan should have 3 balls of the correct weight. If the pans were unbalanced after the first weighing put 3 balls from one of the unbalanced pans into the other pan. If the pans were balanced after the first weighing put 3 of the 4 balls that sat out the first weighing into the other pan.
If the pans are unbalanced after this weighing you will know whether the oddball is heavier or lighter since one of the pans contains balls of the correct weight. If the pans are balanced the 4 th ball that was left out is the oddball and you can find out if it is heavier or lighter by weighing it against a correct-weight ball.
If the pans are unbalanced, you know whether the oddball is heavier or lighter. Take 2 of the 3 balls from the pan (that does not contain the correct weight balls) and weigh them one against the other. You already know whether the oddball is heavier or lighter. If the pans are unbalanced pick the pan that matches the weight direction of the oddball. if the pans are balanced the 3rd ball is the oddball.
You can also solve it using 4 groups of 3 balls. Weigh 3 against 3 and if it balances, you can keep those 6 balls aside as known-equals. If they don't balance, you know the odd ball out is in that group of 6. Next, weigh 3 of the known-equals against either of the 2 groups of 3 unknowns. If it balances, the odd one is in the final group of 3. If it doesn't balance, you know the odd one is in still on the scale. Finally, using the last group of 3 balls that is unknown and unequal, put one on each end and keep the third aside. If the scale balances, you know the lone ball you kept aside is the odd ball. If the scale doesn't balance, you know the odd ball is on the scale. To determine the odd ball and whether it's heavier or lighter, you need to have noted whether the unknown group was heavier or lighter than the known-equal groups. If they were heavier, then the lone ball is heavier.
Way 6 against 6. Then removing 2 balls at a time until the scale eavens out, you can determine that either one of those two last balls is uneaven.
The rest is easy.
(1) Place balls 6 and 6 on scale. Remove one from each side until scale balances.
(2)Take last two removed (or remaining two if scale never balanced) and place on one side (side A) and two equal weighted balls on other (side B). If side A is lower the oddball is heavier, if side B is lower oddball is lighter. Remove one from each side. If scale balances, the ball removed from side A is the oddball, if not the ball remaining on side A is.