XLVII OM - III etap

III etap XLVII Olimpiady Matematycznej

XLVII OM - III - Zadanie 1

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

III

Wyznaczyć wszystkie pary $(n,r)$ , gdzie $n$ jest liczbą całkowitą dodatnią $r$ zaś liczbą rzeczywistą, dla których wielomian $(x + 1)^n - r$ jest podzielny przez wielomian $2x^2 + 2x + 1$ .

Rozwiązanie

Oznaczmy przez $Q_n(x)$ i $R_n(x)$ odpowiednio iloraz i resztę z dzielenia wielomianu $(x + 1)^n$ przez $2x^2 + 2x + 1$ . Para $(n,r)$ jest jedną z szukanych par wtedy i tylko wtedy, gdy $R_n(x)$ jest wielomianem stałym, równym tożsamościowo $r$ .

Dla $n = 1,2,3,4$ mamy:

$ \begin{split} & \left(x + 1\right)^1 =0\cdot\left(2x^2 + 2x + 1\right) + \left(x + 1\right),\\ & (x + 1)^2 = \frac{1}{2} \cdot \left(2x^2 + 2x +1\right) + \left(x + \frac{1}{2}\right),\\ & (x +1)^3 = \left(\frac{1}{2}x +1\right) \left(2x^2 + 2x +1\right) + \frac{1}{2}x,\\ & (x + 1)^4=\left(\frac{1}{2}x^2 + \frac{3}{2}x + \frac{5}{4}\right)\left(2x^2 + 2x + 1\right)-\frac{1}{4}. \end{split} $

Tak więc

$ (1) \qquad R_1(x) = x + 1,\quad R_2(x) = x+\frac{1}{2},\quad R_3(x) = \frac{1}{2}x, \quad R_4(x) = -\frac{1}{4}. $

Dla każdej liczby całkowitej $n \geq 0$ zachodzi równość

$ \begin{split} (x + 1)^{n+4} & = (x + 1)^n(x + 1)^4 = \\ & = \left(Q_n(x)(2x^2 + 2x + 1) + R_n(x)\right)\left(Q_4(x)(2x^2 + 2x + 1)- \frac{1}{4}\right) =\\ & = (\textrm{wielomian podzielny przez}\ (2x^2 + 2x + 1)) - \frac{1}{4}R_n(x). \end{split} $

Wobec tego $R_{n+4}(x) = -\frac{1}{4}R_n(x)$ . Stąd oraz ze wzorów (1) otrzymujemy przez indukcję następujące równości (dla $k = 1,2,3,\ldots$ ):

$ \begin{array}{ll} R_{4k}(x) = \left(-\frac{1}{4}\right)^k, & R_{4k+1}(x) = \left(-\frac{1}{4}\right)^k(x + 1),\\ R_{4k+2}(x) = \left(-\frac{1}{4}\right)^k\left(x + \frac{1}{2}\right), & R_{4k+3}(x) = \left(-\frac{1}{4}\right)^k \left(\frac{1}{2}x\right). \end{array} $

Jak widać, $R_n(x)$ jest wielomianem stałym tylko dla $n = 4k$ ; jego stała wartość wynosi wówczas $( -\frac{1}{4})^k$ .

Wniosek: szukane pary $(n,r)$ mają postać $(4k,(-\frac{1}{4})^k)$ , gdzie $k$ jest liczbą całkowitą dodatnią.

XLVII OM - III - Zadanie 2

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

III

Wewnątrz danego trójkąta $ABC$ wybrano punkt $P$ spełniający warunki: $|\measuredangle PBC|=|\measuredangle PCA| < |\measuredangle PAB|$ . Prosta $BP$ przecina okrąg opisany na trójkącie $ABC$ w punktach $B$ i $E$ . Okrąg opisany na trójkącie $APE$ przecina prostą $CE$ w punktach $E$ i $F$ . Udowodnić, że punkty $A$ , $P$ , $E$ , $F$ są kolejnymi wierzchołkami czworokąta oraz że stosunek pola czworokąta $APEF$ do pola trójkąta $ABP$ nie zależy od wyboru punktu $P$ .

Rozwiązanie

Oznaczmy okrąg opisany na trójkącie $ABC$ przez $\Omega$ , a okrąg opisany na trójkącie $APE$ przez $\omega$ (rysunek 10). Przez punkt $E$ prowadzimy prostą styczną do okręgu $\omega$ i wybieramy na niej dowolny punkt $Q$ , leżący po tej samej stronie prostej $AE$ , co punkty $B$ , $C$ i $P$ (może to być na przykład punkt przecięcia tej prostej z okręgiem $\Omega$ , różny od $E$ ). Leży on po przeciwnej stronie prostej $EP$ niż punkt $A$ - a więc po tej samej stronie prostej $EP$ , co punkt $C$ .

Zachodzą następujące równości kątów:

$ (2) \qquad \quad |\measuredangle EAP| = |\measuredangle QEP|; $

równości (1) wiążą pary kątów wpisanych w okrąg $\Omega$ , a równość (2) wynika stąd, że prosta $ EQ $ jest styczna do okręgu $\omega$ (oraz z wyboru punktu $Q$ ).

Dane w zadaniu warunki dotyczące kątów wyznaczonych przez punkt $P$ prowadzą, w połączeniu z pierwszą równością (1), do następujących konkluzji:

$ (3) \qquad \quad | \measuredangle EAC| = | \measuredangle EBC| = |\measuredangle PBC| = |\measuredangle PCA| $

oraz

$ (4) \qquad \quad |\measuredangle CAP| + |\measuredangle PCA| < |\measuredangle CAP| + |\measuredangle PAB| = |\measuredangle CAB|. $

Korzystając kolejno ze związków (3), (4) oraz ze środkowej równości (1) mamy:

$ \begin{split} |\measuredangle EAP| & = |\measuredangle EAC| + |\measuredangle CAP| =\\ & = |\measuredangle PCA| + |\measuredangle CAP| < |\measuredangle CAB| = |\measuredangle CEB| = |\measuredangle CEP|. \end{split} $

Wobec równości (2) możemy przepisać otrzymaną zależność w postaci

$ (5) \qquad \quad |\measuredangle QEP| < |\measuredangle CEP|. $

Wcześniej stwierdziliśmy, że punkty $Q$ i $C$ leżą po jednej stronie prostej $EP$ . Z nierówności (5) wynika więc, że punkty $P$ i $C$ leżą po różnych stronach prostej $ EQ $ .

Zauważmy dalej, że $P$ i $F$ , jako punkty okręgu stycznego do prostej $ EQ $ , leżą po jednej jej stronie. W takim razie punkty $C$ i $F$ leżą po różnych stronach tej prostej. Stąd wniosek, że punkty $C$ , $E$ , $F$ leżą na prostej $CE$ w takim właśnie porządku.

Równość (3) pokazuje, że prosta $AE$ jest równoległa do $PC$ . Skoro więc punkt $E$ leży między punktami $C$ i $F$ , znaczy to, że punkt $F$ leży po przeciwnej stronie prostej $AE$ niż każdy punkt prostej $PC$ ; w szczególności, leży po przeciwnej jej stronie niż punkt $P$ . Tak więc punkty $A$ , $P$ , $E$ , $F$ są kolejnymi wierzchołkami czworokąta; mamy pierwszą część tezy zadania.

Z udowodnionej równoległości $AE || PC$ wynika ponadto, że trójkąty $APE$ i $ACE$ mają równe pola; mają bowiem wspólny bok $AE$ oraz równe wysokości, opuszczone na ten bok odpowiednio z wierzchołków $P$ i $C$ . Wobec tego pole czworokąta $APEF$ jest równe polu trójkąta $ACF$ .

Czworokąt $APEF$ jest wpisany w okrąg, więc

$ |\measuredangle CFA | = |\measuredangle EFA| = 180^\circ - |\measuredangle APE| = |\measuredangle BPA|. $

Trzecią równość (1) przepisujemy jako $| \measuredangle ACF| = |\measuredangle ABP|$ . Z tych równości wnosimy, że trójkąt $ACF$ jest podobny do trójkąta $ABP$ . Zatem

$ \frac{\textrm{pole}(APEF)}{\textrm{pole}(ABP)} = \frac{\textrm{pole}(ACF)}{\textrm{pole}(ABP)}= \left( \frac{|AC|}{|AB|}\right)^2. $

Otrzymana liczba jest dla danego trójkąta $ABC$ wielkością stałą, niezależną od wyboru punktu $P$ , spełniającego podane warunki.

XLVII OM - III - Zadanie 3

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

III

Dana jest liczba naturalna $n \geq 2$ oraz liczby dodatnie $a_l, a_2, \ldots , a_n$ , których suma równa się 1.

(a) Dowieść, że dla dowolnych liczb dodatnich $x_l, x_2, \ldots , x_n$ o sumie równej 1 zachodzi nierówność

