In many countries, people consider their salaries to be a closely guarded secret. But that makes them all the more curious about where they stand in their enterprise's salary ordering. Let's see if we can help them find out without their losing too much privacy.
There are some number of employees whose salaries are known to be between x and y. You, as a trusted outsider, ask questions of the form "Who has salaries between s1 and s2 inclusive?" The employees agree to answer honestly. At the end, you will tell them the order of their salaries (or they will be able to figure it out, because they are listening to the questions and answers). So they don't get nervous, you want to ask as few questions as possible. Nobody cares about the order among any subgroup of people if their annual salaries are within $5,000 of one another.
Warm-Up:
There are five people and you have found out that Nick and Jeff earn in the interval between $0 and $50,000. In addition, you find out:
$40,000 - $60,000: Jeff and Ariana
$50,000 - $80,000: Ariana, Carol, Joe
On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
How many more questions do you need to find the full order among these five people?
Solution to warm-up:
Two more questions. You already know that Nick earns the least, then Jeff, then Ariana. Ask who earns between $60,000.01 and $70,000. If neither Carol nor Joe, then ask about $70,000.01 - $75,000. If both Carol and Joe are in that higher interval, then you don't care how they are ordered. If not then they earn more than $75,000 and we still don't care. If one of Carol and Joe earns between $60,000.01 and $70,000, then the other earns more and you have your answers. If both earn between $60,000.01 and $70,000, then ask about $65,000.01 - $70,000.
Now here are some challenges for you.
Problems:
1. Suppose there are 10 people who earn between $0 and $200,000. Order them according to the above rules using as few questions as possible. (Hint: my best answer was about 20.)
2. What if there are only 4 people earning between $0 and $200,000? How does that change your strategy? (Hint: my best answer was about 10 questions.)
3. How many questions do you need if there are 4 people earning between $0 and $2,000,000?
4. Can you find an approach to the general problem?
