The 12 Islanders
Recently I was watching an episode of Brooklyn 99 in which Captain Holt poses a challenge, the 12 islanders problem. The problem feels simple at first but as I turned it over casually in my head, I quickly became stuck. Not being one to let a problem lie I sat down last weekend to work my way though it and ended up with what feels to me to be a beautiful solution worth sharing.
The Problem
You are stuck on an island with 12 men. 11 of the men weight the same but one weighs more or less than the other 11. You have a seesaw that you can use 3 times. Find the odd one out (OOO).
Simple enough but the fact that you don’t know wether the OOO is heavier or lighter sticks a spanner in the works. Early attempts yielded the following observations.
A heavier OOO on one side gets the same result as a lighter OOO on the other. (As such weighing 6v6 gives no information.)
Unless you get lucky you can’t use a tree based/If-this-then-that method as it will need 4 uses of the see saw. (This solution is to divide the islanders into 3 groups of 4, A, B & C. weight AvB & BvC after these you will know which group of 4 has the OOO and whether they are heavier or lighter, now weigh 2v2 from the OOO group and then 1v1 from the OOO pair)
Given that you can’t use the tree method the solution has to be some form of combinatorics
3v3 with 6 held out gives the most information from 1 use but 4v4 with 4 held out give more information from multiple uses.
The Solution
Because of the observations we are looking for a set of 3 tests of 4vs4 that results in a unique set of results for each of the 12 men should they be the odd One Out. Additionally because of observation 1 above left vs right tells us nothing on it’s own. It is only if the heavier side changes, stays the same, or the seesaw balances from 1 use to the next that we get any information. For example if the seesaw moves from balancing to being heavier on one side we know that the OOO is one of the men we just added to the seesaw.
After 2 uses there are 5 possible sets of results each of these results isolating at most 3 candidates as the OOO.
Balanced both times. Only 11 & 12 are held out both times and so the OOO must be one of these two.
Balanced, Leaning. Only 9 & 10 are held out for the first use and then included on the second.
Leaning, Balanced. Only 4 & 8 are included in the first use and then held out on the second use.
Leaning both times, the same side. 1, 2, & 5 are included on both uses on the same side.
Leaning both times, swapping sides. 3, 6, & 7 are included on both uses but swap sides between uses.
We can then differentiate these groups by ensuring they are split between being on the same side, swapping sides or being held out on our final use. The result is that every islander can be identified by a unique combination of results.
The fascinating part of this solution is that it is symmetrical. If you swap all the lefts and rights you still identify the same Islander.
Last word
While an interesting challenge and a satisfying solution it’s not immediately clear where this same approach can be applied elsewhere. Recently I played a game called Secret Hitler. It is a classical voting based deception/investigation game. A group of secret fascists are trying to pass legislation and make Hitler chancellor. The fascists know who each other are but everyone else does not. There are a slue of games with this ‘multiple hidden defector mechanic’ (Avalon, 2 rooms & a Boom, One Night Ultimate Werewolf) in all of these you can often ferret out the defectors in much the same way, use votes to see who is aligned together and then try to create tests to break them apart. If they stay together it must be that they know they’re on the same team which only the defectors know.
