Find the largest $K$ satisfying the following: Given any closed intervals $A_1,\ldots, A_N$ of length $1$ where $N$ is an arbitrary positive integer. If their union is $[0,2021]$, then we can always find $K$ intervals from $A_1,\ldots, A_N$ such that the intersection of any two of them is empty.
Problem
Source: 2021 Taiwan Mathematics Olympiad
Tags: combinatorics, Taiwan
22.07.2021 16:25
The answer is $1010$. Taking the intervals $A_k=[k,k+1]\forall k=0,...,2020$ guarantees that $K\leq 1010$. To prove that we can always have $K$, firstly order the sets according to their left endpoint. Now build a subsequence of $A_1,...,A_N$ as follows. $B_0$ is the leftmost interval, $B_{k+1}$ is the leftmost interval to the right of $A_k$ and disjoint from it. It is easy to see that the shortest distance between $A_k$ and $A_{k+1}$ must be $\leq 1$, because otherwise the interval in between couldn't be covered. So in the worst case we must have $B_k=[2k,2k+1]$, but this gives (at least) $1010$ intervals.
23.07.2021 21:01
@above I believe that your proof is correct, but the answer should be $K=1011$ ?
23.07.2021 21:32
Yes you are right
26.10.2021 14:15
We claim that $K=1011$. To see that $K \le 1011$,just consider the intervals $[i,i+1]$ for $0 \le i \le2020$. We show that for any such $N$ intervals, we can find $1011$ such intervals. The key observation is that for any integer $i$, there exists an interval $[k,k+1]$,such that $floor(k)=i$. We verify this by considering the contrary. Suppose there exists an interval $[a-1,a]$ such that $floor(a)=i$.If there doesn't exist one , then the elements of $(i,i+1)$ don't get covered. If $a=i+1$ we are done.If $a<(i+1)$ then the interval $(a,i+1)$ doesn't get covered. Now for $i=0,2,4,...2020$,choose intervals such that the floor of the lower bound is $i$.Since the length of the interval is $1$,they are disjoint.