XLVI OM

XLVI Olimpiada Matematyczna

Opracowanie rozwiązań: Marcin E. Kuczma

XLVI OM - I etap

I etap XLVI Olimpiady Matematycznej

XLVI OM - I - Zadanie 1

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

Wyznaczyć wszystkie pary $(x,y)$ liczb naturalnych, dla których liczby $\frac{x+1}{y}$ oraz $\frac{y+1}{x}$ są naturalne.

Rozwiązanie

Niech $(x,y)$ będzie jedną z szukanych par. Liczby naturalne $y \geq 1$ oraz $x \geq 1$ są odpowiednio dzielnikami liczb $x + 1$ oraz $y + 1$ . Zatem iloczyn $xy$ jest dzielnikiem iloczynu $(x + 1)(y+ 1)$ , równego sumie $xy + x + y + 1$ . Jest więc też dzielnikiem sumy $x + y + 1$ , a zatem zachodzi nierówność $xy \leq x + y + 1$ , czyli $(x-1)(y -1) \leq 2$ . Wartość iloczynu $(x-1)(y-1)$ może być w takim razie równa tylko $2$ , $1$ lub $0$ .

W pierwszym przypadku jeden z czynników $(x - 1)$ i $(y- 1)$ jest równy $2$ , a drugi $1$ , czyli para $(x,y)$ jest jedną z par $(3,2)$ i $(2,3)$ .

W drugim przypadku mamy $x -1 = y -1 = 1$ , czyli $x = y = 2$ . Jednak para $(x,y) = (2,2)$ nie spełnia warunku zadania (iloraz $3/2$ nie jest liczbą naturalną).

W trzecim przypadku co najmniej jeden z czynników $(x - 1)$ i $(y- 1)$ jest zerem. Jeśli na przykład $y - 1 = 0$ , czyli $y = 1$ , to liczba $x$ , jako dzielnik sumy $y + 1 = 2$ , musi być równa $1$ lub $2$ ; tak więc $x = y = 1$ lub $y = 1$ , $x = 2$ lub - przez symetrię - $x = 1$ , $y = 2$ .

Rekapitulując, widzimy, że tylko następujące pary $(x,y)$ mogą spełniać postawione warunki: $(3,2)$ , $(2,3)$ , $(1,1)$ , $(2,1)$ , $(1,2)$ - i istotnie je spełniają; sprawdzenie jest natychmiastowe.

XLVI OM - I - Zadanie 2

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

Dana jest liczba naturalna $n \geq 2$ . Rozwiązać układ równań

$ \begin{cases} x_1|x_1| = x_2|x_2| + (x_1-1)|x_1-1| \\ x_2|x_2| = x_3|x_3| + (x_2-1)|x_2-1| \\ \ldots \ldots \ldots \ldots\\ x_n|x_n| = x_1|x_1| + (x_n-1)|x_1-1| \\ \end{cases} $

Rozwiązanie

Załóżmy, że liczby $x_1, x_2, \ldots, x_n$ spełniają podany układ równań. Przepisujemy ten układ w postaci

$ (1) \qquad x_{i+1} | x_{i+i}| = x_i |x_i|-(x_i-1)|x_i-1| \quad \textrm{dla} \quad i = 1,\ldots,n, $

przyjmując, że niewiadome są numerowane cyklicznie ( $x_{n+1} = x_1$ ). Dodajemy wszystkie równania stronami, redukujemy występujące po obu stronach składniki $x_1 |x_1|$ , $x_2 |x_2|$ , $\ldots$ , $x_n|x_n|$ , i otrzymujemy równość

$ (2) \qquad \sum_{i=1}^n (x_i-1)|x_i-1| =0. $

Zauważmy, że prawa strona $i$ -tego równania układu (1) ma postać różnicy $\Delta_i = f(x_i)- f(x_i-1)$ , gdzie

$ f(x)=x|x| = \left\{ \begin{array}{ccl} x^2 & \textrm{dla} & x \geq 0,\\ -x^2 & \textrm{dla} & x <0. \end{array} \right. $

Tak określona funkcja $f$ jest ściśle rosnąca. W takim razie każda różnica $\Delta_i$ , jest dodatnia, czyli prawe strony wszystkich równań (1) są liczbami dodatnimi. Zatem i lewe strony muszą być liczbami dodatnimi, skąd wniosek, że wszystkie liczby $x_1,x_2,\ldots,x_n$ są dodatnie.

Gdyby wszystkie były mniejsze od $1$ , wówczas wszystkie składniki sumy (2) byłyby liczbami ujemnymi, wbrew temu, że wartość sumy wynosi $0$ . Zatem pewna liczba $x_j$ spełnia nierówność $x_j \geq 1$ , a więc $j$ -te równanie układu (1) możemy przepisać jako $x^2_{j+1} = x^2_j- (x_j-1)^2$ . Stąd

$ x_{j+1} = \sqrt{x_j^2-(x_j-1)^2} = \sqrt{2x_j -1} \geq 1. $

Powtarzając cyklicznie to samo rozumowanie stwierdzamy kolejno, że liczby $x_{j+1}, x_{j+2}, \ldots, x_n, x_1, \ldots, x_j$ są większe lub równe $1$ . Warunek (2) implikuje wobec tego równość

$ \sum_{i=1}^n (x_i-1)^2 = 0. $

Zatem $x_1 = x_2 = \ldots = x_n= 1$ . Układ liczb $(x_1,\ldots,x_n) = (1,\ldots,1)$ spełnia układ równań (1) i jest jego jedynym rozwiązaniem.

XLVI OM - I - Zadanie 3

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

Czworokąt o bokach $a$ , $b$ , $e$ , $d$ jest wpisany w okrąg o promieniu $R$ . Wykazać, że jeżeli $a^2 + b^2 + c^2 + d^2= 8R^2$ , to w czworokącie tym jeden z kątów jest prosty lub przekątne są prostopadłe.

Rozwiązanie

Przypuśćmy, że żaden z kątów wewnętrznych rozważanego czworokąta $ABCD$ nie jest prosty; należy wykazać, że wówczas $AC \bot BD$ . Czworokąt jest wpisany w okrąg, a zatem $|\measuredangle DAB| + | \measuredangle BCD| = 180^\circ$ . Nie tracąc ogólności przyjmijmy, że kąt $DAB$ jest ostry, a kąt $BCD$ jest rozwarty. Wobec tego średnica $CE$ okręgu opisanego na trójkącie $BCD$ przecina bok $BD$ ; stąd zaś wynika, że punkty $A$ i $E$ leżą po tej samej stronie prostej $BD$ (rysunek 1); zatem kąty wpisane $DAB$ i $DEB$ , oparte na łuku $BCD$ , mają jednakową miarę:

$ | \measuredangle DEB| = | \measuredangle DAB | = \alpha < 90^\circ. $

Punkt $A$ nie pokrywa się z $E$ (gdyby się pokrywał, kąty $ABC$ i $CDA$ byłyby proste, wbrew uczynionemu założeniu). Natomiast kąty $EBC$ i $CDE$ oczywiście są proste, więc na mocy twierdzenia Pitagorasa

$ |EB|^2 + |BC|^2 = |CE|^2 = 4R^2, \quad |CD|^2 + |DE|^2 = |CE|^2 = 4R^2, $

i w myśl warunku zadania

$ |AB|^2 + |BC|^2 + |CD|^2 + |DA|^2 = 8R^2 = |EB|^2 + |BC|^2 + |CD|^2 + |DE|^2. $

Stąd

$ |AB|^2 + |AD|^2 = |EB|^2 + |ED|^2. $

Do trójkątów $ABD$ i $EBD$ stosujemy wzór Carnota:

$ |AB|^2 + |AD|^2-|BD|^2 = 2 \cdot |AB| \cdot |AD| \cdot \cos \alpha, $

$ |EB|^2 + |ED|^2-|BD|^2 = 2 \cdot |EB| \cdot |ED| \cdot \cos \alpha. $

Lewe strony otrzymanych równości są równe; a ponieważ kąt $\alpha$ jest ostry, zatem $\cos \alpha \ne 0$ i z przyrównania prawych stron wynika równość iloczynów $|AB| \cdot |AD|$ oraz $|EB| \cdot |ED|$ . Stąd

$ \textrm{pole}(ABD) = \frac{1}{2} \cdot |AB| \cdot |AD| \cdot \sin \alpha = \frac{1}{2} \cdot |EB| \cdot |ED| \cdot \sin \alpha = \textrm{pole}(EBD); $

to znaczy, że punkty $A$ i $E$ leżą w jednakowej odległości od prostej $BD$ (po tej samej jej stronie); tak więc $AE||BD$ . Jednocześnie $AE \bot AC$ (kąt $CAE$ , oparty na średnicy $CE$ , jest prosty). Zatem, ostatecznie, $AC \bot BD$ .

XLVI OM - I - Zadanie 4

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

W pewnej szkole 64 uczniów bierze udział w pięciu olimpiadach przedmiotowych. W każdej z tych olimpiad uczestniczy co najmniej 19 uczniów tej szkoły; żaden z nich nie jest uczestnikiem więcej niż trzech olimpiad. Udowodnić, że jeżeli każde trzy olimpiady mają wspólnego uczestnika, to pewne dwie mają ich co najmniej pięciu.

Rozwiązanie

Oznaczmy olimpiady symbolami $A$ , $B$ , $C$ , $D$ , $E$ . Wyobraźmy sobie tabelę mającą $64$ wierszy, odpowiadających uczniom, oraz $25$ kolumn opatrzonych następującymi nagłówkami:

$ A, B, C, D, E,\quad AB, AC, AD, AE, BC, BD, BE, CD, CE, DE, $

$ ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, CDE. $

W kolumnie z nagłówkiem $X$ , reprezentującej olimpiadę $X \in \{A,B,C,D,E\}$ , w rubryce każdego ucznia wpisujemy $1$ , jeśli uczestniczy on w tej olimpiadzie, a $0$ jeśli nie uczestniczy. W kolumnie $XY$ piszemy $-1$ , jeśli dany uczeń uczestniczy w obu olimpiadach $X$ i $Y$ , a $0$ w przeciwnym przypadku. Wreszcie w kolumnie $XYZ$ piszemy znów $1$ , jeśli uczeń uczestniczy we wszystkich trzech olimpiadach $X$ , $Y$ i $Z$ , a $0$ w przeciwnym przypadku.

Suma liczb w każdej z pierwszych pięciu kolumn $(A, B, C, D, E)$ jest większa lub równa $19$ (bo w każdej olimpiadzie uczestniczy co najmniej $19$ uczniów). Sumy liczb w następnych dziesięciu kolumnach ( $AB$ , $AC$ , $\ldots$ , $DE$ ) oznaczmy kolejno przez $s_1,s_2,\ldots,s_{10}$ . Jeżeli wreszcie, zgodnie z założeniem, każde trzy olimpiady mają wspólnego uczestnika, to w każdej z ostatnich dziesięciu kolumn $(ABC, \ldots, CDE)$ jest co najmniej jedna jedynka, więc suma liczb w każdej z tych kolumn jest większa lub równa $1$ . Wobec tego suma wszystkich liczb w tabeli - oznaczmy ją przez $s$ - spełnia oszacowanie

$ (1) \qquad \quad s \geq 5 \cdot 19 + (s_1+s_2+s_3 + s_4 + s_5+s_6 + s_7 + s_8+s_9 + s_{10}) + 10 \cdot 1. $

Zauważmy teraz, że suma liczb w każdym wierszu wynosi $1$ . Istotnie: jeśli uczeń uczestniczy w dokładnie jednej olimpiadzie, to w jego wierszu znajduje się jedna plus jedynka, poza tym zera; jeśli uczestniczy w dokładnie dwóch olimpiadach ( $X$ i $Y$ ), to są tam dwie plus jedynki (w kolumnach $X$ i $Y$ ) oraz jedna minus jedynka (w kolumnie $XY$ ); a jeśli uczestniczy w dokładnie trzech olimpiadach ( $X$ , $Y$ , $Z$ ), to mamy cztery plus jedynki (w kolumnach $X$ , $Y$ , $Z$ i $XYZ$ ) oraz trzy minus jedynki (w kolumnach $XY$ , $XZ$ , $YZ$ ). Wobec tego suma wszystkich liczb w tabeli wynosi $64$ .

Podstawiając $s = 64$ do nierówności (1) dostajemy oszacowanie

$ s_1+s_2 + s_3+s_4 + s_5+s_6+s_7 + s_8 + s_9 + s_{10} \leq 64 - (5 \cdot 19 + 10 \cdot 1) = -41. $

Wynika z niego, że co najmniej jedna z liczb $s_i$ jest mniejsza od $-4$ , czyli spełnia nierówność $s_i \leq -5$ (są to bowiem liczby całkowite). To znaczy, że w kolumnie, której wyrazy sumują się do wartości $s_i$ , jest co najmniej pięć minus jedynek. To znaczy, że para olimpiad, reprezentowana przez tę kolumnę, ma co najmniej pięciu wspólnych uczestników.

Uwaga. Gdyby odrzucić założenie, że żaden uczeń nie jest uczestnikiem więcej niż trzech olimpiad, wówczas należałoby rozszerzyć tabelę o dalsze kolumny: pięć kolumn reprezentujących czwórki olimpiad ( $ABCD$ , $ABCE$ , $ABDE$ , $ACDE$ , $BCDE$ ) oraz jedną kolumnę odpowiadającą pełnej piątce olimpiad ( $ABCDE$ ).

W kolumnie czwórkowej $TXYZ$ , w rubryce każdego ucznia, wpisujemy znów $-1$ , jeśli uczestniczy on we wszystkich czterech olimpiadach $T$ , $X$ , $Y$ , $Z$ , a $0$ jeśli nie uczestniczy; wreszcie w ostatniej kolumnie piszemy $1$ , jeśli uczeń uczestniczy we wszystkich pięciu olimpiadach, a $0$ w przeciwnym przypadku. W każdym wierszu tak rozszerzonej tabeli suma liczb nadal wynosi $1$ . Można się o tym przekonać, rozpatrując pominięte wcześniej dwie sytuacje: uczeń uczestniczy w dokładnie czterech olimpiadach oraz uczeń uczestniczy we wszystkich pięciu olimpiadach. Suma liczb w całej tabeli będzie więc nadal równa liczbie wierszy, czyli liczbie wszystkich uczniów, biorących udział w co najmniej jednej olimpiadzie.

Jeśli więc zbiór wszystkich uczniów (z owej szkoły), którzy uczestniczą w olimpiadzie $A$ , oznaczymy tym samym symbolem $A$ , i podobne znaczenie nadamy symbolom $B$ , $C$ , $D$ i $E$ , to w wyniku przeprowadzonego rozumowania otrzymamy równość:

$ \begin{split} | A \cup B \cup C \cup D \cup E | = & (|A| + |B| + |C| + |D| + |E|)-\\ & - (|A \cap B| + \ldots + |D \cap E|) +\\ & + (|A \cap B \cap C| + \ldots + |C \cap D \cap E|) -\\ & - (|A \cap B \cap C \cap D)| + \ldots + |B \cap C \cap D \cap E|) +\\ & + |A \cap B \cap C \cap D \cap E| \end{split} $

