XXXVIII OM - I - Zadanie 10

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

Niech $n = 4^k \cdot 5^m$ ( $k$ , $m$ — liczby naturalne). Udowodnić, że każda liczba naturalna mniejsza od $n$ jest dzielnikiem liczby $n$ lub sumą różnych dzielników liczby $n$ .

Rozwiązanie

Uwaga. Przez liczbę naturalną rozumiemy w tym zadaniu liczbę całkowitą dodatnią. Dla $k = 0$ teza jest - jak łatwo zauważyć - nieprawdziwa.

Niech $k \geq 1$ i $m \geq 1$ będą ustalone i niech $s < 4^k5^m$ będzie liczbą naturalną. Dzielimy $s$ przez $5^m$ otrzymując iloraz $a$ i resztę $r$ :

$ s = 5^mq+r; \quad 0 \leq q < 4^k \quad 0 \leq r < 5^m. $

Zapiszmy liczby $q$ i $r$ w układach pozycyjnych o podstawach $2$ i $5$ (odpowiednio) :

$ q=\sum_{i=0}^{2k-1} \alpha_i2^i,\ \alpha_i\in \{ 0,1\} \quad q=\sum_{i=0}^{m-1} xb_i2^i,\ \beta_i\in \{ 0, 1, 2, 3, 4\} \quad $

i rozpatrzmy następujące zbiory indeksów:

$ I_c = \{i: 0 \leq i < 2k-1, \alpha_i = c\};\quad c = 0, 1; $

$ J_c = \{j: 0 < j < m-1, \beta_i = c\}; \quad c = 0, 1, 2, 3, 4. $

Wówczas

$ \begin{split} s&=5^m \sum_{i\in I_1}2^i + \sum_{j\in J_1}5^j +\sum_{j\in J_2}2 \cdot 5^j+\sum_{j\in J_3}3 \cdot 5^j+\sum_{j\in J_4}4 \cdot 5^j=\\ &= \sum_{i\in I_1}5^m2^i + \sum_{j\in J_1}5^j +\sum_{j\in J_2}2 \cdot 5^j+\sum_{j\in J_3} 5^j+\sum_{j\in J_3}2 \cdot 5^j+\sum_{j\in J_4}4 \cdot 5^j \end{split} $

Wszystkie składniki otrzymanej sumy są dzielnikami liczby $4^k5^m$ , i to różnymi, bo zbiory $J_c$ są parami rozłączne. Teza jest więc udowodniona.