Maths Olympiad Prep

Library / /26 of 31

Combinatorics Difficulty 6.9 National olympiad Prove it Belarus

Let nn be a positive integer. On the segment [0,n][0, n] of the real line there are marked mm pairwise distinct segments with integer endpoints. It is known that it's impossible to choose a set of these segments such that the sum of their lengths is nn and their union is [0,n][0, n]. (We say that the two segments are distinct if their endpoints doesn't coincide. The union of the segments is considered as the union of the sets of real numbers.)
Find the maximal possible value of mm.

Solution

Answer: n(n1)2\frac{n(n-1)}{2}.

Each set of segments that satisfies the condition of the problem is called good. Consider a set consisting of all segments of the form [a,b][a, b], where a,bNa, b \in \mathbb{N} and a<bna < b \le n. This collection contains n(n1)/2n(n-1)/2 segments and it is good since even the union of all segments of the collection does not cover the point 00. Therefore the maximum possible value of the number mm is not less than n(n1)/2n(n-1)/2.

Let us prove the following
Claim: For any good collection AA there exists a good collection BB containing the same number of segments and not containing any segment of the form [0,k][0, k], k=1,,nk = 1, \ldots, n.

Proof of the claim: If the set AA does not contain any segment of the form [0,k][0, k], then put B=AB = A. Otherwise among all segments of AA of the form [0,k][0, k], consider the segment [0,s][0, s] of minimum length. Let us exclude the segment [0,s][0, s] from the set and instead add the segment [s,n][s, n], which obviously was not contained in AA. The resulting set will also be good. Indeed if it's possible to select several segments of the total length nn from the new set, the union of which would coincide with the entire segment [0,n][0, n], then among them there must be a segment [s,n][s, n], but then several non-intersecting segments would cover the segment [0,s][0, s] and among them there would be a segment of the form [0,t][0, t] where t<st < s, which is impossible due to the minimality of the number ss. Repeating the described procedure several times, we obtain the required set BB. The assertion is proved.

From the proved statement, in particular, it follows that the number of segments in an arbitrary good set is not more than n(n1)/2n(n-1)/2, and hence the maximum possible value of the number mm is exactly equal to n(n1)/2n(n-1)/2.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.