Member-only story
Debugging “Brooklyn 99" riddle — 12 men on an island…
In season 2 episode 18 of “Brooklyn Nine-Nine”, the following brain teaser was asked:
“There are 12 men on an island. 11 weigh exactly the same amount, but one of them is slightly lighter or heavier. You must figure out which. The island has no escapes, but there is a seesaw. The exciting catch? You can only use it three times.”
In the episode, the characters were not able to solve the puzzle, which led to a revelation of “deceit”, in order to create humor for the audience. However, the puzzle got me thinking, was there an actual solution to this brain teaser? And what would this solution be?
The following will contain the solution and spoil this puzzle. Don’t proceed if you want to try out the puzzle!
The “straightforward” conjecture
As a software engineer, I first pivot towards common problem-solving approaches that I was familiar with. One of the more well-known ones is binary-search.
The premise of binary-search goes like this — you have an ordered set of data, and by checking the exact center of the data, you can find out whether the information you are looking for is at the left or right of the center, hence halving the unknowns. By repeating this process multiple times, you’ll eventually find the answer in lesser tries than if you “brute-forced” and search the entire data set manually. To be more precise, lg(n) times where n is the total size of the data set.
However, for our brain teaser, we don’t have an ordered set of data. But we can model the problem to allow us to use the same principle and eliminate 1/2 the unknowns in each iteration, thus allowing us to arrive at the answer in much fewer tries than brute-forcing.
To do this, what we can do is to place 1/2 of the remaining unknowns on the seesaw (and also equally placed on both sides):
From the above, only 1 of 3 situations can transpire. The seesaw can either tip on either side, or it ends up being balanced.
- If the seesaw tips on either side in 2 of the…
