Maths Olympiad Prep

Library / /14 of 20

Algebra Difficulty 5.8 AIME, harder Prove it Romania

Let nn be a positive integer. Determine all positive integers pp for which there exist positive integers x1<x2<<xnx_1 < x_2 < \dots < x_n such that
1x1+2x2++nxn=p. \frac{1}{x_1} + \frac{2}{x_2} + \dots + \frac{n}{x_n} = p.

Solution

Call good a number pp for which there exist positive integers x1<x2<<xnx_1 < x_2 < \dots < x_n such that 1x1+2x2++nxn=p\frac{1}{x_1} + \frac{2}{x_2} + \dots + \frac{n}{x_n} = p.
Since x1,x2,,xnx_1, x_2, \dots, x_n are integers and x1<x2<<xnx_1 < x_2 < \dots < x_n, we have xkkx_k \ge k, so kxk1\frac{k}{x_k} \le 1, for all k=1,2,,nk = 1, 2, \dots, n. Then 1x1+2x2++nxnn\frac{1}{x_1} + \frac{2}{x_2} + \dots + \frac{n}{x_n} \le n, so every good number, if there exists any, is between 1 and nn.

Next, we will show that any integer p{1,2,,n}p \in \{1, 2, \dots, n\} is good. Obviously, nn is good (for xk=kx_k = k) and 1 is also good (take xk=knx_k = kn). For 2pn12 \le p \le n-1, we write:
k=1nkxk=(1x1+2x2++p1xp1)+(pxp++nxn), \sum_{k=1}^{n} \frac{k}{x_k} = \left( \frac{1}{x_1} + \frac{2}{x_2} + \dots + \frac{p-1}{x_{p-1}} \right) + \left( \frac{p}{x_p} + \dots + \frac{n}{x_n} \right),
so it is enough to choose x1,x2,,xnx_1, x_2, \dots, x_n such that the first sum is equal to p1p-1, and the second sum is equal to 1. We can do that by setting xk=kx_k = k, for k=1,2,,p1k = 1, 2, \dots, p-1 and xk=k(np+1)x_k = k(n-p+1), for pknp \le k \le n. Notice that x1<x2<<xnx_1 < x_2 < \dots < x_n in all cases, so the good numbers are indeed 1, 2, ,\dots, nn.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.