Twelve Men and a Seesaw

And they began to be sorrowful, and to say unto him one by one, Is it I? and another said, Is it I?  And he answered and said unto them, It is one of the twelve...

                                                                                                  Mark 14:19

Suppose there are twelve men, eleven of whom weigh exactly the same amount, and one of whom weighs a different amount. Using a seesaw to compare (greater than, less than, or equal to) the weights of various subsets of these men, can we identify the odd man, and determine whether he is heavy or light, with just three comparisons?

If we were told that the odd man’s weight was greater than the others (rather than just different), it would be easy to identify him with just three comparisons: Split the twelve men into three groups of four, and place two of the groups on opposite sides of the scale (first measurement).  This immediately tells us which of the three groups contains the heavy man, because the scale will tip toward that group, or, if it doesn’t tip, the heavy man must be in the group not on the scale. Then, focusing on the heavy group of four, we can place two of those men on the scale (second measurement), and it will tip toward the heavy man, or else be balanced, in which case we can put the other two men on the scale (third measurement), and it will tip toward the heavy man. So it is easy to solve the puzzle if we know the odd man is heavy. Similar reasoning would apply if we knew that the odd man was light.

However, in the actual puzzle, we don’t know (in advance) whether the odd man is heavier or lighter than the others. This is what makes the puzzle challenging, but we can still apply similar reasoning to identify the odd man in just three measurements, and these measurements will also reveal whether the odd man is heavy or light.

First Solution

We begin just as in the solution of the simpler problem, by splitting the twelve men into three groups of four, and placing two of those groups on opposite sides of the scale (first measurement). There are two possible outcomes:

Case 1:  The first measurement is balanced.   In this case we know the odd man is in the group of four that is not on the scale.  We place three of those men on one end of the scale, and place three of the normal men (from the other groups) on the opposite end (second measurement). Again there are two possible outcomes:

Case 1A:  The second measurement is balanced.  In this case we know the odd man is the only one that hasn’t been on the scales yet. We can then place him on the scale opposite a normal man (third measurement) to determine whether he is heavy or light.

Case 1B:  The second measurement tips.  In this case, we know one of the three men who were not in the first measurement must be the odd man, and we know whether he is heavy or light based on which way the scale tips. We can then place two of these three on opposite sides of the scale (third measurement), and if it tips, we know which of those two is the odd man. If it doesn’t tip, the third man is the odd one.

Case 2:  The first measurement tips.  In this case we know that the four men not on the scale are all normal, and we know that either (a) one of the four men on the heavier side is an odd heavy man, or (b) one of the four men on the lighter side is an odd light man.  At this point we need to decide how to make our second measurement, in such a way that only one additional measurement will suffice to identify the odd man.  Now we make the key step:  For our second measurement, replace three of the men from the lighter side of the scale with three normal men (from the group of four that was not on the scale for the first measurement), and swap the remaining man from the original lighter side with one of the men from the heavier side.  There are three possible outcomes:

Case 2A: The second measurement is balanced.  In this case the odd man must be one of the three that we removed from the lighter side after the first measurement.  Therefore, we know the odd man is light, so we can simply place two of those three men on opposite ends of the scale (third measurement) to determine which one is light, or, if they balance, to conclude that the remaining man is the odd light one.

Case 2B:  The second measurement tips in the same direction as the first.  In this case it’s clear that the two men we swapped must be normal, as are the three normal men we placed on the original lighter side, so one of the three men remaining on the original heavy side must be an odd heavy man.  We can simply place two of those three men on opposite ends of the scale (third measurement) to determine which one is heavy, or, if they balance, to conclude that the remaining man is the odd heavy one.

Case 2C:  The second measurement tips in the opposite direction as the first.  In this case we know that one of the men we swapped from side to side must be the odd man.  Specifically, either the man we moved from the original heavy side is an odd heavy man, or the man we moved from the original light side is an odd light man.  Placing one of these on the scale opposite a normal man (third measurement) suffices to determine which of these two possibilities applies.

To clarify the solution, Let A,B,C,D denote the four men on the heavy (or equal) side of the first measurement, let a,b,c,d denote the four men on the light (or equal) side of the first measurement, and let w,x,y,z denote the four men not involved in the first measurement. The sequence of measurements is as depicted below.

Beneath each of the six lower scales we have listed the odd man, depending on whether the scale tips left, right, or is balanced. For example, if the left-most scale tips left the odd man is A, and if it is balanced the odd man is C, and if it tips right the odd man is B. Beneath the results on the lower right hand side of this figure we have used the symbols “H” and “L” to signify that the odd man is Heavy or Light respectively.

The only non-trivial step in this process is the second measurement after the first measurement is balanced. The justification for this step comes from the realization that we can solve for a set of three men with a single measurement if we know the odd man in that set is lighter than the others. (Of course, we could also have set aside three men from the heavy side, and carried out the analogous process.) It follows that by omitting three men from the light side, and replacing them with three normal men, and then swapping the d and D men, the second measurement effectively leaves us with three possible outcomes: (1) the odd man is one of A,B,C and is heavy, (2) the odd man is one of a,b,c and is light, or (3) the odd man is D (heavy) or d (light). In any of these three outcomes, a single measurement suffices to identify the odd man.

Incidentally, in the figure above we denoted by an asterisk (*) two outcomes that are impossible. When D and w are compared, we already know that w is normal and D is either normal or heavy, so the scale cannot tip right in that case. Likewise when w and z are compared, we already know, by the process of elimination, that z is the odd man, so it cannot be balanced. If it did balance in that case, we would have proven that none of those twelve men is odd, so we could conclude that a thirteenth man – who have never been on the scales – must be the odd man.

This might seem to suggest that we haven’t made full use of the three measurements, raising the question of whether it might be possible to solve the problem for more than twelve men. Notice that, a priori, there would be three possible outcomes (tipping left, balancing, or tipping right) on each of the three measurements, so there could be 3³ = 27 possible distinct outcomes. Ideally we would like to make full use of all these possible outcomes, such that each outcome identifies a unique man, and whether he is heavy or light.

Second Solution

For clarity, we will represent the possible outcomes as trinary numbers, i.e., numbers in the base 3, from 000 to 222, letting “0” denote tipping left, “1” denote balanced, and “2” denote tipping right. Because of the symmetry between heavy and light, it’s clear that complementary outcomes, such as 021 and 201, must represent the same man, one signifying that he is heavy and the other that he is light. Therefore we could try to associate a man with each of the fourteen possible outcomes (or the complements) shown below.

The “Placement” column signifies the side of the scale on which we place this man during the three measurements. An asterisk signifies that the man is not on the scales for that measurement. For example, Man 11 has the placements *RL, which means he is not on the scale for the first measurement, he is on the right side of the scale for the second measurement, the Left side of the scale for the third measurement. These placements match the corresponding trinary number (or the complement) for the outcome identifying that particular man. Initially we simply map 0 to L, 1 to *, and 2 to R, but for the rows identified with “complement” we swap Left and Right. (For rows with two “complements”, we swap twice, which returns the number to the original expression.) This is because if we simply assigned the Left and Right sides according to the basic trinary numbers we would have nine men on the scales for each measurement, and most would be on the left side. To create suitable measurements, we must omit one man (denoted as Man 0 in the above table), and then we must take the complements of some of the arrangements (as indicated in the table above), so that each measurement has four men on the left and four on the right. This leads to the three measurements

These measurements are independent, unlike the first solution, in which the choice of measurements was contingent on the outcomes of the previous measurement(s). Using the trinary numbers to denote the outcomes of these three measurements, we can identify the odd man and his weight according to the table below.

Outcome 111 (all three measurements are balanced) is complementary to itself, and this outcome is impossible if one of the twelve is the odd man. Therefore, the “trinity outcome” 111, should it occur, would imply that the hypothetical Man 13, who is never on the scales, is the odd one, but we wouldn’t know if he is heavy or light.

Generalization

