Komentarz

XXXIV OM - III - Zadanie 2

Dana jest liczba niewymierna $ a $ należąca do przedziału $ (0,1) $ i liczba naturalna $ N $. Udowodnić, że istnieją takie liczby naturalne $ p, q, r, s $, że

\[<br /> \frac{p}{q} < a < \frac{r}{s}, \; \frac{r}{s} - \frac{p}{q} < \frac{1}{N} \quad \text{oraz} \quad rq-ps=1.<br /> \]

Rozwiązanie

Niech $ k $ będzie największą liczbą naturalną spełniającą nierówność $ \frac{1}{k} > a $. Wobec tego

\[<br /> (1) \qquad \frac{1}{1+k} < a < \frac{1}{k},<br /> \]

a zatem przyjmując $ p_0 = 1 $, $ q_0= k+1 $, $ r_0 = 1 $, $ s_0=k $ mamy spełnioną nierówność

\[<br /> \frac{p_0}{q_0} < a < \frac{r_0}{s_0}<br /> \]

oraz warunek $ r_0q_0-p_0s_0 = 1 $, gdyż $ 1 \cdot (k+1)-1 \cdot k = 1 $. Jeżeli ponadto $ \frac{1}{k} - \frac{1}{k+1} < \frac{1}{N} $, to liczby $ p_0 $, $ q_0 $, $ r_0 $, $ s_0 $ stanowią rozwiązanie zadania. Jeśli ostatnia nierówność nie jest spełniona to następujący lemat wskaże drogę do rozwiązania.

Lemat. Jeśli liczby naturalne $ b $, $ c $, $ d $, $ e $ spełniają warunki

\[<br /> \frac{b}{c} < \frac{d}{e} \ \textrm{oraz} \ dc-be=1,<br /> \]

to

\[<br /> \begin{split}<br /> & \frac{b}{c} < \frac{b+d}{c+e},\ (b+d)c - b(c+e) = 1,\<br /> \frac{b+d}{c+e} - \frac{b}{c} = \frac{1}{(c+e)c}, \\<br /> & \frac{b+d}{c+e} < \frac{d}{e},\ d(e+c)-(b+d)e=1,\<br /> \frac{d}{e} - \frac{b+d}{c+e} = \frac{1}{e(c+e)}.<br /> \end{split}<br /> \]

Dowód. $ (b+d)c-b(c+e)= bc+dc-bc-be= dc-be = 1 $. Obliczamy różnicę

\[<br /> \frac{b+d}{c+e}- \frac{b}{c} = \frac{(b+d)c-b(c+e)}{(c+e)c} = \frac{1}{(c+e)c},<br /> \]

skąd oczywiście wynika, że $ \displaystyle \frac{b}{c} < \frac{b+d}{c+e} $. Pozostałe warunki otrzymujemy analogicznie.

Rozważamy cztery ciągi liczb naturalnych $ (p_n) $, $ (q_n) $, $ (r_n) $, $ (s_n) $ określone, jak następuje:

\[<br /> \begin{split}<br /> p_0 = 1,\ q_0 = k+1,\ r_0=1, s_0 = k,\\<br /> p_{n+1} = p_n,\ q_{n + 1} = q_n, r_{n+1} = p_n+r_n,\ s_{n + 1} = q_n+s_n,<br /> \end{split}<br /> \]

gdy

\[<br /> \frac{p_n}{q_n} < a < \frac{p_n+r_n}{q_n+s_n}<br /> \]

oraz

\[<br /> p_{n+1} = p_n+r_n,\ q_{n + 1}= q_n+s_n,\ r_{n + 1}= r_n, s_{n + 1} = s_n,<br /> \]

gdy

\[<br /> \frac{p_n+r_n}{q_n+s_n} < a < \frac{r_n}{s_n}<br /> \]

Z powyższego określenia wynika, na podstawie nierówności (1) i lematu, że liczby $ p_n $, $ q_n $, $ r_n $, $ s_n $ spełniają warunki

\[<br /> \frac{p_n}{q_n} < a < \frac{r_n}{s_n},\ r_nq_n - p_ns_n=1 \ \textrm{oraz} \ \frac{r_n}{s_n}-\frac{p_n}{q_n}=\frac{1}{s_nq_n}.<br /> \]

Iloczyny $ q_ns_n $ tworzą ciąg ściśle rosnący, bowiem przy przejściu od $ n $ do $ n+ 1 $ jeden z czynników zwiększa się, drugi zaś pozostaje nie zmieniony. Wobec tego wystarczy przyjąć tak duże $ n $, żeby zachodziła nierówność $ s_nq_n > N $. Liczby $ p_n $, $ q_n $, $ r_n $, $ s_n $ spełniają wówczas warunki zadania.

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

Dodaj komentarz