3
$\begingroup$

Let $I_1,I_2,\ldots,I_n$ be nondegenerate intervals in $[0,1]$. What is the minimum of $\sum_{1\leq i,j\leq n}\frac{1}{|I_i\cup I_j|}$, where the sum is over pairs of intervals that are not disjoint? When all $I_i=[0,1]$, no pairs are disjoint and the sum is $n^2$. At the other extreme, all pairs are disjoint and the sum is $\sum_i\frac{1}{|I_i|}\geq \frac{n^2}{\sum_i |I_i|}\geq n^2$, attained when $I_i=[\frac{i-1}{n},\frac{i}{n})$.

$\endgroup$
6
  • $\begingroup$ I think you want to add, that the $I_i$ cover the whole interval $[0,1]$ otherwise you could just make the $I_i$ arbitrarily small and disjoint. Also in your first example, when $I_i = [0,1]$ for all $i$, then I thought one would get $\sum_{i<j} 1$ = \frac{n(n-1)}{2}? And just to be scrupulously correct in the other example, if you want to have them disjoint you should choose half open intervals $I_i = [\frac{i-1}{n},\frac{i}{n})$. $\endgroup$ May 28, 2016 at 20:50
  • $\begingroup$ The sum is over all pairs $1\leq i,j\leq n$. Sorry this wasn't clear earlier. $\endgroup$
    – pi66
    May 28, 2016 at 20:51
  • $\begingroup$ I'm not sure I understand; if the intervals are all pairwise disjoint, shouldn't the sum be empty? $\endgroup$ May 28, 2016 at 20:56
  • $\begingroup$ The sum always includes pairs $(i,j)$ where $i=j$. $\endgroup$
    – pi66
    May 28, 2016 at 20:57
  • $\begingroup$ Oh, right. And the $I_k$'s partition $[0,1]$? $\endgroup$ May 28, 2016 at 21:02

1 Answer 1

0
$\begingroup$

If I understood the question correctly, you want that $\bigcup_{i \in I} I_i = [0,1]$ holds, because otherwise you could just choose $I_i := [\frac{i-1}{n},\frac{i-1}{n} + \varepsilon)$ and obtain $$\sum_{1\leq i,j \leq n} \frac{1}{|I_i|} = \sum_{1 =i}^n \frac{1}{|I_i|} = {n\varepsilon}, \; \color{red} {\leftarrow \texttt{this should be } \frac{n}{\varepsilon}} $$ for $\varepsilon > 0$ small enough.

But if $\bigcup_{i \in I} I_i = [0,1]$ cover your whole interval, you can make the same estimate you already did $$\sum_{1\leq i,j \leq n} \frac{1}{|I_i \cup I_j|} \geq \sum_{i=1}^n \frac{1}{|I_i|} \geq \frac{n^2}{\sum_{i=1}^n |I_i|} \geq n^2,$$ since as you already noticed The sum always includes pairs $(i,j)$ where $i=j$.

So the minimum must be $n^2$, attained when $I_i := [\frac{i-1}{n},\frac{i}{n})$.

$~$

Edit: $\bigcup I_i$ need not to cover the whole interval. Also my evaluation of the first sum was wrong (see comments below).

$\endgroup$
4
  • $\begingroup$ The intervals need not cover the whole interval. However small you choose $\epsilon$, $I_i$ and $I_{i+1}$ (for $i<n$) will intersect and their intersection will have length $\epsilon$. This means the term $\frac{1}{|I_i\cap I_{i+1}|}$ in the sum will be $\frac{1}{\epsilon}$ and the sum will end up being very large, rather than very small. $\endgroup$ May 28, 2016 at 21:40
  • $\begingroup$ Why do $I_i$ and $I_{i+1}$ have to intersect? If $\varepsilon < 1$ then clearly $I_i$ and $I_j$ will be disjoint for $i \neq j$ and $I_i := [\frac{i-1}{n},\frac{i-1}{n}+\varepsilon)$. $\endgroup$ May 28, 2016 at 21:50
  • 1
    $\begingroup$ Misread your intervals as $I_i=[\frac{i-1}{n},\frac{i}{n}+\epsilon)$. Still, in your case the sum would be $\frac{n}{\epsilon}$ rather than $n\epsilon$. Notice $\epsilon \leq \frac{1}{n}$ for the intervals to be all disjoint, so the problem persists. $\endgroup$ May 28, 2016 at 21:54
  • $\begingroup$ oh... I see now what you mean, my bad. $\endgroup$ May 28, 2016 at 21:56

You must log in to answer this question.

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