This article was originally posted on my website.
In the show Brooklyn 99, Captain Holt poses a brain teaser to his detectives:
There are twelve men on an island. Eleven weigh exactly the same amount, but
one of them is either lighter or heavier. You must figure out which. The island has no scales but there is a seesaw. The exciting catch? You can only use it three times.
I have misremembered this teaser twice. The first time I assumed that the odd person out was heavier and that the goal was to find the person that weighed the most.
That is fairly simple to determine; it is similar to binary search.
Put 6 people on one side of the seesaw and the other six on the other side. Discard the lighter half.
Split the heavier 6 into groups of three and weigh them against each other. Then put one person from the heavier side on each side of the seesaw. If they are equal then the third person must be the odd one out.
Otherwise, the heavier side of the seesaw is the odd one out.
I was pleased with myself for discovering it so quickly, then I remembered that Holt said the person was either lighter or heavier.
Trying to solve that occupied my thoughts for a long time. I could only get solutions that work most of the time. After looking it up, I found that it was actually mathematically impossible.
I think the approach I took to try to solve it is still interesting.
I reasoned that whatever approach I used had to filter out as many people as possible in the fewest amount of checks. To narrow down the suspect list as much as possible, from twelve to one.
It also had to be "symmetric". That is, no matter how the seesaw balanced, it had to reduce the suspect list the same. If one result reduced the suspect list from twelve to four, and another result reduced the suspect list from twelve to eight, then it wouldn't be a very effective method.
The approach I came up with worked like this:
First split the islanders into four groups of 3. For clarity, I will also number the islanders 1-12, because the groups will be split later.
Put group 1, islanders 1-3, on one side of the seesaw, and group 2 on the other. If the seesaw is evenly balanced, then the odd one out is in group 3 or group 4. If the seesaw is uneven, the the odd one out is in group 1 or group 2.
I'll refer to the groups that contain the odd one out as the "suspect groups" and the groups which have been shown not to contain the odd one out as the "control groups".
Put one of the control groups on one side of the seesaw and one of the suspect groups on the other side of the seesaw.
If the seesaw is evenly balanced, the the other suspect group becomes the only suspect group and everyone on the seesaw is now part of the control group.
If the seesaw is not evenly balanced, then the suspect group on the seesaw becomes the only suspect group.
By now the suspect group should have 3 people, and we can use the seesaw one more time.
There is also a 7% chance that we know if the odd person out is heavier or lighter. This is because we know which group contains the odd person out know, and if that group has previously been compared with a control group, then we know if they were heavier or lighter. However, there is also a chance that we don't know if the person is heavier or lighter, if we have determined that they must be a suspect group by elimination, if the seesaw was evenly balanced for every comparison.
If we know if the odd islander is heavier or lighter, than this is solvable. If not, then we can narrow it down to two people.
We do this by putting one person from the suspect group on each side of the seesaw.
If they are evenly balanced then the third person must be the odd one out. It is possible that we don't know if this person is heavier or lighter.
If the seesaw is not evenly balanced, then it is one of the two people on the seesaw who is the odd one out. If we know if the person is heavier or lighter, then we know who the odd one out is. Otherwise, we can only say that it is between those two.
On relistening to the clip so that I can write this post, I saw that the puzzle could be interpreted to mean: "find out if the odd person out is heavier or lighter"
In that case, it is solvable.
Instead of splitting into groups of 3, split into groups of 4. Weigh group 1 against group 2, then group one against group 3. If the seesaw is even in the first usage, then look at where group 3 is relative to group 1. If the seesaw was uneven in the second usage, then the second comparison will reveal whether group 1 or group 2 contained the odd one out, and since they were both compared in the previous usage, remembering which one was heavier or lighter reveals gives the answer.
All whilst only using the seesaw twice.
Top comments (0)