Brooklyn 99 and the Islander Problem
And some information theory
There are 12 men on an island (referred to as “islanders”). All of them have the same weight except for one, that is either heavier or lighter. The challenge is to find who this islander is and whether or not he is heavier or lighter.
This problem was introduced by Captain Holt in a Brooklyn 99 episode (season 2, episode 19) I was watching with my girlfriend. It made us crazy, and may have endangered our relationship. After a few minutes of trying, we decided to give up and continue the episode. The solution is not revealed during the episode, which left me wondering.
As I woke up the following morning, I realised that this problem has been featured in one of my favourite textbooks, MacKay’s Information Theory, Inference and Learning Algorithms. This made me very happy.
The Problem
There are 12 men on an island (referred to as “islanders”). All of them have the same weight except for one, that is either heavier or lighter. The challenge is to find who this islander is and whether or not he is heavier or lighter.
To do so, there is a simple seesaw (traditional scale with two pans) that can only be used 3 times. How would you proceed?
To operate the seesaw, you can place as many islanders as you want on both pans. The seesaw will generate one of the following outputs:
- Left pan is heavier
- Right pan is heavier
- Both pans have an equal weight
If that sounds like a challenge, I would suggest you give it a try with the app below.
The Game
This is a quick implementation of the Islander problems. You have three weighings, and can drag items to the scale and press “Weigh”. Once ready, you can guess the odd islander. Press “New Game” to start again.
| # | Left pan | Right pan | Outcome |
|---|
The problem is non-trivial, and requires a structured approach. Before the first weighing, there are 24 possibilities. Each of the 12 islanders can be either heavier or lighter. These hypotheses can be noted:
\[ \{1^-,2^-,\dots,12^-,1^+,2^+,\dots,12^+\} \]
Similar to a game of Guess Who, the goal is to find the weighings that eliminate the highest number of hypotheses.
In Guess Who, the best questions eliminate half of the hypotheses. These questions include: “Is the mystery person a man?”, “Do they wear glasses” or “Do they have white hair?”. Can we do the same with the islanders? Can the first weighing eliminate half of the 24 hypotheses shown above?
This may have been a leading question. The short answer is yes, we can even do better than this. This can be done by weighing 1,2,3,4 against 5,6,7,8.
Let’s explore why, depending on the three cases:
- Left pan heavier: this means that either one of 1,2,3,4 is heavier or that one of 5,6,7,8 is lighter; all other hypotheses are ruled out. We only retain 8 hypotheses out of 24, a reduction by a factor 3!
- Right pan heavier: same as above, either one of 1,2,3,4 is lighter or one of 5,6,7,8 is heavier. This is a total of 8 hypotheses out of 24
- Equal weight: the anomalous islander is in 9,10,11,12 but we do not know if he is heavier or lighter. This is another 8 hypotheses
How did we manage to divide the hypothesis space in three? In Guess Who, the best questions only reduce the number of hypotheses by two (e.g., “is the mystery person a man?”).
This difference is related to the amount of information contained in the outcome of the question.
In Guess Who, the outcome of the question is either “Yes” or “No”. With a binary reply, we can do no better than splitting the hypothesis space in two. Weighing groups of islanders has three outcomes: (1) left pan heavier (2) right pan heavier (3) equal weight. It conveys more information than a yes/no answer and allows (with a good strategy) us to split the hypothesis space in three.
Moving forward, the goal of each weighing should be to eliminate around two thirds of the remaining hypotheses. Let’s imagine that the left pan was heavier at the first weighing. This means that either one of 1,2,3,4 is heavier or that one of 5,6,7,8 is lighter. We will note this:
\[ \{1^+,2^+,3^+,4^+,5^-,6^-,7^-,8^-\} \]
What weighing would you do to divide the number of hypotheses by three? Think about it before reading on. There are many right answers.
One way to go is to weigh 1,2,5 against 3,4,6.
Let’s explore the possible outcomes:
- Left pan heavier: one of 1 or 2 is heavier, or 6 is lighter, all other hypotheses are ruled out. Only 3 hypotheses out of 8 remain
- Right pan heavier: one of 3 or 4 is heavier, or 5 is lighter, all other hypotheses are ruled out. Only 3 hypotheses out of 8 remain
- Equal weight: either 7 or 8 is lighter, only 2 hypotheses
The last weighing from there should be trivial, and will be left to the reader.
One optimal strategy is summarised in the tree below:
Final Thoughts
Now, what about playing again?
Footnotes
By Francisco Goya — gallerix.ru, Public Domain, Link.↩︎
By Unknown — https://boardgamegeek.com/image/335812/guess-who, Fair use, Link.↩︎