Opublikowane na Archiwum Olimpiady Matematycznej (https://archom.ptm.org.pl)

XXX OM - I - Zadanie 9

Zawody matematyczne:

XXX OM, 1978-1979

Etap:

I

Niech $r_k(n)$ będzie resztą z dzielenia liczby naturalnej $n$ przez liczbę naturalną $k$ oraz

$<br /> R(n) = r_1(n) + r_2(n) + \ldots + r_n(n).<br />$

Udowodnić, że dla każdej liczby naturalnej $m$ zachodzi równość $R(2^m-1) = R(2^m)$ .

Rozwiązanie

Z określenia liczby $r_k (n)$ wynika, że dla $n \geq 2$ i $k \geq 1$ zachodzą następujące zależności:

Jeżeli $k\mid n$ , to $r_k(n) = 0$ oraz $r_k(n - 1) = k-1$ ,
Jeżeli $k\mid n$ , to $r_k(n) = r_k(n - 1) + 1$ .

Mamy też

$<br /> R(n) = \sum_{k=1}^n r_k(n) = \sum_{k=1}^{n-1} r_k(n),\ \textrm{ponieważ}\ r_n(n) = 0,<br />$

$<br /> R(n-1) = \sum_{k=1}^{n-1} r_k(n-1)<br />$

Wobec tego dla $n \geq 2$ mamy

$<br /> \begin{split}<br /> R(n) - R(n - 1) =\sum_{k=1}^{n-1} (r_k(n) - r_k(n-1)) =<br /> \sum_{\substack{k=1 \\ k \not \mid n}}^{n-1} 1 + \sum_{\substack{k=1 \\ k \mid n}}^{n-1} (-(k-1))=\\<br /> \sum_{k=1}^{n-1} 1 - \sum_{\substack{k=1 \\ k \mid n}}^{n-1} k = n-1 - (\sigma(n)-n)=<br /> 2n - \sigma(n) - 1,<br /> \end{split}<br />$

gdzie $\sigma(n)$ jest sumą wszystkich dzielników naturalnych liczby $n$ .

W szczególności, jeżeli $n = 2^m$ , to

$<br /> \sigma(n) = \sigma(2^m) = 1+2 + 4+ \ldots + 2^m = 2^{m+1} - 1<br />$

i wobec tego

$<br /> R(2^m) -R(2^m-1) = 2 \cdot 2m - (2^{m+1} - 1) - 1 = 0,<br />$

tzn. $R(2^m) = R(2^m - 1)$ dla każdej liczby naturalnej $m$ .

Adres źródła: https://archom.ptm.org.pl/?q=node/971