XLII OM - I - Zadanie 11

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

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

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

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$ :

$ 2^n = kq_k + r_k = 2^jmq_k + r_k. $

Stąd

$ r_k = 2^j(2^{n-j}-mq_k). $

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

$ r_k \geq 2^j \quad \textrm{dla}\ k \in K_j. $

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ść

$ 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} $