(przez $|X|$ oznaczamy liczbę elementów zbioru skończonego $X$ ; w nawiasach w drugiej, trzeciej i czwartej linijce powyższego wzoru znajdują się składniki odpowiadające wszystkim parom, wszystkim trójkom i wszystkim czwórkom zbiorów z rodziny $\{A,B,C,D,E\}$ ). Oczywiście szkoła, uczniowie, olimpiady — to tylko barwne przybranie dla treści matematycznej. Otrzymana równość zachodzi dla dowolnych pięciu zbiorów skończonych $A$ , $B$ , $C$ , $D$ , $E$ .

Analogiczną równość można napisać dla dowolnego skończonego układu zbiorów skończonych; dla dwóch zbiorów ma ona prostą i dobrze znaną postać: $|A \cup B| = |A| + |B| - | A \cap B |$ ; ogólnie zaś, dla $n$ zbiorów, jej zapis jest trochę trudno czytelny:

$ (2) \qquad \quad |A_1 \cup \ldots \cup A_n| = \sum_{k=1}^n \left((-1)^{k+1} \sum_{1 \leq i_1 < \ldots < i_k \leq n} |A_{i_1} \cap \ldots \cap A_{i_k}|\right). $

Jest to tak zwany wzór włączeń i wyłączeń (inaczej: formuła sita). Poprzednie rozumowanie stanowi jego dowód dla $n = 5$ ; w podobny sposób można go udowodnić dla dowolnej liczby naturalnej $n$ . (Trzeba rozważać tabelę składającą się z $2^n$ kolumn, podzieloną na bloki złożone z ${{n}\choose{1}}$ , ${{n}\choose{2}}$ , \ldots, ${{n}\choose{n}}$ kolumn, i wpisywać w kolejnych blokach, na przemian, jedynki i minus jedynki, w zależności od tego, czy element reprezentowany przez poszczególny wiersz tabeli należy do wszystkich $k$ zbiorów, odpowiadających danej kolumnie, czy nie należy). Suma liczb w każdym wierszu takiej tabeli stale wynosi $1$ . Proponujemy, by Czytelnik spróbował zastanowić się, dlaczego tak jest. (Wskazówka: ${{m}\choose{1}} - {{m}\choose{2}} +\ldots+(-1)^{m+1} {{m}\choose{m}} =1$ .)

Dowód wzoru (2) można także przeprowadzić przez indukcję względem $n$ ; również i taki dowód pozostawiamy Czytelnikowi jako ciekawe ćwiczenie.

XLVI OM - I - Zadanie 5

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

Dane są liczby dodatnie $a$ , $b$ . Wykazać równoważność zdań:

$ (1) \qquad \sqrt{a} + 1 > \sqrt{b}, $

$ (2) \qquad ax + \frac{x}{x-1} \quad \text{dla każdego } x>1. $

Rozwiązanie

Załóżmy prawdziwość zdania (2). Podstawiając $x = 1+\frac{1}{\sqrt{a}}$ otrzymujemy nierówność

$ a\left(1 + \frac{1}{\sqrt{a}}\right) + \left(1 + \frac{1}{\sqrt{a}}\right)\sqrt{a} > b, $

czyli $a + \sqrt{a} + \sqrt{a} + 1 > b$ , czyli jeszcze inaczej:

$ (\sqrt{a}+1)^2 > b. $

Ponieważ $b$ jest liczbą dodatnią, wynika stąd warunek (1).

Na odwrót, z warunku (1) wyprowadzamy (2), jak następuje. Niech $x$ będzie dowolną liczbą większą od $1$ . Oznaczmy różnicę $x - 1$ przez $t$ ; jest to liczba dodatnia. Przekształcamy lewą stronę nierówności w warunku (2):

$ \begin{split} ax + \frac{x}{x-1} = & a(t + 1)+ \frac{t+1}{t} = \frac{at^2+at + t + 1}{t} =\\ = & \frac{(t\sqrt{a}-1)^2}{t} + (\sqrt{a} + 1)^2 \geq (\sqrt{a}+1)^2. \end{split} $

Jeśli spełniony jest warunek (1), to liczba $(\sqrt{a}+1)^2$ jest większa od $b$ , więc na mocy powyższego oszacowania wartość wyrażenia $ax + \frac{x}{x-1}$ jest większa od $b$ . Liczba $x > 1$ była wybrana dowolnie; mamy więc zdanie (2).

Wykazane implikacje (2) $\Rightarrow$ (1) oraz (1) $\Rightarrow$ (2) składają się na dowód żądanej równoważności.

XLVI OM - I - Zadanie 6

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

Wewnątrz trójkąta $ABC$ obrano punkt $P$ . Proste $AP$ , $BP$ , $CP$ przecinają boki $BC$ , $CA$ , $AB$ odpowiednio w punktach $A'$ , $B'$ , $C'$ . Przyjmijmy: $u=|AP|:|PA'|$ , $v=|BP|:|PB'|$ , $w=|CP|:|PC'|$ . Wyrazić iloczyn $uvw$ przez sumę $u+v+w$ .

Rozwiązanie

Oznaczmy przez $S$ pole trójkąta $ABC$ , a przez $S_a$ , $S_b$ , $S_c$ - odpowiednio pola trójkątów $PBC$ , $PCA$ , $PAB$ . Niech odcinek $PD$ będzie wysokością w trójkącie $PBC$ , a odcinek $AE$ - wysokością w trójkącie $ABC$ (rysunek 3). Z podobieństwa trójkątów $AEA'$ i $PDA'$ wynika proporcja $|AE|:|PD| = |A'A|:|A'P|$ . Wobec tego

