We have a number of intervals (either finite or infinite), not overlapping if not for their extreme points, which union is [0,1]. One of them is long at least 1/4, and all the others are not longer than 1/4. Suppose that we can query any point in [0,1] to which interval it belongs. Can we identify univocally the longest interval with a finite number of measurements?
I believe it's impossible. I have the sensation there is a nice and short proof using a cardinality argument out there, but was not able to figure it out so far.
The inspiration for this question actually comes from a discrete variation of the problem, which is as follows.
We have a sorted array A of integers, of length n. Suppose one integer appears more than n/4 times, and all the others appear not more than n/4 times. Can we identify the most common integer in constant time?
A simple $O(\log n)$ solution can be designed using binary search. But can there be a constant time solution?
Let's prove that for an arbitrary finite set of queries, we can have two sequences of intervals which give the same answers, but have different longest intervals.
As the queries are finite, we can choose an interval $[a, a + 1/4]$ such that there are no queries in $[a+1/4-\varepsilon, a+1/4 + \varepsilon]$ for a certain small $\varepsilon > 0$. Then, if one of the intervals is $I = [a, a+1/4+\varepsilon]$ in one case, and $I = [a, a+1/4-\varepsilon]$ in the other case, all our queries will give the same answers, even though in the former case $I$ is the longest interval, while in the latter it is not. Therefore we can not distinguish the longest interval with a finite number of queries.
A similar argument holds also for the discrete case.