The Islanders, Generalized
You have been marooned on an island with islanders total (including yourself). All of the islanders have the exact same weight, except for one person who weighs slightly more than everybody else. Your goal is to find that person.
The island has an old see-saw that can function as a makeshift scale: You can put some number of people on one side, and some number on the other, and the scale will either tip in the direction of the heavier side or balance. However, you want to use the see-saw as minimally as possible, since it is very rickety and could break.
What are the minimum numbers of balances needed for 10, 100, and 1000 islanders?
Give your answer as the concatenation of each result. (For example, if they were 34, 6, 123, your answer would be 346123.)
The answer is 357.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Elegantly, the function to describe how many balances you need for n people is ⌈ lo g 3 ( n ) ) ⌉ .
The process is as follows:
First, split the islanders into three groups as evenly as possible, making sure that at least two groups have the same number of people. Weigh those two groups. If the see-saw tips to one side, you know that the heaviest person is on that side. If the see-saw balances, you know that the heaviest person is in the group that wasn't weighed.
After the first iteration, we have a group of unknowns that is more-or-less 3 n . From there, we can repeat the process of splitting into three groups and weighing two of them. After k iterations, we know we have about 3 k n remaining unknown islanders.
Let's look at an example with 10 islanders.
First, we split into groups of 3, 4, and 3 and weigh the two groups of three.
Let's say the see-saw balances. Then, we have 4 remaining people. We split them into groups of 1, 2, and 1. Let's say the see-saw balances again. Then, we have 2 remaining people. We split them into groups of 1, 0, and 1. Because we'll have one person no matter which way the see-saw tips, we have weighed these islanders in 3 trials.
Note that this is a far cry from a proof, but it may be a fun bonus problem to try to prove that the function I stated in the first line comes from the process I described.