Maths Olympiad Prep

Library / /2 of 4

Number theory Difficulty 6.1 National olympiad Find the answer

Let nn be an integer greater than or equal to 11. Find, as a function of nn, the smallest integer k2k\ge 2 such that, among any kk real numbers, there are necessarily two of which the difference, in absolute value, is either strictly less than 1/n1 / n, either strictly greater than nn.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let n n be an integer such that n1 n \geq 1 . We need to find the smallest integer k2 k \geq 2 such that for any set of k k real numbers, there exist at least two numbers, say x x and y y , where either xy<1n |x - y| < \frac{1}{n} or xy>n |x - y| > n .

To solve this problem, we will employ a combinatorial argument based on the Pigeonhole Principle.

Let's begin by considering n2+1 n^2 + 1 numbers placed in the interval [0,n][0, n]. We will divide this interval into n2 n^2 subintervals of length 1n \frac{1}{n} . Since there are n2+1 n^2 + 1 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 1n \frac{1}{n} .

Next, we need to show that k=n2+1 k = n^2 + 1 is not sufficient, so it has to be k=n2+2 k = n^2 + 2 for our condition. Consider the scenario where we choose numbers 0,1n,2n,,n21n,n 0, \frac{1}{n}, \frac{2}{n}, \ldots, \frac{n^2 - 1}{n}, n . Here, the differences between any two numbers do not exceed n n and are not less than 1n \frac{1}{n} . Therefore, the choice of k=n2+1 k = n^2 + 1 allows for a selection where neither condition is met.

Hence, adding one additional number forces a pair to meet the condition that xy<1n |x - y| < \frac{1}{n} or xy>n |x - y| > n since either it creates a subinterval overlap or extends beyond [0,n] [0, n] .

Therefore, the smallest integer k k satisfying the problem's conditions is:
n2+2 \boxed{n^2 + 2}

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.