XXXIV OM - III - Zadanie 2

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

III

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

$ \frac{p}{q} < a < \frac{r}{s}, \; \frac{r}{s} - \frac{p}{q} < \frac{1}{N} \quad \text{oraz} \quad rq-ps=1. $

Rozwiązanie

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

$ (1) \qquad \frac{1}{1+k} < a < \frac{1}{k}, $

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

$ \frac{p_0}{q_0} < a < \frac{r_0}{s_0} $

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

$ \frac{b}{c} < \frac{d}{e} \ \textrm{oraz} \ dc-be=1, $

$ \begin{split} & \frac{b}{c} < \frac{b+d}{c+e},\ (b+d)c - b(c+e) = 1,\ \frac{b+d}{c+e} - \frac{b}{c} = \frac{1}{(c+e)c}, \\ & \frac{b+d}{c+e} < \frac{d}{e},\ d(e+c)-(b+d)e=1,\ \frac{d}{e} - \frac{b+d}{c+e} = \frac{1}{e(c+e)}. \end{split} $

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

$ \frac{b+d}{c+e}- \frac{b}{c} = \frac{(b+d)c-b(c+e)}{(c+e)c} = \frac{1}{(c+e)c}, $

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:

$ \begin{split} p_0 = 1,\ q_0 = k+1,\ r_0=1, s_0 = k,\\ p_{n+1} = p_n,\ q_{n + 1} = q_n, r_{n+1} = p_n+r_n,\ s_{n + 1} = q_n+s_n, \end{split} $

gdy

$ \frac{p_n}{q_n} < a < \frac{p_n+r_n}{q_n+s_n} $

oraz

$ p_{n+1} = p_n+r_n,\ q_{n + 1}= q_n+s_n,\ r_{n + 1}= r_n, s_{n + 1} = s_n, $

gdy

$ \frac{p_n+r_n}{q_n+s_n} < a < \frac{r_n}{s_n} $

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

$ \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}. $

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.