LX OM - I - Zadanie 7

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Ciąg liczb całkowitych $f_0, f_1, f_2, \cdots$ jest określony
przez warunki: $f_0 = 0, f_1 = 1$ ,

$ (1) \qquad f_n = f_{n-1} + f_{n-2} \text{ dla } n =2,3,4, \cdots. $

Znaleźć wszystkie wielomiany W o współczynnikach całkowitych,
mające następującą własność: Dla każdego $n =0, 1, 2, \cdots$
istnieje taka liczba całkowita $k$ , że $W(k)= f_n$ .

Rozwiązanie

Odpowiedź: $W(x)= \varepsilon x+c$ , gdzie $\varepsilon \in \{-1,1\}$
oraz $c$ jest liczbą całkowitą.

Skorzystamy wielokrotnie z następującego faktu: jeżeli $F$
jest wielomianem o współczynnikach całkowitych, to dla dowolnych
różnych liczb całkowitych $u, v$ spełniona jest podzielność
$u-v|F(u)-F (v)$ .

Dla dowodu tego faktu wystarczy zauważyć, że jeżeli $F(x)$
jest sumą jednomianów postaci $a_mx^m$ , gdzie współczynniki
$a_m$ są całkowite, to różnica $F(u)-F(v)$ jest sumą wyrażeń
postaci $a_m(u^m - v^m)$ , a każda liczba postaci $u^m -v^m$
jest podzielna przez $u - v$ .

Ponadto będziemy stosować następujące własności ciągu
$f_0, f_1, f_2, \cdots$ :

Liczby $f_1, f_2, f_3, \cdots$ są dodatnie.
Ciąg $f_2, f_3, f_4, \cdots$ jest ściśle rosnący.
Dla $n =2,3,4, \cdots$ zachodzi nierówność
$f_{n-1} \geqslant \frac{1}{2} f_n$ .
Dla $n =4,5,6, \cdots$ zachodzi nierówność
$f_{n+1} < 3f_{n-1}$ .

Rzeczywiście, własność 1. jest oczywista i pociąga za sobą
własność 2., gdyż dla $n \geqslant 3$ mamy $f_{n-2} > 0$ ,
co daje $f_n = f_{n-1} + f_{n-2} > f_{n-1}$ . Wreszcie własności
3. i 4. wynikają z własności 2., na mocy wzoru (1) mamy bowiem
$2f_{n-1} \geqslant f_{n-1} + f_{n-2} = f_n$ dla $n \geqslant 2$
oraz

$ f_{n+1} = f_n +f_{n-1} =2f_{n-1} +f_{n-2} < 2f_{n-1} +f_{n-1} =3f_{n-1} \text{ dla } n \geqslant 4. $

Przechodzimy do zasadniczej części rozwiązania.

Niech $W$ będzie wielomianem spełniającym warunki zadania.
Istnieje więc liczba całkowita $a$ , dla której $W(a)= f_0 = 0$ ,
oraz liczba całkowita $b$ , dla której $W(b)= f_1 = 1$ .
Na podstawie sformułowanego wyżej faktu różnica $W(b)-W(a) = 1$
jest podzielna przez $b-a$ . Stąd wniosek, że $b-a = \pm 1$ , czyli
$b = a+\varepsilon$ , gdzie $\varepsilon \in \{1,-1\}$ . W tej
sytuacji wielomian $P$ określony wzorem

$ (2) \qquad P(x)= W (a+\varepsilon x) $

spełnia zależności $P(0) = W(a)=0$ i
$P(1) = W (a+\varepsilon)= W(b) = 1$ . Nietrudno ponadto spostrzec,
że zbiory wartości wielomianów $W$ i $P$ przyjmowanych dla
całkowitych argumentów są równe. Innymi słowy, dla każdego
$n =0,1,2, \cdots$ istnieje taka liczba całkowita $k$ , że $P(k)= f_n$ .

Niech $d$ i $e$ będą takimi liczbami całkowitymi, że
$P(d)= f_3 = 2$ oraz $P(e)= f_4 = 3$ . Wówczas

$ d-1|P(d)-P (1) = 2-1=1, \text{ skąd } d \in \{0,2\}; $

