MathDB
Overlapping intervals in the number lines

Source: BdMO 2023 Secondary National P8 Higher Secondary National P6

February 12, 2023
combinatoricsgraph theoryinduction

Problem Statement

We are given nn intervals [l1,r1],[l2,r2],[l3,r3],…,[ln,rn][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−1n-1 pairs of overlapping intervals.
Back to ProblemsView on AoPS