Let be an integer greater than or equal to . Find, as a function of , the smallest integer such that, among any real numbers, there are necessarily two of which the difference, in absolute value, is either strictly less than , either strictly greater than .
Solution
Let be an integer such that . We need to find the smallest integer such that for any set of real numbers, there exist at least two numbers, say and , where either or .
To solve this problem, we will employ a combinatorial argument based on the Pigeonhole Principle.
Let's begin by considering numbers placed in the interval . We will divide this interval into subintervals of length . Since there are numbers, according to the Pigeonhole Principle, at least one subinterval will contain at least two numbers. Therefore, there are at least two numbers within one such subinterval, implying that their difference is less than .
Next, we need to show that is not sufficient, so it has to be for our condition. Consider the scenario where we choose numbers . Here, the differences between any two numbers do not exceed and are not less than . Therefore, the choice of allows for a selection where neither condition is met.
Hence, adding one additional number forces a pair to meet the condition that or since either it creates a subinterval overlap or extends beyond .
Therefore, the smallest integer satisfying the problem's conditions is: