LIX OM - II -Zadanie 6

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:

\[<br /> 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.<br /> \]

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

\[<br /> (*) \qquad s, s-a, s -2a, \dots , s-(3^d -1)a<br /> \]

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

\[<br /> s = \underbrace{a+a+ \dots +a}_{v}+\underbrace{3^d +3^d +\dots +3^d}_{w}.<br /> \]

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.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź