Maths Olympiad Prep

Library / /104 of 133

Combinatorics Difficulty 6.4 National olympiad Prove it Saudi Arabia

The 2013 numbers
11×2,12×3,13×4,,12013×2014 \frac{1}{1 \times 2}, \frac{1}{2 \times 3}, \frac{1}{3 \times 4}, \ldots, \frac{1}{2013 \times 2014}
are arranged randomly on a circle.

a. Prove that there exist ten consecutive numbers on the circle whose sum is less than 14000\frac{1}{4000}.

b. Prove that there exist ten consecutive numbers on the circle whose sum is less than 110000\frac{1}{10000}.

Solution

a.
Consider 201 disjoint blocks B1,B2,,B201B_{1}, B_{2}, \ldots, B_{201} consisting each of 10 numbers, consecutive on the circle. By the pigeonhole principle, there exists a block BkB_{k}, for some 1k2011 \leq k \leq 201, not containing any of the 200 numbers
11×2,12×3,,1200×201 \frac{1}{1 \times 2}, \frac{1}{2 \times 3}, \ldots, \frac{1}{200 \times 201}
The sum of the ten consecutive numbers in this block BkB_{k} is less than or equal to
1201×202+1202×203++1210×211=(12011202)+(12021203)++(12101211)=12011211=10201×211<14000 \begin{aligned} \frac{1}{201 \times 202} + & \frac{1}{202 \times 203} + \cdots + \frac{1}{210 \times 211} \\ & = \left(\frac{1}{201} - \frac{1}{202}\right) + \left(\frac{1}{202} - \frac{1}{203}\right) + \cdots + \left(\frac{1}{210} - \frac{1}{211}\right) \\ & = \frac{1}{201} - \frac{1}{211} = \frac{10}{201 \times 211} < \frac{1}{4000} \end{aligned}

b.
Again, consider the 201 disjoint blocks B1,B2,,B201B_{1}, B_{2}, \ldots, B_{201} like in (a). By the pigeonhole principle, there exists at least 101 blocks Bk1,Bk2,,Bk201B_{k_{1}}, B_{k_{2}}, \ldots, B_{k_{201}}, not containing any of the 100 numbers
11×2,12×3,,1100×101. \frac{1}{1 \times 2}, \frac{1}{2 \times 3}, \ldots, \frac{1}{100 \times 101}.
The sum of the 1010 numbers in these 101 blocks Bk1,Bk2,,Bk201B_{k_{1}}, B_{k_{2}}, \ldots, B_{k_{201}} is less than or equal to
i=1201(bBkib)1101×102+1102×103++1210×211(11011102)+(11021103)++(12101211)<1101 \begin{aligned} \sum_{i=1}^{201} \left( \sum_{b \in B_{k_{i}}} b \right) & \leq \frac{1}{101 \times 102} + \frac{1}{102 \times 103} + \cdots + \frac{1}{210 \times 211} \\ & \leq \left(\frac{1}{101} - \frac{1}{102}\right) + \left(\frac{1}{102} - \frac{1}{103}\right) + \cdots + \left(\frac{1}{210} - \frac{1}{211}\right) \\ & < \frac{1}{101} \end{aligned}
Therefore, there exists at least one block Bki0B_{k_{i_{0}}} among these 101 blocks with the sum of its ten consecutive numbers less than
1101×101<110000. \frac{1}{101 \times 101} < \frac{1}{10000}.

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.