Maths Olympiad Prep

Library / /11 of 19

Number theory Difficulty 8.1 Shortlist Prove it Germany

Problem:

Let NN be a natural number and x1,x2,,xnx_{1}, x_{2}, \ldots, x_{n} further natural numbers less than NN such that the least common multiple of any two of these nn numbers is greater than NN.
Prove that the sum of the reciprocals of these nn numbers is always less than 22; that is,
1x1+1x2++1xn<2 \frac{1}{x_{1}}+\frac{1}{x_{2}}+\cdots+\frac{1}{x_{n}}<2

Solution

Solution:

Since the lcm of xix_{i} and xjx_{j} is greater than NN, among the numbers 1,2,,N1,2, \ldots, N there are no two that are multiples of both xix_{i} and xjx_{j}.
Among the multiples of the natural number xx there are two such that kxN<(k+1)xk x \leq N < (k+1) x, from which it follows that kNx<k+1k \leq \frac{N}{x} < k+1. The number of multiples of xx that are less than NN is accordingly the integer part of Nx\frac{N}{x}, i.e. equal to [Nx]\left[\frac{N}{x}\right].

For the numbers x1,x2,,xnx_{1}, x_{2}, \ldots, x_{n} it therefore holds that [Nx1]+[Nx2]++[Nxn]<N\left[\frac{N}{x_{1}}\right]+\left[\frac{N}{x_{2}}\right]+\cdots+\left[\frac{N}{x_{n}}\right]<N.

On the other hand, [Nxi]>Nxi1\left[\frac{N}{x_{i}}\right]>\frac{N}{x_{i}}-1 and hence Nx1+Nx2++Nxnn<N\frac{N}{x_{1}}+\frac{N}{x_{2}}+\cdots+\frac{N}{x_{n}}-n<N.

But since n<Nn<N, it follows that:
Nx1+Nx2++Nxn<2N\frac{N}{x_{1}}+\frac{N}{x_{2}}+\cdots+\frac{N}{x_{n}}<2N, which finally leads to 1x1+1x2++1xn<2\frac{1}{x_{1}}+\frac{1}{x_{2}}+\cdots+\frac{1}{x_{n}}<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: MathNet, licensed CC-BY-4.0. Statement translated into English from de; metadata (topic, difficulty) added by this project.