A similar question can be posed for any number of measurements. For example, if we were allowed just two measurements, instead of three, we could apply the same “trinary” reasoning as above to determine

Based on this, the two measurements would be

Depending on the outcomes of these two measurements, we can then determine which of the four men (1 through 4) is the odd one, and if it is one of the first three we can also determine whether he is heavy or light, according to the table below, where “0” denotes tipping left, “1” denotes balanced, and “2” denotes tipping right.

Recall that with three measurements we could find the odd man from a group of twelve men (or 13, if we don’t need to determine whether he is heavy or light). With only two measurements we can only find the odd man from a group of three men (or four, if we don’t need to determine whether he is heavy or light).

Suppose we are allowed four measurements. From how many men can we identify the single odd man? The answer is 39 (or 40, if we don’t need to determine whether he is heavy or light). To determine the men to place on the scales for each measurement, we begin by listing the 41 four-digit trinary numbers from 0000 to 1111 in numerical order. Then we exclude the number “0000” because that would result in 27 men on the scales for each measurement, which is an odd number. Each of the remaining 40 numbers is associated with one of the men, and the nth digit of each number signifies whether that man is on the Left side of the scale (“0”), not on the scale (“1”), or the Right side of the scale (“2”). However, with this interpretation, the first measurement would consist of 26 men on the Left side of the scale and 0 men on the Right side. The second measurement would consist of 17 on the Left and 9 on the Right. The third measurement would consist of 14 on the Left and 12 on the Right. The fourth measurement would consist of 13 on the Left and 13 on the Right. We will denote these results as (26|0), (17|9), (14/12), (13|13). Obviously, with the exception of the fourth measurement, these are not suitable measurements.

To provide a suitable set of measurements, we need each column of digits to contain 13 Left (i.e., the digit “0”) and 13 Right (i.e., the digit “2”). To accomplish this, we need to replace some of the numbers with their complements, just as we did in the cases of two measurements and three measurements above. In the previous cases, we just made ad hoc selections, and didn’t explain how we had made those selections. But we can actually proceed in a systematic way.

First, we take the complement of every odd number on the list. Once we have done this, the tallies of Left and Right are (13|13), (12|14), (13|13), and (12|14). Then we complement the number that was originally 1000. We already complemented this on the first step (because it is an odd number), so it is 1222, and complementing it again returns it to its original value of 1000. This doesn’t affect the L/R count for the first measurement, but it reduces the number of “2” digits by one and increases the number of “0” digits by one for each of the later measurements. Therefore we have the tallies(13|13), (13|13), (14|12), (13|13). Next we complement the number 1100, changing it to 1122. This doesn’t affect the first two measurements, but it reduces the number of “0” digits by one and increases the number of “2” digits by one for each of the last two measurements. Therefore we have the tallies (13|13), (13|13), (13|13), (12|14). Then we complement the number that was originally 1110, which was complemented previously (because it is an odd number), so we are changing it from 1112 back to 1110. This doesn’t affect any of the first three measurements, but reduces the number of “2” digits by one and increases the number of “0” digits by one for the last measurement. This leaves us with the tallies (13|13), (13|13), (13|13), (13|13), so we’ve arrived at a suitable set of measurements. Formally we could complete the process by complementing the number 1111, which doesn’t affect any measurement.

In general, if we are allowed N measurements, we can determine the odd man and whether he is heavy or light from up to (3^N – 1)/2 – 1 men, and for each of the N measurements we place (3^N−1 – 1)/2 men on the scales. The selection of men to place on the scales for each measurement can be read directly from the list of trinary numbers from 00...001 to 11...111, after we have first complemented each odd number and then complemented each of the numbers that were originally 10...00, 110...00, 1110...00, ... 1111..111. For example, with N = 5 measurements, we can resolve up to 120 men, placing 40 men on each side of the scale for each measurement, selected by the trinary list of numbers from 00001 to 11111 after first complementing all the odd numbers and then complementing the numbers that were originally 10000, 11000, 11100, 11110, and 11111.

Return to MathPages Main Menu