Maths Olympiad Prep

Library / South African Mathematical Olympiad Third Round /24 of 31

South African Mathematical Olympiad Third Round

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=5⋅24n+1a_1 = 5 \cdot 2^{4n+1} and consider the difference
1720−15⋅24n+1=17⋅24n−1−15⋅24n+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=16≡1mod  52^4 = 16 \equiv 1 \mod 5, the numerator is 17⋅24n−1−1≡17⋅8−1=135≡0mod  517 \cdot 2^{4n-1} - 1 \equiv 17 \cdot 8 - 1 = 135 \equiv 0 \mod 5. Thus the factor 5 cancels, and we have
1720−15⋅24n+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=15⋅24n+1+124n+1−b1+124n+1−b2+⋯+124n+1−br, \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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.