$ \2\sum_{i<j} x_ix_j \leq \frac{n-2}{n-1} + \sum_{i=1}^n \frac{a_ix_i^2}{1-a_i} $

(b) Wyznaczyć wszystkie układy liczb dodatnich $x_l, x_2, \ldots , x_n$ o sumie równej 1 dla których powyższa nierówność staje się równością.

Uwaga: Symbol $\sum_{i<j} x_ix_j$ oznacza sumę $\binom{n}{2}$ składników odpowiadających wszystkim parom wskaźników $i,j$ ze zbioru $\{1,2, \ldots ,n\}$ spełniającym warunek $i < j$ .

Rozwiązanie

Z podanych warunków ( $n \geq 2$ ; $a_i>0$ ; $\sum a_i =1$ ) wynika, że liczby $a_1, a_2, \ldots, a_n$ należą do przedziału $(0;\ 1)$ . Przyjmijmy

$ (1) \qquad \quad c_i=\sqrt{1-a_i} \ \textrm{dla} \ i=1,2,\ldots,n; $

są to także liczby z przedziału $(0;\ 1)$ . Zachodzi dla nich równość

$ (2) \qquad \quad \sum_{i=1}^n c_i^2 = n-1. $

Niech $x_1, x_2,\ldots, x_n$ będą dowolnymi liczbami rzeczywistymi, których suma jest równa $1$ . Wówczas

$ 2 \sum_{i<j} x_ix_j = \left( \sum_{i=1}^n x_i \right) ^2-\sum_{i=1}^n x_i^2=1- \sum_{i=1}^n x_i^2. $

Nierówność dana do udowodnienia przybiera postać

$ 1- \sum_{i=1}^n x_i^2 \leq \frac{n-2}{n-1} + \sum_{i=1}^n \frac{a_ix_i^2}{1-a_i}, $

czyli

$ \sum_{i=1}^n \frac{x_i^2}{1-a_i} \geq \frac{1}{n-1}; $

a używając oznaczenia (1) dostajemy kolejną równoważną postać dowodzonej nierówności:

$ (3) \qquad \quad \sum_{i=1}^n \left( \frac{x_i}{c_i} \right)^2 \geq \frac{1}{n-1}; $

Dla każdego numeru $i \in \{1,2,\ldots,n\}$ mamy oczywistą nierówność

$ (4) \qquad \quad \left( \frac{x_i}{c_i} - \frac{c_i}{n-1} \right)^2 \geq 0. $

Dodajemy te $n$ nierówności stronami (rozpisując kwadraty różnic):

$ \sum_{i=1}^n \left( \left(\frac{x_i}{c_i}\right)^2 - \frac{2x_i}{n-1} + \left(\frac{c_i}{n-1}\right)^2 \right) \geq 0. $

Korzystamy ze wzoru (2) oraz z tego, że $\sum x_i=1$ , i otrzymujemy

$ \sum_{i=1}^n \left( \frac{x_i}{c_i} \right)^2 - \frac{2}{n-1} + \frac{1}{(n-1)^2} \cdot (n-1) \geq 0. $

Po prostym przekształceniu wynika stąd nierówność (3).

Udowodniliśmy tezę (a).

Z przeprowadzonego rozumowania wynika także natychmiast rozstrzygnięcie kwestii (b): nierówność (3) (równoważna nierówności podanej w zadaniu) staje się równością wtedy i tylko wtedy, gdy każda z nierówności (4) (dla $i = 1,2, \ldots,n$ ) przechodzi w równość; to znaczy, gdy $x_i/c_i= c_i/(n - 1)$ , czyli - zgodnie z oznaczeniem (1) — gdy

$ (5) \qquad \quad x_i=\frac{1-a_i}{n-1} \ \textrm{dla} \ i=1,2,\ldots, n. $

XLVII OM - III - Zadanie 4

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

III

W czworościanie $ABCD$ zachodzą następujące równości:

$ |\measuredangle BAC| = |\measuredangle ACD| \quad \text{oraz} \quad |\measuredangle ABD| = |\measuredangle BDC|. $

Dowieść, że krawędzie $AB$ i $CD$ mają jednakową długość.

Rozwiązanie

W dowodzie będziemy korzystali z następującego (znanego) faktu:

$ (*) \qquad \begin{array}{l} \textrm{Suma dwóch kątów płaskich przy dowolnym wierzchołku czworościanu} \\ \textrm{jest większa od trzeciego kąta płaskiego przy tym wierzchołku.} \end{array} $

