Maths Olympiad Prep

Library / /4 of 4

, 2015

Algebra Difficulty 7.0 National olympiad Prove it Romania

Determine all positive integers expressible, for every integer n3n \ge 3, in the form (a1+1)(a2+1)(an+1)1a1a2an\frac{(a_1 + 1)(a_2 + 1)\cdots(a_n + 1) - 1}{a_1a_2\cdots a_n}, where a1,a2,,ana_1, a_2, \ldots, a_n are pairwise distinct positive integers.

Solution

The integers greater than 33 are ruled out by noticing that if a1,a2,a3a_1, a_2, a_3 are pairwise distinct positive integers, then
(a1+1)(a2+1)(a3+1)1a1a2a3=1+1a1+1a2+1a3+1a1a2+1a1a3+1a2a31+1+12+13+112+113+123=3+56 \begin{aligned} \frac{(a_1+1)(a_2+1)(a_3+1)-1}{a_1 a_2 a_3} &= 1 + \frac{1}{a_1} + \frac{1}{a_2} + \frac{1}{a_3} + \frac{1}{a_1 a_2} + \frac{1}{a_1 a_3} + \frac{1}{a_2 a_3} \\ &\le 1 + 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{1 \cdot 2} + \frac{1}{1 \cdot 3} + \frac{1}{2 \cdot 3} = 3 + \frac{5}{6} \end{aligned}
To complete the proof, fix an integer n3n \ge 3, consider an integer a3a \ge 3, and let a1=a2a_1 = a - 2, let ak=a2k2a_k = a^{2^{k-2}}, k=2,,n1k = 2, \dots, n-1, and let an=a2n22a_n = a^{2^{n-2}} - 2. Then 1a1<a2<<an1 \le a_1 < a_2 < \dots < a_n, and
(a1+1)(a2+1)(an+1)1a1a2an=((a1)k=2n1(a2k2+1))(a2n21)1(a2)a1+2++2n3(a2n22)=(a2n21)21(a2)a2n21(a2n22)=a2n2(a2n22)(a2)a2n21(a2n22)=aa2=1+2a2, \begin{aligned} \frac{(a_1+1)(a_2+1)\cdots(a_n+1)-1}{a_1 a_2 \cdots a_n} &= \frac{((a-1) \prod_{k=2}^{n-1} (a^{2^{k-2}}+1)) (a^{2^{n-2}}-1)-1}{(a-2) a^{1+2+\cdots+2^{n-3}} (a^{2^{n-2}}-2)} \\ &= \frac{\left(a^{2^{n-2}}-1\right)^2-1}{(a-2) a^{2^{n-2}-1} (a^{2^{n-2}}-2)} = \frac{a^{2^{n-2}} (a^{2^{n-2}}-2)}{(a-2) a^{2^{n-2}-1} (a^{2^{n-2}}-2)} \\ &= \frac{a}{a-2} = 1 + \frac{2}{a-2}, \end{aligned}
which is integral if and only if a=3a = 3 or a=4a = 4. The former shows that 33 satisfies the required condition, and the latter shows that so does 22.

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.