XXIV OM - III - Zadanie 5

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

\[<br />
(1) \qquad \frac{m}{n} = \frac{2^km}{2^kn} = \frac{qn+r}{2^kn} = \frac{q}{2^k} + \frac{r}{2^kn}.<br />
\]

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ć

\[<br />
q = q_0 + q_1 2 + q_2 2^2 + \ldots + q_{k-1}2^{k-1},<br />
\]

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

\[<br />
(2) \qquad \frac{q}{2^k}= q_0 \frac{1}{2^k} + q_1 \frac{1}{2^{k-1}} +<br />
q_2 \frac{1}{2^{k-2}} + \ldots + q_{k-2} \frac{1}{2}.<br />
\]

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

\[<br />
r = r_0 + r_12 + r_2 2^2 + \ldots + r_{k-1} 2^{k-1},<br />
\]

gdzie $ r_j = 0 $ lub $ 1 $.

Stąd

\[<br />
(3) \qquad \frac{r}{2^kn}= r_0 \frac{1}{2^kn} + r_1 \frac{1}{2^{k-1}n} +<br />
 \ldots + r_{k-2} \frac{1}{2n}.<br />
\]

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

\[<br />
r_j \frac{1}{2^{k-j}n} = \frac{r_j2^j}{2^kn} \leq \frac{r}{2^kn} < \frac{1}{2^k},<br />
\]

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ą.

Komentarze

Dodaj nową odpowiedź