XLVII OM

XLVII Olimpiada Matematyczna

Opracowanie rozwiązań: Marcin E. Kuczma

XLVII OM - I etap

I etap XLVII Olimpiady Matematycznej

XLVII OM - I - Zadanie 1

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

Wyznaczyć wszystkie liczby całkowite $n$ , dla których równanie $2 \sin nx = \tan x + \cot x$ ma rozwiązania w liczbach rzeczywistych $x$ .

Rozwiązanie

Załóżmy, że dane równanie ma rozwiązania w liczbach rzeczywistych: niech $\alpha$ będzie jednym z tych rozwiązań. Oczywiście $\alpha$ nie może być całkowitą wielokrotnością $\pi/2$ , bo dla takich liczb prawa strona traci sens. Zgodnie z równaniem,

$ 2 \sin n \alpha = \tan \alpha + \cot \alpha = \frac{\sin \alpha}{\cos \alpha} + \frac{\cos \alpha}{\sin \alpha} = \frac{\sin^2 \alpha+\cos ^2 \alpha}{\cos \alpha \sin \alpha} = \frac{2}{\sin 2 \alpha}; $

stąd $2\sin n\alpha \cdot \sin 2\alpha=2$ , czyli

$ \cos(n-2)\alpha-\cos(n+2)\alpha = 2 $

(korzystamy tu ze wzoru: $\cos u - \cos v = 2\sin \frac{1}{2}(u+v)\sin\frac{1}{2}(v-u))$ . Różnica dwóch kosinusów jest równa $2$ wtedy i tylko wtedy, gdy pierwszy z nich ma wartość $1$ , a drugi $-1$ . Dostajemy więc układ równości

$ \cos(n-2)\alpha = 1, \quad \cos(n + 2)\alpha = -1, $

z których wynika, że

$ (1) \qquad (n-2)\alpha = 2q\pi, \quad (n + 2)\alpha = (2p + 1) \pi $

( $p, q$ liczby całkowite).

W drugiej z równości (1) mamy po prawej stronie liczbę różną od zera; zatem i lewa strona ma wartość różną od zera. Możemy wobec tego podzielić pierwszą równość stronami przez drugą. Dostajemy związek $\frac{n-2}{n+2}=\frac{2q}{2p+1}$ .

Wprowadzając oznaczenie $n-2 = m$ przepisujemy ten związek w postaci $(2p+1)m = 2q(m+4)$ , czyli

$ (2p-2q+1)m = 8q. $

Widzimy, że liczba $m$ pomnożona przez liczbę nieparzystą daje w wyniku liczbę podzielną przez $8$ , co jest możliwe tylko wtedy, gdy sama liczba $m$ dzieli się przez $8$ . Skoro zaś $n = m + 2$ , znaczy to, że liczba $n$ daje w dzieleniu przez $8$ resztę $2$ .

Biorąc jeszcze pod uwagę warunek zadania mówiący, że liczba $n$ ma być dodatnia, dochodzimy do następującej konkluzji:

$ (2) \qquad \quad n \textrm{ jest liczbą postaci } 8k+2,\ k \textrm{ całkowite},\ k \geq 0. $

Na odwrót, jeśli liczba $n$ ma taką postać, to rozważane równanie ma rozwiązania w liczbach rzeczywistych --- jednym nich jest na przykład liczba $x = \frac{1}{4} \pi$ ; istotnie: dla $x=\frac{1}{4} \pi$ oraz $n = 8k + 2$ mamy $nx = 2k\pi + \frac{1}{2} \pi$ , skąd $\sin nx = 1$ ; zarówno lewa jak i prawa strona równania ma wartość $2$ .

Wniosek: liczby, których wyznaczenie było celem zadania, są scharakteryzowane przez zdanie (2).

Uwaga: Wspomnimy jeszcze wariant rozwiązania polegający na spostrzeżeniu (od razu na początku), że dla każdej liczby $x$ prawa strona równania, jako liczba postaci $t + (1/t)$ , ma wartość bezwzględną nie mniejszą niż $2$ , podczas gdy wartość bezwzględna lewej strony jest nie większa od $2$ . Równanie może więc być spełnione tylko wtedy, gdy obie strony mają wartość $2$ lub $-2$ . Każda z tych możliwości daje układ dwóch prostych równań trygonometrycznych. Dokończenie rozumowania jest łatwym zadaniem i prowadzi do wniosku (2), dającego charakteryzację poszukiwanych liczb $n$ . Czytelnikowi pozostawiamy dopracowanie szczegółów.

stąd $2\sin n\alpha \cdot \sin 2\alpha=2$ , czyli

$ \cos(n-2)\alpha-\cos(n+2)\alpha = 2 $

$ \cos(n-2)\alpha = 1, \quad \cos(n + 2)\alpha = -1, $

z których wynika, że

$ \qquad (1) (n-2)\alpha = 2q\pi, \quad (n + 2)\alpha = (2p + 1) \pi $

( $p, q$ liczby całkowite).

Wprowadzając oznaczenie $n-2 = m$ przepisujemy ten związek w postaci $(2p+1)m = 2q(m+4)$ , czyli

$ (2p-2q+1)m = 8q. $

Biorąc jeszcze pod uwagę warunek zadania mówiący, że liczba $n$ ma być dodatnia, dochodzimy do następującej konkluzji:

$ \qquad (2) \quad n \textrm{ jest liczbą postaci } 8k+2,\ k \textrm{ całkowite},\ k \geq 0. $

Wniosek: liczby, których wyznaczenie było celem zadania, są scharakteryzowane przez zdanie (2).

XLVII OM - I - Zadanie 2

Zawody matematyczne:

XLVIII OM, 1996-1997

Etap:

Liczbą palindromiczną nazywamy taką liczbę naturalną, której zapis dziesiętny czytany od strony lewej do prawej jest taki sam, jak czytany od strony prawej do lewej. Niech $(x_n)$ bedzie rosnącym ciągiem wszystkich liczb palindromicznych. Wyznaczyć wszystkie liczby pierwsze, które są dzielnikami co najmniej jednej z różnic $x_{n+1}-x_n$ .

Rozwiązanie

Zapis dziesiętny liczby palindromicznej $x_n$ (odpowiednio: ( $2m$ )-cyfrowej lub ( $2m-1$ )-cyfrowej) wygląda tak:

$ (1) \qquad \quad x_n = \overline{c_1 c_2\ldots c_{m-1} c_m c_m c_{m-1} \ldots c_2 c_1} $

lub

$ (2) \qquad \quad x_n = \overline{c_1 c_2\ldots c_{m-1} c_m c_{m-1} \ldots c_2 c_1} $

( $c_i \in \{ 0,1,2,3,4,5,6,7,8,9\}$ dla $i = 1, \ldots ,m;\ c_1 \ne 0$ ). Możliwe są trzy sytuacje:

Przypadek I. $c_m \ne 9$ . Jeśli $x_n$ ma postać (1), to $x_{n+1}$ (najmniejsza liczba palindromiczna większa od $x_n$ ) ma zapis dziesiętny

$ (3) \qquad \quad x_{n+1} = \overline{c_1 c_2\ldots c_{m-1} d_m d_m c_{m-1} \ldots c_2 c_1}, $

gdzie $d_m = c_m + 1$ .

Uzasadnienie: przykład (3) pokazuje, że istnieją liczby palindromiczne większe od $x_n$ i mające te same co ona cyfry początkowe $c_1,c_2,\ldots,c_{m-1}$ ; tak więc $x_{n+1}$ musi być jedną z tych liczb. Jej kolejną ( $m$ -tą) cyfrą nie może być $c_m$ , bo wówczas liczba ta byłaby identyczna z $x_n$ (wzór (1)). Biorąc $d_m= c_m +1$ jako kolejną cyfrę dostajemy jedyną liczbę palindromiczną o początkowych cyfrach $c_1,c_2,\ldots,c_{m-1},d_m$ (jej dalsze cyfry są już wyznaczone jednoznacznie; por. wzór (3)); a pisząc na $m$ -tym miejscu jakąkolwiek cyfrą większą od $d_m$ dostajemy liczby jeszcze większe; zatem wzór (3) istotnie przedstawia liczbę $x_{n+1}$ .

Analogiczne rozumowanie pokazuje, że jeśli $x_n$ ma postać (2), to $x_{n+1}$ ma zapis dziesiętny

$ (4) \qquad \quad x_{n+1} = \overline{c_1 c_2\ldots c_{m-1} d_m c_{m-1} \ldots c_2 c_1}, $

gdzie $d_m = c_m + 1$ .

Obliczamy różnicę $x_{n+1} -x_n$ stosując zwykły algorytm odejmowania (to znaczy pisząc cyfry liczby $x_n$ pod odpowiednimi cyframi liczby $x_{n+1}$ i wykonując ,,odejmowanie pisemne''). Wynik odejmowania:

$ (5) \qquad \begin{split} & x_{n+1}-x_n= \overline{11 \underbrace{0 \ldots 00}_{m-1}} = 11 \cdot 10^{m-1} \textrm{ dla liczb danych wzorami } (1), (3);\\ & x_{n+1}-x_n= \overline{1\underbrace{0 \ldots 00}_{m-1}} = 10^{m-1} \textrm{ dla liczb danych wzorami } (2), (4). \end{split} $

Przypadek II. Nie wszystkie cyfry liczby $x_n$ (danej wzorem (1) lub (2)) są dziewiątkami, ale cyfra $c_m$ jest dziewiątką: $c_m = 9$ . Niech $c_k$ będzie ostatnią cyfrą różną od $9$ w ciągu $c_1,c_2,\ldots,c_{m-1},c_m$ . Wtedy

$ x_n = \overline{c_1 c_2\ldots c_{k-1} c_k \underbrace{99 \ldots 99}_l c_k c_{k-1} \ldots c_2 c_1}, $

gdzie $l = 2m-2k$ lub $l = 2m-1-2k$ , w zależności od tego, czy liczba $x_n$ wyraża się wzorem (1), czy (2). W każdym z tych przypadków najmniejsza liczba palindromiczna większa od $x_n$ ma przedstawienie

$ x_{n+1} = \overline{c_1 c_2\ldots c_{k-1} d_k \underbrace{00 \ldots 00}_l d_k c_{k-1} \ldots c_2 c_1}, $

gdzie $d_k = c_k + 1$ . (Szczegółowe uzasadnienie - bardzo podobne do przeprowadzonego w przypadku I.) Algorytm odejmowania daje teraz wynik

$ (6) \qquad \quad x_{n+1}-x_n = \overline{11 \underbrace{0 \ldots 00}_{k-1}} = 11 \cdot 10^{k-1}. $

Przypadek III. Wszystkie cyfry liczby $x_n$ są dziewiątkami:

$ x_n = \overline{\underbrace{99\ldots 99}_p},\quad \textrm{gdzie } p = 2m \textrm{ lub } p = 2m - 1. $

Wtedy $x_{n+1} = \overline{1 \underbrace{00\ldots 0}_{p-1}1}$ , więc

$ (7) \qquad \quad x_{n+1}-x_n = 2. $

Przypadki I, II, III wyczerpują wszystkie możliwości. Otrzymane we wzorach (5), (6), (7) wyniki pokazują, że jedynymi dzielnikami pierwszymi różnic $x_{n+1}-x_n$ są liczby $2$ , $5$ oraz $11$ .

XLVII OM - I - Zadanie 3

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

W pewnej grupie $kn$ osób każda osoba zna więcej niz $(k - 1)n$ innych ( $k$ , $n$ są liczbami naturalnymi). Wykazać, że można z tej grupy wybrać $k + 1$ osób, z których każde dwie sie znają.

Uwaga: Jeżeli osoba $A$ zna osobę $B$ , to osoba $B$ zna osobę $A$ .

Rozwiązanie

Grupkę osób, z których każda zna każdą, będziemy nazywać {\it kliką}. Niech $m$ będzie największą liczbą naturalną, dla której w rozważanej grupie $kn$ osób istnieje $m$ -osobowa klika. Wykażemy, że $m>k$ . Stąd już wyniknie dowodzona teza, bowiem dowolny ( $k+1$ )-elementowy podzbiór takiej maksymalnej $m$ -osobowej kliki jest wówczas ( $k+1$ )-osobową kliką.

Niech więc $\{p_1,\ldots,p_m\}$ będzie $m$ -osobową kliką. Oznaczmy przez $N_i$ zbiór wszystkich osób nieznajomych dla $p_i \ (i = 1,\ldots,m)$ , a przez $n_i$ liczbę osób w zbiorze $N_i$ . Każda osoba $p_i$ zna więcej niż $kn-n$ innych, więc grono jej nieznajomych liczy mniej niż $n-1$ osób:

$ n_i < n -1 \textrm{ dla } i = 1,\ldots,m. $

Poza kliką $\{p_1,\ldots,p_m\}$ znajduje się $kn-m$ osób; oznaczmy ich zbiór przez $Q$ .

Weźmy dowolną osobę $q$ ze zbioru $Q$ . Gdyby była ona znajomą wszystkich osób $p_1,p_2, \ldots, p_m$ , moglibyśmy ją do nich dołączyć, a powstały zbiór $\{p_1,p_2, \ldots, p_m, q \}$ byłby ( $m+1$ )-osobową kliką. To się jednak kłóci z określeniem $m$ jako największej możliwej liczby osób w klice.

Stąd wniosek, że każda osoba ze zbioru $Q$ jest nieznajoma dla kogoś z kliki $\{p_1,\ldots, p_m \}$ , a więc należy do co najmniej jednego zbioru $N_i$ . Wobec tego liczba osób w zbiorze $Q$ (równa $kn-m$ ) nie przekracza łącznej liczby osób w zbiorach $N_1, \ldots , N_m$ . Zachodzi zatem nierówność

$ kn-m \leq n_1 + \ldots +n_m < (n-1)+ \ldots + (n-1) = m(n-1); $

po redukcji: $k<m$ . Jak stwierdziliśmy na wstępie, ta nierówność wystarcza do zakończenia dowodu.

XLVII OM - I - Zadanie 4

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

Prosta styczna do okręgu wpisanego w trójkat równoboczny $ABC$ przecina boki $AB$ i $AC$ odpowiednio w punktach $D$ i $E$ . Udowodnić, że
$\frac{|AD|}{|DB|} + \frac{|AE|}{|EC|} = 1$ .

Rozwiązanie

Uwaga: Jedną z prostych stycznych do okręgu wpisanego w trójkąt $ABC$ jest prosta $BC$ . Dla tej prostej punkt $D$ pokrywa się z $B$ , punkt $E$ pokrywa się z $C$ i rozważane ułamki tracą sens. Niewykluczenie w sformułowaniu zadania takiej sytuacji było oczywistym niedopatrzeniem $\ldots$ W przedstawionych poniżej rozwiązaniach będziemy zatem dodatkowo zakładać - tak, jak to robili Uczestnicy Olimpiady (życzliwie wytykając usterkę) - że prosta $DE$ nie jest prostą $BC$ .

Przyjmijmy oznaczenia:

$ |AB| = |BC| = |CA| = a,\quad |AD|=x,\quad |AE| = y,\quad |DE| = z $

(rysunek 1). Czworokąt $DBCE$ jest opisany na okręgu, więc

$ |DB| + |CE| = |BC| + |ED|, $

czyli $(a-x) + (a-y) =a + z$ , lub prościej: $x + y + z = a$ . Stosując do trójkąta $ADE$ twierdzenie Carnota (wzór kosinusów) dostajemy zależność:

$ z^2 = x^2 + y^2 -2xy \cos 60^\circ = x^2 + y^2- xy. $

W takim razie

$ \begin{split} \frac{|AD|}{|DB|} + \frac{|AE|}{|EC|} & = \frac{x}{a-x}+\frac{y}{a-y} = \frac{x}{y+z}+ \frac{y}{x + z}= \frac{x(x + z)+y(y + z)}{(x + z)(y + z)}= \\ & =\frac{x^2 + y^2 - xy + xy + xz + yz}{(x + z)(y + z)} = \frac{z^2 +xy + xz + yz}{(x+z)(y+z)}=1. \end{split} $

Uwaga: Tezę zadania można uzasadnić bez żadnych rachunków, korzystając z ogólniejszych znanych twierdzeń.

Jeśli $S$ jest punktem wewnętrznym (dowolnego) trójkąta $ABC$ , a proste $AS$ , $BS$ , $CS$ przecinają boki $BC$ , $CA$ , $AB$ odpowiednio w punktach $F$ , $E$ , $D$ , to

$ (2) \qquad \frac{|AD|}{|DB|} + \frac{|AE|}{|EC|} = \frac{|AS|}{|SF|}. $

Jest to twierdzenie Van Aubela}: dowód - zupełnie zresztą łatwy do samodzielnego przeprowadzenia —-- można znaleźć na przykład w książce: S. I. Zetel, {\it Geometria trójkąta, Warszawa 1964 (rozdział I. 15, str. 22). Stosując to twierdzenie do rozważanej sytuacji (równoboczny trójkąt $ABC$ ) wystarczy wykazać, że punkt $S$ , w którym przecinają się odcinki $BE$ i $CD$ , jest środkiem odcinka $AF$ o końcu $F$ leżącym na boku $BC$ : będzie to bowiem znaczyło, że ułamek po prawej stronie wzoru (2) ma wartość $1$ .

W tym celu powołamy się na twierdzenie Brianchona}, które mówi, że w każdym sześciokącie $P_1 P_2 P_3 P_4 P_5 P_6$ opisanym na okręgu przekątne $P_1 P_4$ , $P_2 P_5$ , $P_3 P_6$ przecinają się w jednym punkcie. Dowód znajduje się na przykład w książce: W. W. Prasołow, {\it Zadaczi po planimetrii, część I, Moskwa 1986 (zadanie 3.27, str. 65; rozwiązanie: str. 74): komentarz, a także inne odsyłacze do literatury, znajdzie Czytelnik w publikacji: XLV Olimpiada Matematyczna 1993/94. Sprawozdanie Komitetu Głównego. Warszawa 1995, Uwaga 3 po rozwiązaniu zadania 2 z zawodów trzeciego stopnia, str. 75.

(Twierdzenie Brianchona dopuszcza również sytuację, gdy niektóre kąty sześciokąta są półpełne i sześciokąt redukuje się do czworokąta.)

Niech $P$ i $Q$ będą, jak poprzednio, środkami boków $AB$ i $AC$ . Zdegenerowany do czworokąta sześciokąt $EDPBCQ$ ma wszystkie boki styczne do jednego okręgu (rysunek 3), więc na podstawie zacytowanego twierdzenia, wnosimy, że odcinki $EB$ , $DC$ i $PQ$ przecinają się w jednym punkcie. To znaczy, że punkt $S$ leży na prostej $PQ$ , łączącej środki boków $AB$ i $AC$ . Jest więc środkiem odcinka $AF$ .

XLVII OM - I - Zadanie 5

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

Na płaszczyźnie dany jest trójkat $ABC$ , w którym $|\measuredangle CAB| = \alpha > 90^{\circ}$ , oraz odcinek $PQ$ , którego środkiem jest punkt $A$ . Dowieść, że

$ \left( |BP| + |CQ| \right)\cdot \tan \frac{\alpha}{2} \geq |BC|. $

Rozwiązanie

Oznaczmy przez $M$ środek boku $BC$ trójkąta $ABC$ , a przez $O$ - środek okręgu $\omega$ opisanego na tym trójkącie. Kąt $CAB$ jest z założenia rozwarty. Stąd wynika, że punkty $A$ i $O$ leżą po przeciwnych stronach prostej $BC$ ; w szczególności punkt $O$ nie pokrywa się z $M$ .

Niech $ON$ będzie promieniem okręgu $\omega$ przechodzącym przez punkt $M$ (rysunek 4). Okrąg $\omega'$ o środku $M$ i promieniu $MN$ jest styczny do okręgu $\omega$ w punkcie $N$ , a punkt $A$ leży na zewnątrz okręgu $\omega'$ (lub na nim - gdy pokrywa się z $N$ ). W takim razie $|MA| \geq |MN|$ .

Punkty $B$ i $C$ leżą symetrycznie względem prostej $NO$ , która wobec tego połowi kąt $BNC$ . A ponieważ $| \measuredangle BNC | = |\measuredangle BAC| = \alpha$ (kąty wpisane oparte na długim łuku $BC$ ), dostajemy równość

$ | \measuredangle MNC | = \frac{1}{2}|\measuredangle BNC| = \frac{1}{2} \alpha. $

Na przedłużeniu boku $CA$ odkładamy równy mu długością odcinek $AD$ . Powstaje trójkąt $BCD$ ; punkty $A$ i $M$ są środkami jego boków $CD$ i $CB$ . Trójkąty $BCD$ i $MCA$ są więc podobne. Otrzymujemy zależność

$ (1) \qquad \quad \tan \frac{\alpha}{2} = \tan |\measuredangle MNC| = \frac{|MC|}{|MN|} \geq \frac{|MC|}{|MA|} = \frac{|BC|}{|BD|}. $

Punkt $A$ jest wspólnym środkiem odcinków $PQ$ i $CD$ . Zatem czworokąt $CPDQ$ jest równoległobokiem (który może degenerować się do odcinka; zauważmy, że rozumowanie jest w tym fragmencie zupełnie niezależne od położenia punktów $P$ i $Q$ względem rozważanych do tej pory odcinków i okręgów). Tak więc $|CQ|=|PD|$ , skąd

$ (2) \qquad |BP| + |CQ| = |BP| + |PD| \geq |BD|. $

Mnożymy stronami nierówności (1) i (2) i otrzymujemy nierówność

$ (|BP| + |CQ|) \cdot \tan \frac{\alpha}{2} \geq |BC|, $

która była dana do udowodnienia.

XLVII OM - I - Zadanie 6

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

Dane są dwa ciągi liczb całkowitych dodatnich: ciąg arytmetyczny o różnicy $r > 0$ i ciąg geometryczny o ilorazie $q > 1$ ; liczby naturalne $r$ , $q$ są względnie pierwsze. Udowodnić, że jeśli te ciągi mają jeden wspólny wyraz, to mają nieskończenie wiele wspólnych wyrazów.

Rozwiązanie

Oznaczmy przez $r_i$ resztę z dzielenia liczby $q^i$ przez $r\ (i = 1,2,3,\ldots)$ . W nieskończonym ciągu $(r_1,r_2,r_3,\ldots)$ , którego wyrazy przybierają tylko skończenie wiele wartości, muszą wystąpić powtórzenia. Istnieją zatem różne numery $i$ , $j$ takie, że $r_i = r_j$ . Różnica $q^i-q^j$ jest wówczas podzielna przez $r$ . Przyjmując, że $i >j$ , możemy tę różnicę zapisać tak:

$ q^i-q^j=q^j(q^{i-j} -1). $

Liczba po prawej stronie ma się dzielić przez $r$ (bo lewa strona dzieli się przez $r$ ). Czynnik $q^j$ jest względnie pierwszy z $r$ (warunek zadania). Zatem czynnik $(q^{i-j}-1)$ musi dzielić się przez $r$ . Istnieje więc liczba całkowita $l$ taka, że $q^{i-j}-1=lr$ . Oznaczając różnicę $i-j$ przez $k$ mamy równość $q^k=1+lr$ .

Niech $(a_1,a_2,\ldots)$ będzie rozważanym ciągiem arytmetycznym, a $(b_1,b_2, \ldots)$ rozważanym ciągiem geometrycznym. Zakładamy, że mają one wspólny wyraz $a_m = b_n$ . Wówczas

$ b_{n + k} =b_nq^k =b_n(1+lr) =a_m(1+lr) =a_m+r \cdot l a_m =a_{m+s}, $

gdzie $s=la_m$ . Znaleźliśmy w ten sposób nową parę wspólnych wyrazów rozpatrywanych ciągów (o numerach większych od $m$ i $n$ ). Powtarzając to rozuwanie znajdujemy nieskończenie wiele wspólnych wyrazów.

XLVII OM - I - Zadanie 7

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

Liczby nieujemne $a$ , $b$ , $c$ , $p$ , $q$ , $r$ spełniają warunki:

$ a + b + c = p + q + r = 1; \quad p, q, r \leq \frac{1}{2}. $

Udowodnić, że $8abc \leq pa + qb + rc$ oraz rozstrzygnąć, kiedy zachodzi równość.

Rozwiązanie

Bez straty ogólności można przyjąć, że $a \geq b \geq c$ . Przeprowadzimy ciąg szacowań opartych na następujących nierównościach (które są konsekwencjami przyjętego przed chwilą założenia oraz warunków zadania):

$ \begin{split} & (1) \qquad \quad pa \geq pb; \quad (1-2r)(b-c)\geq 0;\\ & (2) \qquad \quad a(b+c)^2 \geq a \cdot 4bc; \quad (1-a)(2a-1)^2\geq 0. \end{split} $

Korzystając z zależności (1) dostajemy oszacowanie:

$ \begin{split} pa+qb+rc & \geq (p+q)b+rc = (1-r)b+rc =\\ & = \frac{1}{2} (1-2r)(b-c) + \frac{1}{2}(b+c) \geq \frac{1}{2} (b+c) = \frac{1}{2}(1-a); \end{split} $

korzystając zaś ze związków (2) mamy:

$ \begin{split} 8abc & = 2a \cdot 4bc \leq 2a(b+c)^2 = 2a(1-a)^2 =\\ & = \frac{1}{2} (1-a)[1-(2a-1)^2] \leq \frac{1}{2}(1-a). \end{split} $

Widzimy więc, że liczba $\frac{1}{2}(1-a)$ jest nie mniejsza niż lewa strona danej do udowodnienia nierówności i nie większa niż prawa jej strona. Stąd, rzecz jasna, wynika teza.

Aby udowodniona nierówność stała się równością, musi zachodzić równość w każdym kroku powyższych szacowań; to znaczy: obie nierówności (1) oraz obie nierówności (2) muszą stać się równościami. Przypuśćmy więc, że tak jest.

Znak równości w drugim ze związków (2) oznacza, że $a=1$ lub $a=\frac{1}{2}$ ; zatem $a \ne 0$ i pierwszy ze związków (2) implikuje równość $(b + c)^2 = 4bc$ , która zachodzi tylko dla $b = c$ . Wobec założenia, że suma liczb $a,b,c$ jest równa $1$ wnosimy, że

$ (3) \qquad \quad (a, b, c) = (1,0,0) \ \textrm{ lub }\ (a,b,c) = \left(\frac{1}{2}, \frac{1}{4}, \frac{1}{4}\right). $

W każdym przypadku $a >b$ ; przejście pierwszej z nierówności (1) w równość jest więc możliwe tylko dla $p = 0$ . Wówczas $q + r= 1 -p= 1$ ; a skoro $q,r \in \langle 0;\ \frac{1}{2} \rangle$ , zatem $q = r = \frac{1}{2}$ , czyli

$ (4) \qquad \quad (p,q,r)=\left(0,\frac{1}{2},\frac{1}{2}\right). $

Wykazaliśmy w ten sposób, że jeśli dana w zadaniu nierówność staje się równością, to są spełnione warunki (3) i (4). Na odwrót, jeśli te warunki są spełnione, to zachodzi równość w każdym ze związków (1) i (2), i wobec tego wszystkie przeprowadzone szacowania są de facto ciągami równości. Rozważana nierówność przechodzi w równość.

[Zamiast powoływać się na owe szacowania można po prostu obliczyć wartość wyrażeń $8abc$ oraz $pa + qb + rc$ dla trójek liczb (3) i (4).]

Odrzucając założenie, że $a \geq b \geq c$ , dostajemy odpowiedź: równość zachodzi wtedy i tylko wtedy, gdy szóstka liczb $(a,b,c,p,q,r)$ ma jedną z następujących postaci:

$ \begin{array}{ccc} (1,0,0,0,\frac{1}{2},\frac{1}{2}), & (0,1,0,\frac{1}{2},0,\frac{1}{2}), & (0,0,1,\frac{1}{2},\frac{1}{2},0),\\ (\frac{1}{2}, \frac{1}{4}, \frac{1}{4}, 0, \frac{1}{2}, \frac{1}{2}), & (\frac{1}{4}, \frac{1}{2}, \frac{1}{4}, \frac{1}{2}, 0, \frac{1}{2}), & (\frac{1}{4}, \frac{1}{4}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}, 0). \end{array} $

Uwaga: Dla każdej trójki liczb $a,b,c \geq 0$ i dla każdej trójki wykładników $p,q,r \geq 0$ o sumie $p + q + r = 1$ zachodzi nierówność (5); wyrażenia figurujące w niej po lewej i prawej stronie noszą odpowiednio nazwy: średnia arytmetyczna ważona} i {\it średnia geometryczna ważona liczb $a, b, c$ z wagami $p, q, r$ .

Szybki dowód dostaje się z nierówności Jensena dla funkcji wypukłej $f(x)= e^x$ :

$ e^{pu+qv+rw} \leq pe^u+qe^v + re^w \quad \textrm{dla dowolnych liczb } u,v,w \in \mathbb{R}. $

(Obszerniejszy komentarz na temat funkcji wypukłych i nierówności Jensena można znaleźć na przykład w publikacji: XXXVII Olimpiada Matematyczna, Sprawozdanie Komitetu Głównego, Warszawa 1989, str. 41-42.)

Gdy liczby $a, b, c$ są dodatnie, wystarczy przyjąć $u = \ln a$ , $v = \ln b$ , $w = \ln c$ , aby otrzymać nierówność (5).

Gdy któraś (jedna lub więcej) z nieujemnych liczb $a, b, c$ jest zerem, bierzemy dowolne ciągi liczb dodatnich $(a_n), (b_n), (c_n)$ , zbieżne odpowiednio do $a$ , $b$ , $c$ ; wykładniki $p, q, r$ pozostają przy tym ustalone. Dla każdej trójki $a_n,b_n,c_n$ , zachodzi nierówność analogiczna do (5), więc w granicy otrzymujemy nierówność (5) dla rozważanej trójki $a, b, c$ .

XLVII OM - I - Zadanie 8

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

Ze środka kwadratu wybiega promień świetlny, który odbija się od boków kwadratu zgodnie z zasadą kąt padania jest równy kątowi odbicia. Po pewnym czasie promień wraca do środka kwadratu. Promień nigdy nie trafił w wierzchołek, ani nie przeszedł wcześniej przez środek. Dowieść, że liczba odbić od boków kwadratu jest nieparzysta.

Rozwiązanie

Na płaszczyźnie z prostokątnym układem współrzędnych $Oxy$ prowadzimy wszystkie proste o równaniach $x = c$ ( $c$ całkowite) oraz $y = c$ ( $c$ całkowite); w ten sposób cała płaszczyzna zostaje pokryta nieskończoną siatką kwadratów jednostkowych. W każdej parze kwadratów o wspólnym boku identyfikujemy punkty symetryczne względem tego boku (rysunek 5). Tak więc, na przykład, punkt $X = (u,v)$ w kwadracie $OABC$ o wierzchołkach $O = (0,0)$ , $A = (1,0)$ , $B = (1,1)$ , $C = (0,1)$ jest utożsamiony z punktami $(2-u,v)$ oraz $(u,2-v)$ w kwadratach jednostkowych przyległych do $OABC$ od prawej strony i od góry, a także z dwoma punktami w dwóch kwadratach jednostkowych przyległych do $OABC$ od lewej strony i od dołu.

Poprzez symetrie względem dalszych prostych siatki, punkt ten ma swoje repliki we wszystkich kwadratach siatki - po jednej w każdym kwadracie jednostkowym. Środek kwadratu $OABC$ , czyli punkt $P=(\frac{1}{2},\frac{1}{2})$ , jak każdy inny, ma nieskończenie wiele kopii; są nimi środki wszystkich kwadratów siatki, czyli punkty postaci $(\frac{1}{2}+ m, \frac{1}{2} +n)$ , gdzie $m, n$ mogą być dowolnymi liczbami całkowitymi.

Możemy zakładać, że $OABC$ jest tym kwadratem, którego dotyczy zadanie, oraz że promień świetlny został wysłany z punktu $P$ ,,w prawo w górę'' (wzdłuż odcinka prostej o dodatnim współczynniku kierunkowym). Pierwszy raz odbija się więc od boku $AB$ lub $BC$ , w pewnym punkcie $Q$ . Następny raz trafia w brzeg kwadratu $OABC$ w pewnym punkcie $R$ .

Fragment $QR$ jego trajektorii ma swoją kopię $QR'$ w kwadracie przyległym do $OABC$ (przy boku $AB$ lub $BC$ ), która jest prostoliniowym przedłużeniem odcinka $PQ$ ; prostoliniowość wynika z zasady odbicia. Istotnie: w sytuacji jak na rysunku, punkt $R'$ jest symetryczny do $R$ względem prostej $AB$ , wobec czego $|\measuredangle BQR|= |\measuredangle BQR'|$ ; a skoro także $|\measuredangle BQR|= |\measuredangle PQA|$ (zasada odbicia), zatem punkt $R'$ leży na półprostej $PQ^\to$ .

Analogicznie, następny fragment drogi promienia ma w kolejnym kwadracie siatki swój obraz, będący przedłużeniem odcinka $QR'$ . I tak dalej: każdy kolejny fragment drogi można identyfikować z coraz to dalszym odcinkiem półprostej $PQ^\to$ . W ten sposób cała trajektoria promienia, od startu z punktu $P$ do powrotu do punktu $P$ , odpowiada pewnej prostoliniowej drodze na płaszczyźnie, o początku w punkcie $P$ i końcu w pewnym punkcie $Z$ , który jest jedną z replik środka kwadratu $OABC$ . Tak więc $Z$ jest punktem postaci $(\frac{1}{2} +m, \frac{1}{2} + n)$ dla pewnej pary liczb naturalnych $m, n$ .

Na odcinku $PZ$ leży w szczególności punkt $M=(\frac{1}{2}(1+m),\frac{1}{2}(1 + n))$ , środek tego odcinka. Jeśli obie liczby $m, n$ są parzyste, to $M$ jest środkiem pewnego kwadratu siatki, czyli obrazem środka $P$ kwadratu $OABC$ . Jeśli obie liczby $m, n$ są nieparzyste, to $M$ jest punktem o współrzędnych całkowitych, czyli obrazem wierzchołka kwadratu $OABC$ . Każda z tych sytuacji jest wykluczona przez warunki zadania. Zatem liczby $m$ i $n$ są różnej parzystości, a więc ich suma jest liczbą nieparzystą.

Zauważmy jednak, że odcinek $PZ$ przecina $m$ prostych pionowych oraz $n$ prostych poziomych, będących liniami siatki. Każdy taki punkt przecięcia odpowiada punktowi odbicia promienia od brzegu kwadratu $OABC$ . Jest to odpowiedniość wzajemnie jednoznaczna, bowiem odcinek $PZ$ nie przechodzi przez żaden węzeł siatki (,,promień nie trafił w wierzchołek kwadratu''). Stąd wniosek, że liczba odbić jest równa sumie $m + n$ ; suma ta zaś - jak wykazaliśmy - jest liczbą nieparzystą. Teza jest więc udowodniona.

XLVII OM - I - Zadanie 9

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

Wielomian o współczynnikach całkowitych daje przy dzieleniu przez wielomian $x^2 - 12x + 11$ resztę $990x - 889$ . Wykazaż, że wielomian te nie ma pierwiastków całkowitych.

Rozwiązanie

Zgodnie z założeniem, rozważany wielomian ma postać

$ (1) \qquad \quad P(x) = (x-1)(x-11)Q(x) + (990x-889), $

gdzie $Q(x)$ jest pewnym wielomianem.

Dalsze rozumowanie opiera się na następującym spostrzeżeniu: dla każdej pary różnych liczb całkowitych $k, m$

$ (2) \qquad \quad \ \textrm{liczba}\ P(k) - P(m) \ \textrm{dzieli się przez} \ k - m. $

[Uzasadnienie: jeżeli $P(x) = a_0 + a_1x + \ldots +a_nx^n$ ( $a_i$ całkowite), to różnica $P(k) - P(m)$ jest sumą składników $a_i(k^i-m^i)$ dla $i = 1,\ldots,n$ , a każdy z tych składników dzieli się przez $k - m$ .]

Przypuśćmy, że wielomian $P(x)$ ma pierwiastek całkowity $x_0$ . Przyjmując w (2) $k = 1, m = x_0$ , a następnie $k = 11, m = x_0$ , stwierdzamy, że

$ (3) \qquad \quad P(1) \ \textrm{dzieli się przez}\ 1-x_0, \quad P(11) \ \textrm{dzieli się przez}\ 11-x_0. $

Ale z przedstawienia (1) widać, że $P(1) = 101$ , a $P(11) = 10001$ . Różnica $1-x_0$ , jako dzielnik liczby pierwszej $P(1) = 101$ , musi być jedną z liczb: $-101$ , $-1$ , $1$ , $101$ . Dla tych wartości $x_0$ różnica $11 -x_0$ przyjmuje odpowiednio wartości: $-91$ , $9$ , $11$ , $111$ . Wszelako żadna z nich nie jest dzielnikiem liczby $P(11) = 10001 ( = 73 \cdot 137)$ .

Jednoczesne spełnienie warunków (3) nie jest więc możliwe. Sprzeczność dowodzi, że wielomian $P(x)$ nie ma pierwiastka całkowitego.

XLVII OM - I - Zadanie 10

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

Wykazać, że równanie $x^x = y^3 + z^3$ ma nieskończenie wiele rozwiązań w liczbach całkowitych dodatnich $x, y, z$ .

Rozwiązanie

Przedstawimy obszerną klasę rozwiązań tego równania.

Niech $m, n$ będą dodatnimi liczbami całkowitymi spełniającymi warunek:

$ (1) \qquad m + n -1 \ \textrm{jest liczbą podzielną przez}\ 3. $

Dla każdej liczby całkowitej $c$ liczba $c^3-c = c(c-1)(c+1)$ dzieli się przez $3$ . Z tożsamości $m^3 + n^3 -1 = (m^3 - m) + (n^3 - n) + (m + n -1)$ widać zatem, że warunek (1) pociąga za sobą warunek:

$ m^3 +n^3 -1\ \textrm{jest liczbą podzielną przez}\ 3. $

Weźmy $x = m^3+n^3$ . Różnica $x-1$ dzieli się przez $3$ , więc liczba $x^{x-1}$ jest sześcianem liczby całkowitej. Wobec tego

$ x^x = x \cdot x^{x-1} = (m^3 + n^3)x^{x-1} = m^3x^{x-1} + n^3x^{x-1} $

jest przedstawieniem liczby $x^x$ w postaci sumy dwóch sześcianów, i mamy to, o co chodziło.

Wniosek: wystarczy przyjąć

$ (2) \qquad \ x = m^3 + n^3, \quad y = mx^{(x-1)/3}, \quad z = nx^{(x-1)/3}; $

równanie $x^x = y^3 + z^3$ będzie spełnione. Wobec dowolności wyboru liczb $m$ i $n$ spełniających warunek (1) dostajemy nieskończoną rodzinę rozwiązań tego równania.

Uwaga: Specyfikując parametry $m$ i $n$ według jakiejś bardziej konkretnej reguły można otrzymać różne nieskończone zbiory rozwiązań badanego równania (będą one podzbiorami rodziny opisanej powyżej).

Biorąc na przykład $m=1$ , $n = 3k$ ( $k \geq 1$ całkowite) dostajemy zgodnie ze wzorami (2) następujący ciąg rozwiązań:

$ x = 27k^3+1,\quad y = (27k^3 + 1)^{9k^3},\quad z = 3k(27k^3 + 1)^{9k^3} \quad (k = 1,2,3,\ldots). $

Można też przyjąć we wzorach (2) $m = n = 3r + 2$ ( $r \geq 0$ całkowite); daje to ciąg rozwiązań

$ x=2(3r + 2)^3, \quad y = z=(3r + 2)[2(3r + 2)^3]^v, $

gdzie $v = \frac{1}{3}[2(3r + 2)^3-1] = 18r^3+ 36r^2+ 24r+ 5\quad (r = 0,1,2,\ldots)$ .

Szczególny przypadek tej ostatniej konstrukcji otrzymamy przyjmując $m = n = 2^{2j + 1}$ ( $j \geq 0$ całkowite), bowiem $2^{2j+1} = 2 \cdot 4^j \equiv 2 \pmod 3$ ; wzory (2) dają teraz:

$ \begin{split} x = 2^{6j+4}, \quad y = z = & 2^{2j+1} (2^{6j+4})^{(2^{6j+4}-1)/3}=2^w,\\ \textrm{gdzie}\ w = & 2j + 1 + \frac{1}{3}(6j + 4) (2^{6j+4} - 1) =\\ & = \frac{1}{3}[(6j+4)2^{6j+4}-1] \quad (j=0,1,2,\ldots). \end{split} $

Wszystkie te serie zostały znalezione przez rozwiązujących. Oczywiście są możliwe przeróżne inne specyfikacje parametrów $m$ i $n$ spełniających warunek (1).

Jako ciekawostkę podamy jeden przykład rozwiązania, które nie ma postaci (1), (2); także i ten przykład pochodzi z prac uczniowskich. Niech

$ s = 2^{(6i+4)/3}, \quad x = 2s^3 = 2^{6i+5}, \quad y = z = sx^{(x-1)/3} \quad (i = 0,1,2,\ldots); $

przypomina to wzory (2); rolę liczb $m, n$ przejęła liczba $s$ , która wszelako nie jest całkowita! Proponujemy Czytelnikom sprawdzenie, że liczba $sx^{(x-1)/3}$ już jest całkowita i że rozważane równanie jest spełnione.

Większość podanych przykładowo serii rozwiązań stanowią trójki $(x,y,z)$ , w których $y = z$ . Można bez znaczniejszych trudności udowodnić (to kolejna sugestia zadania dla Czytelnika), że ogólne rozwiązanie równania $x^x = 2y^3$ w liczbach całkowitych dodatnich ma postać

$ x = 2^{6\alpha + \gamma} (6 \beta + \delta)^3, \quad y=(\frac{1}{2} x^x)^{1/3}, $

gdzie $\alpha, \beta$ są dowolnymi nieujemnymi liczbami całkowitymi, a $(\gamma,\delta)$ jest jedną z następujących czterech par: $(1,5), (2,5), (4,1), (5,1)$ .

XLVII OM - I - Zadanie 11

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

W konkursie skoków narciarskich uczestniczy 65 zawodników. Startują oni kolejno, według ustalonego wcześniej porządku. Każdy wykonuje jeden skok. Przyjmujemy, że uzyskane wyniki są różne od zera oraz że każda kolejność końcowa jest jednakowo prawdopodobna. W każdym momencie konkursu liderem nazywamy zawodnika, który do tego momentu uzyskał najlepszy wynik. Oznaczmy przez $p$ prawdopodobieństwo tego, że w czasie całego konkursu dokładnie jeden raz nastąpiła zmiana lidera. Wykazać, że $p > \frac{1}{16}$ .

Rozwiązanie

Będziemy rozpatrywać analogiczne zagadnienie dla dowolnej liczby uczestniczących zawodników. Oznaczmy tę liczbę przez $n$ . Zadanie polega na wyznaczeniu prawdopodobieństwa zdarzenia:

$ A : \textrm{w czasie konkursu ma miejsce dokładnie jedna zmiana lidera.} $

Dla każdej liczby $k \in \{0,1, \ldots, n-1 \}$ określamy następujące zdarzenie:

$ B_k \textrm{: najlepszy wynik został uzyskany w } (k-1) \textrm{-ym skoku.} $

Zgodnie z założeniem każda kolejność końcowa jest jednakowo prawdopodobna; stąd wynika, że zdarzenia $B_0, B_1, \ldots, B_{n-1}$ są jednakowo prawdopodobne: $P(B_k) = 1/n$ dla $k = 0,1,\ldots,n-1$ .

Przypuśćmy, że zaszło zdarzenie $B_0$ - to znaczy, że pierwszy skoczek zostaje liderem i już do końca konkursu nie oddaje prowadzenia; zmiana lidera nie następuje. Wyklucza to zajścia zdarzenia $A$ ; prawdopodobieństwo zdarzenia $A$ przy warunku $B_0$ jest więc zerowe: $P(A|B_0) = 0$ .

Ustalmy teraz wartość $k \in \{1, \ldots, n-1\}$ i przypuśćmy, że zaszło zdarzenie $B_k$ . Wynik $(k+1)$ -go skoku, jako najlepszy w całym konkursie, z konieczności przynosi zmianę lidera, i to już ostatnią. Warunek konieczny i dostateczny, aby była to zmiana jedyna, można sformułować następująco:

$ W_k: \begin{array}{l} \textrm{w serii początkowych } k \textrm{ skoków (od pierwszego do } k \textrm{-tego)}\\ \textrm{najlepszy wynik pada już w pierwszym skoku.} \end{array} $

Niezależnie od tego, jakie wyniki zostały uzyskane w tej serii $k$ skoków, każde ich uporządkowanie (w obrębie tej serii) jest jednakowo prawdopodobne. Najlepszy może być w niej wynik pierwszego, drugiego, $\ldots$ , $k$ -tego skoku, z jednakowym prawdopodobieństwem, równym $1/k$ .

Takie jest, w szczególności, prawdopodobieństwo spełnienia warunku $W_k$ , który - jak pamiętamy - jest równoważny zajściu zdarzenia $A$ pod warunkiem zajścia zdarzenia $B_k$ . Liczba $1/k$ jest więc prawdopodobieństwem warunkowym: $P(A|B_k) = 1/k$ dla $k = 1, \ldots, n-1$ .

Na podstawie wzoru na prawdopodobieństwo całkowite obliczamy:

$ (1) \qquad \quad P(A)= \sum_{k=0}^{n-1} P(A|B_k) \cdot P(B_k) = 0 + \sum_{k=1}^{n-1} \frac{1}{k} \cdot \frac{1}{n} = \frac{1}{n} \sum_{k=1}^{n-1} \frac{1}{k}. $

Dla $n = 65$ dostajemy prawdopodobieństwo, o które chodzi w zadaniu:

$ p = \frac{1}{65} \left(1+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{64}\right). $

Sumę $1+\frac{1}{2}+\frac{1}{3}+\ldots+\frac{1}{64}$ szacujemy z dołu grupując jej wyrazy, jak następuje:

$ 1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4} + \left(\frac{1}{5}+\ldots+\frac{1}{8}\right)+ \left(\frac{1}{9}+\ldots+\frac{1}{16}\right) + \left(\frac{1}{17}+\ldots+\frac{1}{32}\right)+ \left(\frac{1}{33}+\ldots+\frac{1}{64}\right). $

