XXIX OM - I - Zadanie 7

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

Dla ustalonej liczby nąturalnej $n>2$ określamy: $x_1 = n$ , $y_1=1$ , $x_{i+1} = \left[\frac{1}{2}(x_i+y_i)\right]$ , $y_{i+1} = \left[ \frac{n}{x_{i+1}}\right]$ Dowieść że najmniejsza z liczb $x_1 x_2, \ldots, x_n$ jest równa [\sqrt{n}].
Uwaga. $[a]$ oznacza największą liczbę całkowitą nie większą od $a$ .

Rozwiązanie

Dla dowolnej liczby całkowitej $k$ liczba $\left[ \frac{k}{2} \right]$ jest równa $\frac{k}{2}$ lub $\frac{k-1}{2}$ w zależności od tego, czy liczba $k$ jest parzysta, czy nieparzysta. Wobec tego $\left[ \frac{k}{2} \right] \geq \frac{k-1}{2}$ dla każdej liczby całkowitej $k$ . Mamy też $a \geq [a] > a - 1$ na mocy określenia symbolu $[a]$ . Wreszcie $\frac{1}{2} \left( x_i + \frac{n}{x_i} \right) \geq \sqrt{n}$ , ponieważ średnia geometryczna liczb
dodatnich $x_i$ i $\frac{n}{x_i}$ nie przekracza ich średniej arytmetycznej.

Biorąc powyższe pod uwagę otrzymujemy, że

$ \begin{split} x_{i+1} &= \left[ \frac{1}{2} (x_i + y_i) \right] \geq \frac{1}{2} (x_i +y_i -1 )=\frac{1}{2} \left( x_i + \left[ \frac{n}{x_i} \right] - 1 \right) >\\ &>\frac{1}{2} \left( x_i + \frac{n}{x_i} - 2 \right) \geq \sqrt{n} - 1 \geq [\sqrt{n}] - 1, \end{split} $

to znaczy $x_{i+1} > [\sqrt{n}] - 1$ . Wynika stąd, że $x_{i+1} \geq [\sqrt{n}]$ dla $i = 1, 2, \ldots , n -1$ . Mamy też $x_1 = n \geq \sqrt{n} \geq [\sqrt{n}]$ .

Z drugiej strony, jeżeli dla pewnego $i = 1, 2, \ldots , n- 1$ zachodzi $x_i > [\sqrt{n}]$ , to $x_i > \sqrt{n}$ i wobec tego

$ \begin{split} x_{i+1}&= \left[ \frac{1}{2} (x_i + y_i) \right] \leq \frac{1}{2} (x_i + y_i) = \frac{1}{2} \left( x_i + \left[ \frac{n}{x_i} \right] \right) \leq \\ &\leq\frac{1}{2} \left( x_i + \frac{n}{x_i} \right)< \frac{1}{2} \left( x_i + \frac{x_i^2}{x_i} \right) = x_i, \end{split} $

to znaczy $x_{i+1} < x_i$ .

Gdyby więc wszystkie wyrazy ciągu $x_1, x_2, \ldots, x_n$ były większe od $[\sqrt{n}]$ , to byłby on ciągiem malejącym liczb naturalnych większych od $[\sqrt{n}]$ . Jest to niemożliwe, ponieważ $x_1 = n$ i ciąg ma $n$ wyrazów. Wobec tego pewien wyraz ciągu jest równy $[\sqrt{n}]$ i jest to najmniejsza
z liczb $x_1, x_2, \ldots, x_n$ .

Uwaga. Z powyższego rozwiązania wynika, że jeżeli dla pewnego $i = 1,2, \ldots ,n- 1$ zachodzi nierówność $x_{i+1} \geq x_i$ , to jest najmniejszym wyrazem ciągu $x_1, x_2, \ldots , x_n$ i wobec tego $x_i= [\sqrt{n}]$ .

Z tego zadania na mocy powyższej uwagi wynika stosunkowo prosty sposób obliczania przybliżonych wartości pierwiastków kwadratowych z liczb naturalnych. Pokażemy go na przykładzie liczby $n = 1977$ . Obliczamy początkowe wyrazy ciągów $(x_i)$ i $(y_i)$ podanych w zadaniu i wyniki umieszczamy w tabelce:

$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline x_i & 1977 & 989 & 495 & 249 & 128 & 71 & 49 & 44 & 44 \\ y_i & 1 & 1 & 3 & 7 & 15 & 27 & 40 & 44 & 44 \\ \hline \end{array} $

Ponieważ $x_9 = x_8$ , więc wynika stąd, że $[\sqrt{1977}] = x_8 = 44$ . Wystarczyło więc obliczyć tylko $9$ wyrazów ciągu $(x_1, x_2, \ldots , x_{1977})$ , by znaleźć $[\sqrt{1977}]$ , zamiast wszystkich $1977$ jego wyrazów. W tym przykładzie zresztą mamy $x_i = 44$ dla $8 \leq i \leq 1977$ . Nie zawsze jednak ciąg $(x_i)$ jest monotoniczny. Czytelnik zechce znaleźć odpowiedni przykład.