Maths Olympiad Prep

Library / /90 of 128

Algebra Difficulty 6.0 AIME, harder Prove it Philippines

Problem:
Find all positive integers nn for which there exists a set of exactly nn distinct positive integers, none of which exceed n2n^{2}, whose reciprocals add up to 11.

Solution

Solution:
The answer is all n2n \neq 2. For n=1n=1, the set {1}\{1\} works. For n=2n=2, no set exists, simply because the sum of reciprocals of two distinct integers cannot be equal to 11. For n=3n=3, take {2,3,6}\{2,3,6\}.

For n>3n>3, the identity
1k=1k+r+1k(k+1)+1(k+1)(k+2)++1(k+r1)(k+r) \frac{1}{k} = \frac{1}{k+r} + \frac{1}{k(k+1)} + \frac{1}{(k+1)(k+2)} + \cdots + \frac{1}{(k+r-1)(k+r)}
allows us to extend a sum of tt terms to one of exactly t+rt+r terms. Taking k=3k=3 and r=n3r=n-3 allows us to turn the sum 1=1/2+1/3+1/61 = 1/2 + 1/3 + 1/6 to the nn-term sum
1=12+16+1n+134+145++1(n1)n 1 = \frac{1}{2} + \frac{1}{6} + \frac{1}{n} + \frac{1}{3 \cdot 4} + \frac{1}{4 \cdot 5} + \cdots + \frac{1}{(n-1)n}
This construction works provided that nk(k+1)n \neq k(k+1) for any kk. Otherwise, we have n6n \geq 6, and instead we apply the above to the sum 1=1/2+1/3+1/10+1/151 = 1/2 + 1/3 + 1/10 + 1/15, taking k=3k=3, r=n4r=n-4 to yield
1=12+110+115+1n1+134+145++1(n2)(n1) 1 = \frac{1}{2} + \frac{1}{10} + \frac{1}{15} + \frac{1}{n-1} + \frac{1}{3 \cdot 4} + \frac{1}{4 \cdot 5} + \cdots + \frac{1}{(n-2)(n-1)}
The above then works, because if n=k(k+1)n = k(k+1) for some kk, then n12,10,15n-1 \neq 2, 10, 15, and n1m(m+1)n-1 \neq m(m+1) for any mm by parity, since n1n-1 is odd and m(m+1)m(m+1) is always even. This construction is not unique; there are other similar ones.

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.