XXIV OM - III - Zadanie 5

Zawody matematyczne:

XXIV OM, 1972-1973

Etap:

III

Dowieść, że każdy dodatni ułamek właściwy $\frac{m}{n}$ można przedstawić w postaci skończonej sumy odwrotności różnych liczb naturalnych.

Rozwiązanie

\spos{1} Obierzmy tak liczbę naturalną $k$ , by $n \leq 2^k$ . Niech $q$ i $r$ będą odpowiednio ilorazem i resztą z dzielenia liczby $2^km$ przez $n$ , tzn. niech $2^km = qn + r$ , gdzie $0 \leq r < n$ .

Wtedy

$ (1) \qquad \frac{m}{n} = \frac{2^km}{2^kn} = \frac{qn+r}{2^kn} = \frac{q}{2^k} + \frac{r}{2^kn}. $

Mamy $qn \leq gn + r = 2^km < 2^kn$ , ponieważ $\displaystyle \frac{m}{n} < 1$ . Stąd $q < 2^k$ . Wobec tego zapis liczby $q$ w systemie dwójkowym ma postać

$ q = q_0 + q_1 2 + q_2 2^2 + \ldots + q_{k-1}2^{k-1}, $

gdzie $q_i = 0$ lub $1$ . Stąd

$ (2) \qquad \frac{q}{2^k}= q_0 \frac{1}{2^k} + q_1 \frac{1}{2^{k-1}} + q_2 \frac{1}{2^{k-2}} + \ldots + q_{k-2} \frac{1}{2}. $

Z określenia liczb $r$ i $k$ mamy $r < n \leq 2^k$ . Wobec tego zapis liczby $r$ w systemie dwójkowym ma postać

$ r = r_0 + r_12 + r_2 2^2 + \ldots + r_{k-1} 2^{k-1}, $

gdzie $r_j = 0$ lub $1$ .

Stąd

$ (3) \qquad \frac{r}{2^kn}= r_0 \frac{1}{2^kn} + r_1 \frac{1}{2^{k-1}n} + \ldots + r_{k-2} \frac{1}{2n}. $

Przy tym dla $j = 0, 1, \ldots, k-1$ mamy

$ r_j \frac{1}{2^{k-j}n} = \frac{r_j2^j}{2^kn} \leq \frac{r}{2^kn} < \frac{1}{2^k}, $

ponieważ $r < n$ . Zatem każdy składnik niezerowy sumy (3) jest mniejszy od każdego niezerowego składnika sumy (2). Składniki te są więc różne.

Z (1), (2) i (3) otrzymujemy więc przedstawienie liczby $\displaystyle \frac{m}{n}$ w postaci sumy różnych ułamków postaci $\displaystyle \frac{1}{t}$ , gdzie $t$ jest liczbą naturalną.