W pierwszym nawiasie mamy cztery składniki, w drugim osiem, w trzecim szesnaście, w czwartym - trzydzieści dwa. W każdym nawiasie najmniejszy jest składnik ostatni, więc suma liczb w pierwszym, drugim, trzecim, czwartym nawiasie szacuje się z dołu odpowiednio przez liczby: $4 \cdot \frac{1}{8}, 8 \cdot \frac{1}{16}, 16 \cdot \frac{1}{32}, 32 \cdot \frac{1}{64}$ . Każda z nich równa się $\frac{1}{2}$ ; łączna suma liczb w tych czterech nawiasach przekracza $2$ . Stąd, ostatecznie,

$ p > \frac{1}{65}\left(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+2\right) = \frac{1}{65} \cdot \frac{49}{12} = \frac{196}{195} \cdot \frac{1}{16} > \frac{1}{16}. $

(Sumę $1+\frac{1}{2}+ \ldots +\frac{1}{64}$ można oczywiście obliczyć z dowolną dokładnością; wartość prawdopodobieństwa $p$ wynosi $0,07298\ldots$ z dokładnością do pięciu cyfr znaczących: jest to troszkę więcej niż $\frac{1}{14}$ .)

Uwaga 3. W numerze $5/1996$ czasopisma Matematyka Maciej Radziejewski (członek Komitetu Okręgowego Olimpiady Matematycznej w Poznaniu) w interesującym artykule O rozwiązaniach zadań olimpijskich dzieli się wrażeniami ze sprawdzania zadań 2, 4, 10 i 11 z zawodów pierwszego stopnia XLVII O. M.; niektóre myśli z tych omówień zostały wykorzystane w niniejszym opracowaniu. We wspomnianym artykule są naszkicowane także i inne sposoby podejścia, są skomentowane sytuacje pojawiające się w rozwiązaniach (jest na przykład wspomniany dualizm, o którym mowa wyżej, w Uwadze 2) oraz są analizowane różne wątki z prac uczniowskich.