(To proste twierdzenie pojawiło się na przykład jako lemat w rozwiązaniu jednego z zadań XXIV Olimpiady Matematycznej; można więc znaleźć dowód w broszurze: XXIV Olimpiada Matematyczna. Sprawozdanie Komitetu Głównego, Warszawa 1974, str. 66 - ale zachęcamy raczej do samodzielnego przeprowadzenia tego dowodu; jest to nietrudnym ćwiczeniem.)

Rozwijamy siatkę czworościanu $ABCD$ na płaszczyźnie $ABC$ ; replikami ścian $BCD$ , $CAD$ , $ABD$ są przystające do nich (odpowiednio) trójkąty $BCD_1$ , $CAD_2$ , $ABD_3$ (rysunek 11).

Zgodnie z założeniem, $| \measuredangle BAC| = | \measuredangle ACD_2|$ ; jest to równość kątów naprzemianległych dla prostych $AB$ i $CD_2$ przeciętych sieczną $AC$ . Proste te są wobec tego równoległe: $AB||CD_2$ , przy tym wektory $\overrightarrow{BA}$ i $\overrightarrow{CD_2}$ są zgodnie skierowane.

Uzupełniamy trójkąt $BCD_2$ do równoległoboku $BCD_2E$ ; punkt $E$ leży na półprostej $BA^\to$ . Mamy związki:

$ |CD_1| =|CD_2| = |EB|, \quad |BD_1| = |BD_3|( = |BD|), $

$ | \measuredangle BD_1C| = | \measuredangle ABD_3| = |\measuredangle EBD_3| $

(równość miar kątów $BD_1C$ i $ABD_3$ , czyli miar kątów $BDC$ i $ABD$ , jest dana w założeniach). Ze związków tych wynika, że trójkąt $BD_1C$ przystaje do trójkąta $D_3BE$ i wobec tego $|D_3E| = |BC| = |D_2E|$ .

Przypuśćmy teraz, wbrew tezie zadania, że $|AB| \ne |CD|$ . Punkt $E$ nie pokrywa się wówczas z punktem $A$ , tworzą się niezdegenerowane trójkąty $AED_2$ i $AED_3$ . Są one przystające, bowiem $|AD_2| = |AD_3| ( = |AD|)$ oraz $|D_2E| = |D_3E|$ (co wykazaliśmy przed chwilą). Zatem $|\measuredangle EAD_2| = | \measuredangle EAD_3|$ , czyli $| \measuredangle BAD_2| = | \measuredangle BAD_3|$ ; ta ostatnia równość wynika z poprzedniej niezależnie od tego, czy punkt $E$ leży między $B$ i $A$ , czy też $A$ leży między $B$ i $E$ . Tak więc

$ |\measuredangle BAD_3| = |\measuredangle BAD_2| = |\measuredangle BAC| + |\measuredangle CAD_2| = |\measuredangle BAC| + |\measuredangle CAD|. $

Trójkąt $ABD_3$ przystaje do $ABD$ (zgodnie ze sposobem rozwijania siatki czworościanu $ABCD$ ), i wobec tego $|\measuredangle BAD_3| = |\measuredangle BAD|$ .

Otrzymane równości dają sprzeczność z własnością (*), w myśl której

$ |\measuredangle BAD| < |\measuredangle BAC| + |\measuredangle CAD|. $

Sprzeczność pokazuje niesłuszność przypuszczenia, że $|AB| \ne |CD|$ , i tym samym kończy dowód.

XLVII OM - III - Zadanie 5

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

III

Dla liczby naturalnej $k \geq 1$ oznaczmy przez $p(k)$ najmniejszą liczbę pierwszą, która nie jest dzielnikiem liczby $k$ . Jeśli $p(k) > 2$ , to przyjmujemy, że $q(k)$ jest iloczynem wszystkich liczb pierwszych mniejszych od $p(k)$ ; gdy zaś $p(k) = 2$ , to przyjmujemy $q(k) = 1$ . Określamy ciąg $(x_n)$ wzorami:

$ x_0 = 1, \quad x_{n+1} = \frac{x_n p(x_n)}{q(x_n)} \text{ dla } n = 0,1,2,\ldots . $

Wyznaczyć wszystkie liczby naturalne $n$ , dla których zachodzi równość $x_n = 111111$ .

Rozwiązanie

Niech $p_0 = 2$ , $p_1 = 3$ , $p_2 = 5$ , $p_3 = 7$ , $\ldots$ będzie rosnącym ciągiem wszystkich liczb pierwszych. Wyrazy rozważanego w zadaniu ciągu $(x_n)$ dadzą się scharakteryzować przez cyfry zapisu wskaźnika $n$ w dwójkowym układzie pozycyjnym. Wykażemy mianowicie, że dla $n \geq 1$ zachodzi implikacja:

$ (*) \qquad \textrm{jeżeli} \ n=\overline{c_m c_{m-1}\ldots c_1c_0} = \sum_{i=0}^m c_i 2^i \quad (c_i \in \{0,\ 1\}),\ \textrm{to}\ x_n = \prod_{i=0}^m p^{c_i}_i. $

Dla $n = 1$ jest to prawda ( $x_1 = x_0 p(x_0)/q(x_0) =p(1)/q(1) = 2 = p_0$ ).

Przyjmijmy słuszność zdania (*) dla pewnej liczby naturalnej $n \geq 1$ . Jeżeli $n$ jest liczbą parzystą, to $c_0 = 0$ , więc

$ n=\sum_{i=1}^m c_i 2^i \quad \textrm{oraz} \quad x_n=\prod_{i=1}^m p^{c_i}_i. $

Zatem $p(x_n) = 2$ , $q(x_n) = 1$ , i zgodnie z podanym wzorem rekurencyjnym: $x_{n+1} =2x_n$ . Tak więc

$ n+1 =2^0 + \sum_{i=1}^m c_i2^i, \quad x_{i+1}=p_0 \cdot \prod_{i=1}^m p^{c_i}_i; $

reguła (*) zachowuje słuszność dla $n + 1$ .

Jeżeli natomiast $n$ jest liczbą nieparzystą, to $c_0 = 1$ . Załóżmy, że zapis dwójkowy liczby $n$ nie składa się z samych jedynek (przypadek, gdy tak jest, rozpatrzymy za chwilę). Niech $j$ będzie najmniejszym numerem, dla którego $c_j =0$ . To znaczy, że

$ n = \overline{c_m c_{m-1} \ldots c_{j+1} 0 \underbrace{11 \ldots 11}_{j} } = \sum_{i=0}^{j-1} 2^i + \sum_{i=j+1}^m c_i 2^i. $

Reguła (*) (która w myśl założenia indukcyjnego zachodzi dla rozważanej liczby $n$ ) daje równość

$ x_n = \prod_{i=0}^{j-1} p_i \cdot \prod_{i=j+1}^m p^{c_i}_i. $

Zatem $p(x_n) =p_j$ , $q(x_n)=\prod_{i=0}^{j-1} p_i$ . Liczby $n+ 1$ oraz $x_{n+1}$ mają więc przedstawienia:

$ n+1 = \overline{c_m c_{m-1} \ldots c_{j+1}1 \underbrace{00\ldots 00}_j}= 2^j + \sum_{i=j+1}^{m} c_i 2^i, $

$ x_{n+1} = \frac{x_n}{q(x_n)} \cdot p_j = p_j \cdot \prod_{i=j+1}^m p^{c_i}_i; $

także i w tym przypadku reguła (*) jest słuszna dla $n + 1$ .

Pozostała do rozpatrzenia sytuacja, gdy w przedstawieniu dwójkowym liczby $n$ są same jedynki:

$ n=\overline{\underbrace{11\ldots11}_{m+1}} = \sum_{i=0}^m 2^i. $

Zgodnie z założeniem indukcyjnym (*) oraz z podanym wzorem rekurencyjnym mamy teraz:

$ x_n=\prod_{i=0}^m p_i, \quad p(x_n)=p_{m+1}, \quad q(x_n)=\prod_{i=0}^m p_i = x_n. $

Zatem

$ x_{n+1} = \frac{x_n}{q(x_n)} \cdot p_{m+1} = p_{m+1}; \quad \textrm{jednocześnie} \ n +1 = 2^{m+1}. $

Jak widać, również w takim przypadku reguła (*) zachowuje słuszność dla $n+1$ .

Na mocy zasady indukcji implikacja (*) zachodzi dla wszystkich liczb naturalnych $n \geq 1$ .

Różne liczby $n$ mają różne rozwinięcia dwójkowe. Wynika stąd (wobec charakteryzacji ( $*$ )), że w ciągu $(x_n)$ żadna liczba nie powtarza się. Pozostaje zauważyć, że w rozkładzie na czynniki pierwsze liczba $111111$ ma postać iloczynu $3\cdot 7\cdot 11 \cdot 13 \cdot 37$ , czyli spełnia równość $111111 = p_1p_3p_4p_5p_{11}$ . Stąd wniosek, że dla liczby $n = 2^1 + 2^3 +2^4 + 2^5 + 2^{11} = 2106$ , i tylko dla niej, zachodzi równość $x_n = 111111$ .

Uwaga: Z przeprowadzonego rozumowania wynika, że w ciągu $(x_n)$ występują wszystkie dodatnie liczby całkowite bezkwadratowe, to znaczy nie dzielące się przez kwadrat żadej liczby pierwszej; innymi słowy, mające rozkład na iloczyn różnych czynników pierwszych; przy tym każda taka liczba pojawia się w tym ciągu dokładnie raz.

Wzór rekurencyjny, generujący ów ciąg, naśladuje algorytm dodawania jedynki w dwójkowym układzie pozycyjnym. Do zauważenia tego faktu oraz jego precyzyjnego opisu sprowadza się powyższe rozwiązanie.

XLVII OM - III - Zadanie 6

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

III

Spośród wszystkich permutacji $f$ zbioru $\{1,2, \ldots , n\}$ spełniających warunek

$ f(i) \geq i-1 \quad \text{ dla } i=1, 2, \ldots, n $

wybieramy jedną (każdy wybór jest jednakowo prawdopodobny). Niech $p_n$ będzie prawdopodobieństwemtego, że wybrana permutacja spełnia warunek

$ f(i) \leq i+1 \quad \text{ dla } i=1, 2, \ldots, n $

Wyznaczyć wszystkie liczby naturalne $n$ , dla których $p_n > \frac{1}{3}$ .

Rozwiązanie

Oznaczmy przez $V_n$ zbiór tych permutacji zbioru $\{1,2,\ldots,n\}$ (czyli różnowartościowych funkcji $f: \{1,2,\ldots,n\} \to \{1,2,\ldots,n\}$ ), które spełniają pierwszy z podanych warunków:

$ (1) \qquad \quad f(i) \geq i-1 \ \textrm{dla} \ i=1,2,\ldots,n. $

Oznaczmy ponadto przez $U_n$ zbiór tych permutacji $f$ , które spełniają oba podane warunki: (1) oraz

$ (2) \qquad \quad f(i) \leq i+1 \ \textrm{dla} \ i=1,2,\ldots,n. $

(Oczywiście $U_n$ jest podzbiorem zbioru $V_n$ .) Niech $v_n$ będzie liczbą permutacji w zbiorze $V_n$ i niech $u_n$ będzie liczbą permutacji w zbiorze $U_n$ . Wówczas $p_n=u_n/v_n$ .

Rozpatrzymy najpierw przypadki banalne: $n = 1$ , $n = 2$ . W zbiorze jednoelementowym można określić tylko jedną permutację; w zbiorze dwuelementowym dwie. Każda z nich spełnia warunki (1), (2). Zatem $u_1 =v_1 = 1$ , $u_2=v_2 = 2$ .

Ustalmy $n \geq 3$ . Jeśli permutacja $f$ zbioru $\{1,2,\ldots,n\}$ spełnia warunek (1), to w szczególności $f(n) \geq n - 1$ , co oznacza, że $f(n) = n$ lub $f(n) = n - 1$ . Tak więc zarówno zbiór $V_n$ , jak i $U_n$ , jest sumą dwóch podzbiorów, złożonych (odpowiednio) z tych permutacji, które spełniają pierwszy bądź drugi człon tej alternatywy. Oznaczmy te podzbiory, jak następuje:

$ V_n' = \{f \in V_n: f(n)=n\}, \quad V_n'' = \{f \in V_n: f(n)=n-1 \}, $

$ U_n' = \{f \in U_n: f(n)=n\}, \quad U_n'' = \{f \in U_n: f(n)=n-1 \}, $

i przyjmijmy, że w zbiorach tych jest (odpowiednio): $v'_n$ permutacji, $v''_n$ permutacji, $u'_n$ permutacji, $u''_n$ permutacji. Wówczas $v_n = v'_n + v''_n$ , $u_n = u'_n+u''_n$ .

Weźmy dowolną permutację $f \in V'_n$ : spełnia ona równość $f(n) = n$ , a zatem $f(i) \leq n - 1$ dla $i \leq n - 1$ . Przyjmując

$ (3) \qquad \quad \varphi(i)=f(i) \quad \textrm{dla}\ i= 1,2,\ldots,n-1 $

określamy permutację $\varphi: \{1,2, \ldots, n-1\} \to \{1,2, \ldots,n-1\}$ . Warunek (1) jest spełniony przez permutację $f$ , więc także przez permutację $\varphi$ . To znaczy, że $\varphi \in V_{n-1}$ .