$ \frac{S}{S_a} = \frac{\frac{1}{2}|BC|\cdot |AE|}{\frac{1}{2}|BC|\cdot |PD|}= \frac{|AE|}{|PD|} = \frac{|A'A|}{|A'P|} = \frac{|A'P|+|PA|}{|A'P|}= 1+ \frac{|PA|}{|A'P|} = 1+u. $

Tak więc

$ \frac{S_a}{S} = \frac{1}{1+u}, \quad \textrm{i analogicznie} \quad \frac{S_b}{S} = \frac{1}{1+v}, \quad \frac{S_c}{S} = \frac{1}{1+w}. $

Otrzymujemy równość

$ \begin{split} 1 = & \frac{S_a + S_b + S_c}{S} = \frac{1}{1+u} + \frac{1}{1+v} + \frac{1}{1+w} = \\ = & \frac{(1 + v)(1 + w) + (1 + w)(1 + u) + (1 + u)(1 + v)}{(1 + u)(1 + v)(1 + w)}= \\ = & \frac{3 + 2(u + v + w) + (vw + wu + uv)}{1 + (u + v + w) + (vw + wu + uv) + uvw}. \end{split} $

Licznik musi być równy mianownikowi. Daje to szukany związek:

$ uvw = u + v + w + 2. $

Uwaga. Stosunki $p=S_a \colon S$ , $q=S_b \colon S$ , $r=S_c \colon S$ wyznaczają położenie punktu $P$ jednoznacznie. Mówiąc wyraźniej: dla każdej trójki liczb dodatnich $p$ , $q$ , $r$ o sumie równej $1$ istnieje dokładnie jeden punkt $P$ leżący wewnątrz danego trójkąta $ABC$ , dla którego stosunki pól trójkątów $PBC$ , $PCA$ , $PAB$ do pola trójkąta $ABC$ są równe odpowiednio $p$ , $q$ , $r$ . Liczby $p$ , $q$ , $r$ noszą nazwę współrzędnych barycentrycznych punktu $P$ ; nazwa ta ma proste uzasadnienie fizyczne: punkt $P$ jest środkiem ciężkości układu mas punktowych $p$ , $q$ , $r$ umieszczonych w wierzchołkach $A$ , $B$ , $C$ .

XLVI OM - I - Zadanie 7

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

(a) Rozstrzygnąć, czy istnieje funkcja różniczkowalna $f: \mathbb{R} \to \mathbb{R}$ nie równa tożsamościowo zeru, spełniająca warunki:

$ 2f(f(x)) = f(x) \geq 0 \quad \text{ dla } x\in \mathbb{R} $

(b) Rozstrzygnąć, czy istnieje funkcja różniczkowalna $f: \mathbb{R} \to \mathbb{R}$ nie równa tożsamościowo zeru, spełniająca warunki:

$ -1 \leq 2f(f(x)) = f(x) \leq 1 \quad \text{ dla } x\in \mathbb{R} $

Rozwiązanie

(a) Nie ma takiej funkcji. Dowód: Przypuśćmy, że funkcja $f$ spełnia podane warunki. Nie jest tożsamościowo równa zeru, więc istnieje $x_0 \in \mathbb{R}$ , dla którego $f(x_0)>0$ . Przyjmijmy

$ x_n = f(x_{n-1}) \quad \textrm{dla} \quad n = 1,2,3,\ldots. $

Z równości $2f(f(x_{n-1})) = f(x_{n-1})$ dostajemy wniosek, że

$ 2x_{n+1} = x_n \quad \textrm{dla} \quad n = 1,2,3,\ldots. $

Stąd przez oczywistą indukcję

$ x_n = x_1/2^{n-1} \quad \textrm{dla} \quad n = 1,2,3,\ldots. $

Ciąg ( $x_n$ ) jest więc zbieżny do zera. Ponieważ $x_1 = f(x_0) > 0$ , zatem wszystkie wyrazy $x_n$ są (dla $n \geq 1$ ) liczbami dodatnimi.

Wobec ciągłości funkcji $f$ , wzór $x_n = f(x_{n-1})$ daje w granicy (przy $n$ dążącym do nieskończoności) równość $f(0) = 0$ . Funkcja $f$ przyjmuje (z założenia) tylko wartości nieujemne, a zatem wartość $0$ w punkcie $x = 0$ jest wartością minimalną. Wobec założenia różniczkowalności (na całym zbiorze $\mathbb{R}$ , więc w szczególności w punkcie $0$ ) pochodna $f'(0)$ musi być równa zeru. Ale pochodna ta jest jednocześnie granicą ciągu ilorazów różnicowych

$ \frac{f(x_n)-f(0)}{x_n-0} = \frac{f(x_n)}{x_n} = \frac{x_{n+1}}{x_n} =\frac{1}{2}. $

Jest to, jak widać, ciąg stały, zbieżny do liczby $1/2$ , różnej od zera. Otrzymana sprzeczność kończy dowód.

(b) Takie funkcje istnieją. Przykład:

$ (1) \qquad f(x)=\left\{ \begin{array}{ccl} -1-\dfrac{1}{2x} & \textrm{dla} & x<-1,\\ \dfrac{x}{2} & \textrm{dla} & -1 \leq x \leq 1, \\ 1-\dfrac{1}{2x} & \textrm{dla} & x>1. \end{array} \right. $

Jest to funkcja nieparzysta: $f(-x) = -f(x)$ . Wewnątrz każdego z przedziałów $(-\infty;\ -1)$ , $(-1;\ 1)$ , $(1;\ \infty)$ jest ona różniczkowalna. Wykażemy, że jest też różniczkowalna w punktach $1$ oraz $-1$ (i tym samym jest różniczkowalna w zbiorze wszystkich liczb rzeczywistych).

Obliczamy iloraz różnicowy dla prawostronnego oraz dla lewostronnego otoczenia punktu $x_0 = 1$ :

$ \frac{f(x)-f(1)}{x-1} = \left\{ \begin{split} \frac{(1-\frac{1}{2x})-\frac{1}{2}}{x-1} & = \frac{1}{2x} \quad \textrm{dla} \quad x>1,\\ \frac{\frac{x}{2}-\frac{1}{2}}{x-1} & = \frac{1}{2} \quad \ \ \textrm{dla} \quad -1<x<1. \end{split} \right. $

Przy $x$ dążącym do $1$ oba uzyskane wyrażenia dążą do granicy $1/2$ , co oznacza, że w punkcie $1$ obie pochodne jednostronne istnieją i są równe; istnieje więc pochodna $f'(1)$ (jej wartość wynosi $1/2$ , co dla dalszego rozumowania nie ma znaczenia). Stąd, wobec nieparzystości funkcji $f$ , wynika istnienie pochodnej $f'(-1)$ (także równej $1/2$ ). Tak więc $f$ jest funkcją różniczkowalną w całym zbiorze $\mathbb{R}$ .

Ze wzoru (1) określającego funkcję $f$ widać, że jest ona ściśle rosnąca w każdym z przedziałów $(-\infty;\ -1 \rangle$ , $\langle -1;\ 1 \rangle$ , $\langle 1;\ \infty)$ ; zatem, wobec ciągłości w punktach $-1$ i $1$ , funkcja ta jest rosnąca w całym zbiorze $\mathbb{R}$ . Granica funkcji $f$ przy $x \to -\infty$ równa się $-1$ , a granica przy $x \to \infty$ równa się $1$ . Wobec tego wszystkie wartości funkcji $f$ leżą w przedziale $(-1;\ 1)$ .

Weźmy dowolną liczbę rzeczywistą $x$ . Jak wykazaliśmy, $f(x)$ jest liczbą z przedziału $(-1;\ 1)$ , a więc spełnia nierówność

$ (2) \qquad \quad -1 \leq f(x) \leq 1. $

Przepisujemy odpowiedni fragment wzoru (1) (ze zmianą oznaczenia zmiennej):

$ (3) \qquad \quad f(y) = \frac{y}{2} \quad \textrm{dla}\quad y \in \langle -1;\ 1 \rangle. $

Podstawiamy $y = f(x)$ i otrzymujemy równość

$ (4) \qquad \quad f(f(x)) = \frac{f(x)}{2}. $

Liczba $x$ była wybrana dowolnie. Uzyskane związki (2) i (4) pokazują, że funkcja $f$ , określona wzorem (1), spełnia wszystkie postulowane warunki.

Uwaga. Ten przykład można rozmaicie modyfikować, otrzymując wiele innych przykładów. Narzucone warunki mówią tylko, że $f \colon \mathbb{R} \to \langle -1;\ 1 \rangle$ ma być funkcją różniczkowalną, spełniającą równość $f(y) = y/2$ dla wszystkich liczb $y$ , które są wartościami tej funkcji. Skoro zaś zbiór jej wartości jest podzbiorem przedziału $\langle -1;\ 1\rangle$ , warunek ten będzie automatycznie spełniony, jeśli będzie prawdziwe zdanie (3). Wystarczy więc funkcję określoną w przedziale $\langle -1;\ 1 \rangle$ wzorem (3) przedłużyć w dowolny sposób do funkcji określonej na całej prostej liczbowej, dbając jedynie o to, by była ona różniczkowalna (w szczególności w punktach sklejenia) oraz by jej wartości nie wychodziły poza przedział $\langle -1;\ 1\rangle$ .

XLVI OM - I - Zadanie 8

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

W ostrosłupie prawidłowym $n$ -kątnym kąty nachylenia ściany bocznej i krawędzi bocznej do płaszczyzny podstawy wynoszą odpowiednio $\alpha$ i $\beta$ . Udowodnić, że $\sin^2 \alpha - \sin^2 \beta \leq \tan ^2 \frac{\pi}{2n}$ .

Rozwiązanie

Przyjmijmy, że bok $n$ -kąta foremnego $A_1A_2\ldots A_n$ , będącego podstawą ostrosłupa, ma długość $2a$ . Niech $O$ będzie wspólnym środkiem koła opisanego na tym wielokącie oraz koła weń wpisanego; przyjmijmy, że promienie tych kół mają długości (odpowiednio) $R$ oraz $r$ . Wierzchołek ostrosłupa oznaczmy przez $S$ , a długość odcinka $OS$ (wysokość ostrosłupa) - przez $h$ .

Weźmy jedną z krawędzi podstawy - na przykład $A_1A_2$ - i oznaczmy przez $M$ jej środek. Niech $\varphi = | \measuredangle A_1OM| = | \measuredangle A_2OM| = \pi/n$ . Kąt dwuścienny między płaszczyzną podstawy (czyli płaszczyzną $A_1A_2O$ ) a płaszczyzną ściany bocznej $A_1 A_2S$ ma miarę taką, jak kąt płaski $OMS$ . Z przyjętych oznaczeń wynikają następujące zależności (rysunek 4):

$ (1) \qquad |\measuredangle OMS| = \alpha, \ |\measuredangle OA_1S| = \beta, \ \tan \alpha=\frac{|OS|}{|OM|} = \frac{h}{r}, \ \tan \beta = \frac{|OS|}{|OA_1|} = \frac{h}{R}, $

$ (2) \qquad \quad \cos \varphi = \frac{|OM|}{|OA_1|}=\frac{r}{R}, \quad \sin \varphi = \frac{|A_1M|}{|OA_1|} = \frac{a}{R}, \quad R^2=a^2+r^2; $

należy zaś wykazać, że

$ (3) \qquad \quad \sin^2 \alpha - \sin^2 \beta \leq \tan^2 \frac{\varphi}{2}. $

Przydatne będą zależności trygonometryczne:

$ (4) \qquad \quad \tan \frac{\varphi}{2} = \frac{\sin(\varphi/2)}{\cos(\varphi/2)}= \frac{2 \sin (\varphi/2) \cos (\varphi/2)}{2 \cos^2 (\varphi/2)}= \frac{\sin \varphi}{1+\cos \varphi}, $

$ (5) \qquad \quad \sin^2 \alpha = \frac{\cos^2 \alpha \cdot \tan^2 \alpha}{\cos^2 \alpha + \sin^2 \alpha} = \frac{\tan^2 \alpha}{1+\tan^2 \alpha}, \quad \sin^2 \beta = \frac{\tan^2 \beta}{1+\tan^2 \beta}. $

Korzystając ze wzorów (4) i (2) otrzymujemy równość

$ (6) \qquad \quad \tan^2 \frac{\varphi}{2} = \left( \frac{\sin \varphi}{1+ \cos \varphi} \right)^2 = \left( \frac{a/R}{1+ (r/R)} \right)^2 = \left( \frac{a}{R+r} \right)^2 = \frac{R^2-r^2}{(R+r)^2} = \frac{R-r}{R+r}; $

a na podstawie związków (5) i (1) mamy:

$ \begin{split} \sin^2 \alpha - \sin^2 \beta & =\frac{(h/r)^2}{1+(h/r)^2} - \frac{(h/R)^2}{1+(h/R)^2}=\\ &= \frac{h^2}{h^2+r^2} - \frac{h^2}{h^2+R^2} = \frac{h^2(R^2-r^2)}{(h^2+r^2)(h^2+R^2)}. \end{split} $

Stąd

$ (7) \qquad \quad \frac{\sin^2 \alpha - \sin^2 \beta}{\tan^2 (\varphi/2)} = \frac{h^2(R^2-r^2)}{(h^2+r^2)(h^2+R^2)} \cdot \frac{R+r}{R-r} = \frac{h^2(R+r)^2}{(h^2+r^2)(h^2+R^2)}. $

A ponieważ

$ \begin{split} (h^2+r^2) & (h^2 + R^2)-h^2(R + r)^2 =\\ & = (h^4+h^2(R^2+r^2) + R^2r^2)-h^2(R^2 + r^2+2Rr) = \\ & = h^4 + R^2r^2-2h^2Rr = (h^2 - Rr)^2 \geq 0, \end{split} $

zatem licznik ułamka otrzymanego po prawej stronie równości (7) jest nie większy niż mianownik. Wobec tego wartość ilorazu (7) nie przekracza $1$ ; tym samym nierówność (3) została wykazana.

XLVI OM - I - Zadanie 9

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

Niech $a$ i $b$ będą liczbami rzeczywistymi, których suma jest równa 1. Wykazać, że jeżeli $a^3$ i $b^3$ są liczbami wymiernymi, to $a$ i $b$ też są liczbami wymiernymi.

Rozwiązanie

Podnosimy równość $a + b = 1$ stronami do drugiej i trzeciej potęgi i otrzymujemy związki: $a^2 +2ab + b^2 = 1$ , czyli

$ (1) \qquad a^2 + b^2 = 1-2ab, $

oraz $a^3 + 3a^2b + 3ab^2 + b^3 = 1$ , czyli

$ (2) \qquad a^3 + b^3 = 1-3ab(a + b)= 1-3ab. $

Jeśli więc liczby $a^3$ oraz $b^3$ są wymierne, to z równości (2) wynika, że iloczyn $ab = (1-a^3-b^3)/3$ jest liczbą wymierną, i wobec równości (1) także suma $a^2 + b^2$ jest liczbą wymierną. W takim razie również liczba $a^2 + ab + b^2$ jest wymierna - a przy tym różna od zera, co widać na przykład z przekształcenia

$ 4(a^2+ab + b^2) = 3(a + b)^2 + (a-b)^2 = 3 + (a-b)^2 > 0. $

Liczby $a^3$ oraz $b^3$ są wymierne, więc wymierna jest też ich różnica $a^3 -b^3$ . Stąd wniosek, że różnica

$ a-b= \frac{a^3-b^3}{a^2+ab + b^2} $

jest liczbą wymierną. W połączeniu z warunkiem $a + b = 1$ daje to żądaną konkluzję: liczby

$ a=\frac{(a + b) + (a-b)}{2}=\frac{1+ (a-b)}{2}\ \textrm{oraz}\ b= \frac{(a +b)-(a-b)}{2}=\frac{1-(a-b)}{2} $

są wymierne.

XLVI OM - I - Zadanie 10

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

Dana jest prosta $k$ oraz leżące na niej trzy różne punkty. Każdy z nich jest początkiem pary półprostych; wszystkie te półproste leżą w jednej półpłaszczyźnie o krawędzi $k$ . Każda z tych par półprostych wyznacza z każdą inną czworokąt. Dowieść, że jeśli w dwa z tych czworokątów można wpisać okrąg, to również w trzeci można wpisać okrąg.

Rozwiązanie

Oznaczmy trzy dane punkty przez $A_1$ , $A_2$ , $A_3$ . Dla $i = 1,2,3$ oznaczmy przez $p_i$ , $q_i$ dwie dane półproste o wspólnym początku $A_i$ , a przez $l_i$ - dwusieczną utworzonego przez nie kąta. Te dwusieczne przecinają się (parami) w punktach $O_1$ , $O_2$ , $O_3$ :

$ \{O_1\} = l_2 \cap l_3, \quad \{O_2\} = l_3 \cap l_1, \quad \{O_3\} = l_1 \cap l_2 $

(rysunek 5). Przyjmijmy ponadto oznaczenia (dla $i,j \in \{1,2,3\}, i \ne j$ ):

$h_i$ - odległość punktu $O_i$ od prostej $k$ ,
$O_i'$ - rzut punktu $O_i$ na prostą $k$ ,
$r_{ij}$ - odległość punktu $O_i$ od półprostej $p_j$ ,
$T_{ij}$ - rzut punktu $O_i$ na półprostą $p_j$ .

Punkt $A_3$ jest środkiem jednokładności, która punkty $O_1$ , $O_1'$ , $T_{13}$ odwzorowuje odpowiednio na punkty $O_2$ , $O_2'$ , $T_{23}$ . Wynika stąd proporcja $|O_1T_{13}| \colon |O_2T_{23}| = |O_1O_1'| \colon |O_2O_2'|$ , czyli

$ \frac{r_{13}}{r_{23}}= \frac{h_1}{h_2}. $

Przez cykliczne przesunięcie numerów $1, 2, 3$ otrzymujemy (analogicznie):

$ \frac{r_{21}}{r_{31}}= \frac{h_2}{h_3} \quad \textrm{oraz} \quad \frac{r_{32}}{r_{12}}= \frac{h_3}{h_1}. $

Mnożąc stronami te trzy proporcje dostajemy po prawej stronie jedynkę, a po lewej - ułamek, którego licznik musi być wobec tego równy mianownikowi:

$ (1) \qquad \quad r_{13}r_{21}r_{32} = r_{23}r_{31}r_{12}. $

Zauważmy teraz, że jeżeli w czworokąt wyznaczony przez pary półprostych $p_1$ , $q_1$ oraz $p_2$ , $q_2$ da się wpisać okrąg, to jego środek leży zarówno na dwusiecznej $l_1$ , jak i na dwusiecznej $l_2$ . Środkiem tym jest więc punkt $O_3$ , a promień jest równy obu odległościom $r_{31} = |O_3T_{31}|$ oraz $r_{32} = |O_3T_{32}|$ ; tak więc $r_{31} = r_{32}$ .

Na odwrót, jeśli zachodzi równość $r_{31} =r_{32}$ , to punkt $O_3$ jest środkiem okręgu stycznego do półprostych $p_1$ , $q_1$ , $p_2$ , $q_2$ , a więc wpisanego w rozważany czworokąt. Zatem równość $r_{31} = r_{32}$ jest warunkiem koniecznym i dostatecznym istnienia takiego okręgu.

I znów prżez analogię (przez cykliczne przesunięcie numerów) wnosimy, że w czworokąt wyznaczony przez pary półprostych $p_2$ , $q_2$ oraz $p_3$ , $q_3$ da się wpisać okrąg wtedy i tylko wtedy, gdy $r_{12} = r_{13}$ , natomiast w czworokąt wyznaczony przez pary półprostych $p_3$ , $q_3$ oraz $p_1$ , $q_1$ da się wpisać okrąg wtedy i tylko wtedy, gdy $r_{23}= r_{21}$ .

Zadanie sprowadza się więc do wykazania, że jeżeli zachodzą dwie spośród równości $r_{12}=r_{13}$ , $r_{23} = r_{21}$ , $r_{31} = r_{32}$ , to zachodzi także i trzecia. Ta implikacja jest zaś natychmiastowym wnioskiem z uzyskanej powyżej równości (1).

XLVI OM - I - Zadanie 11

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

Dane są liczby naturalne $n > m > 1$ . Ze zbioru $\{1,2, \ldots ,n\}$ losujemy bez zwracania $m$ liczb. Obliczyć wartość oczekiwaną różnicy między największą a najmniejszą wylosowaną liczbą.

Rozwiązanie

Zdarzeniem elementarnym jest wybór $m$ -elementowego podzbioru ze zbioru $n$ -elementowego. Te zdarzenia elementarne są jednakowo prawdopodobne; jest ich ${n}\choose{m}$ . Oznaczmy największą i najmniejszą wybraną liczbę odpowiednio przez $a$ i $b$ . Rozważana zmienna losowa $X$ , czyli różnica $a-b$ , może przyjąć każdą wartość całkowitą od $m - 1$ do $n-1$ .

Ustalmy liczbę naturalną $r$ spełniającą nierówności $m-1 \leq r \leq n- 1$ . W zbiorze $\{1,2,\ldots,n\}$ jest $n - r$ par liczb $a$ , $b$ o różnicy $a - b = r$ . Przy ustalonym położeniu liczb $a$ i $b$ mamy ${r-1}\choose{m-2}$ możliwości wyboru pozostałych $m-2$ liczb ze zbioru $\{b+1,\ldots,a-1\}$ . Wobec tego iloczyn $(n -r) {{r-1}\choose{m-2}}$ wyraża ilość $m$ -elementowych podzbiorów zbioru $\{1,2,\ldots,n\}$ , w których różnica między największym a najmniejszym elementem wynosi $r$ - czyli ilość zdarzeń elementarnych, w których badana zmienna losowa $X$ przyjmuje wartość $r$ .

Dzieląc ten iloczyn przez liczbę wszystkich zdarzeń elementarnych otrzymujemy prawdopodobieństwo tego, że $X = r$ ; oznaczmy je przez $p_r$ . Tak więc

$ p_r = P(X=r)= {{n}\choose{m}}^{-1} (n-r) {{r-1}\choose{m-2}}. $

Korzystając z łatwych do uzasadnienia związków

$ {{r-1}\choose{m-2}} =\frac{m - 1}{r} {{r}\choose{m-1}}= \frac{(m-1)m}{r(r+1)} {{r+1}\choose{m}} $

przekształcamy uzyskane wyrażenie, jak następuje:

$ \begin{split} p_r & = {{n}\choose{m}}^{-1} \left[ (n+1) {{r-1}\choose{m-2}} - (r+1) {{r-1}\choose{m-2}} \right]=\\ & = {{n}\choose{m}}^{-1} \cdot \frac{m-1}{r} \left[ (n+1) {{r}\choose{m-1}} - m {{r+1}\choose{m}} \right]. \end{split} $

Ponieważ $r$ przebiega wartości od $m-1$ do $n-1$ , zatem wartość oczekiwana zmiennej losowej $X$ , czyli liczba

$ E(X) = \sum_{r=m-1}^{n-1} rp_r, $

jest równa

$ (1) \qquad \quad E(X)= {{n}\choose{m}}^{-1} (m-1) \left[ (n+1) \sum_{r=m-1}^{n-1} {{r}\choose{m-1}} - m \sum_{r=m-1}^{n-1} {{r+1}\choose{m}} \right]. $

Aby zwinąć sumy w nawiasie kwadratowym, skorzystamy ze wzoru

$ (2) \qquad \quad \sum_{s=j}^N {{s}\choose{j}} = {{N+1}\choose{j+1}} \quad \textrm{dla} \quad N \geq j \geq 0 $

(patrz: Uwaga). Przyjmując w tym wzorze najpierw $N= n -1$ , $j = m-1$ , a następnie $N = n$ , $j = m$ , otrzymujemy kolejno:

$ \sum_{r=m-1}^{n-1} {{r}\choose{m-1}} = {{n}\choose{m}}, \quad \sum_{r=m-1}^{n-1} {{r+1}\choose{m}} = \sum_{s=m}^{n} {{s}\choose{m}}= {{n+1}\choose{m+1}} $

(zastosowaliśmy zmianę wskaźnika sumowania: $s = r + 1$ ). Możemy teraz dokończyć rachunek (1):

$ \begin{split} E(X)& = {{n}\choose{m}}^{-1} (m-1) \left[ (n+1) {{n}\choose{m}} - m {{n+1}\choose{m+1}} \right]=\\ & = (m-1) \left[ (n+1) - m \cdot \frac{(n+1)!}{(m+1)!(n-m)!} \cdot \frac{m!(n-m)!}{n!} \right]=\\ & = (m-1) \left[ (n+1) - m \cdot \frac{n+1}{m+1} \right]= \frac{(m-1)(n+1)}{m+1}. \end{split} $

Jest to szukana wartość.

Uwaga. Wzór (2) jest dobrze znany. Można go łatwo udowodnić przez indukcję względem $N$ przy ustalonym $j$ . Można go też ,,zobaczyć'', przyglądając się uważnie trójkątowi Pascala; proponujemy to Czytelnikom jako przyjemne ćwiczenie spostrzegawczości.

XLVI OM - I - Zadanie 12

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

Ciąg $(x_n)$ jest określony następująco:

$ x_1 = \frac{1}{2}, \quad x_n = \frac{2n-3}{2n} \cdot x_{n-1} \quad \text{ dla } n=2,3,4,\ldots . $

Udowodnić, że dla każdej liczby naturalnej $n \geq 1$ zachodzi nierówność

$ x_1 + x_2 + \ldots + x_n < 1. $

Rozwiązanie

Weźmy pod uwagę ciąg liczb dodatnich $(y_n)$ określony, jak następuje:

$ y_n= (2n-1)x_n \quad \textrm{dla} \quad n= 1,2,3,\ldots . $

Podany wzór rekurencyjny dla ciągu $(x_n)$ implikuje analogiczny wzór dla ciągu $(y_n)$ :

$ y_n = (2n-1) \cdot \frac{2n-3}{2n} \cdot x_{n-1}= \frac{(2n-1)(2n-3)}{2n} \cdot \frac{y_{n-1}}{2(n-1)-1}, $

czyli

$ (1) \qquad \quad y_n = \frac{2n-1}{2n} \cdot y_{n-1} \quad \textrm{dla} \quad n=2,3,4, \ldots. $

Przyjmijmy dodatkowo $y_0 = 1$ . Uzyskany wzór rekurencyjny jest wówczas słuszny także dla $n= 1$ . Zauważmy teraz, że

$ (2) \qquad \quad y_{n-1}-y_n=\frac{2n}{2n-1} \cdot y_n-y_n=\frac{y_n}{2n-1} = x_n \quad \textrm{dla} \quad n=1,2,3,\ldots. $

Stąd

$ (3) \qquad \quad x_1+x_2 + \ldots + x_n = (y_0-y_1) + (y_1-y_2) + \ldots +(y_{n-1} - y_n) = y_0 - y_n = 1 - y_n < 1 $

- co było do wykazania.

XLVI OM - II etap

II etap XLVI Olimpiady Matematycznej

XLVI OM - II - Zadanie 1

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

Wielomian $P(x)$ ma współczynniki całkowite. Udowodnić, że jeżeli liczba $P(5)$ dzieli się przez 2, a liczba $P(2)$ dzieli się przez 5, to liczba $P(7)$ dzieli się przez 10.

Rozwiązanie

Dowód opiera się na spostrzeżeniu, że jeśli $P(x) = a_0 + a_1x + \ldots + a_nx^n$ jest wielomianem o współczynnikach całkowitych, to dla każdej pary różnych liczb całkowitych $u$ , $v$ różnica $P(u) - P(v)$ jest podzielna przez różnicę $u-v$ . Istotnie:

$ P(u)-P(v) = a_1(u-v) + a_2(u^2-v^2) + \ldots + a_n(u^n-v^n), $

a każda z różnic $u^k - v^k$ rozkłada się na czynniki:

$ u^k-v^k = (u-v)(u^{k-1}v^0 + u^{k-2}v^1+ \ldots + u^0 v^{k-1}). $

Przyjmując w szczególności $u = 7$ , $v = 5$ widzimy, że różnica $P(7)-P(5)$ dzieli się przez $2$ ; przyjmując następnie $u = 7$ , $v = 2$ stwierdzamy, że różnica $P(7)-P(2)$ dzieli się przez $5$ . Stąd, wobec warunków danych w założeniu zadania, wnosimy, że liczba $P(7)$ dzieli się zarówno przez $2$ , jak i przez $5$ . A ponieważ liczby $2$ i $5$ są względnie pierwsze, zatem liczba $P(7)$ dzieli się przez iloczyn $2 \cdot 5$ , czyli przez $10$ .

XLVI OM - II - Zadanie 2

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

W sześciokącie wypukłym $ABCDEF$ zachodzą następujące równości: $|AB| = |BC|$ , $|CD| = |DE|$ , $|EF| = |FA|$ . Wykazać, że proste zawierające wysokości trójkątów $BCD$ , $DEF$ i $FAB$ poprowadzone odpowiednio z wierzchołków $C$ , $E$ , $A$ przecinają się w jednym punkcie.

Rozwiązanie

Przyjmijmy oznaczenia:

$k_1$ - okrąg o środku $D$ i promieniu $|DC| = |DE|$ ;
$k_2$ - okrąg o środku $F$ i promieniu $|FE| = |FA|$ ;
$k_3$ - okrąg o środku $B$ i promieniu $|BA| = |BC|$ .

Okręgi $k_2$ i $k_3$ przecinają się w punkcie $A$ ; oznaczmy drugi punkt ich przecięcia przez $A'$ (por. Uwaga 2); podobnie, oznaczmy przez $C'$ drugi (oprócz $C$ ) punkt przecięcia okręgów $k_3$ i $k_1$ , a przez $E'$ - drugi (oprócz $E$ ) punkt przecięcia okręgów $k_1$ i $k_2$ (rysunek 7). Punkty $A$ i $A'$ są położone symetrycznie względem prostej przechodzącej przez środki $F$ i $B$ okręgów $k_2$ i $k_3$ ; zatem $AA' \bot FB$ . To znaczy, że prosta $AA'$ zawiera wysokość trójkąta $FAB$ , poprowadzoną z wierzchołka $A$ ; jest więc jedną z trzech prostych, których dotyczy teza zadania. Pozostałe dwie proste, o które chodzi, to - analogicznie - proste $CC'$ i $EE'$ .

Prosta $AA'$ jest osią potęgową pary okręgów $k_2$ , $k_3$ ; prosta $CC'$ jest osią potęgową pary $k_3$ , $k_1$ , a prosta $EE'$ - pary $k_1$ , $k_2$ . Wiadomo (por. Uwaga 1), że dla każdej trójki okręgów trzy osie potęgowe wyznaczone przez pary tych okręgów tworzą pęk prostych przecinających się w jednym punkcie lub równoległych. W rozważanej sytuacji proste $AA'$ , $CC'$ , $EE'$ , jako prostopadłe odpowiednio do boków $FB$ , $BD$ , $DF$ trójkąta $DFB$ , nie mogą być równoległe - a zatem przecinają się w jednym punkcie. Dowód jest zakończony.

Uwaga 1. Dla Czytelników, którzy nie są dość oswojeni z twierdzeniem o współpękowości osi potęgowych przedstawimy szkicowo jego dowód, wraz z określeniami użytych pojęć.

Niech $P$ będzie punktem leżącym w płaszczyźnie okręgu $k$ i niech $l$ będzie dowolną prostą przechodzącą przez punkt $P$ i przecinającą okrąg $k$ w dwóch punktach $U$ i $V$ . Wartość iloczynu $|PU| \cdot |PV|$ zależy tylko od okręgu $k$ i punktu $P$ , nie zależy natomiast od wyboru prostej $l$ . [Uzasadnienie: przypuśćmy, że inna prosta $l'$ przecina okrąg $k$ w punktach $U'$ i $V'$ ; dobrze znana równość $|PU| \cdot |PV | = |PU'| \cdot |PV'|$ wynika z podobieństwa trójkątów $PU U'$ i $PV'V$ .]

Tę stałą wartość, wziętą ze znakiem plus, gdy punkt $P$ leży na zewnątrz okręgu $k$ , a ze znakiem ,,minus'', gdy $P$ leży wewnątrz $k$ , nazywamy potęgą punktu $P$ względem okręgu $k$ ; jest ona równa różnicy $|OP|^2 - r^2$ , gdzie przez $O$ i $r$ został oznaczony środek i promień okręgu $k$ . [Uzasadnienie: niech $UV$ będzie średnicą zawartą w prostej $OP$ ; jeden z odcinków $PU$ , $PV$ ma długość $|OP|+r$ , a drugi $\pm (|OP| - r)$ ; znak ,,plus'' lub ,,minus'' w zależności od tego, czy punkt $P$ leży na zewnątrz $k$ , czy wewnątrz $k$ ; zatem (odpowiednio) $|PU| \cdot |PV| = \pm (|OP|^2-r^2)$ .]

Niech będą dane dwa okręgi o niepokrywających się środkach $O_1$ , $O_2$ i promieniach $r_1$ , $r_2$ . Jeżeli punkt $P$ ma równe potęgi względem obu tych okręgów, to ta sama własność przysługuje także punktowi $Q$ określonemu jako rzut prostokątny punktu $P$ na prostą $O_1O_2$ ; wynika to z równości $|O_1Q|^2-|O_2Q|^2 = |O_1P|^2-|O_2P|^2 = r_1^2-r_2^2$ ; przy tym na prostej $O_1O_2$ jest dokładnie jeden punkt $Q$ taki, że $|O_1Q|^2-|O_2Q|^2 = r_1^2 - r_2^2$ . Stąd wniosek, że zbiór punktów o równych potęgach względem dwóch danych okręgów jest prostą prostopadłą do $O_1O_2$ ; nazywamy ją osią potęgową tej pary okręgów. Gdy okręgi przecinają się w dwóch punktach, wówczas każdy z tych punktów ma zerową potęgę względem obu okręgów, a więc oś potęgowa jest prostą przechodzącą przez punkty przecięcia. Gdy okręgi są styczne, oś potęgowa jest prostą styczną do nich obu w punkcie ich styczności.

Jeżeli rozważamy dowolną trójkę okręgów $k_1$ , $k_2$ , $k_3$ (o parami różnych środkach) i jeśli te środki nie są współliniowe, to oś potęgowa pary $k_1$ , $k_3$ przecina oś potęgową pary $k_2$ , $k_3$ . Punkt przecięcia ma jednakową potęgę względem wszystkich trzech okręgów, a więc leży też na osi potęgowej pary $k_1$ , $k_2$ . Jeśli natomiast środki okręgów $k_1$ , $k_2$ , $k_3$ są współliniowe, to każda z tych trzech osi jest prostopadła do prostej przechodzącej przez środki. Stąd teza twierdzenia: trzy rozważane osie potęgowe albo przecinają się w jednym punkcie albo są równoległe.

Uwaga 2. W treści zadania jest mowa o trójkątach $BCD$ , $DEF$ , $FAB$ ; należy stąd wnosić, że każdy z kątów $BCD$ , $DEF$ , $FAB$ jest mniejszy od kąta półpełnego. Wszelako rozumowanie pozostaje w mocy także w przypadku, gdy któryś z tych kątów jest półpełny (i odpowiedni trójkąt degeneruje się do odcinka; przez ,,prostą zawierającą wysokość'' należy wówczas rozumieć prostą prostopadłą do owego odcinka, przechodzącą przez odpowiedni wierzchołek). Dwa spośród okręgów $k_1$ , $k_2$ , $k_3$ są wtedy styczne; ale ich oś potęgowa nadal jest prostą zawierającą wysokość (w sprecyzowanym przed chwilą sensie), więc dalsze rozumowanie nie wymaga żadnych modyfikacji.

XLVI OM - II - Zadanie 3

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

Dane są liczby niewymierne dodatnie $a$ , $b$ , $c$ , $d$ , przy czym $a+b = 1$ . Udowodnić, że $c+d = 1$ wtedy i tylko wtedy, gdy dla każdej liczby naturalnej $n$ zachodzi równość $[na] +[nb] = [nc] + [nd]$ .

Uwaga: $[x]$ jest największą liczbą całkowitą nie większą od $x$ .

Rozwiązanie

Weźmy dowolną liczbę naturalną $n \geq 1$ . W myśl określenia symbolu $[x]$ ,

$ [na] \leq na < [na] + 1, \quad [nc] \leq nc < [nc] + 1, $

$ [nb] \leq nb < [nb]+ 1, \quad [nd] \leq nd < [nd] + 1. $

Iloczyny $na$ , $nb$ , $nc$ , $nd$ nie mogą być liczbami całkowitymi (bo liczby $a$ , $b$ , $c$ , $d$ są z założenia niewymierne), a więc w żadnym z wypisanych związków nie może zachodzić równość. Dodając nierówności w lewym ,,słupku'' i w prawym ,,słupku'' (i korzystając z założenia, że $a + b=1$ ) otrzymujemy wobec tego zależności

$ (1) \qquad \quad k_n<n<k_n + 2, \quad l_n < n(c + d)<l_n + 2, $

gdzie

$ k_n = [na] + [nb], \quad l_n = [nc] + [nd]. $

Liczby $n$ oraz $k_n$ są całkowite, więc pierwsza z nierówności podwójnych (1) implikuje równość $n = k_n + 1$ .

Jeśli teraz $c + d = 1$ , to liczba $l_n$ , podobnie jak $k_n$ , musi (na mocy drugiej pary nierówności (1)) spełniać równość $n = l_n + 1$ ; tak więc $k_n = l_n( = n-1)$ dla $n = 1,2,3,\ldots$ .

Na odwrót, zakładając, że $k_n = l_n$ dla $n = 1,2,3,\ldots$ , otrzymujemy z drugiej pary związków (1) nierówność podwójną

$ \frac{k_n}{n} < c+d < \frac{k_n+2}{n} \quad \textrm{dla} \quad n=1,2,3,\ldots; $

a ponieważ $k_n = n - 1$ , zatem

$ 1-\frac{1}{n} < c+d < 1+ \frac{1}{n} \quad \textrm{dla} \quad n=1,2,3,\ldots. $

Jedyną wartością sumy $c + d$ spełniającą ten nieskończony układ nierówności podwójnych jest liczba $1$ .

Wykazaliśmy więc żądaną równoważność:

$ (c + d=1) \Longleftrightarrow (k_n = l_n \quad \textrm{dla} \quad n = 1,2,3,\ldots ). $

XLVI OM - II - Zadanie 4

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

Liczby dodatnie $x_l, x_2, \ldots , x_n$ spełniają warunek

$ \sum_{i=1}^n x_i \leq \sum_{i=1}^n x_i^2 $

Dowieść, że dla każdej liczby rzeczywistej $t$ większej od 1 zachodzi nierówność

$ \sum_{i=1}^n x_i^t \leq \sum_{i=1}^n x_i^{t+1} $

Rozwiązanie

Oznaczmy krótko:

$ (1) \qquad \quad f(t) = \sum_{i=1}^n x_i^{t+1} - \sum_{i=1}^n x_i^t \quad \textrm{dla} \quad t \geq 1. $

Wiedząc, że $f(1) \geq 0$ , mamy udowodnić, że $f(t) \geq 0$ dla $t > 1$ . W tym celu oczywiście wystarczy wykazać, że

$ (2) \qquad \quad f(t) \geq f(1) \quad \textrm{dla} \quad t>1. $

Ta zaś nierówność wynika z następującego przekształcenia:

$ f(t)-f(1) = \sum_{i=1}^n \left( (x_i^{t+1} - x_i^t) - (x_i^2 - x_i) \right) = \sum_{i=1}^n x_i (x_i-1)(x_i^{t-1} -1). $

Dla każdego numeru $i = 1,\ldots,n$ i dla każdej wartości $t>1$ obie różnice w nawiasach są liczbami dodatnimi, obie są liczbami ujemnymi, lub obie są równe zeru. Uzyskana suma jest więc liczbą nieujemną; nierówność (2) jest wykazana.

XLVI OM - II - Zadanie 5

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

Okręgi wpisane w ściany $ABC$ i $ABD$ czworościanu $ABCD$ są styczne do krawędzi $AB$ w tym samym punkcie. Wykazać, że punkty styczności tych okręgów z krawędziami $AC$ , $BC$ oraz $AD$ , $BD$ leżą na jednym okręgu.

Rozwiązanie

Przyjmijmy, że okrąg wpisany w ścianę $ABC$ jest styczny do krawędzi $AC$ , $BC$ i $AB$ odpowiednio w punktach $P$ , $Q$ , $T$ , a okrąg wpisany w ścianę $ABD$ jest styczny do krawędzi $AD$ , $BD$ i $AB$ odpowiednio w punktach $R$ , $S$ , $T$ (ten sam punkt $T$ , zgodnie z założeniem). Mamy następujące równości odcinków stycznych:

$ (1) \qquad \quad |AP| = |AT| = |AR|, \quad |BQ| = |BT| = |BS|, $

$ (2) \qquad |CP| = |CQ|, \quad |DR| = |DS|. $

Jeżeli punkt $T$ jest środkiem krawędzi $AB$ , to trójkąty $ABC$ i $ABD$ są równoramienne, a proste $PQ$ i $RS$ są równoległe do prostej $AB$ ; punkty $P$ i $Q$ są położone symetrycznie względem płaszczyzny przechodzącej przez $T$ i prostopadłej do $AB$ , punkty $R$ i $S$ także są położone symetrycznie względem tej płaszczyzny, a zatem odcinki $PQ$ i $RS$ są podstawami trapezu równoramiennego, na którym daje się opisać okrąg.

W dalszym ciągu zakładamy, że punkt $T$ nie jest środkiem krawędzi $AB$ ; nie tracąc ogólności przyjmijmy, że $|AT| > |BT|$ . Żadna z prostych $PQ$ i $RS$ nie jest równoległa do $AB$ . Punkty $A$ , $B$ , $P$ , $Q$ leżą w płaszczyźnie ściany $ABC$ , więc prosta $PQ$ przecina prostą $AB$ ; oznaczmy punkt przecięcia przez $U$ . Analogicznie, punkty $A$ , $B$ , $R$ , $S$ leżą w płaszczyźnie ściany $ABD$ , więc prosta $RS$ przecina prostą $AB$ ; oznaczmy punkt przecięcia przez $V$ .

Punkty $U$ i $V$ leżą na półprostej $AB^\to$ , poza odcinkiem $AB$ ; wobec tego

$ (3) \qquad |AU| = |AB| + |BU| \quad \textrm{oraz}\quad |AV| = | AB| + |BV|. $

(Rysunek 10 przedstawia usytuowanie rozważanych punktów i prostych oddzielnie na płaszczyźnie $ABC$ i na płaszczyźnie $ABD$ .)

Na mocy twierdzenia o odcinkach stycznych i siecznych (zastosowanego do okręgów wpisanych w trójkąty $ABC$ i $ABD$ ) mamy równości:

$ (4) \qquad |UP|\cdot |UQ| = |UT|^2, \quad |VR|\cdot |VS| = |VT|^2. $

Zastosujmy teraz twierdzenie Menelausa do trójkąta $ABC$ przeciętego prostą $PQ$ oraz do trójkąta $ABD$ przeciętego prostą $RS$ :

$ \frac{|AU|}{|UB|} \cdot \frac{|BQ|}{|QC|} \cdot \frac{|CP|}{|PA|} =1 \quad \textrm{oraz} \quad \frac{|AV|}{|VB|} \cdot \frac{|BS|}{|SD|} \cdot \frac{|DR|}{|RA |} =1. $

Wobec związków (2) i (1) dostajemy stąd proporcje

$ \frac{|AU|}{|BU|}=\frac{|AP|}{|BQ|}=\frac{|AT|}{|BT|} \quad \textrm{oraz} \quad \frac{|AV|}{|BV|}=\frac{|AR|}{|BS|}=\frac{|AT|}{|BT|}. $

Zastępując $|AU|$ i $|AV|$ przez prawe strony wzorów (3) otrzymujemy równania, z których obliczamy:

$ (5) \qquad \quad |BU|= \frac{|AB| \cdot |BT|}{|AT|-|BT|} \quad \textrm{oraz} \quad |BV|= \frac{|AB| \cdot |BT|}{|AT|-|BT|}. $

Zatem $|BU| = |BV|$ . Stąd wniosek, że punkt $U$ pokrywa się z $V$ ; jest więc punktem przecięcia prostych $PQ$ i $RS$ .

Para prostych przecinających się wyznacza płaszczyznę. Tak więc punkty $P$ , $Q$ , $R$ , $S$ leżą na jednej płaszczyźnie. Skoro zaś punkty $U$ i $V$ pokrywają się, zatem ze związków (4) otrzymujemy równość $|UP| \cdot |UQ| = |UR| \cdot |US|$ . Wynika z niej, że punkty $P$ , $Q$ , $R$ , $S$ leżą na jednym okręgu.

Uwaga 1. Twierdzenie Menelausa zostało wykorzystane jedynie do wyprowadzenia równości (5); nie jest ono jednak do tego niezbędne. Proponujemy Czytelnikom znalezienie innych uzasadnień wzorów (5).

Uwaga 2. Doszedłszy do wniosku, że punkty $P$ , $Q$ , $R$ , $S$ są współpłaszczyznowe, można rozumować w sposób następujący: przez środek okręgu $PQT$ prowadzimy prostą prostopadłą do płaszczyzny $ABC$ , a przez środek okręgu $RST$ prowadzimy prostą prostopadłą do płaszczyzny $ABD$ . Proste te leżą w jednej płaszczyźnie (prostopadłej do $AB$ i przechodzącej przez punkt $T$ ), a przy tym nie są równoległe, zatem przecinają się. Z równości (1) łatwo wynika, że punkt ich przecięcia jest jednakowo odległy od punktów $P$ , $Q$ , $T$ , $R$ , $S$ - jest więc środkiem sfery, na której leżą te punkty. Sfera ta w przecięciu z płaszczyzną $PQRS$ daje poszukiwany okrąg.

XLVI OM - II - Zadanie 6

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

Kwadrat o boku długości $n$ dzielimy na $n^2$ kwadratów jednostkowych. Wyznaczyć wszystkie liczby naturalne $n$ , dla których taki kwadrat mozna pociąć wzdłuż linii tego podziału na kwadraty, z których każdy ma bok długości 2 lub 3.

Rozwiązanie

Jeśli $n$ jest liczbą parzystą, to kwadrat o wymiarach $n \times n$ można pociąć na kwadraty $2 \times 2$ . Przyjmijmy więc, że $n$ jest liczbą nieparzystą. Kwadrat $n \times n$ składa się z $n$ rzędów, po $n$ pól (kwadracików jednostkowych) w każdym rzędzie. Malujemy te rzędy na czarno i biało, na przemian (w ,,zebrę''). Wobec nieparzystości $n$ oba rzędy skrajne otrzymują jednakowy kolor - przyjmijmy, że czarny. Różnica między liczbą czarnych pól a liczbą białych pól w całej tak pomalowanej szachownicy wynosi $n$ .

Przypuśćmy, że podział na kwadraty $2 \times 2$ i $3 \times 3$ jest wykonalny. Każdy kwadrat $2 \times 2$ ma dwa pola białe i dwa czarne. Każdy kwadrat $3 \times 3$ ma trzy pola białe i sześć czarnych lub na odwrót. Różnica między liczbą czarnych pól a liczbą białych pól w kwadracie $2 \times 2$ wynosi $0$ , a w kwadracie $3 \times 3$ wynosi $3$ lub $-3$ . Dodając te wszystkie różnice (odpowiadające poszczególnym kwadratom podziału) otrzymujemy liczbę podzielną przez $3$ . Ale, jednocześnie, obliczona w ten sposób suma równa się różnicy między liczbą czarnych pól a liczbą białych pól w całej szachownicy, czyli równa się $n$ .

Wniosek: jeśli rozważany podział jest wykonalny, to liczba $n$ jest podzielna przez $2$ lub przez $3$ . Na odwrót, jeśli $n$ dzieli się przez $2$ lub przez $3$ , to kwadrat $n \times n$ daje się pociąć w żądany sposób (na same tylko kwadraty o wymiarach $2 \times 2$ lub o wymiarach $3 \times 3$ ).

Uwaga 1. Gdy $n$ dzieli się przez $6$ , to oczywiście można szachownicę pociąć zarówno na kwadraty $2 \times 2$ , jak i na kwadraty $3 \times 3$ . Ponadto możliwe są podziały ,,mieszane''; Czytelnik może przekonać się (jest to łatwe ćwiczenie), że jeśli $n$ jest liczbą większą od $6$ i podzielną przez $2$ lub przez $3$ , to kwadrat $n \times n$ daje się pociąć na kwadraty $2 \times 2$ i $3 \times 3$ , z wykorzystaniem obu rodzajów.

XLVI OM - III etap

III etap XLVI Olimpiady Matematycznej

XLVI OM - III - Zadanie 1

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

III

Wyznaczyć liczbę podzbiorów zbioru $\{1,2, \ldots , 2n\}$ , w których równanie $x + y = 2n+1$ nie ma rozwiązań.

Rozwiązanie

Zbiór $A$ , zawarty w zbiorze $\{1,2,\ldots,2n\}$ , będziemy nazywali dobrym, jeśli ma on wymaganą w zadaniu własność; to znaczy, gdy równanie $x + y = 2n + 1$ nie ma rozwiązania $x,y \in A$ .

Zbiór $\{1,2,\ldots,2n\}$ jest sumą następujących rozłącznych podzbiorów dwuelementowych (czyli par liczb):

$ P_1 = \{1,2n\},\ P_2 = \{2,2n-1\}, \ \ldots,\ P_n = \{n,n+1\}; $

symbol $P_j$ oznacza parę $\{j, 2n+1-j\}$ .

Podzbiór $A$ zbioru $\{1,2,\ldots,2n\}$ jest dobry wtedy i tylko wtedy, gdy nie zawiera żadnej pary $P_j$ , czyli - równoważnie - gdy dla każdego numeru $j \in \{1,2,\ldots,n\}$ część wspólna $P_j \cap A$ jest albo zbiorem pustym, albo zbiorem jednoelementowym $\{j\}$ , albo zbiorem jednoelementowym $\{2n+1-j\}$ . Dobry zbiór $A$ jest więc jednoznacznie wyznaczony przez wybór jednej z tych trzech opcji dla każdego $j \in \{1,2,\ldots,n\}$ . Stąd wniosek, że liczba dobrych zbiorów wynosi $3^n$ .

XLVI OM - III - Zadanie 2

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

III

Przekątne pięciokąta wypukłego dzielą ten pięciokąt na pięciokąt i dziesięć trójkątów. Jaka jest maksymalna możliwa do uzyskania liczba trójkątów o równych polach?

Rozwiązanie

Oznaczmy rozważany pięciokąt przez $ABCDE$ , a pięciokąt utworzony przez punkty przecięcia przekątnych - przez $KLMNP$ tak, by następujące trójkąty były tymi, o których mowa w zadaniu:

$\Delta_0$ : trójkąt $LEM$ ; $\quad \Delta_1$ : trójkąt $EMA$ ;
$\Delta_2$ : trójkąt $MAN$ ; $\quad \Delta_3$ : trójkąt $ANB$ ;
$\Delta_4$ : trójkąt $NBP$ ; $\quad \Delta_5$ : trójkąt $BPC$ ;
$\Delta_6$ : trójkąt $PCK$ ; $\quad \Delta_7$ : trójkąt $CKD$ ;
$\Delta_8$ : trójkąt $KDL$ ; $\quad \Delta_9$ : trójkąt $DLE$

(rysunek 12). Rozpoczniemy od wykazania implikacji:

$ (1) \qquad \begin{array}{l} \textrm{jeśli numer $i$ jest liczbą nieparzystą},\\ \textrm{to pola trójkątów $\Delta_{i-1}$, $\Delta_i$, $\Delta_{i+1}$ nie są wszystkie równe}; \end{array} $

przyjmujemy, że numeracja trójkątów jest cykliczna (to znaczy, przyjmujemy: $\Delta_{-1} = \Delta_9$ ; $\Delta_{10} = \Delta_0$ ).

Przypuśćmy, że na przykład trójkąty $\Delta_4$ , $\Delta_5$ , $\Delta_6$ mają równe pola. Z równości pol trójkątów $NBP$ i $BPC$ wynika, że odcinek $BP$ jest środkową w trójkącie $BCN$ ; z równości pól trójkątów $BPC$ i $PCK$ wynika, że odcinek $CP$ jest środkową w trójkącie $BCK$ . Punkt $P$ byłby zatem wspólnym środkiem przekątnych $BK$ i $CN$ czworokąta $BCKN$ , który wobec tego powinien być równoległobokiem - ale przecież proste $BN$ i $CK$ przecinają się w punkcie $E$ . Sprzeczność; implikacja (1) jest wykazana.

Przechodzimy do właściwego rozwiązania. Przykład pięciokąta foremnego pokazuje, że można uzyskać pięć trójkątów $\Delta_i$ o równych polach. Udowodnimy, że nie można uzyskać siedmiu takich trójkątów.

Przypuśćmy więc, że istnieje siedmioelementowy zbiór $Z$ , zawarty w zbiorze $\{0,1,\ldots,9\}$ , taki, że trójkąty $\Delta_i$ o numerach $i \in Z$ mają równe pola. Niech $k$ , $l$ , $m$ będą trzema liczbami ze zbioru $\{0,1,\ldots,9\}$ , nie należącymi do $Z$ . Weźmy pod uwagę wszystkie trójki kolejnych indeksów:

$ T_i = \{i-1,i,i+1\} \quad \textrm{dla} \quad i = 0,1,\ldots,9 $

(gdzie, jak poprzednio, dodawanie $i \pm 1$ należy rozumieć modulo $10$ ). Każda z liczb ze zbioru $\{0,1,\ldots,9\}$ należy do dokładnie trzech trójek $T_i$ . Dotyczy to, w szczególności, każdej z liczb $k$ , $l$ , $m$ . Łącznie więc trójelementowy zbiór $\{k,l,m\}$ ma niepuste przecięcie z co najwyżej dziewięcioma trójkami $T_i$ . Zostaje co najmniej jedna trójka $T_j$ nie zawierająca żadnej z liczb $k$ , $l$ , $m$ , a więc zawarta w zbiorze $Z$ . Numer $j$ musi być liczbą parzystą, w myśl spostrzeżenia (1).

Nie tracąc ogólności przyjmijmy, że $j = 2$ . To znaczy, że liczby $1$ , $2$ , $3$ należą do zbioru $Z$ . Wobec tego liczby $0$ i $4$ nie mogą doń należeć (bowiem - znów na mocy uwagi (1) - wykluczone są trójki $\{0,1,2\}$ oraz $\{2,3,4\}$ ); zatem jedna z liczb $k$ , $l$ , $m$ równa się $0$ , a inna równa się $4$ . Trzecia z tych liczb musi wchodzić w skład trójki $\{6,7,8\}$ (która w przeciwnym razie byłaby zawarta w zbiorze $Z$ , wbrew implikacji (1)). Role numerów $6$ i $8$ są w tym kontekście symetryczne. Mamy więc do rozpatrzenia dwie istotnie różne sytuacje:

$ \{k,l,m\} = \{0,4,7\}\quad \textrm{oraz} \quad \{k,l,m\} = \{0,4,6\}; $

zbiór $Z$ , odpowiednio, ma jedną z następujących postaci:

$ Z= \{1,2,3,5,6,8,9\},\quad Z = \{1,2,3,5,7,8,9\}. $

Niech $S_i$ będzie polem trójkąta $\Delta_i$ ; (dla $i = 0,1,\ldots,9$ ). Wykażemy, że zachodzą implikacje:

$ (2) \qquad (S_1 = S_2 = S_3,\quad S_5 = S_6,\quad S_8 = S_9) \Longrightarrow (S_3<S_5); $

$ (3) \qquad (S_1 = S_2 = S_3,\quad S_7 = S_8 = S_9) \Longrightarrow (S_2>S_5). $

Będzie to dowód, że żaden z wypisanych powyżej siedmioelementowych zbiorów $Z$ nie może być zbiorem numerów trójkątów o równych polach. W myśl wcześniejszych stwierdzeń, będzie to jednocześnie uzasadnienie wniosku, że wśród dziesięciu trójkątów $\Delta_i$ nigdy nie ma siedmiu trójkątów o jednakowych polach.

Dowód implikacji (2). Z danych w przesłance równości pól:

$ \textrm{pole}(MAN) = \textrm{pole}(ANB), \quad \textrm{pole}(BPC) = \textrm{pole}(PCK) $

oraz

$ \textrm{pole}(EMA) = \textrm{pole}(MAN), \quad \textrm{pole}(KDL) = \textrm{pole}(DLE) $

wynika (odpowiednio), że punkty $N$ i $P$ są środkami odcinków $BM$ i $BK$ , a punkty $M$ i $L$ są środkami odcinków $EN$ i $EK$ (rysunek 13).

Tak więc odcinek $NP$ łączy środki dwóch boków trójkąta $BMK$ , odcinek $ML$ łączy środki dwóch boków trójkąta $ENK$ , i wobec tego

$ |NP| = \frac{1}{2} \cdot |MK|,\quad NP||MK \quad \textrm{- czyli} \quad AN||MK $

- oraz

$ |ML| = \frac{1}{2} \cdot |NK|, \quad ML||NK \quad \textrm{- czyli} \quad AM||NK. $

Uzyskane związki równoległości pokazują, że czworokąt $AMKN$ jest równoległobokiem; stąd $|MK|= |AN|$ . Prosta $MK$ jest równoległa do $NC$ , więc trójkąty $ENC$ i $EMK$ są jednokładne w skali $|EN|\colon |EM| = 2$ . W takim razie $|NC| = 2 \cdot |MK|$ , i w konsekwencji

$ |PC|= |NC|-|NP| = 2\cdot|MK|-\frac{1}{2} \cdot |MK| = \frac{3}{2} \cdot |MK| = \frac{3}{2} \cdot |AN|. $

Leżące na jednej prostej odcinki $PC$ i $AN$ są podstawami trójkątów $ANB$ i $BPC$ o wspólnym wierzchołku $B$ . Stosunek długości tych podstaw jest więc jednocześnie stosunkiem pól trójkątów: pole( $BPC$ ): pole( $ANB$ ) = $3 \colon 2$ , czyli $S_5 \colon S_3 = 3 \colon 2$ . Konkluzja implikacji (2) jest tym samym udowodniona.

Dowód implikacji (3). Dane w przesłance równości pól trójkątów:

$ (4) \qquad \quad \textrm{pole}(AEM) = \textrm{pole}(AMN) = \textrm{pole}(ANB) $

oraz

$ (5) \qquad \quad \textrm{pole}(DEL) = \textrm{pole}(DLK) = \textrm{pole}(DKC) $

pokazują, że punkty $M$ i $N$ dzielą odcinek $EB$ na trzy równe części, i podobnie punkty $L$ i $K$ dzielą odcinek $EC$ na trzy równe części. Wobec tego prosta $BC$ jest równoległa do $ML$ (czyli do $AM$ ). Skoro zaś $N$ jest środkiem odcinka $BM$ , zatem trójkąty $AMN$ i $CBN$ są jednokładne w skali $-1$ (rysunek 14). Stąd wniosek, że pole( $AMN$ ) = pole( $CBN$ ) $>$ pole( $CBP$ ), czyli $S_2 > S_5$ . To kończy dowód implikacji (3), i tym samym także dowód ogólnej tezy: nie można mieć siedmiu trójkątów $\Delta_i$ o równych polach.

Przeprowadzone w tym ostatnim przypadku rozumowanie (dowód (3)) daje jednocześnie wskazówkę, jak uzyskać sześć trójkątów $\Delta_i$ mających jednakowe pola. Bierzemy dowolny trójkąt równoramienny $BCE$ , w którym $|EB| = |EC|$ . Na bokach $EB$ oraz $EC$ znajdujemy punkty $M$ i $N$ oraz $L$ i $K$ , dzielące te boki na trzy równe części:

$ |EM| = |MN| = |NB|,\quad |EL| = |LK| = |KC|. $

Punkty przecięcia prostej $ML$ z prostymi $CN$ oraz $BK$ oznaczmy odpowiednio przez $A$ i $D$ (rysunek 14 może nadal służyć jako ilustracja; trzeba tylko w wyobraźni przesunąć punkt $E$ do położenia na symetralnej boku $BC$ , i odpowiednio przemieścić pozostałe punkty). Zachodzą wówczas równości (4) oraz (5); a dzięki założeniu, że trójkąt $BCE$ jest równoramienny (i wynikającej stąd symetrii całej konfiguracji) osiągamy to, że wszystkie pola występujące w związkach (4) oraz (5) są równe.

Wniosek: sześć spośród trójkątów $\Delta_i$ może mieć równe pola, i liczby tej nie można już zwiększyć.

XLVI OM - III - Zadanie 3

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

III

Dana jest liczba pierwsza $p \geq 3$ . Określamy ciąg $(a_n)$ wzorami

$ \begin{split} a_n = n & \text{ dla } n=0,1,2,\ldots,p-1, \\ a_n = a_{n-1} + a_{n-p} & \text{ dla } n\geq p. \end{split} $

Wyznaczyć resztę z dzielenia liczby $a_{p^3}$ przez $p$ .

Rozwiązanie

Podany wzór rekurencyjny

$ (1) \qquad \quad a_n = a_{n-1} + a_{n-p} \quad \textrm{dla} \quad n \geq p $

możemy zastosować do każdego ze składników jego prawej strony (pod warunkiem, że numer $n - p$ jest nie mniejszy od $p$ , czyli że $n \geq 2p$ ); dostajemy zależność

$ a_n = (a_{n-2} + a_{n-1-p}) + (a_{n-p-1} + a_{n-2p}) = a_{n-2} + 2a_{n-1-p} + a_{n-2p}. $

Stosując ponownie wzór (1) do każdego ze składników ostatniej sumy otrzymujemy równość

$ \begin{split} a_n &= (a_{n-3}+ a_{n-2-p}) + 2(a_{n-p-2}+ a_{n-1-2p}) + (a_{n-2p-1} +a_{n-3p}) = \\ & = a_{n-3} + 3a_{n-2-p} + 3a_{n-1-2p} + a_{n-3p} \end{split} $

(jeśli tylko $n \geq 3p$ ). Po $k$ -krotnym zastosowaniu analogicznego przekształcenia uzyskujemy związek

$ \begin{split} (2) \qquad \quad a_n & = a_{n-k} + {{k}\choose{1}} a_{n-k+1-p} + {{k}\choose{2}} a_{n-k+2-2p}+\ldots+ a_{n-kp}=\\ & = \sum_{i=0}^k {{k}\choose{i}} a_{n-k+i-ip}, \end{split} $

sensowny i słuszny pod warunkiem że $n \geq kp$ .

(Wyprowadzenie wzoru (2) ma charakter indukcyjny; proponujemy Czytelnikowi, jako proste ćwiczenie, przeprowadzenie szczególowego uzasadnienia, przez indukcję względem $k = 1,2,\ldots,[n/p]$ , z wielokrotnym wykorzystaniem wzoru (1).)

Jeśli teraz $n \geq p^2$ , to możemy w równości (2) podstawić $k = p$ , otrzymując

$ (3) \qquad \quad a_n = \sum_{i=0}^p {{p}\choose{i}} a_{n+i -(i+1)p}. $

Dla $i = 1,2,\ldots,p-1$ współczynniki dwumianowe ${{p}\choose{i}}$ są liczbami podzielnymi przez $p$ (patrz: Uwaga). Jeśli więc z sumy napisanej po prawej stronie równości (3) odrzucimy wszystkie składniki z wyjątkiem dwóch skrajnych (odpowiadających wartościom wskaźnika $i = 0$ oraz $i = p$ ), to otrzymamy liczbę przystającą do $a_n$ modulo $p$ :

$ (4) \qquad \quad a_n \equiv a_{n-p} +a_{n-p^2} \pmod p $

(dla $n \geq p^2$ ). Przyrównując (modulo $p$ ) prawe strony związków (1) i (4) stwierdzamy, że $a_{n-1}+a_{n-p} \equiv a_{n-p} + a_{n-p^2}$ , czyli

$ a_{n-1} \equiv a_{n-p^2} \pmod p. $

Oznaczmy przez $r_j$ resztę z dzielenia liczby $a_j$ przez $p$ (dla $j = 0,1,2,\ldots$ ). Uzyskaną zależność przepisujemy w postaci

$ r_{n-1} = r_{n-p^2} \quad \textrm{dla} \quad n \geq p^2. $

To znaczy, że ciąg ( $r_j$ ) jest okresowy, z okresem $p^2-1$ ; zatem

$ r_n = r_{n-k(p^2-1)} \quad \textrm{dla} \quad k = 1,2,\ldots,[n/(p^2-1)]. $

Podstawiamy $n = p^3$ , $k = p$ , i otrzymujemy wynik:

$ r_{p^3}= r_{p^3-p(p^2-1)} = r_p. $

Pozostaje zauważyć, że (w myśl wzoru (1))

$ a_p = a_{p-1} +a_0 = (p-1) + 0 = p-1 $

i wobec tego $r_{p^3} = r_p = p-1$ . Tak więc reszta z dzielenia liczby $a_{p^3}$ przez $p$ równa się $p-1$ .

Uwaga. Fakt, na który powołaliśmy się w rozwiązaniu:

liczba pierwsza $p$ jest dzielnikiem liczb ${{p}\choose{1}}$ , ${{p}\choose{2}}$ , $\ldots$ , ${{p}\choose{p-1}}$

jest dobrze znany (oraz banalnie prosty: w równości ${{p}\choose{i}} \cdot (i!) \cdot ((p-i)!) = p!$ czynniki $i!$ oraz $(p-i)!$ są dla $i \in \{1,2,\ldots,p-1\}$ niepodzielne przez $p$ , więc czynnik ${{p}\choose{i}}$ musi dzielić się przez $p$ ).

XLVI OM - III - Zadanie 4

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

III

Dla danej liczby naturalnej $n \geq 1$ wyznaczyć najmniejszą wartość wyrażenia

$ x_1 + \frac{x_2^2}{2} + \frac{x_3^3}{3} + \ldots + \frac{x_n^n}{n} $

gdzie $x_1, x_2, \ldots , x_n$ są liczbami dodatnimi spełniającymi warunek

$ \frac{1}{x_1} + \frac{1}{x_2} + \ldots + \frac{1}{x_n} = n. $

Rozwiązanie

Kluczem do rozwiązania jest nierówność

$ (1) \qquad \quad \frac{x^k}{k} + \frac{1}{x} \geq 1 + \frac{1}{k} \quad \textrm{dla} \quad x>0,\ k = 1,2,3,\ldots. $

Oto jej dowód: różnica między wyrażeniem po lewej stronie (1) i wyrażeniem po prawej stronie (1), pomnożona przez dodatni czynnik $kx$ , jest równa

$ (x^{k+1}+k)-(kx + x) = x(x^k-1) + k(1-x) = x(x-1) \sum_{i=0}^{k-1} x^i + k(1-x) = $

$ = (x-1) \left( \sum_{j=1}^k x^j-k \right) = (x-1) \sum_{j=1}^k (x^j-1) = \sum_{j=1}^k (x-1)(x^j-1). $

Ta suma jest nieujemna, bo wszystkie jej składniki są liczbami nieujemnymi.

Podstawiamy w (1) $x = x_k$ dla $k = 1,\ldots,n$ (gdzie $x_1,\ldots,x_n$ są danymi w zadaniu liczbami) i dodajemy uzyskane nierówności stronami:

$ \sum_{k=1}^n \frac{x_k^k}{k} + \sum_{k=1}^n \frac{1}{x_k} \geq \sum_{k=1}^n \left( 1 + \frac{1}{k} \right) = n + \sum_{k=1}^n \frac{1}{k}. $

Druga suma po lewej stronie ma wartość $n$ , zgodnie z warunkiem danym w założeniach. A zatem

$ \sum_{k=1}^n \frac{x_k^k}{k} \geq \sum_{k=1}^n \frac{1}{k}. $

Gdy $x_1 = \ldots = x_n = 1$ , nierówność ta staje się równością. Tak więc minimalna wartość badanego wyrażenia wynosi $1 + \frac{1}{2} + \frac{1}{3} +\ldots + \frac{1}{n}$ .

Uwaga 1. Wyjściową nierówność (1) można uzasadnić wieloma sposobami. Na przykład tak: średnia arytmetyczna układu $k+1$ liczb, z których jedna jest równa $x^k$ , a pozostałe są równe $1/x$ , jest nie mniejsza niż średnia geometryczna tych liczb:

$ \frac{1}{1+k} \left( x^k + \underbrace{\frac{1}{x} + \ldots + \frac{1}{x}}_k \right) \geq \left( x^k \cdot \underbrace{\frac{1}{x} \cdot \ldots \cdot \frac{1}{x}}_k \right)^{1/(k+1)}=1; $

stąd $x^k + \dfrac{k}{x} \geq k+1$ , co jest równoważnym zapisem nierówności (1).

Można także w znanej nierówności Bernoulli'ego

$ (1 + a)^k \geq 1 + ka, $

zachodzącej dla wszystkich liczb $a \geq -1$ (oraz dla $k = 1,2,3,\ldots$ ), podstawić $a = x-1$ , otrzymując: $x^k \geq 1 + k(x - 1)$ . Stąd

$ \frac{x^k}{k} + \frac{1}{x} \geq \frac{1+k(x-1)}{k} + \frac{1}{x} = x+\frac{1}{x} + \frac{1}{k} -1 = 1+ \left( \sqrt{x} - \frac{1}{\sqrt{x}}\right)^2 + \frac{1}{k} \geq 1+\frac{1}{k}. $

Można wreszcie potraktować lewą stronę (1) jako funkcję zmiennej $x$ przebiegającej przedział $(0;\ \infty)$ i przekonać się, że jej pochodna jest ujemna w przedziale $(0;\ 1)$ oraz dodatnia w $(1;\ \infty)$ , wobec czego dla $x = 1$ osiągana jest wartość minimalna, równa $1 + (1/k)$ .

XLVI OM - III - Zadanie 5

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

III

Niech $n$ i $k$ będą liczbami naturalnymi. Z urny, w której znajduje się 11 kartek ponumerowanych liczbami od 1 do $n$ , losujemy kartki kolejno po jednej, bez zwracania. Gdy pojawi się kartka o numerze podzielnym przez $k$ , przerywamy losowanie. Dla ustalonego $n$ wyznaczyć te liczby $k \leq n$ , dla których wartość oczekiwana liczby wylosowanych kartek jest równa dokładnie $k$ .

Rozwiązanie

Ustalmy liczbę naturalną $k \in \{1,2,\ldots,n\}$ . Weźmy pod uwagę następujące zdarzenia:

$ \begin{array}{cl} \mathcal{A}_j: & \textrm{liczba podzielna przez } k\ \textrm{pojawia się po raz pierwszy} \\ & \textrm{w } j\ \textrm{-tym losowaniu}\ (j=1,2,\ldots,n);\\ \mathcal{B}_j: & \textrm{liczba podzielna przez } k\ \textrm{nie pojawia się} \\ & \textrm{w żadnym spośród pierwszych} j\ \textrm{losowań}\ (j=0,1,2,\ldots,n). \end{array} $

Oznaczmy prawdopodobieństwa tych zdarzeń: $p_j = P(\mathcal{A}_j)$ , $q_j=P(\mathcal{B}_j$ ). Oczywiście $\mathcal{B}_0$ jest zdarzeniem pewnym. Zatem $q_0=1$ .

Zajście zdarzenia $\mathcal{A}_j$ jest równoważne temu, że wylosowano $j$ kartek, po czym losowanie przerwano - czyli temu, że rozważana w zadaniu zmienna losowa $X$ (liczba wylosowanych kartek) przyjmuje wartość $j$ . Tak więc

$ p_j = P(X=j)\quad \textrm{dla}\quad i = 1,2,\ldots,n. $

Zajście zdarzenia $\mathcal{A}_j$ jest jednocześnie równoważne temu, że liczba podzielna przez $k$ nie pojawiła się w pierwszych $j-1$ losowaniach, natomiast pojawiła się w pierwszych $j$ losowaniach - czyli że zaszło zdarzenie $\mathcal{B}_{j-1}$ , ale nie zaszło zdarzenie $\mathcal{B}_j$ . Inaczej mówiąc, zdarzenie $\mathcal{A}_j$ jest równe różnicy zdarzeń $\mathcal{B}_{j-1}$ i $\mathcal{B}_j$ (traktowanych jako podzbiory odpowiedniej przestrzeni probabilistycznej). Wobec tego

$ p_j = P(\mathcal{B}_{j-1} \setminus \mathcal{B}_j) = q_{j-1}-q_j \quad \textrm{dla}\quad j = 1,2,\ldots,n $

(korzystamy z tego, że $\mathcal{B}_j \subset \mathcal{B}_{j-1}$ ).

Wartość oczekiwana zmiennej losowej $X$ równa się

$ \begin{split} E(X) & = \sum_{j=1}^n j \cdot P(X=j) = \sum_{j=1}^n j \cdot p_j = \sum_{j=1}^n j(q_{j-1} - q_j)=\\ & = (q_0-q_1) + 2(q_1 -q_2) + 3(q_2 -q_3) + \ldots + n(q_{n-1} -q_n) = \\ & = q_0 + q_1 + q_2 + \ldots + q_{n-1} -nq_n. \end{split} $

W zbiorze $\{1,2,\ldots,n\}$ jest $m$ liczb podzielnych przez $k$ oraz jest $l$ liczb niepodzielnych przez $k$ , przy czym

$ m= \left[ \frac{n}{k} \right] \geq 1, \quad l = n-m \leq n-1 $

(symbol $[t]$ oznacza, jak zwykle, największą liczbę całkowitą, nie przekraczają $t$ ). Jeżeli $j > l$ , to w którymś z pierwszych $j$ losowań musiała pojawić się liczba podzielna przez $k$ , co oznacza, że $\mathcal{B}_j$ jest zdarzeniem niemożliwym. Zatem $q_j = 0$ dla $j > l$ , i w takim razie

$ (1) \qquad \quad E(X) = q_0+q_1 +q_2 + \ldots + q_l. $

Z warunków zadania wynika, że dla $j \leq l$ prawdopodobieństwa $q_j$ wyrażają się wzorem

$ (2) \qquad \quad q_j=P(\mathcal{B}_j) = \frac{l}{n} \cdot \frac{l-1}{n-1} \cdot \ldots \cdot \frac{l-j+1}{n-j+1} \quad (j\ \textrm{czynników}). $

Istotnie: w pierwszym losowaniu wyciągamy liczbę niepodzielną przez $k$ z prawdopodobieństwem $l/n$ ; zostaje w urnie $n-1$ kartek, w tym $l-1$ kartek z liczbami niepodzielnymi przez $k$ ; w drugim losowaniu wyciągamy liczbę niepodzielną przez $k$ z prawdopodobieństwem $(l- 1)/(n- 1)$ ; i tak dalej. Wyciągnięcie w $j$ kolejnych losowaniach kartek z liczbami niepodzielnymi przez $k$ odbywa się z prawdopodobieństwem równym iloczynowi napisanemu po prawej stronie wzoru (2).

Przekształcamy ten iloczyn, jak następuje:

$ q_j = \frac{l!}{(l-j)!} \cdot \frac{(n-j)!}{n!} = \frac{l!(n-l)!}{n!} \cdot \frac{(n-j)!}{(l-j)!(n-l)!}= $

$ ={{n}\choose{l}}^{-1} {{n-j}\choose{n-l}} = {{n}\choose{m}}^{-1} {{n-j}\choose{m}} $

(bo $l + m = n$ ). Po podstawieniu tych wyrażeń równość (1) przybiera postać

$ E(X) = {{n}\choose{m}}^{-1} \sum_{j=0}^{n-m} {{n-j}\choose{m}} = {{n}\choose{m}}^{-1} \sum_{s=m}^n {{s}\choose{m}} $

(zastosowaliśmy zmianę wskaźnika sumowania: $s = n-j$ ). Ostatnia suma daje się zwinąć w znany sposób:

$ \sum_{s=m}^n {{s}\choose{m}} = {{n+1}\choose{m+1}} $

(por. rozwiązanie zadania 11 z zawodów pierwszego stopnia tej olimpiady: wzór (2) oraz Uwaga na stronie 51). Stąd

$ E(X) = {{n}\choose{m}}^{-1} {{n+1}\choose{m+1}} = \frac{m!(n-m)!}{n!} \cdot \frac{(n+1)!}{(m+1)!(n-m)!} = \frac{n+1}{m+1}. $

W zadaniu chodzi o ustalenie warunków na to, by wartość $E(X)$ była równa dokładnie $k$ - czyli na to, by zachodziła równość

$ (3) \qquad \quad \frac{n+1}{m+1}=k. $

Jeśli związek (3) zachodzi, to oczywiście $k$ jest dzielnikiem liczby $n + 1$ . Na odwrót, jeśli $n+1$ dzieli się przez $k$ , wówczas z nierówności

$ \frac{n + 1}{k} - 1 \leq \frac{n}{k} < \frac{n+1}{k} $

(której skrajne człony są liczbami całkowitymi) wnosimy, że

$ m= \left[ \frac{n}{k} \right] = \frac{n+1}{k}-1, $

czyli zachodzi równość (3).

Mamy więc odpowiedź: szukanymi wartościami $k$ są wszystkie dzielniki liczby $n + 1$ należące do zbioru $\{1,2,\ldots,n\}$ .

XLVI OM - III - Zadanie 6

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

III

Dane są trzy niewspółpłaszczyznowe półproste $k$ , $l$ , $m$ o wspólnym początku $P$ oraz punkt $A$ różny od $P$ należący do $k$ . Wykazać, że istnieje dokładnie jedna para punktów $B$ , $C$ , należących odpowiednio do $l$ i $m$ , taka, że

$ |PA| + |AB| = |PC| + |CB| \quad \text{oraz} \quad |PB| + |BC| = |PA| + |AC|. $

Rozwiązanie

Rozpoczniemy od analizy postulowanych warunków. Załóżmy, że punkty $B \in l$ , $C \in m$ spełniają te warunki:

$ (1) \qquad \quad |PA| + |AB| = |PC| + |CB|\quad \textrm{oraz}\quad |PB| + |BC| = |PA| + |AC|. $

W powstały trójkąt $ABC$ wpisujemy okrąg. Punkty styczności tego okręgu z bokami $BC$ , $CA$ , $AB$ oznaczmy odpowiednio przez $Q$ , $R$ , $S$ (rysunek 15). Zachodzą więc równości

$ (2) \qquad \quad |BS| = |BQ|,\quad |CQ| = |CR|,\quad |AR| = |AS|. $

Odejmujemy stronami pierwszą równość (2) od pierwszej równości (1): otrzymujemy związek $|PA| + |AB|-|BS| = |PC| + |CB|-|BQ|$ , czyli

$ (3) \qquad \quad |PA| +|AS| = |PC| + |CQ|. $

Następnie odejmujemy stronami drugą równość (2) od drugiej równości (1): dostajemy związek $|PB| + |BC|-|CQ| = |PA| + |AC|-|CR|$ , czyli

$ (4) \qquad \quad |PB| + |BQ| = |PA| + |AR|. $

Trzecia równość (2) pokazuje, że lewa strona (3) równa się prawej stronie (4). Oznaczmy tę wspólną wartość przez $t$ . Tak więc

$ (5) \qquad |PA| + |AR| = |PA| + |AS| = t, $

i wobec zależności (2) i (4) oraz (2) i (3):

$ (6) \qquad |PB| + |BS| = |PB| + |BQ| = t, $

$ (7) \qquad |PC| + |CR| = |PC| + |CQ| = t. $

Na półprostych $k$ , $l$ , $m$ odkładamy odcinki $PK$ , $PL$ , $PM$ o jednakowej długości $t$ : $|PK| = |PL| = |PM| = t$ . Liczba $t$ jest większa od każdej z odległości $|PA|$ , $|PB|$ , $|PC|$ , więc punkty $A$ , $B$ , $C$ leżą odpowiednio na odcinkach $PK$ , $PL$ , $PM$ . Wobec tego

$ (8) \qquad \begin{split} t=|PK| = |PA| & + |AK|,\quad t=|PL| = |PB| + |BL|, \\ & t=|PM| = |PC| + |CM|. \end{split} $

Porównując te związki z uzyskanymi wcześniej związkami (5), (6), (7) dochodzimy do równości

$ (9) \qquad \begin{split} |AK| = |AR| = & |AS|,\quad |BL| = |BQ| = |BS|,\\ & |CM| = |CQ| = |CR|. \end{split} $

Weźmy pod uwagę okrąg $\omega_1$ dopisany do trójkąta $PBC$ przy boku $BC$ ; punkty jego styczności z bokiem $BC$ oraz z przedłużeniami boków $PB$ i $PC$ oznaczmy odpowiednio przez $Q'$ , $L'$ , $M'$ . Oczywiście $|PL'| = |PM'|$ . Jednocześnie

$ |PL'| = |PB| + |BL'| = |PB| + |BQ'|, $

$ |PM'| = |PC| + |CM'| = |PC| + |CQ'|, $

skąd (wobec (6) i (7))

$ \begin{split} |PL'| + |PM'| & = |PB| + |PC| + |BQ'| + |CQ'| = |PB| + |PC| + |BC| =\\ & = |PB| + |PC| + |BQ| + |CQ| = 2t, \end{split} $

czyli $|PL'| = |PM'| = t$ . To znaczy, że punkt $L'$ pokrywa się z $L$ , a punkt $M'$ pokrywa się z $M$ . Ponadto $|BQ'| = |BL'| = |BL| = |BQ|$ , więc także punkt $Q'$ pokrywa się z $Q$ . Punkty $Q$ , $L$ , $M$ są zatem punktami styczności okręgu $\omega_1$ z prostymi $BC$ , $PB$ , $PC$ .

Analogicznie stwierdzamy, że punkty $R$ , $M$ , $K$ są punktami styczności okręgu $\omega_2$ , dopisanego do trójkąta $PCA$ , z bokiem $CA$ i z przedłużeniami boków $PC$ i $PA$ ; podobnie, punkty $S$ , $K$ , $L$ są punktami styczności okręgu $\omega_3$ , dopisanego do trójkąta $PAB$ , z bokiem $AB$ i z przedłużeniami boków $PA$ i $PB$ . Okręgi $\omega_1$ , $\omega_2$ , $\omega_3$ są więc styczne do płaszczyzny $ABC$ .

Przeprowadzona analiza daje wskazówkę do dowodu zarówno istnienia poszukiwanej pary punktów $B$ , $C$ , jak również jej jedyności.

Odłóżmy na półprostych $k$ , $l$ , $m$ odcinki $PK_0$ , $PL_0$ , $PM_0$ mające jednakową (dowolną) długość $s: |PK_0| = |PL_0| =|PM_0| = s$ . Weźmy pod uwagę trzy okręgi:

$\sigma_1$ - okrąg styczny do półprostych $l$ i $m$ w punktach $L_0$ i $M_0$ ,
$\sigma_2$ - okrąg styczny do półprostych $m$ i $k$ w punktach $M_0$ i $K_0$ ,
$\sigma_3$ - okrąg styczny do półprostych $k$ i $l$ w punktach $K_0$ i $L_0$ .

Istnieje wówczas dokładnie jedna płaszczyzna $\pi$ , styczna do tych trzech okręgów i taka, że punkty $K_0$ , $L_0$ , $M_0$ leżą po przeciwnej jej stronie niż punkt $P$ . Ten fakt, intuicyjnie jasny, można uzasadnić w następujący sposób.

Rozważamy ruchomy punkt $X$ , przebiegający odcinek $PK_0$ . Z punktu $X$ prowadzimy proste styczne do okręgów $\sigma_3$ i $\sigma_2$ , przecinające odcinki $PL_0$ i $PM_0$ odpowiednio w punktach $Y$ i $Z$ .

Gdy punkt $X$ znajduje się blisko punktu $P$ , punkty $Y$ i $Z$ leżą blisko punktów $L_0$ i $M_0$ ; odcinek $YZ$ przecina wówczas okrąg $\sigma_1$ (w dwóch punktach).

Gdy $X$ znajduje się blisko punktu $K_0$ , punkty $Y$ i $Z$ leżą blisko punktu $P$ ; odcinek $YZ$ jest wówczas rozłączny z okręgiem $\sigma_1$ .

Gdy $X$ przebiega odcinek $PK_0$ , oddalając się od jego końca $P$ , punkty $Y$ i $Z$ przebiegają odcinki $L_0P$ i $M_0P$ , zbliżając się do $P$ .

Istnieje zatem dokładnie jedno położenie punktu $X$ , wyznaczające punkty $Y$ i $Z$ tak, że odcinek $YZ$ jest styczny do okręgu $\sigma_1$ . Płaszczyzna $XYZ$ jest wówczas styczna do wszystkich trzech okręgów $\sigma_1$ , $\sigma_2$ , $\sigma_3$ ; jest to płaszczyzna $\pi$ , o którą nam chodziło. Wyznaczające tę płaszczyznę położenia punktów $X$ , $Y$ , $Z$ nazwijmy odpowiednio: $A_0$ , $B_0$ , $C_0$ .

Jeżeli szukane punkty $B$ i $C$ istnieją, to okręgi $\omega_1$ , $\omega_2$ , $\omega_3$ , określone w przeprowadzonej wcześniej analizie zadania, są obrazami okręgów $\sigma_1$ , $\sigma_2$ , $\sigma_3$ w jednokładności o środku $P$ i skali $t/s$ ; wynika to z równości:

$ |PK| = |PL| = |PM| = t, \quad |PK_0| - |PL_0| = |PM_0| = s. $

Obrazem płaszczyzny $\pi$ (czyli $A_0B_0C_0$ ) w tej jednokładności jest równoległa do niej płaszczyzna $ABC$ . Stąd wynika, że punkty $B$ i $C$ są wyznaczone jednoznacznie jako punkty przecięcia półprostych $l$ i $m$ z płaszczyzną równoległą do $\pi$ , przechodzącą przez punkt $A$ .

Na odwrót, określając punkty $B$ i $C$ w ten właśnie sposób, spełnimy warunki zadania, bowiem przedstawione w analizie rozumowanie można odwrócić: jednokładność, przeprowadzająca płaszczyznę $\pi$ do położenia, w którym przechodzi ona przez punkt $A$ , odwzorowuje okręgi $\sigma_1$ , $\sigma_2$ , $\sigma_3$ na okręgi $\omega_1$ , $\omega_2$ , $\omega_3$ , dopisane do trójkątów $PBC$ , $PCA$ , $PAB$ przy bokach $BC$ , $CA$ , $AB$ .

Oznaczając ich punkty styczności z tymi bokami odpowiednio przez $Q$ , $R$ , $S$ , a punkty styczności z półprostymi $k$ , $l$ , $m$ odpowiednio przez $K$ , $L$ , $M$ , oraz oznaczając przez $l$ wspólną długość odcinków $PK$ , $PL$ , $PM$ , uzyskujemy kolejno równości (9), (8) oraz (5), (6) i (7); z nich zaś - związki

$ |PA| + |AB| = |PA| + |AS| + |BS| = |PA| + |AK| + |BL| = t + |BL|, $

$ |PC| + |CB| = |PC| + |CQ| + |BQ| = |PC| + |CM| + |BL| = t + |BL| $

oraz

$ |PB| + |BC| = |PB| + |BQ| + |CQ| = |PB| + |BL| + |CM| = t + |CM|, $

$ |PA| + |AC| = |PA| + |AR| + |CR| = |PA| + |AK| + |CM| = t + |CM|. $

Spełnione są więc warunki (1); dowód jest zakończony.