Maths Olympiad Prep

Library / /15 of 22

Algebra Difficulty 6.8 National olympiad Prove it South Africa

A representation of 1720\frac{17}{20} as a sum of reciprocals
1720=1a1+1a2++1ak \frac{17}{20} = \frac{1}{a_1} + \frac{1}{a_2} + \cdots + \frac{1}{a_k}
is called a calm representation with kk terms if the aia_i are distinct positive integers and at most one of them is not a power of two.

a. Find the smallest value of kk for which 1720\frac{17}{20} has a calm representation with kk terms.

b. Prove that there are infinitely many calm representations of 1720\frac{17}{20}.

Solution

Note first that there is no calm representation with 2 terms: if either a1a_1 or a2a_2 is 1 or a1=a2=12a_1 = a_2 = \frac{1}{2}, then the sum is greater than 1720\frac{17}{20}. Otherwise, the sum is at most 12+13=56<1720\frac{1}{2} + \frac{1}{3} = \frac{5}{6} < \frac{17}{20}, thus too small.

On the other hand, there is a representation with 3 terms, namely
1720=12+14+110, \frac{17}{20} = \frac{1}{2} + \frac{1}{4} + \frac{1}{10},
showing that the smallest possible value of kk is 3.

Now we show that there are infinitely many calm representations: take a1=524n+1a_1 = 5 \cdot 2^{4n+1} and consider the difference
17201524n+1=1724n11524n+1. \frac{17}{20} - \frac{1}{5 \cdot 2^{4n+1}} = \frac{17 \cdot 2^{4n-1} - 1}{5 \cdot 2^{4n+1}}.
Since 24=161mod52^4 = 16 \equiv 1 \mod 5, the numerator is 1724n111781=1350mod517 \cdot 2^{4n-1} - 1 \equiv 17 \cdot 8 - 1 = 135 \equiv 0 \mod 5. Thus the factor 5 cancels, and we have
17201524n+1=A24n+1 \frac{17}{20} - \frac{1}{5 \cdot 2^{4n+1}} = \frac{A}{2^{4n+1}}
for some positive integer A<24n+1A < 2^{4n+1}. Since AA has a binary representation as A=2b1+2b2++2brA = 2^{b_1} + 2^{b_2} + \dots + 2^{b_r} with distinct nonnegative integers b1,b2,,brb_1, b_2, \dots, b_r, we get
1720=1524n+1+124n+1b1+124n+1b2++124n+1br, \frac{17}{20} = \frac{1}{5 \cdot 2^{4n+1}} + \frac{1}{2^{4n+1-b_1}} + \frac{1}{2^{4n+1-b_2}} + \dots + \frac{1}{2^{4n+1-b_r}},
which is a calm representation for every nn. This completes the proof.

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.