wartość $d = 0$ wykluczamy, gdyż $P(0) = 0 \neq 2$ . Zatem $d = 2$ ;
podobnie

$ e-2|P (e)-P(2) = 3-2=1, \text{ skąd } e \in\{1,3\} $

i w efekcie $e = 3$ . Doszliśmy w ten sposób do wniosku, że

$ (3) \qquad P(k)= k \text{ dla } k =0,1,2,3. $

Wykażemy przez indukcję, że

$ (4) \qquad P(f_n)= f_n \text{ dla } n =0,1,2, \cdots. $

Prawdziwość związku (4) dla $n \leqslant 4$ wynika wprost z
relacji (3). Przyjmijmy z kolei, iż równość (4) jest spełniona
dla $n =0,1, \cdots,m$ , gdzie $m \geqslant 4$ ; należy dowieść,
że $P(f_{m+1})= f_{m+1}$ .

Na podstawie założeń zadania istnieje liczba całkowita $k$ ,
dla której $P(k)= f_{m+1}$ . Przypuśćmy najpierw, że
$k < f_{m-1}$ ; na mocy własności 3. uzasadnionej na początku rozwiązania oraz
nierówności $m-1 > 2$ mamy wtedy

$ f_m - k >f_m - f_{m-1} = f_{m-2} \geqslant \frac{1}{2} f_{m-1}, $

a ponadto ma miejsce podzielność

$ f_m -k |P(f_m)-P(k)= f_m-f_{m+1} = -f_{m-1}. $

Liczba $f_m -k$ jest więc dzielnikiem liczby $f_{m-1}$ większym
od jej połowy, co implikuje równość $f_m - k = f_{m-1}$ . Wówczas
jednak $k = f_m - f_{m-1} = f_{m-2}$ , co nie jest możliwe, gdyż
założenie indukcyjne orzeka, że $P(f_{m-2})= f_{m-2}$ , natomiast
$P(k)= f_{m+1}$ .

Udowodniliśmy tym samym, że $k \geqslant f_{m-1}$ . Ponieważ
na mocy własności 4. oraz warunku $m \geqslant 4$ dostajemy

$ f_{m+1} = f_m +f_{m-1} =2f_{m-1} +f_{m-2} < 3f_{m-1}, $

więc nierówność $k \geqslant f_{m-1}$ pociąga za sobą nierównosć
$k> \frac{1}{3} f_{m+1}$ . Z drugiej strony, spełniona jest podzielność

$ k = k -0|P(k)-P(0) = f_{m+1}-0= f_{m+1}. $

W konsekwencji liczba $k$ jest dzielnikiem liczby $f_{m+1}$
większym od jej jednej trzeciej. Zatem $k = f_{m+1}$ lub
$k = \frac{1}{2} f_{m+1}$ . Pierwszy przypadek prowadzi do wniosku,
że $P(f_{m+1})= f_{m+1}$ , co jest tożsame z tezą indukcyjną.
Natomiast drugi przypadek jest niemożliwy: wynikałoby zeń bowiem,
że $k = 1$ lub

$ k-1= \frac{1}{2} f_{m+1}-1|P(k)-P(1) = f_{m+1}-1 = 2(\frac{1}{2}f_{m+1}-1)+1 = 2(k-1)+1, $

a zatem $k - 1|1$ , czyli $k \leqslant 2$ . W rezultacie
$f_{m+1} =2k \leqslant 4 < f_5$ , co przeczy założeniu $m \geqslant 4$ .

To kończy rozumowanie indukcyjne.

Udowodniona właśnie zależność (4) wraz z własnością 2. pozwala
stwierdzić, że równość $P(x)= x$ zachodzi dla nieskończenie wielu
liczb całkowitych $x$ . Skoro $P$ jest wielomianem, równość ta jest
prawdziwa dla każdej liczby rzeczywistej $x$ . Uwzględniając równość
(2) dostajemy teraz

$ (5)\qquad W(x)= \varepsilon (x-a) $

dla każdej liczby rzeczywistej $x$ , gdzie $\varepsilon \in \{-1,1\}$ oraz $a$
jest liczbą całkowitą. By zakończyć rozwiązanie, pozostaje już
tylko spostrzec, że każdy wielomian postaci (5) ma żądaną własność.