LIX OM - II -Zadanie 6

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

Dana jest liczba całkowita dodatnia $n$ niepodzielna przez 3. Udowodnić, że istnieje liczba $m$ o następującej własności:
Każda liczba całkowita nie mniejsza niż $m$ jest sumą cyfr pewnej wielokrotności liczby $n$ .

Rozwiązanie

Przez liczbę dobrą będziemy rozumieć taką liczbę całkowitą dodatnią, która jest sumą cyfr pewnej wielokrotności liczby $n$ .

Zauważmy przede wszystkim, że suma dwóch liczb dobrych jest również liczbą dobrą. Rzeczywiście, niech $k_1, k_2$ będą
wielokrotnościami liczby $n$ o sumach cyfr odpowiednio równych $s_1, s_2$ . Niech $t$ będzie taką liczbą całkowitą, że
$10^t >k_2$ . Wówczas liczba $k = 10^t \cdot k_1 +k_2$ jest wielokrotnością liczby $n$ , zaś suma cyfr liczby $k$ jest równa
$s_1 +s_2$ , gdyż przy dodawaniu liczb $10^t \cdot k_1$ i $k_2$ niezerowe cyfry występują na różnych pozycjach.

Liczba $n$ nie jest podzielna przez 3, zatem jej suma cyfr a także nie jest podzielna przez 3.

Niech teraz $b$ będzie taką liczbą całkowitą, że $10^{3^b} >n$ . Przyjmijmy, że kolejnymi cyframi zapisu dziesiętnego
liczby $n$ są cyfry $c_1, c_2, \dots , c_l$ . Możemy oczywiście przyjąć, że $c_l \neq 0$ , gdyż podzielenie liczby
$n$ przez 10 nie zmienia warunków zadania. Wówczas kolejnymi cyframi zapisu dziesiętnego liczby
$(10^{3^b} -1)n = \underbrace{999\dots 99}_{3^b} \cdot n$ , podzielnej przez n, są cyfry:

$ c_1,c_2, \dots , c_l-1,c_l -1, \underbrace{9, 9, \dots , 9, 9}_{3^b-l}, 9-c_1, 9-c_2, \dots , 9-c_{l-1}, 10-c_l. $

Stąd wynika, że suma cyfr liczby $(10^{3^b} -1)n$ wynosi $9\cdot 3^b = 3^{b+2}$

Udowodniliśmy zatem, iż liczbami dobrymi są: liczba $a$ , która nie jest podzielna przez 3, oraz liczba $3^d$ , gdzie $d = b+2$ .

Wykażemy, że każda liczba całkowita nie mniejsza niż $a \cdot 3^d$ jest dobra. Wyniknie stąd, że liczba
$m = a\cdot 3^d$ spełnia tezę zadania.

Niech więc $s \geqslant a\cdot 3^d$ będzie dowolną liczbą całkowitą. Liczby

$ (*) \qquad s, s-a, s -2a, \dots , s-(3^d -1)a $

są wówczas dodatnie. Ponadto żadne dwie z nich nie dają tej samej reszty z dzielenia przez $3^d$ (gdyż podzielność
$3^d |(s - ia) - (s - ja)=(j - i)a$ przy pewnych wskaźnikach $0 \leqslant i,j \leqslant 3^d -1$ ze względu na niepodzielność
liczby a przez 3 jest możliwa tylko wtedy, gdy $3^d |j-i$ , co jednak pociąga $i=j$ ). Liczb wypisanych w ciągu (*) jest
$3d$ , istnieje więc wśród nich liczba, która jest podzielna przez $3^d$ . Niech na przykład $s-va = w \cdot 3^d$ . Wówczas
$v,w \geqslant 0$ oraz

$ s = \underbrace{a+a+ \dots +a}_{v}+\underbrace{3^d +3^d +\dots +3^d}_{w}. $

Liczby $a$ i $3^d$ są dobre. Zatem z powyższego przedstawienia wnioskujemy, że liczba $s$ jako suma liczb dobrych również jest
dobra, a tego dowodziliśmy.