0
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ If you divide the interval in four, then one of those has to be in the longest interval( if there is more than one, you finish.). Now, consider the middle point(eights) of those points. Probably one of those is also in the longest interval. and so you will get an answer. Am i missing something? $\endgroup$
    – Phicar
    Commented Jul 1, 2020 at 19:47
  • $\begingroup$ How would you distinguish between $[0, 1/8 - 2 \varepsilon], [1/8 - 2 \varepsilon, 3/8 - \varepsilon], [3/8 - \varepsilon, 5/8 - \varepsilon], ... $ and $[0, 1/8 - \varepsilon], [1/8 - \varepsilon, 3/8 - 2\varepsilon], [3/8 -2 \varepsilon, 5/8 - \varepsilon], ... $ with your strategy? Your queries give the same answers for both cases, but the longest interval are the second and third respectively. $\endgroup$
    – Albatossable
    Commented Jul 1, 2020 at 20:28
  • $\begingroup$ I see, i misunderstood the question. $\endgroup$
    – Phicar
    Commented Jul 1, 2020 at 20:35
  • $\begingroup$ Thank you nonetheless, the counterexample to your strategy can be easily adapted to a simple proof as in the answer. $\endgroup$
    – Albatossable
    Commented Jul 1, 2020 at 21:41
  • $\begingroup$ Could you explain what you mean by "query"? What information does a query yield? For instance, if I query $x \in [0,1]$, is the left-endpoint and the right-endpoint of the subinterval containing $x$ returned? $\endgroup$
    – MathematicsStudent1122
    Commented Jul 1, 2020 at 21:44

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .