XLVII OM - I - Zadanie 2

Liczbą palindromiczną nazywamy taką liczbę naturalną, której zapis dziesiętny czytany od strony lewej do prawej jest taki sam, jak czytany od strony prawej do lewej. Niech $ (x_n) $ bedzie rosnącym ciągiem wszystkich liczb palindromicznych. Wyznaczyć wszystkie liczby pierwsze, które są dzielnikami co najmniej jednej z różnic $ x_{n+1}-x_n $.

Rozwiązanie

Zapis dziesiętny liczby palindromicznej $ x_n $ (odpowiednio: ($ 2m $)-cyfrowej lub ($ 2m-1 $)-cyfrowej) wygląda tak:

\[<br />
(1) \qquad \quad x_n = \overline{c_1 c_2\ldots c_{m-1} c_m c_m c_{m-1} \ldots c_2 c_1}<br />
\]

lub

\[<br />
(2) \qquad  \quad x_n = \overline{c_1 c_2\ldots c_{m-1} c_m c_{m-1} \ldots c_2 c_1}<br />
\]

($ c_i \in \{ 0,1,2,3,4,5,6,7,8,9\} $ dla $ i = 1, \ldots ,m;\ c_1 \ne 0 $). Możliwe są trzy sytuacje:

Przypadek I. $ c_m \ne 9 $. Jeśli $ x_n $ ma postać (1), to $ x_{n+1} $ (najmniejsza liczba palindromiczna większa od $ x_n $) ma zapis dziesiętny

\[<br />
(3) \qquad  \quad x_{n+1} = \overline{c_1 c_2\ldots c_{m-1} d_m d_m c_{m-1} \ldots c_2 c_1},<br />
\]

gdzie $ d_m = c_m + 1 $.

Uzasadnienie: przykład (3) pokazuje, że istnieją liczby palindromiczne większe od $ x_n $ i mające te same co ona cyfry początkowe $ c_1,c_2,\ldots,c_{m-1} $; tak więc $ x_{n+1} $ musi być jedną z tych liczb. Jej kolejną ($ m $-tą) cyfrą nie może być $ c_m $, bo wówczas liczba ta byłaby identyczna z $ x_n $ (wzór (1)). Biorąc $ d_m= c_m +1 $ jako kolejną cyfrę dostajemy jedyną liczbę palindromiczną o początkowych cyfrach $ c_1,c_2,\ldots,c_{m-1},d_m $ (jej dalsze cyfry są już wyznaczone jednoznacznie; por. wzór (3)); a pisząc na $ m $-tym miejscu jakąkolwiek cyfrą większą od $ d_m $ dostajemy liczby jeszcze większe; zatem wzór (3) istotnie przedstawia liczbę $ x_{n+1} $.

Analogiczne rozumowanie pokazuje, że jeśli $ x_n $ ma postać (2), to $ x_{n+1} $ ma zapis dziesiętny

\[<br />
(4) \qquad  \quad x_{n+1} = \overline{c_1 c_2\ldots c_{m-1} d_m c_{m-1} \ldots c_2 c_1},<br />
\]

gdzie $ d_m = c_m + 1 $.

Obliczamy różnicę $ x_{n+1} -x_n $ stosując zwykły algorytm odejmowania (to znaczy pisząc cyfry liczby $ x_n $ pod odpowiednimi cyframi liczby $ x_{n+1} $ i wykonując ,,odejmowanie pisemne''). Wynik odejmowania:

\[<br />
(5) \qquad<br />
\begin{split}<br />
& x_{n+1}-x_n= \overline{11 \underbrace{0 \ldots 00}_{m-1}} = 11 \cdot 10^{m-1}  \textrm{ dla liczb danych wzorami } (1), (3);\\<br />
& x_{n+1}-x_n=  \overline{1\underbrace{0 \ldots 00}_{m-1}} = 10^{m-1}  \textrm{ dla liczb danych wzorami } (2), (4).<br />
\end{split}<br />
\]

Przypadek II. Nie wszystkie cyfry liczby $ x_n $ (danej wzorem (1) lub (2)) są dziewiątkami, ale cyfra $ c_m $ jest dziewiątką: $ c_m = 9 $. Niech $ c_k $ będzie ostatnią cyfrą różną od $ 9 $ w ciągu $ c_1,c_2,\ldots,c_{m-1},c_m $. Wtedy

\[<br />
x_n = \overline{c_1 c_2\ldots c_{k-1} c_k \underbrace{99 \ldots 99}_l c_k c_{k-1} \ldots c_2 c_1},<br />
\]

gdzie $ l = 2m-2k $ lub $ l = 2m-1-2k $, w zależności od tego, czy liczba $ x_n $ wyraża się wzorem (1), czy (2). W każdym z tych przypadków najmniejsza liczba palindromiczna większa od $ x_n $ ma przedstawienie

\[<br />
x_{n+1} = \overline{c_1 c_2\ldots c_{k-1} d_k \underbrace{00 \ldots 00}_l d_k c_{k-1} \ldots c_2 c_1},<br />
\]

gdzie $ d_k = c_k + 1 $. (Szczegółowe uzasadnienie - bardzo podobne do przeprowadzonego w przypadku I.) Algorytm odejmowania daje teraz wynik

\[<br />
(6) \qquad  \quad x_{n+1}-x_n = \overline{11 \underbrace{0 \ldots 00}_{k-1}} = 11 \cdot 10^{k-1}.<br />
\]

Przypadek III. Wszystkie cyfry liczby $ x_n $ są dziewiątkami:

\[<br />
x_n = \overline{\underbrace{99\ldots 99}_p},\quad \textrm{gdzie } p = 2m \textrm{ lub } p = 2m - 1.<br />
\]

Wtedy $ x_{n+1} = \overline{1 \underbrace{00\ldots 0}_{p-1}1} $, więc

\[<br />
(7) \qquad  \quad x_{n+1}-x_n = 2.<br />
\]

Przypadki I, II, III wyczerpują wszystkie możliwości. Otrzymane we wzorach (5), (6), (7) wyniki pokazują, że jedynymi dzielnikami pierwszymi różnic $ x_{n+1}-x_n $ są liczby $ 2 $, $ 5 $ oraz $ 11 $.

Komentarze

Dodaj nową odpowiedź