Consider $m$ segments on the real line. Each segment has its two endpoints in the set of integers $\{1, 2, \ldots, 2024\}$, and no two segments have the same length. No segment is entirely contained in another segment, but two segments may partially overlap each other. What is the maximum value of $m$?
Problem
Source: Pan African Mathematics Olympiad p4
Tags: combinatorics, PAMO 2024
16.08.2024 17:37
If two segments have the same left end-point, then one of them contains the other. Similarly, the right end-points are also distinct. Consider the longest segment. Suppose that its left end-point is $L$, and the right end-point is $R$. Since the segments have different lengths, we have that $R - L \geq m$. Every other segment either has its left end-point before $L$, and so there are at most $L - 1$ such segments, or it has its right end-point after $R$, and there are at most $2024 - R$ such segments. If its left end-point were on or after $L$ and its right end-point were on before $R$ then it would be contained within the longest segment. It also can't have both its left end-point before $L$ and its right end-point after $R$ because then it would contain the longest segment, but even if this were allowed to happen, it wouldn't change our estimate for the upper bound on how many segments there are. We see that there are at most $(L - 1) + (2024 - R) + 1 = 2024 - (R - L) \leq 2024 - m$ segments. Thus $m \leq 2024 - m$, giving us $m \leq 1012$. On the other hand, it is possible to obtain $1012$ segments by having a segment with endpoints $k$ and $2k$ for each $1 \leq k \leq 2012$.