On a line, there are $n$ closed intervals (none of which is a single point) whose union we denote by $S$. It's known that for every real number $d$, $0<d\le 1$, there are two points in $S$ that are a distance $d$ from each other. (a) Show that the sum of the lengths of the $n$ closed intervals is larger than $\frac{1}{n}$. (b) Prove that, for each positive integer $n$, the $\frac{1}{n}$ in the statement of part (a) cannot be replaced with a larger number.
Problem
Source: XVII OlimpĂada Matemática Rioplatense (2008)
Tags: algebra unsolved, algebra
13.02.2012 14:16
I only proved that the intervals must be disjoint and these intervals are included in $ [0,1] $...
14.02.2012 13:54
(b) consider the following closed intervals: $[0,1/n]$ and $[k/n, k/n+\epsilon]$ for $k=2,3,\ldots,n$ then the total length is $1/n + (n-1)\epsilon$ which can be made as close to $1/n$ as one wishes. For $d \in (0,1]$ we can write it as $d=k/n-y$ for some $y \in [0,1/n]$ and $k \in \{1,\ldots,n\}$.
14.02.2012 15:11
maybe is a stupid question...but how can you be sure that these intervals are good?
14.02.2012 15:23
The man just explained it kamil9876 wrote: For $d \in (0,1]$ we can write it as $d=k/n-y$ for some $y \in [0,1/n]$ and $k \in \{1,\ldots,n\}$. I took the liberty to replace his $x$ letter with $d$, so it's clearer to you we take an arbitrary distance $d$ in $(0,1]$ and find such $k$ and $y$. Just think that the $d$ value must fall into some interval $(\ell/n,(\ell+1)/n]$, for some $0\leq \ell \leq n-1$.
15.02.2012 03:48
Now for (a): Define $D(A,B)=\{|a-b| : a\in A, b\in B\}$. If $A$ and $B$ are intervals then $D(A,B)$ is an interval of length at most $len(A)+len(B)$ while $D(A,A)$ is an interval of length exactly equal to $len(A)$. Let $I_1,I_2...I_n$ be $n$ such intervals. Then $[0,1] \subset \bigcup_{i\leq j} D(I_i, I_j)$ thus $1 \leq \sum_{i\leq j } len(D(I_i,I_j))\leq \sum_{i<j} (len(I_i) + len(I_j)) + \sum_{i=1}^n{len(I_i})= n \sum_{i=1}^n len(I_i) $ Hence the result.