Browse · MathNet
PrintIRL_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 .
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