XLVII OM - I - Zadanie 12

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

Rozstrzygnąć, czy istnieją takie dwa przystające sześciany o wspólnym środku, że każda ściana pierwszego sześcianu ma punkt wspólny z każdą ścianą drugiego sześcianu.

Rozwiązanie

Udowodnimy, że nie istnieją dwa sześciany $\mathcal{C}$ i $\mathcal{C'}$ , dla których byłby spełniony warunek:

$\quad (*) \quad$ każda ściana sześcianu $\mathcal{C}$ ma punkty wspólne z każdą ścianą $\mathcal{C'}$ .

Podane w zadaniu dodatkowe założenia (przystawanie, wspólny środek) nic są do niczego potrzebne.

Niech więc będą dane dwa sześciany $\mathcal{C}$ i $\mathcal{C'}$ . Ponieważ w zdaniu (*) role symboli $\mathcal{C}$ i $\mathcal{C'}$ są symetryczne, można bez szkody dla ogólności przyjąć, że długość krawędzi sześcianu $\mathcal{C'}$ jest nie mniejsza niż długość krawędzi sześcianu $\mathcal{C}$ . Pokażemy trzema sposobami, że warunek (*) nie może być spełniony.

Niech $\mathcal{C}$ będzie sześcianem o krawędzi jednostkowej, a $\mathcal{C'}$ - sześcianem o krawędzi długości $\geq 1$ . Wybierzmy dwie przeciwległe ściany $\mathcal{S}$ i $\mathcal{T}$ sześcianu $\mathcal{C'}$ . Płaszczyzna ściany $\mathcal{S}$ dzieli przestrzeń na dwie półprzestrzenie; oznaczmy przez $\mathcal{H}$ tę półprzestrzeń, która nie zawiera kwadratu $\mathcal{T}$ . Przyjmijmy, że $\mathcal{H}$ jest półprzestrzenią domkniętą; to znaczy, że płaszczyzna ściany $\mathcal{S}$ jest podzbiorem zbioru $\mathcal{H}$ .

Przypuśćmy, że w zbiorze $\mathcal{H}$ znajdują się dwa wierzchołki $A$ , $B$ sześcianu $\mathcal{C}$ , nie będące końcami jednej krawędzi. Oznaczmy środek odcinka $AB$ przez $M$ ; jest to także punkt zbioru $\mathcal{H}$ .

Jeżeli $AB$ jest jedną z czterech przekątnych sześcianu $\mathcal{C}$ przecinających jego wnętrze, to $M$ jest jego środkiem. Każdy punkt sześcianu $\mathcal{C}$ jest odległy od $M$ co najwyżej o $\frac{1}{2} \sqrt{3}$ . Jest to liczba mniejsza niż $1$ . Ponieważ odległość kwadratu $\mathcal{T}$ od półprzestrzeni $\mathcal{H}$ wynosi co najmniej $1$ , zatem kwadrat $\mathcal{T}$ nie zawiera żadnego punktu sześcianu $\mathcal{C}$ .

Jeżeli $AB$ jest przekątną jednej ze ścian sześcianu $\mathcal{C}$ , to $M$ jest środkiem tej ściany. Wszystkie jej punkty są odległe od $M$ co najwyżej o $\frac{1}{2} \sqrt{2}$ , wobec czego cała ta ściana jest rozłączna z kwadratem $\mathcal{T}$ .

Pozostaje do rozpatrzenia sytuacja, gdy w zbiorze $\mathcal{H}$ albo nie ma żadnego wierzchołka sześcianu $\mathcal{C}$ , albo jest dokładnie jeden wierzchołek, albo są dokładnie dwa wierzchołki, połączone krawędzią. Pozostałe wierzchołki (w liczbie $8$ , $7$ lub $6$ ) leżą poza zbiorem $\mathcal{H}$ : w każdym przypadku można wśród nich znaleźć cztery punkty będące wierzchołkami pewnej ściany sześcianu $\mathcal{C}$ . Ściana ta nie ma punktów wspólnych ze zbiorem $\mathcal{H}$ , a więc nie ma punktów wspólnych ze ścianą $\mathcal{S}$ sześcianu $\mathcal{C}$ .

Wykazaliśmy, że sześcian $\mathcal{C}$ ma ścianę rozłączną albo z $\mathcal{S}$ , albo z $\mathcal{T}$ . Warunek (*) nie może być spełniony.

Uwaga 2. Zastępując w treści zadania słowo sześciany wszędzie przez równoległościany dostajemy problem znacznie ogólniejszy. Autor niniejszego opracowania nie zna odpowiedzi na pytanie zawarte; w tak przeformułowanym zadaniu.

Uwaga 3. Kostką czterowymiarową nazywamy podzbiór czterowymiarowej przestrzeni $\mathbb{R}^4$ podobny do zbioru

$ \mathcal{C} = \{ (x_1,x_2,x_3,x_4) \in \mathbb{R}^4: |x_i| \leq 1 \quad \textrm{dla}\ i = 1,2,3,4 \} $

(podobny w sensie geometrycznym). Podzbiór zbioru $\mathcal{C}$ złożony z punktów o pierwszej współrzędnej równej $1$ jest izometryczny z trójwymiarowym sześcianem; to samo można powiedzieć o pozostałych siedmiu podzbiorach zbioru $\mathcal{C}$ otrzymanych przez ustalenie którejkolwiek współrzędnej i nadanie jej wartości $1$ lub wartości $-1$ . Te podzbiory nazywamy ścianami kostki $\mathcal{C}$ . Jeśli $\mathcal{C'}$ jest inną kostką, otrzymaną z kostki $\mathcal{C}$ przez podobieństwo, to obrazy ścian kostki $\mathcal{C}$ w tym podobieństwie tworzą ściany kostki $\mathcal{C'}$ .

Dla kostek czterowymiarowych można postawić problem analogiczny do rozpatrywanego w zadaniu: czy istnieją w przestrzeni $\mathbb{R}^4$ takie dwie kostki, że każda ściana jednej z nich ma punkty wspólne z każdą ścianą drugiej? Odpowiedź może się wydać zaskakująca: w $\mathbb{R}^4$ takie pary istnieją. Podamy przykład - bez żadnych uzasadnień; sprawdzenie prawdziwości wszystkich stwierdzeń w następnym akapicie może być ambitnym zadaniem dla Czytelnika.

Jedną z kostek będzie zbiór $\mathcal{C}$ zdefiniowany powyżej. Jej wierzchołkami są punkty postaci $(\pm 1, \pm 1, \pm 1, \pm 1)$ (wybór znaków jest dowolny; kostka taka ma więc szesnaście wierzchołków). Weźmy teraz pod uwagę inną szesnastkę punktów: osiem punktów postaci $(\pm 1, \pm 1, \pm 1, \pm 1)$ , w których iloczyn współrzędnych równa się $1$ , oraz osiem punktów mających po trzy współrzędne równe $0$ , a pozostałą równą $2$ lub $-2$ . Ta szesnastka punktów także jest zbiorem wierzchołków czterowymiarowej kostki $\mathcal{C'}$ , i to przystającej do $\mathcal{C}$ . Przy tym każda trójwymiarowa ściana jednej kostki ma z każdą trójwymiarową ścianą drugiej kostki co najmniej jeden wspólny wierzchołek!

XLVII OM - II etap

II etap XLVII Olimpiady Matematycznej

XLVII OM - II - Zadanie 1

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

Rozstrzygnąć, czy każdy wielomian o współczynnikach całkowitych jest sumą trzecich potęg wielomianów o współczynnikach całkowitych.

Rozwiązanie

Jeśli $P(x) = a_0 + a_1 x + a_2 x^2 + \ldots + a_n x^n$ jest wielomianem o współczynnikach całkowitych, to $(P(x))^3 = b_0 + b_1x + b_2 x^2 + b_3 x^3 +\ldots + b_{3n}x^{3n}$ ; przy tym $b_0 = a_0^3$ , $b_1= 3a_0^2 a_1$ . Tak więc trzecia potęga wielomianu o współczynnikach całkowitych ma współczynnik przy $x$ podzielny przez $3$ .

Również suma trzecich potęg takich wielomianów ma tę samą własność.

Zatem żaden wielomian, w którym współczynnik przy $x$ nie jest podzielny przez $3$ (na przykład $W(x)=x$ ) nie jest sumą trzecich potęg wielomianów o współczynnikach całkowitych.

XLVII OM - II - Zadanie 2

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

Okrąg o środku $O$ wpisany w czworokąt wypukły $ABCD$ jest styczny do boków $AB$ , $BC$ , $CD$ , $DA$ odpowiednio w punktach $K$ , $L$ , $M$ , $N$ , przy czym proste $KL$ i $MN$ przecinają się w punkcie $S$ . Dowieść, że proste $BD$ i $OS$ są prostopadłe.

Rozwiązanie

Oznaczmy rzuty prostokątne punktów $B$ i $D$ na prostą $OS$ odpowiednio przez $U$ i $V$ . Kąty $OKB$ , $OLB$ i $OUB$ są proste, a zatem punkty $K$ , $L$ i $U$ leżą na okręgu, którego średnicą jest odcinek $OB$ (rysunek 7). (Punkt $U$ może się pokrywać z $O$ i nie można wówczas mówić o kącie $OUB$ ; ale w takim przypadku stwierdzenie, że $U$ jest punktem wspomnianego okręgu nie wymaga żadnego uzasadnienia.) Analogicznie, punkty $M$ , $N$ i $V$ leżą na okręgu, którego średnicą jest odcinek $OD$ . Stosując do tych okręgów twierdzenie o odcinkach siecznych otrzymujemy równości

$ |SK| \cdot |SL| = |SO| \cdot |SU| \quad \textrm{oraz} \quad |SM| \cdot |SN| = |SO| \cdot |SV|. $

To samo twierdzenie, zastosowane do okręgu $w$ wpisanego w czworokąt $ABCD$ pokazuje, że lewe strony powyższych związków są równe. Zatem i prawe strony muszą być równe, czyli zachodzi równość $|SU|=|SV|$ ; przy tym odcinki $SU$ i $SV$ są zawarte w półprostej $SO^\to$ . Stąd wniosek, że punkty $U$ i $V$ pokrywają się, i wobec tego prosta $BD$ jest prostopadła do $OS$ .

Uwaga: Przeprowadzone rozumowanie nie zależy od tego, czy $S$ jest punktem przecięcia półprostych $KL^\to$ i $NM^\to$ , czy półprostych $LK^\to$ i $MN^\to$ . Ta sama uwaga odnosi się także i do dalszych sposobów rozwiązania.

XLVII OM - II - Zadanie 3

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

Wykazać, że jeśli każda z liczb $a$ , $b$ , $c$ jest nie mniejsza od $-\frac{3}{4}$ oraz jeśli $a+b+c=1$ , to

$ \frac{a}{a^2+1} + \frac{b}{b^2+1} + \frac{c}{c^2+1} \leq \frac{9}{10}. $

Rozwiązanie

Sposób I

Dla $x \geq - \frac{3}{4}$ zachodzi nierówność

$ (1) \qquad \quad (3x-1)^2(4x + 3) \geq 0 $

(patrz: Uwaga 1). Przekształcamy tę nierówność, jak następuje:

$ (2) \qquad \begin{split} & 36x^3 + 3x^2-14x + 3 \geq 0; \\ & 50x \leq 36x^3 + 36x + 3x^2 + 3;\\ & 50x \leq (36x + 3)(x^2 + 1);\\ & \frac{x}{x^2+1} \leq \frac{18}{25}x + \frac{3}{50}. \end{split} $

Teraz wystarczy podstawić dane liczby $a$ , $b$ , $c$ :

$ \frac{a}{a^2+1} + \frac{b}{b^2+1}+\frac{c}{c^2+1} \leq \frac{18}{25} (a+b+c) + 3 \cdot \frac{3}{50} = \frac{18}{25} \cdot 1 + 3 \cdot \frac{3}{50} = \frac{9}{10} $

i mamy tezę zadania.

Sposób II

Funkcja dana wzorem

$ f(x)=\frac{x}{x^2+1} \quad \text{ dla } x\in\mathbb{R} $

jest dwukrotnie różniczkowalna w zbiorze liczb rzeczywistych. Obliczamy jej pochodną pierwszego i drugiego rzędu:

$ f'(x)=\frac{1-x^2}{(x^2+1)^2}, \qquad f''(x)=\frac{2x(x^2-3)}{(x^2+1)^3} $

Z otrzymanych wzorów widać, że funkcja $f$ jest rosnąca w przedziale $\langle -1; 1)$ , a malejąca, w każdym z przedziałów $(-\infty;-1\rangle$ i $\langle 1;\infty)$ oraz że jest wypukła w przedziałach $\langle -\sqrt{3}; 0 \rangle$ i $\langle \sqrt{3};\infty)$ , a wklęsła w przedziałach $(-\infty;\sqrt{3}\rangle$ i $\langle 0;\sqrt{3}\rangle$ (rysunek 9)).

Prosta $l$ styczna do wykresu w punkcie $\left(\frac{1}{3}, f\left(\frac{1}{3}\right)\right)$ ma równanie

$ y=f'\left(\frac{1}{3}\right)\left(x-\frac{1}{3}\right)+f\left(\frac{1}{3}\right) = \frac{18}{25}\left(x-\frac{1}{3}\right)+\frac{3}{10} = \frac{18}{25}x + \frac{3}{50} $

i przecina ten wykres ponownie w punkcie $\left(-\frac{3}{4}, f\left(-\frac{3}{4}\right)\right)$ , czyli $\left(-\frac{3}{4}, \frac{12}{25}\right)$

Z wcześniejszych spostrzeżeń na temat przebiegu funkcji $f$ wynika, że w następujących przedziałach żaden punkt jej wykresu nie leży powyżej prostej $l$ :

— w przedziale $\langle 0; 1\rangle$ (bo funkcja $f$ jest w tym przedziale wklęsła);

— w przedziale $\langle 1;\infty)$ (bo funkcja $f$ jest w tym przedziale malejąca);

— w przedziale $\langle—1;0\rangle$ (bo funkcja $f$ jest w tym przedziale wypukła).

Tak więc w całym przedziale $\langle —\frac{3}{4};\infty)$ zachodzi nierówność $f(x) \leq \frac{18}{25}x + \frac{3}{50}$ czyli nierówność (2) z poprzedniego rozwiązania; pozostaje powtórzyć jego końcówkę.

