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.

Komentarze

Dodaj nową odpowiedź