LIX OM - I -Zadanie 10

Zawody matematyczne:

LIX OM, 2007-2008

Etap:

Dana jest liczba pierwsza p. Ciąg liczb całkowitych dodatnich $a_1, a_2, a_3, \dots$ spełnia warunek

$ (1) \qquad a_{n+1} = a_n +p\left[ \sqrt[p]{a_n} \right]\quad \text{dla } n =1, 2,3,\dots. $

Wykazać, że pewien wyraz tego ciągu jest $p$ -tą potęgą liczby całkowitej.
(Uwaga: Symbol $[x]$ oznacza największą liczbę całkowitą nie przekraczającą $x$ .)

Rozwiązanie

Zdefiniujmy ciągi liczb całkowitych nieujemnych $b_1, b_2, b_3, \dots$ oraz $r_1, r_2, r_3, \dots$
w następujący sposób:

$ b_n^p \leqslant a_n < (b_n + 1)^p \quad \text{ oraz } \quad r_n = a_n -b_^p $

dla $n =1,2,3,\dots$ . Inaczej mówiąc, $r_n$ jest różnicą między wyrazem an a największą nie
przekraczającą tego wyrazu $p$ -tą potęgą liczby całkowitej. Warunek (1) przepisujemy teraz w postaci

$ (2) \qquad a_{n+1} = a_n +pb_n. $

Zauważmy, ze jeżeli $r_n = 0$ , to $a_n = b_n^p$ jest $p$ -tą potęgą liczby całkowitej. Zadanie będzie
więc rozwiązane, jeśli udowodnimy, że $r_n = 0$ dla pewnej wartości $n$ .

Przypuśćmy, że wszystkie wyrazy ciągu $r_1, r_2, r_3, \dots$ są liczbami całkowitymi dodatnimi. Niech
$r_m$ będzie najmniejszym wśród tych wyrazów. Mamy więc $a_m = b_m^p +rm$ . Ponadto
$b_{m-1} <b_m$ , gdyż w przeciwnym razie mielibyśmy

$ r_{m-1} = a_{m-1} -b^p_{m-1} < a_m -b^p_{m-1} = r_m $

wbrew określeniu $m$ . Zauważmy dalej, że $a_{m-1} <(b_{m-1}+1)^p \leqslant b^p_m \leqslant a_m$
i wobec tego zachodzi nierówność

$ (3)\qquad r_m = a_m -b_m^p <am -a_{m-1} = pb_{m-1} < pb_m. $

Niech ponadto $k>m$ będzie najmniejszym wskaźnikiem, dla którego $b_k >b_m$ . Wówczas
$b_m = b_{m+1} = \dots = b_{k-1}$ , więc na mocy (2) otrzymujemy

$ \begin{split} a_{m+1} &= a_m +pb_m, \\ a_{m+2} &= a_{m+1} +pb_m, \\ \dots \\ a_k &= a_{k-1} +pb_m \end{split} $

i sumując stronami dochodzimy do wniosku, że

$ (4) \qquad a_k = a_m +pb_m(m -k)= b^p_m +pb_m(m-k)+r_m. $

Wykażemy z kolei, że $b_k = b_m +1$ . Istotnie, gdyby zachodziła nierówność
$b_k \geqslant b_m +2= b_{k-1} +2$ , mielibyśmy $a_{k-1} < (b_{k-1} +1)^p$ , $a_k \geqslant (b_{k-1} +2)^p$
oraz

$ (5) \qquad pb_{k-1} = a_k -a_{k-1} > (b_{k-1} +2)^p -(b_{k-1} +1)^p, $

ale pisząc $x = b_{k-1} +2$ , $y = b_{k-1} +1$ mamy $x-y =1$ , $x>y>b_{k-1}$ i widzimy, że

$ x^p-y^p=(x-y)(x^{p-1} + x^{p-2}y +\dots +y^{p-1}) > 1\cdot py^{p-1} > pb^{p-1}_{k-1} \geqslant pb_{k-1}. $

Nierówność (5) jest więc fałszywa, co dowodzi równości $b_k = b_m +1$ .

Na mocy (4) możemy zatem napisać

$ (b_m +1)^p +r_k = b^p_k +r_k = a_k = b^p_m +pb_m(m-k)+r_m, $

czyli

$ (6) \qquad r_m -r_k=(b_m+1)^p -b^p_m -pb_m(m-k). $

Ze wzoru dwumianowego otrzymujemy

$ (b_m +1)^p - b_m^p = \binom{p}{1} b^{p-1}_m + \binom{p}{2}b^{p-2}_m + \dots + \binom{p}{p-1} b_m +1 $

Ponieważ $p$ jest liczbą pierwszą, więc współczynniki dwumianowe $\binom{p}{i}$ są dla $i =1,2,\dots ,p - 1$
liczbami podzielnymi przez $p$ . Zatem liczba $(b_m + 1)^p - b_m^p$ daje resztę 1 z dzielenia przez
$pb_m$ . Wobec tego z (6) wynika, że liczba $r_m -r_k$ daje resztę 1 z dzielenia przez $pb_m$ .

W (3) uzyskaliśmy nierówność $r_m <pb_{m-1}$ korzystając jedynie z tego, że
$b_{m-1} <b_m$ . Analogicznie wyprowadzamy z nierówności $b_{k-1} <b_k$ , że $r_k <pb_m$ .
Liczby $r_m$ i $r_k$ należą więc do przedziału $(0; pb_m)$ , a różnica $r_m-r_k$ daje resztę 1 z dzielenia
przez $pb_m$ . Wynika stąd, że $r_k = r_m -1$ , co przeczy założeniu, że $r_m$ jest najmniejszym wyrazem
w ciągu $r_1, r_2, r_3, \dots$ .

To oznacza, że $r_n = 0$ dla pewnego wskaźnika $n$ , skąd wynika teza.