We are given $n$ intervals $[l_1,r_1],[l_2,r_2],[l_3,r_3],\dots, [l_n,r_n]$ in the number line. We can divide the intervals into two sets such that no two intervals in the same set have overlaps. Prove that there are at most $n-1$ pairs of overlapping intervals.
Problem
Source: BdMO 2023 Secondary National P8 Higher Secondary National P6
Tags: combinatorics, graph theory, induction
gghx
14.02.2023 14:53
Induct, removing the interval with the smallest $r_i$ (which can intersect at most one other interval).
grey_hat_hacker
15.04.2023 16:31
Let the intervals be considered vertices of a graph and edges if there is an overlapping interval. It is obvious that no three intervals can have an overlapping interval. Else we cant divide them into two given sets. There can't be any cycle in the graph since if there were, then if we arrange the intervals of the cycle in ascending order of the values of $l_i$ the last interval would coincide with all the preceding intervals and then we would find 3 pairs of overlapping interval which is not possible So there are n-1 edges
Soaeb
26.02.2024 09:44
There are 3 and more intervals that can have an overlapping interval @grey_hat_hacker
Mathematician2080
28.02.2024 18:58
I think @grey_hat_hacker meant that 3 intervals cannot have a same overlapping interval. He is correct, since, by PHP, 2 of them must be in one of the set and it would contradict.