XXIX OM - I - Zadanie 7

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

\[<br /> \begin{split}<br /> 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) >\\<br /> &>\frac{1}{2} \left( x_i + \frac{n}{x_i} - 2 \right) \geq \sqrt{n} - 1 \geq [\sqrt{n}] - 1,<br /> \end{split}<br /> \]

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

\[<br /> \begin{split}<br /> x_{i+1}&= \left[ \frac{1}{2} (x_i + y_i) \right] \leq \frac{1}{2} (x_i + y_i) =<br /> \frac{1}{2} \left( x_i + \left[ \frac{n}{x_i} \right] \right) \leq \\<br /> &\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,<br /> \end{split}<br /> \]

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:

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

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.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź