XLV OM - I etap

I etap XLV Olimpiady Matematycznej

XLV OM - I - Zadanie 1

Zawody matematyczne:

XLV OM, 1993-1994

Etap:

Udowodnić, że układ równań

$ \begin{cases} a^2 - b = c^2 \\ b^2 - a = d^2 \end{cases} $

nie ma rozwiązań w liczbach całkowitych dodatnich $a$ , $b$ , $c$ , $d$ .

Rozwiązanie

Przypuśćmy, że liczby całkowite $a,b,c,d > 0$ spełniają podany układ. Różnice $a^2 - c^2 = b$ oraz $b^2 - d^2 = a$ są wówczas liczbami dodatnimi. Zachodzą więc nierówności $a> c$ oraz $b> d$ , czyli $a \geq c +1 \geq 2$ oraz $b \geq d +1 \geq 2$ . Stąd

$ b = a^2-c^2 \geq a^2-(a-1)^2 = 2a-1 $

oraz

$ a = b^2-d^2 \geq b^2 -(b-1)^2 = 2b-1. $

Dodając te nierówności stronami dostajemy zależność $a + b \geq 2a + 2b - 2$ , czyli $a + b \leq 2$ . Jest to sprzeczność z uzyskanymi wcześniej oszacowaniami $a \geq 2$ oraz $b\geq 2$ . Dowodzi ona, że rozważany układ równań nie ma rozwiązań w liczbach całkowitych dodatnich.

XLV OM - I - Zadanie 2

Zawody matematyczne:

XLV OM, 1993-1994

Etap:

Ciąg funkcji $f_0, f_1, f_2, \ldots$ jest określony następująco:

$ f_0(x) = |x| \quad \text{ dla wszystkich } x \in \mathbb{R}, $

$ f_{n+1}(x) = |f_n(x)-2| \quad \text{ dla } n=O,1,2, \ldots \text{ oraz wszystkich } x \in \mathbb{R}. $

Dla każdej liczby naturalnej $n$ rozwiązać równanie $f_n(x) = 1$ .

Rozwiązanie

Oznaczmy symbolem $M_k$ zbiór wszystkich liczb całkowitych nieparzystych z przedziału $\langle 1; 2k+1 \rangle$ . Weźmy dowolne liczby całkowite $m \geq 1$ , $k \geq 0$ . Zgodnie z określeniem rozważanego ciągu funkcji, następujące zdania (1), (2), (3) są kolejno równoważne:

$ (1) \qquad f_m(x) \in M_k; $

$ (2) \qquad |f_{m-1}(x)-2| \in M_k; $

$ (3) \qquad f_{m-1}(x)-2 \in M_k \quad \textrm{lub} \quad 2-f_{m-1}(x) \in M_k. $

Wszystkie funkcje $f_n$ przyjmują wyłącznie wartości nieujemne; wynika to natychmiast z ich określenia rekurencyjnego. Zatem jedyną liczbą ze zbioru $M_k$ , która może być równa różnicy $2 -f_{m-1}(x)$ , jest liczba $1$ . Wobec tego drugi człon alternatywy (3) jest równoważny temu, że $f_{m-1}(x) = 1$ . Ciąg kolejno równoważnych zdań (1), (2), (3) może więc być kontynuowany następująco:

$ (4) \qquad f_{m-1}(x)-2 \in M_k \quad \textrm{lub} \quad f_{m-1}(x) = 1; $

$ (5) \qquad f_{m-1}(x)\in M_{k+1}. $

Otrzymaliśmy w ten sposób równoważność między warunkami (1) i (5):

$ f_m(x) \in M_k \Longleftrightarrow f_{m-1}(x) \in M_{k+1}. $

Ustalmy $n$ . Z uzyskanej równoważności wnioskujemy kolejno, że

$ \begin{split} f_n(x)=1 &\Longleftrightarrow f_n(x)\in M_0 \Longleftrightarrow f_{n-1}(x)\in M_1 \Longleftrightarrow f_{n-2}(x)\in M_2 \Longleftrightarrow \\ & \Longleftrightarrow \ldots \Longleftrightarrow f_0(x) \in M_n \Longleftrightarrow |x| \in M_n \end{split} $

(bo $f_0(x) = |x|$ , z definicji funkcji $f_0$ .) Warunek $|x| \in M_n$ oznacza oczywiście, że $x$ jest liczbą nieparzystą z przedziału $\langle-2n- 1;2n +1\rangle$ .

Wniosek: Dla dowolnie ustalonej liczby naturalnej $n$ , zbiór rozwiązań równania $f_n(x) = 1$ tworzą wszystkie liczby całkowite nieparzyste z przedziału $\langle-2n- 1;2n +1\rangle$ .

XLV OM - I - Zadanie 3

Zawody matematyczne:

XLV OM, 1993-1994

Etap:

Dowieść, że jeżeli $a$ , $b$ , $c$ są długościami boków trójkąta, to

$ \frac{1}{a} + \frac{1}{b} + \frac{1}{c} \leq \frac{1}{b+c-a} + \frac{1}{c+a-b} + \frac{1}{a+b-c}. $

Rozwiązanie

Jeśli liczby $a$ , $b$ , $c$ są długościami boków trójkąta, to liczby $x$ , $y$ , $z$ dane wzorami

$ x = \frac{b+c-a}{2}, \quad y =\frac{c+a-b}{2}, \quad z = \frac{a+b-c}{2} $

są dodatnie. Traktując układ tych trzech równości jako układ równań z niewiadomymi $a$ , $b$ , $c$ , wyznaczamy: $a = y + z$ , $b = z + x$ , $c = x + y$ . Dana do udowodnienia nierówność przybiera postać

$ (1) \qquad \frac{1}{y+z} + \frac{1}{z+x} +\frac{1}{x+y} \leq \frac{1}{2x}+\frac{1}{2y}+\frac{1}{2z}. $

Liczby dodatnie $x$ i $y$ spełniają nierówność

$ (2) \qquad \frac{1}{x+y}\leq \frac{1}{4}\left(\frac{1}{x}+\frac{1}{y}\right); $

oto uzasadnienie:

$ \frac{1}{x}+\frac{1}{y}-\frac{4}{x+y}=\frac{(x+y)^2-4xy}{xy(x+y)}=\frac{(x-y)^2}{xy(x+y)} \geq 0. $

Analogicznie,

$ (3) \qquad \frac{1}{y+z} \leq \frac{1}{4}\left(\frac{1}{y}+\frac{1}{z}\right) \quad \textrm{oraz} \quad \frac{1}{z+x} \leq \frac{1}{4}\left(\frac{1}{z}+\frac{1}{x}\right). $

Dodając stronami nierówność (2) oraz obie nierówności (3) dostajemy dowodzoną tezę (1).

XLV OM - I - Zadanie 4

Zawody matematyczne:

XLV OM, 1993-1994

Etap:

Dany jest okrąg o środku $O$ , punkt $A$ wewnątrz tego okręgu oraz cięciwa $PQ$ , nie będąca średnicą, przechodząca przez $A$ . Proste $p$ i $q$ są styczne do rozważanego okręgu odpowiednio w punktach $P$ i $Q$ . Prosta $l$ przechodząca przez punkt $A$ i prostopadła do $OA$ przecina proste $p$ i $q$ odpowiednio w punktach $K$ i $L$ . Wykazać, że $|AK|=|AL|$ .

Rozwiązanie

Rozpoczynamy od spostrzeżenia, że punkty $P$ i $K$ leżą po jednej stronie prostej $OA$ , a punkty $Q$ i $L$ leżą po drugiej jej stronie (niezależnie od tego, czy punkt $A$ leży na odcinku $PQ$ bliżej końca $P$ czy końca $Q$ ). Cięciwa $PQ$ danego okręgu nie jest jego średnicą, więc proste styczne $p$ i $q$ przecinają się. Oznaczmy punkt przecięcia przez $S$ .

Na trójkącie $OAK$ opisujemy okrąg $\omega_1$ . Na trójkącie $OAL$ opisujemy okrąg $\omega_2$ . Kąty $OAK$ i $OAL$ są z założenia proste, więc średnicami tych okręgów są (odpowiednio) odcinki $OK$ i $OL$ (rysunek 1).

Proste $p$ i $q$ , styczne do danego okręgu, są prostopadłe do jego promieni $OP$ i $OQ$ ; kąty $OPK$ i $OQL$ są więc proste. Zatem okrąg $\omega_1$ przechodzi przez punkt $P$ , a okrąg $\omega_2$ przechodzi przez punkt $Q$ . (W szczególnym przypadku, gdy punkt $A$ jest środkiem cięciwy $PQ$ i w konsekwencji punkty $K$ i $L$ pokrywają się, odpowiednio, z punktami $P$ i $Q$ -- nie można wprawdzie mówić o kątach $OPK$ i $OQL$ , ale konkluzja, że $P \in \omega_1$ , $Q \in \omega_2$ , jest oczywiście nadal słuszna.)

Kąty $OPA$ i $OKA$ są kątami wpisanymi w okrąg $\omega_1$ , opartymi na wspólnym łuku $OA$ (korzystamy tu z wcześniejszego spostrzeżenia, że punkty $P$ i $K$ leżą po tej samej stronie prostej $OA$ ). Mają więc te kąty jednakową rozwartość: $|\measuredangle OPA| = |\measuredangle OKA|$ ; podobnie $|\measuredangle OQA| = |\measuredangle OLA|$ (kąty wpisane w okrąg $\omega_2$ , oparte na wspólnym łuku $OA$ ). Zauważmy wreszcie, że

$ |\measuredangle OPA| = |\measuredangle OPQ| = |\measuredangle OQP| = |\measuredangle OQA|, $

bowiem trójkąt $POQ$ jest równoramienny.

Z uzyskanych równości kątów wynika, że

$ |\measuredangle OKA| = |\measuredangle OLA|. $

Wobec tego trójkąty prostokątne $OAK$ i $OAL$ są przystające i otrzymujemy żądaną równość odcinków $|AK| = |AL|$ .

XLV OM - I - Zadanie 5

Zawody matematyczne:

XLV OM, 1993-1994

Etap:

Udowodnić, że jeżeli wielomian $x^3 + ax^2 + bx + c$ ma trzy różne pierwiastki rzeczywiste, to wielomian $x^3 + ax^2 + \frac{1}{4}(a^2 + b)x +\frac{1}{8}(ab - c)$ także ma trzy różne pierwiastki rzeczywiste.

Rozwiązanie

Oznaczmy dane w zadaniu wielomiany przez $P(x)$ i $Q(x)$ :

$ P(x) = x^3 + ax^2 + bx + c, \quad Q(x) = x^3 + ax^2 + \frac{1}{4}(a^2 + b)x + \frac{1}{8}(ab - c). $

Zastępujemy w wielomianie $P(x)$ zmienną $x$ przez różnicę $2x - a$ i przekształcamy uzyskane wyrażenie:

$ \begin{split} P(2x - a) &= (2x - a)^3 + a(2x - a)^2 + b(2x - a) + c =\\ &= -8(-x^3 + ax^2- \frac{1}{4} (a^2 + b)x + \frac{1}{8}(ab-c)) = -8Q(-x). \end{split} $

Z otrzymanej tożsamości

$ (1) \qquad 8Q(-x) = -P(2x-a) $

natychmiast wynika, że jeśli liczba $\xi$ jest pierwiastkiem wielomianu $P(x)$ , to liczba $-\frac{1}{2}(\xi + a)$ jest pierwiastkiem wielomianu $Q(x)$ .

A zatem, jeżeli liczby $x_1$ , $x_2$ , $x_3$ są trzema różnymi pierwiastkami wielomianu $P(x)$ , to liczby $-\frac{1}{2}(x_1 + a)$ , $-\frac{1}{2}(x_2 + a)$ , $-\frac{1}{2}(x_3 + a)$ są trzema różnymi pierwiastkami wielomianu $Q(x)$ .

{\kom Uwaga.} Pomysł, aby przekształcać wyrażenie $P(2x - a)$ nie wymaga żadnego ,,objawienia''. Sama postać wielomianów $P(x)$ i $Q(x)$ (a także i teza zadania \ldots) sugeruje, że - być może - istnieją stałe $\alpha$ , $\beta$ , $\gamma$ , dla których równość

$ (2) \qquad P(\alpha x + \beta) = \gamma Q(x) $

jest spełniona tożsamościowo (przy czym $\alpha \neq 0$ , $\gamma \neq 0$ ). Porównując współczynniki przy $x^3$ widzimy, że jeśli takie stałe istnieją, to $\gamma$ musi być równe $\alpha^3$ . Postulowana tożsamość (2) przybiera postać

$ P(\alpha x + \beta) = \alpha^3Q(x). $

Podstawiając wyrażenia określające wielomiany $P(x)$ i $Q(x)$ , i przyrównując współczynniki wielomianów otrzymanych po lewej i prawej stronie wzoru (2), uzyskujemy układ trzech równań z dwiema niewiadomymi ( $\alpha$ i $\beta$ ). Okazuje się, że - niezależnie od wartości danych stałych (,,parametrów'') $a$ , $b$ , $c$ - układ ten zawsze ma rozwiązanie $\alpha = -2$ , $\beta = -a$ (więc $\gamma = -8$ ); na ogół jest to jego jedyne rozwiązanie, ale dla niektórych szczególnych wartości stałych $a$ , $b$ , $c$ mogą istnieć jeszcze inne rozwiązania. Nie ma to jednak znaczenia: dla znalezionych wartości liczb $\alpha$ , $\beta$ , $\gamma$ zawsze spełniona jest tożsamość (2); po zastąpieniu $x$ przez $-x$ przybiera ona postać (1).

Oczywiście, redagując rozwiązanie zadania, nikt nie ma obowiązku ,,tłumaczyć się'', skąd pomysł badania wyrażenia $P(2x-a)$ .

XLV OM - I - Zadanie 6

Zawody matematyczne:

XLV OM, 1993-1994

Etap:

Funkcja $f: \mathbb{R} \to \mathbb{R}$ jest ciągła. Wykazać, że jeżeli dla każdej liczby rzeczywistej $x$ istnieje taka liczba naturalna $n$ , że $(\underbrace{f \circ \ldots \circ f}_{n})(x) = 1$ , to $f(1)=1$ .

Rozwiązanie

Symbolem $f^r$ będziemy oznaczali $r$ --tą iteratę funkcji $f$ , czyli $r$ -krotne złożenie (superpozycję) $f \circ f \circ \ldots \circ f$ .

Przypuśćmy, wbrew tezie, że $f(1) \neq 1$ . Niech $m$ będzie najmniejszą dodatnią liczbą naturalną, dla której zachodzi równość

$ (1) \qquad f^m(1) = 1 $

(taka liczba istnieje w myśl warunku zadania). Skoro $f(1) \neq 1$ , zatem $m \geq 2$ . Przyjmijmy $x_0 = 1$ i oznaczmy wartość $f(1)$ przez $x_1$ , wartość $f(x_1)$ przez $x_2$ , i dalej, indukcyjnie, wartość $f(x_i)$ przez $x_{i+1}$ (dla $i = 1,2,\ldots,m - 1$ ); wówczas $x_m = f^m(1) = 1$ . Otrzymujemy układ liczb rzeczywistych $x_0,x_1,\ldots,x_{m-1},x_m$ spełniający warunki

$ x_0 = x_m = 1, \quad x_{i+1} = f(x_i) \quad \textrm{dla } i = 0,1,\ldots ,m - 1. $

Niech $x_k$ będzie najmniejszą, a $x_l$ - największą spośród liczb $x_0,x_1, \ldots ,x_{m-1}$ . Zachodzą więc nierówności

$ (2) \qquad x_k \leq x_{k+1}, \quad x_l \geq x_{l+1} $

(faktycznie zachodzą tu nierówności ostre, bo liczby $x_0, x_1, \ldots, x_{m-1}$ są wszystkie różne, co wynika z określenia m jako minimalnej liczby spełniającej warunek (1); ale dla dalszego ciągu rozumowania nie ma to znaczenia - wystarczą słabe nierówności (2)).

Weźmy pod uwagę funkcję $g(x) = f(x) - x$ ; jest to funkcja ciągła. Przyjmuje ona w punktach $x_k$ i $x_l$ wartości

$ g(x_k) = f(x_k)-x_k = x_{k+1}-x_k \geq 0 $

oraz

$ g(x_l) = f(x_l)-x_l = x_{l+1}-x_l \leq 0; $

istnieje więc (na mocy własności Darboux) liczba $c \in \langle x_k; x_l \rangle$ , dla której zachodzi równość $g(c) = 0$ , czyli $f(c) = c$ . Stąd wynika, że

$ f^n(c) = c \quad \textrm{dla każdego $n$ naturalnego}. $

Skorzystajmy ponownie z warunku zadania, który mówi, że dla pewnego $n$ wartość $f^n(c)$ ma być równa $1$ . Otrzymujemy wniosek, że $c = 1$ . Równość $f(c) = c$ orzeka teraz, że $f(1) = 1$ - wbrew początkowemu przypuszczeniu - i tym samym dowodzi błędności tego przypuszczenia. Zatem, ostatecznie, $f(1)=1$ .

XLV OM - I - Zadanie 7

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

Na zewnątrz czworokąta wypukłego $ABCD$ budujemy trójkąty podobne $APB$ , $BQC$ , $CRD$ , $DBA$ w ten sposób, że

$ |\measuredangle PAB| = |\measuredangle QBC| = |\measuredangle RCD| = |\measuredangle SDA|, |\measuredangle PBA| = |\measuredangle QCB| = |\measuredangle RDC| = |\measuredangle SAD|· $

Dowieść, że jeśli czworokąt $PQRB$ jest równoległobokiem, to czworokąt $ABCD$ też jest równoległobokiem.

Rozwiązanie

Jeżeli czworokąt $PQRS$ jest równoległobokiem, to jego przekątne $PR$ i $QS$ mają wspólny środek $O$ . Oznaczmy środki przekątnych $AC$ i $BD$ czworokąta $ABCD$ odpowiednio przez $M$ i $N$ . Aby dowieść, że czworokąt $ABCD$ jest równoległobokiem, wystarczy wykazać, że punkty $M$ i $N$ pokrywają się. (Na rysunku 3 czworokąt $PQRS$ przypomina równoległobok, natomiast czworokąt $ABCD$ równoległoboku nie przypomina. Zatem - jeśli teza ma być słuszna - rysunek ten nie jest ilustracją zadania. Mimo to, a raczej właśnie dzięki temu, taki rysunek jest ,,bezpieczny''; nie skłania bowiem do korzystania z zależności geometrycznych, które nie wynikają bezpośrednio z założeń, a jedynie mogłyby zostać zasugerowane rysunkiem wykonanym zgodnie z dowodzoną tezą.)

Przyjmijmy dalsze oznaczenia

$ \lambda =\frac{|PB|}{|PA|} \quad \textrm{oraz} \quad \varphi=\measuredangle(\overrightarrow{PA},\overrightarrow{PB}); $

ostatni symbol oznacza miarę kąta zorientowanego, mierzonego od wektora $\overrightarrow{PA}$ do wektora $\overrightarrow{PB}$ w takim kierunku, by miara ta była liczbą z przedziału $(0;\pi)$ (w sytuacji jak na rysunku 3, jest to kierunek {\it dodatni}, to znaczy przeciwny do kierunku ruchu wskazówek zegara).

Z podobieństwa czterech trójkątów wymienionych w treści zadania wynika, że w każdym z tych trójkątów odpowiednie boki (traktowane jako wektory o wspólnym początku) tworzą ten sam kąt $\varphi$ , a stosunek ich długości wyraża się tą samą liczbą $\lambda$ , co w trójkącie $PAB$ :

$ {\def\arraystretch{2} (1) \qquad \begin{array}{c} \lambda=\cfrac{|PB|}{|PA|}=\cfrac{|QC|}{|QB|}=\cfrac{|RD|}{|RC|}=\cfrac{|SA|}{|SD|},\\ \varphi= \measuredangle(\overrightarrow{PA},\overrightarrow{PB})= \measuredangle(\overrightarrow{QB},\overrightarrow{QC})= \measuredangle(\overrightarrow{RC},\overrightarrow{RD})=\measuredangle(\overrightarrow{SD},\overrightarrow{SA}). \end{array}} $

Przesunięcie o wektor $\overrightarrow{PO}$ przeprowadza trójkąt $PAB$ do położenia $OA'B'$ , natomiast przesunięcie o wektor $\overrightarrow{RO}$ przeprowadza trójkąt $RCD$ do położenia $OC'D'$ (rysunek 4). Punkt $O$ jest środkiem odcinka $PR$ ; mamy wobec tego następujące równości (wektorów swobodnych):

$ (2) \qquad \overrightarrow{AA'} = \overrightarrow{BB'} = \overrightarrow{PO} = \overrightarrow{OR} = \overrightarrow{C'C} = \overrightarrow{D'D}. $

Operacja przesunięcia nie zmienia długości odcinków (wektorów) ani kątów między nimi, a zatem w trójkątach $OA'B'$ i $OC'D'$ zachodzą równości analogiczne do (1):

$ {\def\arraystretch{2.5} (3) \qquad \begin{array}{c} \lambda=\dfrac{|OB'|}{|OA'|}=\dfrac{|OD'|}{|OC'|},\\ \varphi= \measuredangle(\overrightarrow{OA'},\overrightarrow{OB'})= \measuredangle(\overrightarrow{OC'},\overrightarrow{OD'}).\end{array}} $

Weźmy pod uwagę przekształcenie $f$ określone jako złożenie jednokładności o środku $O$ i skali $\lambda$ z obrotem wokół punktu $O$ o kąt $\varphi$ (w ustalonym uprzednio kierunku). Przy tym przekształceniu wektor $\overrightarrow{OA'}$ zmienia swą długość w stosunku $\lambda$ i obraca się o kąt $\varphi$ ; tak więc, zgodnie z równościami (3), punkt $A'$ jest odwzorowywany na punkt $B'$ , a punkt $C$ - analogicznie - na punkt $D'$ :

$ (4) \qquad f(A') = B' \quad \textrm{oraz} \quad f(C') = D'. $

Przekształcenie $f$ jest podobieństwem. Ze związków (4) wynika wobec tego, że obrazem środka $M'$ odcinka $A'C'$ jest środek $N'$ odcinka $B'D'$ :

$ f(M') = N'. $

(Punkty $M'$ i $N'$ nie zostały zaznaczone na rysunku 4, aby nie zaciemniać go jeszcze bardziej.) Równości (2) pokazują wszelako, że czworokąty $AA'CC'$ oraz $BB'DD'$ są równoległobokami. W takim razie środek przekątnej $A'C'$ pokrywa się ze środkiem przekątnej $AC$ , a środek przekątnej $B'D'$ pokrywa się ze środkiem przekątnej $BD$ . Tak więc $M' = M$ , $N' = N$ i mamy związek

$ (5) \qquad f(M) = N. $

Rozważając trójkąty $OB''C''$ i $OD''A''$ powstałe przez przesunięcie trójkątów
$QBC$ i $SDA$ odpowiednio o wektory $\overrightarrow{QO}$ i $\overrightarrow{SO}$ (rysunek 4) i przeprowadzając w pełni analogiczne rozumowanie, dochodzimy do równości

$ (6) \qquad f(N) = M. $

Rozwiązanie zadania zostało na samym wstępie sprowadzone do wykazania, że punkty $M$ i $N$ się pokrywają. Zależności (5) i (6) implikują równości

$ f\circ f(M) = M \quad \textrm{oraz} \quad f\circ f(N) = N. $

Zauważmy, że przekształcenie $f\circ f$ jest złożeniem jednokładności o skali $\lambda^2$ z obrotem o kąt $2\varphi$ . Ponieważ $0 < 2\varphi< 2\pi$ , jedynym punktem, który w tym przekształceniu nie zmienia swojego położenia; jest punkt $O$ (wspólny środek obrotu i jednokładności). Zatem zarówno punkt $M$ , jak i punkt $N$ , pokrywa się z $O$ . Dowód jest zakończony.

XLV OM - I - Zadanie 8

Zawody matematyczne:

XLV OM, 1993-1994

Etap:

Dane są takie liczby naturalne $a$ , $b$ , $c$ , że $a^3$ dzieli się przez $b$ , $b^3$ dzieli się przez $c$ , a $c^3$ dzieli się przez $a$ . Udowodnić, że liczba $(a+b+c)^{13}$ jest podzielna przez $abc$ .

Rozwiązanie

Liczba $(a + b + c)^{13}$ jest iloczynem trzynastu czynników, z których każdy równa się $a + b + c$ . Wymnażając te trzynaście identycznych wyrażeń otrzymamy sumę wielu (mianowicie $3^{13}$ ) składników postaci

$ (1) \qquad a^kb^mc^n; \quad k,m,n\geq 0 \ \textrm{całkowite,}\ k + m + n = 13. $

Wystarczy wykazać, że każdy taki składnik dzieli się przez iloczyn $abc$ . Jest to oczywiste, gdy żaden z wykładników $k$ , $m$ , $n$ nie jest zerem, bo wówczas $a^kb^mc^n = abc \cdot a^{k-1}b^{m-1}c^{n-1}$ . Pozostaje zająć się przypadkiem, gdy co najmniej jeden z tych wykładników równa się zeru.

Ponieważ układ założeń jest niezmienniczy względem cyklicznej zmiany oznaczeń ( $a \mapsto b \mapsto c \mapsto a$ ), nie tracimy ogólności zakładając, że $n = 0$ . Iloczyn (1) ma wtedy postać

$ (2) \qquad a^kb^m; \quad k,m\geq 0 \ \textrm{całkowite,}\ k + m = 13. $

Zadanie zostało sprowadzone do wykazania, że dla każdej takiej pary wykładników $k$ , $m$ liczba $a^kb^m$ dzieli się przez $abc$ .

Z podanych w zadaniu założeń wynika, że

$ a^9 \textrm{ dzieli się przez } c,\quad b^9 \textrm{ dzieli się przez } a. $

Liczbę postaci (2) możemy zapisać następująco jako iloczyn czterech czynników (pooddzielanych kropkami):

$ \begin{array}{lcl} \textrm{gdy}& k = 13 ,\ m = 0 &:\ a^kb^m = a \cdot a^3\cdot a^9\cdot 1;\\ \textrm{gdy}& 10\leq k \leq 12,\ 1\leq m \leq 3 &:\ a^kb^m = a\cdot b \cdot a^9 \cdot (a^{k-10}b^{m-1});\\ \textrm{gdy}& 1\leq k \leq 9,\ 4\leq m \leq 12 &:\ a^kb^m = a\cdot b \cdot b^3 \cdot (a^{k-1}b^{m-4});\\ \textrm{gdy}& k = 0 ,\ m = 13 &:\ a^kb^m = b^9 \cdot b\cdot b^3\cdot 1. \end{array} $

W każdym z powyższych przedstawień pierwszy czynnik dzieli się przez $a$ , drugi dzieli się przez $b$ , a trzeci dzieli się przez $c$ ; czwarty jest zaś pewną liczbą naturalną. Tak więc, w każdym przypadku, iloczyn $a^kb^m$ jest liczbą podzielną przez iloczyn $abc$ . W myśl poprzednich uwag, kończy to dowód.

XLV OM - I - Zadanie 9

Zawody matematyczne:

XLV OM, 1993-1994

Etap:

W konferencji bierze udział $2n$ osób. Każdy uczestnik konferencji ma wśród pozostałych uczestników co najmniej $n$ znajomych. Udowodnić, że wszystkich uczestników konferencji można zakwaterować w pokojach dwuosobowych tak, by każdy uczestnik mieszkał ze swoim znajomym.

Rozwiązanie

W zadaniu zakłada się milcząco, że jeśli pewna osoba zna inną, to ta druga osoba zna pierwszą, oraz że nikt nie jest swoim własnym znajomym.

Niech $m$ będzie maksymalną liczbą rozłącznych par znajomych, jakie można utworzyć spośród uczestników konferencji. Zadanie sprowadza się do wykazania, że $m = n$ . Przypuśćmy więc, że $m < n$ i niech $P_1,\ldots, P_m$ będzie układem $m$ rozłącznych par znajomych. Zbiór pozostałych uczestników konferencji (tych, którzy nie znaleźli się w żadnej z par $P_1,\ldots ,P_m$ ) oznaczmy przez $Q$ .

Weźmy pod uwagę dowolnych dwóch uczestników $A$ i $B$ ze zbioru $Q$ . Żaden z nich nie ma znajomego w zbiorze $Q$ (gdyby miał, utworzyłby wraz z tym znajomym ( $m + 1$ )--szą parę, wbrew maksymalności $m$ ). Zatem - w myśl założenia - zarówno uczestnik $A$ , jak i $B$ , ma w zbiorze $P_1\cup \ldots \cup P_m$ co najmniej $n$ znajomych.

Każdemu uczestnikowi konferencji przyporządkujmy liczbę $2$ , $1$ lub $0$ , w zależności od tego, czy zna on obie osoby $A$ i $B$ , dokładnie jedną z nich, czy żadną. Dla $i = 1,\ldots,m$ oznaczmy przez $s_i$ sumę liczb przyporządkowanych dwóm uczestnikom konferencji, tworzącym parę $P_i$ . Z konkluzji ostatniego zdania w poprzednim akapicie wynika nierówność $s_1 + \ldots + s_m \geq 2n$ , bowiem suma $s_1 + \ldots + s_m$ wyraża liczbę wszystkich ,,połączeń'' (w sensie relacji ,,bycia znajomym'') między elementami zbioru $P_1 \cup \ldots\cup P_m$ i elementami zbioru $\{A,B\}$ .

Gdyby wszystkie składniki sumy $s_1 + \ldots + s_m$ były mniejsze lub równe $2$ , wartość tej sumy nie przekraczałaby $2m$ , a więc byłaby mniejsza od $2n$ . W takim razie co najmniej jeden składnik jest większy od $2$ . Nie tracąc ogólności przyjmijmy, że $s_m \geq 3$ (kolejność ponumerowania można zmienić w razie potrzeby). Oznaczmy uczestników tworzących parę $P_m$ przez $C$ i $D$ . Suma przyporządkowanych im liczb (czyli $s_m$ ) wynosi $3$ lub $4$ , a to znaczy, że co najmniej jeden z tych uczestników zna obie osoby $A$ i $B$ , a drugi zna co najmniej jedną z tych osób. Możemy przyjąć (znów: kwestia oznaczeń), że $C$ jest znajomym zarówno $A$ , jak i $B$ , zaś $D$ jest znajomym $B$ .

Rozdzielamy parę $\{C,D\}$ i tworzymy dwie nowe pary: $\{A,C\}$ oraz $\{B,D\}$ . Wraz z pozostałymi parami $P_1,\ldots,P_{m-1}$ mamy w ten sposób $m + 1$ rozłącznych par znajomych. Uzyskana sprzeczność z maksymalnością $m$ dowodzi tezy zadania.

XLV OM - I - Zadanie 10

Zawody matematyczne:

XLV OM, 1993-1994

Etap:

Liczby dodatnie $p$ i $q$ spełniają warunek $p+q=1$ . Wykazać, że dla dowolnych liczb naturalnych $m$ i $n$ zachodzi nierówność

$ (1 - p^m)^n +(1- q^n)^m \geq 1. $

Rozwiązanie

Wyobraźmy sobie szachownicę prostokątną mającą $m$ rzędów poziomych i $n$ rzędów pionowych. Przyjmijmy, że pola są kolorowane losowo: dla każdego pola prawdopodobieństwo pomalowania na biało wynosi $p$ , a prawdopodobieństwo pomalowania na czarno wynosi $q$ .

Ustalmy rząd pionowy $C$ . Prawdopodobieństwo tego, że wszystkie pola w rzędzie $C$ są białe, wynosi $p^m$ . Zatem prawdopodobieństwo tego, że co najmniej jedno pole w rzędzie $C$ jest czarne, równa się $1 - p^m$ .

Mamy $n$ rzędów pionowych, i do każdego z nich odnosi się konkluzja poprzedniego zdania. Tak więc liczba $(1 - p^m)^n$ wyraża prawdopodobieństwo zdarzenia:

$ \mathcal{A} : \textrm{ każdy rząd pionowy zawiera co najmniej jedno czarne pole.} $

Weźmy pod uwagę zdarzenie przeciwne do $\mathcal{A}$ :

$ \mathcal{A'} : \textrm{ istnieje rząd pionowy z wszystkimi polami białymi.} $

Skoro, jak stwierdziliśmy przed chwilą, $P(\mathcal{A}) = (1-p^m)^n$ , zatem

$ P(\mathcal{A}') = 1-(1-p^m)^n. $

Do analogicznych wniosków dojdziemy rozważając zdarzenia:

$ \mathcal{B} : \textrm{ każdy rząd poziomy zawiera co najmniej jedno białe pole} $

oraz

$ \mathcal{B'} : \textrm{ istnieje rząd poziomy z wszystkimi polami czarnymi.} $

Są to zdarzenia wzajemnie przeciwne. Z uwagi na symetrię konfiguracji, ich prawdopodobieństwa dane są wzorami analogicznymi do uzyskanych dla zdarzeń $\mathcal{A}$ i $\mathcal{A}'$ :

$ P(\mathcal{B}) = (1-q^n)^m,\quad P(\mathcal{B}') = 1-(1-q^n)^m. $

Zauważmy teraz, że zdarzenia $\mathcal{A}'$ i $\mathcal{B}'$ nie mogą zajść jednocześnie; znaczyłoby to bowiem, że istnieje rząd pionowy cały biały oraz istnieje rząd poziomy cały czarny; pole na przecięciu tych rzędów musiałoby mieć oba kolory naraz, co nie jest możliwe. Suma prawdopodobieństw zdarzeń wzajemnie się wykluczających nie przekracza jedności: $P(\mathcal{A}')+P(\mathcal{B}') \leq 1$ . Podstawiając znalezione wartości $P(\mathcal{A}')$ i $P(\mathcal{B}')$ otrzymujemy oszacowanie

$ [1-(1-p^m)^n]+[1-(1-q^n)^m] \leq 1; $

po prostym przekształceniu:

$ (1-p^m)^n+(1-q^n)^m \geq 1 $

- a to jest właśnie nierówność dana do udowodnienia.

XLV OM - I - Zadanie 11

Zawody matematyczne:

XLV OM, 1993-1994

Etap:

Trójkąt o obwodzie $2p$ jest wpisany w koło o promieniu $R$ i opisany na kole o promieniu $r$ . Dowieść, że $p < 2(R + r)$ .

Rozwiązanie

Niech $ABC$ będzie rozważanym trójkątem; przyjmijmy zwykłe oznaczenia

$ a = |BC|,\ b=|CA|,\ c=|AB|;\ \alpha=|\measuredangle BAC|, $

zakładając (bez straty ogólności), że $a$ jest największym kątem tego trójkąta. Zatem $a \geq 60^\circ$ . Oznaczmy przez $I$ środek okręgu wpisanego w trójkąt $ABC$ , a przez $A'$ , $B'$ , $C'$ punkty styczności tego okręgu z bokami $BC$ , $CA$ , $AB$ .

Przyjmijmy ponadto

$ x = |AB'| = |AC'|, \ y=|BC'| = |BA'|, \ z = |CA'| = |CB'| $

(rysunek 5). Tak więc $a = y + z$ , $b = z + x$ , $c = x+y$ . Zauważmy teraz, że

$ x = |AB'| = r \cot(\alpha/2) \leq r \cot 30^\circ = \sqrt{3}r < 2r. $

Stąd, wobec oczywistego oszacowania $a \leq 2R$ , otrzymujemy nierówność

$ p = \frac{1}{2}(a + b + c) = x + y + z = a + x < a + 2r \leq 2R + 2r, $

którą mieliśmy udowodnić.

{\kom Uwaga:} Jak widać, zachodzi nierówność silniejsza od wymaganej:

$ p = a + x \leq a + \sqrt{3} r \leq 2R + \sqrt{3}r. $

Jest to faktycznie nierówność ostra, bo wykorzystane w niej oszacowania $x \leq \sqrt{3}r$ oraz $a\leq 2R$ nie mogą jednocześnie stać się równościami: pierwsze z nich przechodzi w równość tylko dla trójkąta równobocznego, a drugie - tylko dla trójkąta prostokątnego.

XLV OM - I - Zadanie 12

Zawody matematyczne:

XLV OM, 1993-1994

Etap:

Udowodnić, że sumy przeciwległych kątów dwuściennych czworościanu są równe wtedy i tylko wtedy, gdy sumy przeciwległych krawędzi tego czworościanu są równe.

Rozwiązanie

Dla czwórki niewspółpłaszczyznowych punktów $U$ , $V$ , $X$ , $Y$ będziemy oznaczać symbolem $|\measuredangle X(UV)Y|$ rozwartość wypukłego kąta dwuściennego utworzonego przez półpłaszczyzny o wspólnej krawędzi $UV$ , przechodzące przez punkty $X$ i $Y$ .

Niech będzie dany czworościan $ABCD$ . Wykażemy równoważność następujących stwierdzeń:

$ (1) \qquad |AB| + |CD| = |AC| + |BD|; $

$ (2) \qquad |\measuredangle C(AB)D| + |\measuredangle A(CD)B| = |\measuredangle B(AC)D| + |\measuredangle A(BD)C|. $

Z tej równoważności wyniknie teza zadania.

Dowód implikacji (1) $\Longrightarrow$ (2). Przyjmijmy, że okrąg wpisany w trójkąt $ABC$ ma środek $I$ i jest styczny do boków $AB$ , $AC$ , $BC$ odpowiednio w punktach $E$ , $F$ , $K$ , zaś okrąg wpisany w trójkąt $BCD$ ma środek $J$ i jest styczny do boków $BD$ , $CD$ , $BC$ odpowiednio w punktach $G$ , $H$ , $L$ (rysunek 6). Równość (1) przepisujemy w postaci

$ (3) \qquad |AE| + |BE| + |CH| + |DH| = |AF| + |CF| + |BG| + |DG|. $

Następujące odcinki stycznych do rozważanych okręgów mają równe długości:

$ \begin{array}{lll} |AE| = |AF|, &\quad |BE| = |BK|, &\quad |CF| = |CK|, \\ |DG| = |DH|, &\quad |BG| = |BL|, & \quad |CH| = |CL|. \end{array} $

Zatem pierwszy i ostatni składnik lewej strony równości (3) redukuje się z pierwszym i ostatnim składnikiem prawej strony, a równość między sumami pozostałych (środkowych) składników można przepisać jako

$ |BK| + |CL| = |BL| + |CK|. $

A ponieważ także $|BK| + |CK| = |BL| + |CL|\ (= |BC|)$ , zatem $|BK| = |BL|$ i $|CK| = |CL|$ , czyli punkt $L$ pokrywa się z $K$ .

Płaszczyzna $IJK$ jest prostopadła do prostej $BC$ . Leżące w tej płaszczyźnie proste, przechodzące przez punkty $I$ oraz $J$ i prostopadłe odpowiednio do płaszczyzn $ABC$ oraz $BCD$ , przecinają się w punkcie, który oznaczymy przez $S$ . Odcinki $IE$ , $IF$ , $IK$ są równej długości (jako promienie tego samego okręgu). Wobec tego trójkąty prostokątne $SIE$ , $SIF$ , $SIK$ są przystające i otrzymujemy równości

$ (4) \qquad |\measuredangle SEI| = |\measuredangle SFI|, \quad |SE| = |SF| = |SK|. $

W ten sam sposób z przystawania trójkątów $SJG$ , $SJH$ , $SJK$ wnosimy, że

$ (5) \qquad |\measuredangle SGJ| = |\measuredangle SHJ|, \quad |SG| = |SH| = |SK|. $

(Warto zauważyć, że punkt $S$ jest środkiem sfery stycznej do krawędzi $AB$ , $AC$ , $BC$ , $BD$ , $CD$ odpowiednio w punktach $E$ , $F$ , $K$ , $G$ , $H$ .)

Oznaczmy przez $P$ i $Q$ rzuty prostokątne punktu $S$ na płaszczyzny $ABD$ i $ACD$ (rysunek 7). Trójkąty prostokątne $SPE$ i $SPG$ mają wspólny bok $SP$ i równe przeciwprostokątne $SE$ i $SG$ (odcinki tej samej długości, co $SK$ ; por. (4), (5)); są więc przystające i zachodzi równość kątów

$ (6) \qquad |\measuredangle SEP| = |\measuredangle {SGP}|. $

Analogiczne rozumowanie pokazuje, że

$ (7) \qquad |\measuredangle SFQ| = |\measuredangle SHQ|. $

Punkty $E$ , $F$ , $G$ , $H$ są odpowiednio rzutami prostokątnymi punktu $S$ na krawędzie $AB$ , $AC$ , $BD$ , $CD$ (rysunki 6 i 7). Tak więc:
\begin{center}
punkty $S$ , $E$ , $P$ , $I$ leżą w płaszczyźnie prostopadłej do $AB$ ;\\
punkty $S$ , $F$ , $Q$ , $I$ leżą w płaszczyźnie prostopadłej do $AC$ ;\\
punkty $S$ , $G$ , $P$ , $J$ leżą w płaszczyźnie prostopadłej do $BD$ ;\\
punkty $S$ , $H$ , $Q$ , $J$ leżą w płaszczyźnie prostopadłej do $CD$ .\\
\end{center}
Stąd (rysunek 8) wynika pierwsza z napisanych poniżej równości; a pozostałe wynikają z niej przez analogię:

$ \begin{split} &|\measuredangle C (AB)D| = |\measuredangle IEP| = |\measuredangle IES| + |\measuredangle SEP|,\\ &|\measuredangle A (CD)B| = |\measuredangle QHJ| = |\measuredangle QHS| + |\measuredangle SHJ|,\\ &|\measuredangle B (AC)D| = |\measuredangle IFQ| = |\measuredangle IFS| + |\measuredangle SFQ|,\\ &|\measuredangle A (BC)D| = |\measuredangle PGJ| = |\measuredangle PGS| + |\measuredangle SGJ|. \end{split} $

Dowodzona równość (2) jest teraz bezpośrednim wnioskiem ze związków (4), (5), (6), (7). Implikacja (1) $\Longrightarrow$ (2) jest więc wykazana.

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

(8) W każdym czworościanie suma dwóch kątów płaskich przy dowolnym wierzchołku jest większa od trzeciego kąta płaskiego przy tym wierzchołku.

Innymi słowy, ,,odległość'' między półprostymi o wspólnym początku, mierzona rozwartością kąta między nimi, spełnia ,,warunek trójkąta'': trzy półproste o wspólnym początku wyznaczają, parami, trzy takie kąty, z których każdy jest mniejszy od sumy pozostałych dwóch.

(To proste twierdzenie pojawiło się na przykład jako lemat w rozwiązaniu zadania 5 z zawodów II stopnia XXIV Olimpiady Matematycznej; oczywiście Czytelnik znajdzie dowód w publikacji: XXIV Olimpiada Matematyczna. Sprawozdanie Komitetu Głównego, Warszawa 1974, str. 66 - ale zachęcamy raczej do samodzielnego przeprowadzenia tego dowodu; jest to nietrudnym ćwiczeniem.)

Dowód implikacji (2) $\Longrightarrow$ (1). Przypuśćmy, że zachodzi równość (2) i nie zachodzi równość (1); niech na przykład

$ (9) \qquad |AB| + |CD|> |AC| + |BD| $

(przy założeniu nierówności przeciwnej wystarczy oczywiście odpowiednio zmienić oznaczenia).

Weźmy pod uwagę ruchomy punkt $X$ przesuwający się wzdłuż krawędzi $CD$ . Gdy $X$ pokrywa się z $C$ , różnica $|BX|-|CX| = |BC|$ jest większa niż $|AB|-|AC|$ (nierówność dla boków trójkąta $ABC$ ). Gdy $X$ pokrywa się z $D$ , różnica $|BX|-|CX| = |BD|-|CD|$ jest mniejsza niż $|AB|- |AC|$ (co wynika z (9)). Zatem istnieje takie położenie punktu $X$ , przy którym różnica $|BX|-|CX|$ równa się $|AB| - |AC|$ , czyli

$ |AB| + |CX| = |AC| + |BX|; $

w dalszym ciągu $X$ oznacza ustalony punkt odcinka $CD$ spełniający tę równość. Jest ona dla czworościanu $ABCX$ analogiczna do równości (1). Na mocy pierwszej części dowodu zachodzi analogiczna do (2) równość sum kątów dwuściennych:

$ (10) \qquad |\measuredangle C(AB)X| + |\measuredangle A(CX)B| = |\measuredangle B(AC)X| + |\measuredangle A(BX)C|. $

Skoro punkt $X$ leży na odcinku $CD,$ zatem (rysunek 9)

$ (11) \qquad \begin{array}{c} |\measuredangle C(AB)D| = |\measuredangle C(AB)X| + |\measuredangle D(AB)X|,\\ |\measuredangle B(AC)D| = |\measuredangle B(AC)X|, \quad |\measuredangle A(BD)C| = |\measuredangle A(BD)X|,\\ |\measuredangle A(CD)B| = |\measuredangle A(CX)B| \end{array} $

oraz

$ (12) \qquad |\measuredangle A(BX)C| = 180^\circ-|\measuredangle A(BX)D|. $

Wstawiając związki (11) do równości (2), a związek (12) do (10), otrzymujemy równości

$ |\measuredangle C(AB)X| + |\measuredangle D(AB)X| + |\measuredangle A(CX)B| = |\measuredangle B(AC)X| + |\measuredangle A(BD)X| $

oraz

$ |\measuredangle C(AB)X| + |\measuredangle A(CX)B| = |\measuredangle B(AC)X| + 180^\circ -|\measuredangle A(BX)D|, $

które po odjęciu stronami dają zależność

Niech $Z$ będzie dowolnie wybranym punktem wewnątrz czworościanu $ABDX$ . Oznaczmy przez $U$ , $V$ , $W$ rzuty prostokątne punktu $Z$ odpowiednio na płaszczyzny $BDX$ , $BAX$ , $BAD$ (rysunek 9). Rzutując punkty $V$ i $W$ na prostą $AB$ otrzymujemy ten sam punkt $Y$ (rzut punktu $Z$ na $AB$ ). W czworokącie $ZVYW$ kąty przy wierzchołkach $V$ i $W$ są proste. Tak więc

$ |\measuredangle D(AB)X| = |\measuredangle VYW| = 180^\circ-|\measuredangle VZW|. $

Analogicznie pokazujemy, że

Po uwzględnieniu tych równości związek (13) przybiera postać

$ |\measuredangle VZW| = |\measuredangle UZW| + |\measuredangle UZV|. $

A to już jest sprzeczność: skoro $ABDX$ jest (niezdegenerowanym) czworościanem, zatem punkty $Z$ , $U$ , $V$ , $W$ są niewspółpłaszczyznowe i $ZUVW$ jest (niezdegenerowanym) czworościanem. Zgodnie z twierdzeniem (8), suma kątów $UZW$ i $UZV$ powinna być ostro większa od kąta $VZW$ . Sprzeczność kończy dowód implikacji (2) $\Longrightarrow$ (1).

Dowód tezy zadania. Oznaczmy długości krawędzi danego czworościanu $ABCD$ , jak następuje:

$ |AB| = a_1, \ |AC| = a_2, \ |AD| = a_3, \ |CD| = b_1, \ |BD| = b_2, \ |BC| = b_3 $

i przyjmijmy, że kąt dwuścienny utworzony przez ściany o wspólnej krawędzi $a_i$ ma miarę $\alpha_i$ , a kąt dwuścienny utworzony przez ściany o wspólnej krawędzi $b_i$ ma miarę $\beta_i$ . Udowodniliśmy równoważność między warunkami (1) i (2), czyli równoważność

$ (14) \qquad (a_1+b_1 =a_2 + b_2) \Longleftrightarrow (\alpha_1 +\beta_1 = \alpha_2 + \beta_2) . $

Stąd - przez analogię - wnioskujemy, że słuszne są także równoważności

$ (15) \qquad (a_2 + b_2 =a_3 + b_3) \Longleftrightarrow (\alpha_2 + \beta_2 = \alpha_3 + \beta_3 ) , $

$ (16) \qquad (a_1 + b_1 =a_3 + b_3) \Longleftrightarrow (\alpha_1+\beta_1 = \alpha_3+\beta_3). $

Zespół zdań (14), (15), (16) implikuje równoważność

$ (17) \qquad \begin{split} &(a_i + b_i = a_j + b_j \textrm{ dla każdej pary różnych numerów } i,j) \Longleftrightarrow\\ \Longleftrightarrow\ & (\alpha_i + \beta_i = \alpha_j + \beta_j \textrm{ dla każdej pary różnych numerów } i,j) \end{split} $

( $i,j \in \{1,2,3\}$ ), która jest tezą zadania.

Uwaga 2: W rozwiązaniu wykazaliśmy więcej niż wymagało zadanie: wykazaliśmy prawdziwość samej równoważności (14) (angażującej tylko dwie pary przeciwległych krawędzi i przeciwległych kątów dwuściennych), nie korzystając z zależności logicznych między warunkami figurującymi w (15) i (16). Jak zauważyliśmy przed chwilą, zdania (15) i (16), i w konsekwencji (17), są już prostymi stąd wnioskami.