Na odwrót, jeśli $\varphi$ jest dowolną permutacją zbioru $\{1,2,\ldots,n-1\}$ należącą do zbioru $V_{n-1}$ , to przyjmując

$ (4) \qquad \quad f(i)= \left\{ \begin{array}{ccl} \varphi(i) & \textrm{dla} & i \leq n-1,\\ n & \textrm{dla} & i=n \end{array} \right. $

dostajemy permutację zbioru $\{1,2,\ldots,n\}$ spełniającą warunek (1) wraz z równością $f(n) =n$ , czyli permutację należącą do zbioru $V'_n$ .

Wzór (3) określa operację zawężenia $f$ do zbioru $\{1,2,\ldots,n-1\}$ ; wzór (4) określa operację rozszerzenia $\varphi$ do zbioru $\{1,2,\ldots,n\}$ . Te dwie operacje są wzajemnie odwrotne, więc ustalają wzajemnie jednoznaczną odpowiedniość pomiędzy elementami zbioru $V'_n$ i elementami zbioru $V_{n-1}$ . Stąd wniosek, że zbiory te liczą tyle samo elementów (są równoliczne): $v'_n = v_{n-1}$ .

Weźmy dowolną permutację $f \in V''_n$ : spełnia ona równość $f(n) = n-1$ . Istnieje w zbiorze $\{1,2,\ldots,n-1\}$ dokładnie jeden element $i_0$ taki, że $f(i_0) = n$ . Przyjmując

$ (5) \qquad \quad \psi(i) = \left\{ \begin{array}{lll} f(i) & \textrm{dla} & i \ne i_0, 1 \leq i \leq n-1,\\ n-1 & \textrm{dla} & i=i_0 \end{array} \right. $

określamy permutację $\psi: \{1,2,\ldots,n-1\} \to \{1,2,\ldots,n-1\}$ . Przy tym

$ \psi(i) \geq i-1 \quad \textrm{dla}\ i = 1,2,\ldots,n-1 $

(dla $i \ne i_0$ wynika to z warunku (1), a dla $i = i_0$ mamy $\psi(i_0) = n- 1 \geq i_0 - 1$ ). To znaczy, że $\psi \in V_{n-1}$ .

Na odwrót, jeśli $\psi$ jest dowolną permutacją zbioru $\{1,2,\ldots,n-1\}$ należącą do zbioru $V_{n-1}$ , to istnieje element $i_0 \in \{1,2,\ldots,n-1\}$ , dla którego zachodzi równość $\psi(i_0) = n - 1$ . Przyjmując

$ (6) \qquad \quad f(i) = \left\{ \begin{array}{ccl} \psi(i) & \textrm{dla} & i \ne i_0,\ 1 \leq i \leq n-1,\\ n & \textrm{dla} & i=i_0\\ n-1 & \textrm{dla} & i=n \end{array} \right. $

dostajemy permutację zbioru $\{1,2,\ldots,n\}$ . Spełnia ona warunek (1) oraz równość $f(n) = n - 1$ , więc należy do zbioru $V''_n$ .

Jak poprzednio, operacje wyznaczania $\psi$ przez $f$ (wzór (5)) oraz wyznaczania $f$ przez $\psi$ (wzór (6)) są wzajemnie odwrotne. Ustalają zatem wzajemnie jednoznaczną odpowiedniość pomiędzy elementami zbioru $V''_n$ i elementami zbioru $V_{n-1}$ . Tak więc $v''_n = v_{n-1}$ . W połączeniu z poprzednią konkluzją otrzymujemy związek:

$ (7) \qquad \quad v_n = v'_n + v''_n = 2 v_{n-1} \quad \textrm{dla} \ n \geq 3. $

Uzyskaliśmy wzór rekurencyjny dla ciągu $(v_n)$ .

Podobne rozumowanie da nam wzór rekurencyjny dla ciągu $(u_n)$ .

Weźmy permutację $f \in U'_n$ (zatem $f(n) = n$ ) i niech $\varphi$ będzie zawężeniem $f$ do zbioru $\{1,2,\ldots,n-1\}$ ; to znaczy, definiujemy $\varphi$ wzorem (3). Warunki (1) i (2) są spełnione przez permutację $f$ , więc także przez $\varphi$ . To znaczy, że $\varphi \in U_{n-1}$ .

Na odwrót, jeśli $\varphi$ jest permutacją zbioru $\{1,2,\ldots ,n-1\}$ należącą do $U_{n-1}$ , to możemy ją rozszerzyć do permutacji $f$ zbioru $\{1,2,\ldots,n\}$ , przyjmując $f(n) = n$ . Rozszerzona permutacja spełnia warunki (1) i (2) oraz $f(n) = n$ , więc należy do zbioru $U'_n$ .

Wzajemnie odwrotne operacje rozszerzania i zawężania dają odpowiedniość między elementami zbiorów $U'_n$ i $U_{n-1}$ . Zatem $u'_n = u_{n-1}$ .

Weźmy wreszcie dowolną permutację $f \in U''_n$ (zatem $f(n) = n-1$ ). Wobec warunku (2), element $n$ nie może być równy $f(k)$ dla żadnego $k < n - 1$ ; musi być równy $f(n - 1)$ . Permutacja $f$ zamienia więc miejscami elementy $n-1$ i $n$ . Zawężamy ją do zbioru $\{1,2,\ldots,n-2\}$ ; to znaczy, przyjmujemy

$ (8) \qquad \quad \psi(i)=f(i) \quad \textrm{dla} \ i = 1,2,\ldots,n-2; $

dostajemy permutację $\psi$ zbioru $\{1,2,\ldots,n-2\}$ . Warunki (1) i (2) są spełnione przez $f$ , więc i przez $\psi$ . Zatem $\psi \in U_{n-2}$ .

Na odwrót, jeśli $\psi$ jest permutacją zbioru $\{1,2,\ldots,n-2\}$ należącą do $U_{n-2}$ , to rozszerzamy ją do permutacji $f$ zbioru $\{1,2,\ldots,n\}$ , przyjmując

$ (9) \qquad \quad f(i)=\left\{ \begin{array}{ccc} \psi(i) & \textrm{dla} & i \leq n-2,\\ n & \textrm{dla} & i=n-1,\\ n-1 & \textrm{dla} & i=n. \end{array} \right. $

Rozszerzona permutacja spełnia warunki (1) i (2) oraz $f(n)=n-1$ , czyli należy do zbioru $U''_n$ .

Także i teraz operacje zawężania (wzór (8)) i rozszerzania (wzór (9)) są wzajemnie odwrotne i dają odpowiedniość między elementami zbiorów $U''_n$ i $U_{n-2}$ . Zatem $u''_n=u_{n-2}$ . W konsekwencji

$ (10) \qquad \quad u_n =u'_n+u''_n = u_{n-1} + u_{n-2} \quad \textrm{dla}\ n \geq 3. $

Mamy wzór rekurencyjny dla ciągu $(u_n)$ .

[Jak widać, $(u_n)$ jest ciągiem Fibonacci'ego; podobnie wzór (7) pozwala wywnioskować, że $(v_n)$ jest ciągiem kolejnych potęg dwójki; nie będziemy jednak w tym rozwiązaniu korzystać z jawnych przedstawień tych ciągów.]

Ze wzoru (10) wynika, że $u_n>u_{n-1}$ dla $n \geq 3$ ; a skoro $u_2 = 2$ , $u_1 = 1$ , zatem $u_n >u_{n-1}$ dla $n\geq 2$ . W takim razie dla $n \geq 3$ zachodzi nierówność $u_{n-1} >u_{n-2}$ . Wzór (10) daje więc oszacowanie

$ u_n =u_{n-1} +u_{n-2} < u_{n-1}+u_{n-1} =2u_{n-1}. $

Stąd oraz z zależności (7) wnosimy, że

$ \frac{p_n}{p_{n-1}} = \frac{u_n}{v_n} \cdot \frac{v_{n-1}}{u_{n-1}} = \frac{v_{n-1}}{v_n} \cdot \frac{u_n}{u_{n-1}} < \frac{1}{2} \cdot 2 = 1 \quad \textrm{dla}\ n \geq 3; $

ciąg $(p_n)$ jest malejący (począwszy od drugiego wyrazu).

Korzystając ze wzorów (10) i (7) obliczamy początkowe wyrazy ciągów $(u_n)$ i $(v_n)$ i stwierdzamy, że $u_6=13$ , $u_7 = 21$ , $v_6 = 32$ , $v_7 = 64$ . Wobec tego $p_6= \frac{13}{32} > \frac{1}{3}$ , $p_7 = \frac{21}{64} < \frac{1}{3}$ , i z monotoniczności ciągu $(p_n)$ wynika odpowiedź: nierówność $p_n > \frac{1}{3}$ zachodzi tylko dla $n =1, 2, 3, 4, 5, 6$ .