XLVII OM - I - Zadanie 2

Zawody matematyczne:

XLVIII OM, 1996-1997

Etap:

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:

$ (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} $

lub

$ (2) \qquad \quad x_n = \overline{c_1 c_2\ldots c_{m-1} c_m c_{m-1} \ldots c_2 c_1} $

( $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

$ (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}, $

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

$ (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}, $

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:

$ (5) \qquad \begin{split} & 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);\\ & x_{n+1}-x_n= \overline{1\underbrace{0 \ldots 00}_{m-1}} = 10^{m-1} \textrm{ dla liczb danych wzorami } (2), (4). \end{split} $

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

$ 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}, $

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

$ 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}, $

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

$ (6) \qquad \quad x_{n+1}-x_n = \overline{11 \underbrace{0 \ldots 00}_{k-1}} = 11 \cdot 10^{k-1}. $

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

$ x_n = \overline{\underbrace{99\ldots 99}_p},\quad \textrm{gdzie } p = 2m \textrm{ lub } p = 2m - 1. $

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

$ (7) \qquad \quad x_{n+1}-x_n = 2. $

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$ .