You have just landed on Mars where you find 7 identical-looking spheres. From prior missions, you know the following:
Your job is to carry out as few comparisons as possible, with the goal of holding in your hand a sphere that you are certain has the majority color. What is the smallest number of comparisons that is guaranteed to work?
- Each sphere is colored on the inside.
- One of the colors occurs for a strict majority of the spheres (4 or more).
- When two spheres of the same color touch each other, they both glow.
Source: Stan Wagon (Macalester College) posed this problem for the recent Iowa problem fest.
© Copyright 1997 Stan Wagon. Reproduced with permission.