Note the following first.
If there are k people in a $5,000 interval, then we don't need any more questions, because we don't care about their order. If there are k people in a $10,000 interval, then we need only one more question. If there are k people in a $20,000 interval, then the number of additional questions depends on k. If k = 2, then we need only two more questions if both are in the same $10,000 range and only one more question otherwise; if k = 3, then we again need only two more questions in the worst case; for k >= 4 we need at most three more questions asking about the first and second $10,000 intervals and then about subintervals of size $5,000.
Now we can answer the questions.
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.
1. For $200,000, ask about every $40,000 interval except the last:
$0 - $40,000
$40,001 - $80,000
$80,001 - $120,000
$120,001 - $160,000
So, suppose each $40,000 interval (including $160,000 - $200,000) has 2 names -- the worst case. We will find their order by three more questions: there is one question to ask about the first $20,000 or second $20,000. Then for each $20,000 interval, there is a question about the first $10,000 or the second $10,000. Similarly, for each $5,000 interval. So for 10 people in the $0 - $200,000 interval, you would need at least 4 + (5*3) = 19 questions.
2. If there are only four people between $0 and $200,000, then first ask whether any earn more than $160,000. In the worst case there are none. Then ask about $80,000. In the worst case there are two below and two above. Then for each $80,000 interval ask about a $40,000 interval (worst case: both in one), then a $20,000 interval (worst case: both in one), then a $10,000 interval (worst case: both in one), and then $5,000. So the total number of questions is 2 + (2*4) = 10.
3. First ask about the first $1 million interval. In the worst case there are two in the lower million and two in the upper million. Further decompose each half to a $500,000 interval, a $250,000 interval, a $125,000 interval, then $80,000 (in the worst case), $40,000, $20,000, and two more. This gives a total of 1 + (2*8) = 17 questions.
4. The key observation, which we can credit to Ivan Rezanka, is that binary search is a good general strategy. For example, if you have an interval of size $80,000, you might as well ask about 0 to $40,000 and then if at least two people are in that interval, you can ask about 0 to $20,000 next. This gives as much information as asking about 0 to $20,000 and then next $20,000.01 to $40,000. Further you might be lucky and require no more questions (if there is only one person or none in that interval). When the size of the interval is not a power of 2 times $5,000, the analysis becomes trickier. But the basic idea does not change. See Ivan's analysis here: http://cs.nyu.edu/cs/faculty/shasha/papers/salariesivan.doc