Uwaga 1. Oba przedstawione sposoby rozwiązania sprowadzają się do zastosowania nierówności (2). Jej wyprowadzenie w pierwszym rozwiązaniu, czysto algebraiczne, jest krótkie i zgrabne; ale jak wpaść na pomysł, by rozpocząć od nierówności (1) - niewątpliwie prawdziwej, lecz w żaden sposób nie sugerowanej treścią zadania? Otóż staje się ona naturalna w świetle rozumowania analitycznego, zastosowanego w drugim rozwiązaniu.

Z podobną sytuacją często można się spotkać przy wyprowadzaniu różnych nierówności. W rozumowaniu prowadzącym do szukanego oszacowania (nie znanego uprzednio) zwykle stosuje się metody analizy matematycznej: badanie znaku pochodnych i wynikającą stąd interpretację w terminach własności wykresów rozważanych funkcji. Znalazłszy oszacowanie, warto następnie spróbować znaleźć inny jego dowód, oparty jedynie na prostych przekształceniach algebraicznych (wolny od języka pochodnych, stycznych, wypukłości itd.), a przez to bardziej elementarny i bardziej elegancki.

W przykładzie z tego zadania do nierówności (1) najłatwiej dojść od tyłu, przekształcając równoważnie nierówność (2), znalezioną przy użyciu rachunku różniczkowego. Redagując rozwiązanie odwracamy kolejność: zaczynamy od ,,bardzo prawdziwej'' nierówności (1) i otrzymujemy (2) jako jej konsekwencję. Nie mamy przy tym obowiązku tłumaczyć się, skąd taki fortunny pomysł ...

Uwaga 2. Podana w zadaniu nierówność jest słuszna dla każdej trójki liczb $a$ , $b$ , $c$ spełniającej warunek $a + b + c= 1$ ; założenie, że $a,b,c \geq -\frac{3}{4}$ , jest zbędne.

Dla dowodu przyjmijmy, że $a \geq b \geq c$ . Gdy $c \geq -\frac{3}{4}$ , mamy sytuację już rozpatrzoną; nierówność zachodzi.

