XXXII - II - Zadanie 4

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

Dane są liczby naturalne $k, n$ . Określamy indukcyjnie dwa ciągi liczb $(a_j)$ i $(r_j)$ w sposób następujący:
Krok pierwszy: dzielimy $k$ przez $n$ i otrzymujemy iloraz $a_1$ i resztę $r_i$ ,
krok j-ty: dzielimy $k+r_{j-1}$ przez $n$ i otrzymujemy iloraz $a_j$ i resztę $r_j$ . Obliczyć sumę $a_1 + \ldots + a_n$ .

Rozwiązanie

Zgodnie z określeniem

$ \begin{split} k & = a_1n+r_1 \\ k+r_1 & = a_2n+r_2 \\ k+r_2 & = a_3n+r_3\\ \vdots & = \vdots \\ k+r_{n-1} & = a_nn+r_n \end{split} $

Dodając te równości otrzymamy

$ nk+r_1 + r_2+ \ldots + r_{n-1} = n(a_1 + a_2+ \ldots + a_n) + r_1 + r_2+ \ldots + r_n, $

więc

$ nk= n(a_1 + a_2+ \ldots + a_n) + r_n, $

Liczba $r_n$ jako reszta z dzielenia $k+r_{n-1}$ przez $n$ spełnia warunek $0 \leq r_n < n$ , z ostatniej równości wynika natomiast, że $r_n$ jest liczbą podzielną przez $n$ . Wobec tego $r_n = 0$ i

$ nk = n(a_1 + a_2+ \ldots + a_n). $

więc

$ a_1 + a_2+ \ldots + a_n = k. $