Maths Olympiad Prep

Library / /38 of 42

Combinatorics Difficulty 7.1 National olympiad, round 2 Prove it Ireland

Let NN be a positive integer, LL and xix_i (1iN1 \le i \le N) real numbers such that
0x1<x2<x3<<xNL. 0 \le x_1 < x_2 < x_3 < \dots < x_N \le L.
What is the least value of NN which ensures that at least 10 successive numbers xix_i all lie within a distance 1 of each other (i.e. we want xi,,xi+9x_i, \dots, x_{i+9} so that xi+9xi+1x_{i+9} \le x_i + 1)? Your answer should give NN as a function of LL and be valid for all L>0L > 0.

Solution

Let M=LM = \lfloor L \rfloor be the least integer greater than or equal to LL. We claim that the least value of NN is 9M+19M + 1.

First, we show that 9M+19M + 1 points are enough. Partition [0,L][0, L] into subintervals I1,,IMI_1, \dots, I_M, where
Ik=[k1,k),1k<MIM=[M1,L]. \begin{aligned} I_k &= [k-1, k), \quad 1 \le k < M \\ I_M &= [M-1, L]. \end{aligned}
These intervals are of length at most 11 and, given at least 9M+19M + 1 distinct points in [0,L][0, L], the average number of points in each of them is at least (9M+1)/M>9(9M + 1)/M > 9, and so one such subinterval must contain strictly more than 99 points xix_i, as required.

For the converse direction, we first note that a:=(L(M1))/Ma := (L-(M-1))/M is positive. Define the subintervals of length aa
Jk=[(k1)(1+a),(k1)(1+a)+a],1kM. J_k = [(k-1)(1+a), (k-1)(1+a)+a], \quad 1 \le k \le M.
Since
(M1)(1+a)+a=M1+Ma=L, (M-1)(1+a) + a = M - 1 + Ma = L,
every JkJ_k is a subinterval of [0,M][0, M]. By picking nine distinct points in each JkJ_k, we claim that we have a set of 9M9M points such that there are not 1010 of these points all within a distance 11 of each other. To justify the claim, it suffices to note that if xJkx \in J_k and yJk+1y \in J_{k+1} then yx>k(1+a)((k1)(1+a)+a)=1y-x > k(1+a) - ((k-1)(1+a)+a) = 1.

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.