XLII OM - I - Zadanie 11

Dla danej liczby naturalnej $ n>10^3 $ oraz każdego $ k \in \{1,\ldots, n\} $ rozważamy resztę $ r_k $ z dzielenia $ 2^n $ przez $ k $. Dowieść że $ r_1+\ldots r_n > 2n $.

Rozwiązanie

Dla $ j = 0,1,2,3,4 $ oznaczmy przez $ K_j $ zbiór tych liczb całkowitych dodatnich, które nie przekraczają $ n $, dzielą się przez $ 2^j $, ale nie przez $ 2^{j+1} $, oraz mają co najmniej jeden dzielnik nieparzysty większy od $ 1 $. Tak więc

\[<br />
\begin{split}<br />
& K_0 = \{k \colon k \ \textrm{nieparzyste}, 3 \leq k \leq n \},\\<br />
& K_1 = \{k \colon k = 2m,\  m\ \textrm{nieparzyste}, 3 \leq m \leq [n/2]\}.\\<br />
& K_2 = \{k \colon k = 4m,\  m\ \textrm{nieparzyste}, 3 \leq m \leq [n/4]\},\\<br />
& K_3 = \{k \colon k = 8m,\  m\ \textrm{nieparzyste}, 3 \leq m \leq [n/8]\},\\<br />
& K_4 = \{k \colon k = 16m,\ m\ \textrm{nieparzyste}, 3 \leq m \leq [n/16]\}.<br />
\end{split}<br />
\]

Ustalmy $ j \in \{0,1,2,3,4\} $ i weźmy pod uwagę dowolną liczbę $ k \in K_j $. Zatem $ k= 2^jm $, $ m $ nieparzyste, $ m \geq 3 $. Niech $ q_k $ i $ r_k $ będą ilorazem i resztą z dzielenia $ 2^n $ przez $ k $:

\[<br />
2^n = kq_k + r_k = 2^jmq_k + r_k.<br />
\]

Stąd

\[<br />
r_k = 2^j(2^{n-j}-mq_k).<br />
\]

Liczba w nawiasie jest dodatnia (bo reszta $ r_k $ nie może być zerem). Wobec tego prawa strona nie jest mniejsza niż $ 2^j $.

Wykazaliśmy więc, że

\[<br />
r_k \geq 2^j \quad \textrm{dla}\ k \in K_j.<br />
\]

Zbiór $ K_j $ ma tyle elementów, ile jest liczb nieparzystych $ m $ spełniających warunki $ 3 \leq m \leq [n/2^j] $ - a więc nie mniej niż $ \frac{1}{2} [n/2^j] - 1 $.

Niech $ s_j $ oznacza sumę liczb $ r_k $, gdy $ k $ przebiega zbiór $ K_j $. Wobec znalezionych oszacowań dostajemy nierówność

\[<br />
s_j = \sum_{k \in K_j} r_k \geq 2^j \left( \frac{1}{2} \left[ \frac{n}{2^j} \right]-1 \right) > 2^j \left( \frac{1}{2} \left( \frac{n}{2^j}-1 \right)-1 \right) = \frac{n-3 \cdot 2^j}{2}<br />
\]

(skorzystaliśmy z tego, że $ [x] > x - 1 $).

Zbiory $ K_0 $, $ K_1 $, $ K_2 $, $ K_3 $, $ K_4 $ są rozłącznymi podzbiorami zbioru $ \{1,\ldots,n\} $. Wobec tego

\[<br />
\sum_{k=1}^n r_k \geq s_0+s_1+s_2+s_3+s_4 > \sum_{j=0}^4 \frac{n-3 \cdot 2^j}{2} = \frac{5n-93}{2}.<br />
\]

Pozostaje zauważyć, że dla $ n > 93 $ (a tym bardziej dla $ n > 10^3 $) otrzymana w wyniku liczba $ \frac{1}{2}(5n -93) $ przekracza $ 2n $.

Komentarze

Dodaj nową odpowiedź