Jeżeli $c \leq -3$ , to $a+b= 1-c \geq 4$ , więc $a \geq 2$ . Funkcja $f$ maleje w przedziale $\langle 1;\ \infty)$ , a zatem $f(a) \leq f(2) = \frac{2}{5}$ . Maksymalną wartością funkcji $f$ jest $f(1) = \frac{1}{2}$ . Wobec tego

$ f(a)+f(b)+f(c) \leq \frac{2}{5} + \frac{1}{2} + 0 = \frac{9}{10}. $

Jeśli $- 3 \leq c \leq -\frac{1}{3}$ , to z przebiegu funkcji $f$ wnosimy, że wartość $f(c)$ jest nie większa od wartości $f(-3) = f(-\frac{1}{3}) = - \frac{3}{10}$ . Stąd

$ f(a) + f(b) + f(c) \leq \frac{1}{2} + \frac{1}{2} - \frac{3}{10} = \frac{7}{10}. $

Suma przedziałów $(-\infty;\ -3 \rangle$ , $\langle -3;\ -\frac{1}{3} \rangle$ i $\langle - \frac{3}{4};\ \infty)$ pokrywa (i to ,,z nawiązką'') całą prostą liczbową. Zatem istotnie żadne dolne ograniczenie zakresu zmienności $c$ nie jest potrzebne.

[Mamy tu typowy przykład zadania, w którym założenia zostały dopasowane - nieco sztucznie - do przewidywanej metody rozwiązywania.]

XLVII OM - II - Zadanie 4

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

Dany jest ciąg $a_1, a_2, \ldots , a_{99}$ liczb ze zbioru $\{0,1,2,3,4,5,6,7,8,9\}$ . Zakładamy, że dla $i =1,2, \ldots, 98$ zachodzą implikacje:

$ \textrm{jeśli } a_i = 1, \text{ to } a_{i+1} \neq 2; \quad \text{ a jeśli } a_i = 3, \text{ to } a_{i+1} \neq 4. $

Udowodnić, że dla pewnych dwóch różnych liczb $k,l \in \{1,2, ... ,98\}$ zachodzą równości: $a_k = a_l$ oraz $a_{k+1} = a_{l+1}$ .

Rozwiązanie

Oznaczmy przez $P_k$ parę uporządkowaną $(a_k,a_{k+1})$ . Należy udowodnić, że w ciągu $P_1,P_2,\ldots,P_{98}$ pewna para powtarza się. Zgodnie z warunkiem zadania, pary $(1,2)$ oraz $(3,4)$ są w tym ciągu niedopuszczalne.

Przypuśćmy, wbrew tezie, że w ciągu $P_1,P_2,\ldots,P_{98}$ nie ma powtórzeń. Z dziesięciu liczb jednocyfrowych można utworzyć $10 \cdot 10 - 2 = 98$ różnych par dopuszczalnych. Każda z nich musi zatem wystąpić w tym ciągu dokładnie jeden raz.

Oprócz pary $(1,1)$ istnieje dziewięć dopuszczalnych par postaci $(x,1)$ oraz tylko osiem dopuszczalnych par postaci $(1,y)$ . Jeśli wszystkie one mają się pojawić, to jedynka musi raz wystąpić w ciągu $a_1,a_2,\ldots,a_{99}$ na miejscu, które nie ma prawego sąsiada - czyli na ostatnim miejscu.

Ponieważ role symboli $1$ i $3$ są symetryczne, analogiczne rozumowanie pokazuje, że także trójka musi wystąpić na ostatnim miejscu. Jednak te warunki nie mogą być spełnione jednocześnie. Otrzymana sprzeczność kończy dowód.

XLVII OM - II - Zadanie 5

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

Znaleźć wszystkie pary liczb całkowitych $(x,y)$ spełniające równanie

$ x^2(y - 1) + y^2(x - 1) = 1. $

Rozwiązanie

Podstawiamy $x = u + 1$ , $y = v + 1$ i przekształcamy równanie:

$ \begin{split} (u + 1)^2v + (v + 1)^2u = 1; \\ (u + v)uv + 4uv + (u + v) = 1; \\ (u + v + 4)(uv + 1) = 5. \end{split} $

Jeden z czynników otrzymanego iloczynu musi być równy $5$ lub $-5$ , a drugi (odpowiednio) $1$ lub $-1$ .

Stąd wynika, że liczby $u + v$ oraz $uv$ spełniają jeden z następujących układów równań:

$ \left\{ \begin{split} u+v&=1 \\ uv&=0, \end{split} \right. \quad\left\{ \begin{split} u+v & = -9 \\ uv& = -2, \end{split} \right. \quad \left\{ \begin{split} u+v & = -3 \\ uv& =4, \end{split} \right. \quad \left\{ \begin{split} u+v & = -5 \\ uv& =-6. \end{split} \right. $

W takim razie liczby $u$ i $w$ są pierwiastkami jednego z następujących trójmia-nów kwadratowych:

$ t^2-t; \quad t^2 + 9t -2; \quad t^2 + 3t + 4; \quad t^2 + 5t-6. $

Pierwszy z nich ma pierwiastki $0$ , $1$ , ostatni zaś - pierwiastki $-6$ , $1$ ; pozostałe dwa nie mają pierwiastków całkowitych. Daje to następujące rozwiązania $(x,y)$ rozważanego równania: $(1,2)$ , $(2,1)$ , $(-5,2)$ , $(2,-5)$ .

XLVII OM - II - Zadanie 6

Zawody matematyczne:

XLVII OM, 1995-1996

Etap:

Wewnątrz równoległościanu,którego krawędzie mają długości $a$ , $b$ , $c$ , leży punkt $P$ . Dowieść. że istnieje wierzchołek równoległościanu, którego odległość od punktu $P$ nie przekracza $\frac{1}{2}\sqrt{a^2 + b^2 + c^2}$ .

Rozwiązanie

Ściany równoległościanu wyznaczają sześć płaszczyzn. Niech $\pi$ będzie tą płaszczyzną, której odległość od punktu $P$ jest najmniejsza; jeśli są dwie takie płaszczyzny (lub więcej), wybieramy dowolną z nich i ją oznaczamy przez $\pi$ . Niech $ABCD$ będzie ścianą równoległościanu zawartą w płaszczyźnie $\pi$ i niech $N$ będzie rzutem prostokątnym punktu $P$ na tę płaszczyznę.

Przyjmijmy, że cztery krawędzie równoległościanu, łączące wierzchołki $A$ , $B$ , $C$ , $D$ z wierzchołkami ściany $A'B'C'D'$ równoległej do $ABCD$ , mają długość $c$ . (Nie tracimy przez to ogólności, bo w razie potrzeby można zmienić oznaczenia długości krawędzi.)

Punkt $P$ jest oddalony od ściany $A'B'C'D'$ nie mniej niż od ściany $ABCD$ . Zatem $|NP| \leq \frac{1}{2} c$ .

Wykażemy, że punkt $N$ leży w obrębie rówuoległoboku $ABCD$ . Przypuśćmy, że jest inaczej. Wówczas odcinek $PN$ przecina brzeg równoległościanu w pewnym punkcie $X$ , należącym do jakiejś innej ściany. Odległość punktu $P$ od płaszczyzny tej ściany nie przekracza długości odcinka $PX$ , a więc jest mniejsza od długości odcinka $PN$ , czyli od odległości punktu $P$ od płaszczyzny $\pi$ . To się jednak kłóci z wyborem płaszczyzny $\pi$ ; sprzeczność dowodzi fałszywości uczynionego przypuszczenia.

Tak więc $N$ jest punktem równoległoboku $ABCD$ , którego boki mają długości $a$ i $b$ . Powtarzamy rozumowanie: spośród prostych $AB$ , $BC$ , $CD$ , $DA$ wybieramy tę, której odległość od punktu $N$ jest najmniejsza; jeśli jest więcej niż jedna taka prosta, wybieramy którąkolwiek z nich.

Przyjmijmy, że jest to prosta $AB$ i że $|AB| = a$ (w razie potrzeby zmieniamy oznaczenia). Niech $K$ będzie rzutem prostokątnym punktu $N$ na prostą $AB$ . Rozumując podobnie jak poprzednio zauważamy, że $|KN| \leq \frac{1}{2}b$ oraz że $K$ jest punktem odcinka $AB$ ; gdyby bowiem punkt $K$ leżał na prostej $AB$ poza odcinkiem $AB$ , wówczas odcinek $NK$ przecinałby inny bok równoległoboku $ABCD$ , i wobec tego odległość punktu $N$ od tego boku byłaby mniejsza niż odległość $N$ od prostej $AB$ - wbrew wyborowi owej prostej.

Możemy wreszcie bez straty ogólności założyć, że punkt $K$ leży na odcinku $AB$ w odległości nie większej od końca $A$ niż od $B$ . Zatem $|AK| \leq \frac{1}{2} a$ .

Kierunki prostych $AK$ , $KN$ , $NP$ są parami prostopadłe. Odcinki $AK$ , $KN$ , $NP$ są więc trzema prostopadłymi krawędziami prostopadłościanu, którego wewnętrzną przekątną jest odcinek $AP$ . Długości tych odcinków nie przekraczają (odpowiednio) liczb $\frac{1}{2}a$ , $\frac{1}{2}b$ , $\frac{1}{2}c$ . Zatem, ostatecznie,

$ |AP| = \sqrt{|AK|^2 + |KN|^2 + |NP|^2} \leq \frac{1}{2} \sqrt{a^2 + b^2 + c^2}; $

punkt $A$ jest wierzchołkiem, którego istnienie trzeba było wykazać.

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