Maths Olympiad Prep

Library / /6 of 12

Algebra Difficulty 8.3 Shortlist Prove it Netherlands

Find all positive integers nn for which there exist nn distinct positive integers a1,a2,,ana_1, a_2, \dots, a_n, none of them greater than n2n^2, such that
1a1+1a2++1an=1. \frac{1}{a_1} + \frac{1}{a_2} + \dots + \frac{1}{a_n} = 1.

Solution

The answer is that the given property holds for all n2n \ne 2. For n=1n = 1, the set {1}\{1\} satisfies (3). For n=2n = 2, note that no set satisfies (3); if a1a_1 or a2a_2 equals 11, then 1a1+1a2>1\frac{1}{a_1} + \frac{1}{a_2} > 1, if a1a_1 and a2a_2 are both at least two, then 1a1+1a212+13<1\frac{1}{a_1} + \frac{1}{a_2} \le \frac{1}{2} + \frac{1}{3} < 1.

1k=1k++1k(k+1)+1(k+1)(k+2)++1(k+1)(k+).(4) \frac{1}{k} = \frac{1}{k+\ell} + \frac{1}{k(k+1)} + \frac{1}{(k+1)(k+2)} + \cdots + \frac{1}{(k+\ell-1)(k+\ell)}. \quad (4)
Indeed, if we use 1k(k+1)=1k1k+1\frac{1}{k(k+1)} = \frac{1}{k} - \frac{1}{k+1} then the right-hand side of (4) is equal to
1k++(1k1k+1)+(1k+11k+2)++(1k+11k+)=1k++1k1k+. \frac{1}{k+\ell} + \left(\frac{1}{k} - \frac{1}{k+1}\right) + \left(\frac{1}{k+1} - \frac{1}{k+2}\right) + \cdots + \left(\frac{1}{k+\ell-1} - \frac{1}{k+\ell}\right) = \frac{1}{k+\ell} + \frac{1}{k} - \frac{1}{k+\ell}.

Substituting k=1k=1 and =n1\ell=n-1 into (4), we obtain an identity
1=1n+112+123+134+145++1(n1)n.(5) 1 = \frac{1}{n} + \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \frac{1}{3 \cdot 4} + \frac{1}{4 \cdot 5} + \cdots + \frac{1}{(n-1) \cdot n}. \qquad (5)
If nk(k+1)n \neq k(k+1) for all k1k \ge 1, this is a sum of nn distinct reciprocals, each with denominator smaller than n2n^2. This shows that the given property holds for all n3n \ge 3 not of the form k(k+1)k(k+1).

Suppose that there exists some k1k \ge 1 such that n=k(k+1)n = k(k+1). Then we apply to the right-hand side of (5) the substitutions 1n+1(n1)n=1n1\frac{1}{n} + \frac{1}{(n-1)n} = \frac{1}{n-1} and 16=110+115\frac{1}{6} = \frac{1}{10} + \frac{1}{15}. Then we get the identity
1=1n1+12+110+115+134+145++1(n2)(n1).(6) 1 = \frac{1}{n-1} + \frac{1}{2} + \frac{1}{10} + \frac{1}{15} + \frac{1}{3 \cdot 4} + \frac{1}{4 \cdot 5} + \cdots + \frac{1}{(n-2) \cdot (n-1)}. \quad (6)
This is a sum of nn reciprocals. Note that each denominator of each reciprocal is smaller than n2n^2; this is only non-obvious for the term 115\frac{1}{15}, and since n=k(k+1)n = k(k+1) and n3n \ge 3, we in particular have n6n \ge 6, and therefore n2>15n^2 > 15. Now we show that these reciprocals are distinct.
Note that k(k+1)k(k+1) is always even. Since nn is of the form k(k+1)k(k+1), n1n-1 is odd and therefore not of this form. Furthermore, n1n-1 is also unequal to 22, 1010 and 1515, since 33, 1111 and 1616 are not of the form k(k+1)k(k+1). Also, 1010 and 1515 themselves are not of the form k(k+1)k(k+1). Therefore all the reciprocals in the right-hand side of (6) are distinct. So the given property holds for all n3n \ge 3 of the form k(k+1)k(k+1) as well. \square

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 and solution reproduced as published; topic and difficulty added by this site.