MathDB

P8

Part of 2023 Bangladesh Mathematical Olympiad

Problems(1)

Overlapping intervals in the number lines

Source: BdMO 2023 Secondary National P8 Higher Secondary National P6

2/12/2023
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.
combinatoricsgraph theoryinduction