Skip to main content
OlympiadHQ

Browse · MathNet

Print

IRL_ABooklet

Ireland counting and probability

Problem

Let be a positive integer, and () real numbers such that What is the least value of which ensures that at least 10 successive numbers all lie within a distance 1 of each other (i.e. we want so that )? Your answer should give as a function of and be valid for all .
Solution
Let be the least integer greater than or equal to . We claim that the least value of is .

First, we show that points are enough. Partition into subintervals , where These intervals are of length at most and, given at least distinct points in , the average number of points in each of them is at least , and so one such subinterval must contain strictly more than points , as required.

For the converse direction, we first note that is positive. Define the subintervals of length Since every is a subinterval of . By picking nine distinct points in each , we claim that we have a set of points such that there are not of these points all within a distance of each other. To justify the claim, it suffices to note that if and then .
Final answer
9*ceil(L) + 1

Techniques

Pigeonhole principleColoring schemes, extremal arguments