One of my favorite shows right now is Brooklyn Nine-Nine. During season 2 episode 18, titled “Captain Peralta”, Captain Holt presents this riddle to the team:

There are twelve men on an island. Eleven weigh exactly the same amount, but one of them is slightly lighter or heavier. You must figure out which. The island has no scales, but there is a seesaw. You can only use it three times.

This isn’t exactly a programming post, but it does demonstrate the same kind of problem solving that is often found in devising efficient algorithms.

I decided to represent each islander with a letter from A to L. This makes it easy to unambiguously and concisely represent combinations of islanders. I show each trial with the seesaw as a column. The “Test” column shows what islanders are put on the seesaw as left vs. right. The “Result” column shows “=” if both sides were equal, “<” if the left side weighed less than the right, or “>” if the left side weighed more than the right. Then the “Possibilities” column shows what possible solutions remain given the result of the trial. As we move from the 1st trial towards the 3rd we can see the remaining possibilities reduce as more results eliminate solutions.

When solving this puzzle we know right away that we cannot rely on the seesaw always tilting to the left or right. This seems to be people’s initial attempt at solving this problem. Just put six on one side and six on the other and work your way down. However, 3 trials and only 2 possible results would only give us up to 8 solutions because 2 x 2 x 2 = 8. So we know that we have to rely some trials being balanced to find all the solutions. Therefore, it is probably not a good idea to put six vs. six because there is no way that seesaw could be balanced since the different islander would always be on the seesaw giving only two possible results which doesn’t tell us which side the different islander is on.

The first trial that gives the most information is to do four vs. four (ABCD vs. EFGH). No matter what the result we have reduced the possible solutions from 24 to 8.

• If the seesaw is equal then we know those eight islanders (ABCDEFGH) can be eliminated from being either lighter or heavier. The remaining four islanders (IJKL) could then be either lighter or heavier.
• If the seesaw is unbalanced then we know the four untested islanders (IJKL) can be eliminated. We also know that all the islanders on the heavier side cannot be lighter. And all the islanders on the lighter side cannot be heavier.

What we do for the second trial depends on the type of result for the first trial because the pattern of remaining possibilities is different.

• If the first trial was balanced then we have four remaining islanders (IJKL) that could be either lighter or heavier. We can work out the remaining possibilities by comparing three remaining islanders (IJK) with three normal islanders (ABC).

  Possibilities	Test	Result	Possibilities
  I lighter I heavier J lighter J heavier K lighter K heavier L lighter L heavier	IJK vs. ABC	=	L lighter L heavier
  		<	I lighter J lighter K lighter
  		>	I heavier J heavier K heavier

  • If the second trial was balanced, then you know that that last remaining islander (L) is the different islander. Compare him with any other islander. That will tell you if he is lighter or heavier than the other islanders. This third trial cannot be balanced since we know that this last islander (L) is different from all the other islanders.
  • If the second trial was unbalanced, then you now know if the different islander is either lighter or heavier. You also know that the last untested islander (L) is normal. You can weigh two of the remaining islanders against each other to determine which of the remaining three islanders is different. I will show the case where the three islanders (IJK) are lighter.

    Possibilities	Test	Result	Possibilities
    I lighter J lighter K lighter	I vs. J	=	K lighter
    		<	I lighter
    		>	J lighter

• If the first trial was unbalanced, then this gets much less intuitive. For simplicity, we will only consider the result where the left side is lighter than the right side (ABCD < EFGH). The last case where the left side is heavier than the right side is just the inverse. The key to this trial is to find a test that will make the best use of the three possible seesaw results. Specifically, we don't want to use a test that only has two possible outcomes (like ABC vs. EFG). So I chose to take two potentially lighter islanders with one potentially heavier islander for each side (ABE vs. CDF). This has all three possible outcomes and leaves us with either two or three remaining possibilities.

  Possibilities	Test	Result	Possibilities
  A lighter B lighter C lighter D lighter E heavier F heavier G heavier H heavier	ABE vs. CDF	=	G heavier H heavier
  		<	A lighter B lighter F heavier
  		>	C lighter D lighter E heavier

  • If the second trial is balanced, then you only have two potentially heavier islanders left. Just weigh them against each other and whoever is heavier is the different islander. It is not possible for this last trial to be balanced since you know one of them is the heavier islander.
  • If the second trail is unbalanced, then weigh the remaining potentially lighter islanders against each other. If the third trial is balanced then the last potentially heavier islander is the different islander. If the third trial is unbalanced, then the islander on the lighter side is the different islander.

Here is the full solution: