Maths Olympiad Prep

Library / /364 of 520

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it

9.250 Mark some intervals on a line segment of length 1 such that no two intervals have a common interior, and the distance between any two points, whether in the same interval or different intervals, is not equal to 0.1. Prove: The sum of the lengths of the marked intervals does not exceed 0.5.

Solution

[Proof] Without loss of generality, let the line segment of length 1 be [0,1][0,1]. Let MM be the union of points on the marked intervals, and N=[0,1]\MN=[0,1] \backslash M, i.e., NN is the union of points on some intervals in [0,1][0,1] that have no common interior. Suppose kk is a natural number and 1k101 \leqslant k \leqslant 10, and let xkx_{k} and yky_{k} denote the sum of the lengths of the intervals formed by M[k110,k10]M \cap\left[\frac{k-1}{10}, \frac{k}{10}\right] and N[k110,k10]N \cap\left[\frac{k-1}{10}, \frac{k}{10}\right], respectively. Since any two points in MM are not 0.1 units apart, when k=1,3,5,7,9k=1,3,5,7,9, ykxk+1y_{k} \geqslant x_{k+1}. When k=2,4,6,8,10k=2,4,6,8,10, ykxk1y_{k} \geqslant x_{k-1}. From k=110(xk+yk)=1\sum_{k=1}^{10}\left(x_{k}+y_{k}\right)=1, it follows that the sum of the lengths of the marked intervals k=110xk12\sum_{k=1}^{10} x_{k} \leqslant \frac{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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.