XL OM

XL Olimpiada Matematyczna

Opracowanie rozwiązań: Marcin E. Kuczma

XL OM - I etap

I etap XL Olimpiady Matematycznej

XL OM - I - Zadanie 1

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Udowodnić, że jeśli liczby $k$ , $n$ ( $k < n$ ) są względnie pierwsze, to liczba $\binom{n-1}{k-1}$ jest podzielna przez $k$ .

Rozwiązanie

Oznaczmy:

$ N= \binom{n}{k}=\frac{n!}{k!(n-k)!}, \quad M=\binom{n-1}{k-1}=\frac{(n-1)!}{(k-1)!(n-k)!}. $

Są to liczby całkowite. Zachodzi równość

$ \frac{N}{M}=\frac{n!}{k!(n-k)!}\cdot \frac{(k-1)!(n-k)!}{(n-1)!}=\frac{n}{k} $

czyli $M \cdot n = N \cdot k$ . Zatem liczba $k$ jako względnie pierwsza z $n$ , musi być
dzielnikiem $M$ ; a to właśnie mieliśmy wykazać.

XL OM - I - Zadanie 2

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Dla ustalonej liczby naturalnej $n$ znaleźć liczbę rozwiązań równania

$ x^2 - [x^2] = (x - [x])^2 $

spełniających warunek $1 \leq x \leq n$ .
Uwaga. $[t]$ jest największą liczbą całkowitą nie większą od $t$ .

Rozwiązanie

Oznaczmy lewą i prawą stronę podanego równania przez $L(x)$ i $P(x)$ . Przedstawiając liczbę rzeczywistą $x$ w postaci $x = k + r$ , gdzie $k = [x]$ , $r = x - [x] \in\langle 0; 1)$ , możemy napisać:

$ \begin{split} L(x) &= k^2 + 2kr + r^2 - [k^2 + 2kr + r^2] =\\ &= 2kr + r^2 - [2kr + r^2] ,\\ P(x) &= r^2. \end{split} $

Zatem $L(x) = P(x)$ wtedy i tylko wtedy, gdy $[2kr + r^2] = 2kr$ . Ta zaś równość jest równoważna stwierdzeniu, że $2kr$ jest liczbą całkowitą. Stąd wniosek, że liczba $x = k + r$ ( $k$ całkowite, $r \in \langle 0; 1)$ ) spełnia warunki zadania wtedy i tylko wtedy, gdy

$ (1) \qquad k \in \{1,\ldots , n - 1\} , \quad 2kr\ \textrm{całkowite} $

lub

$ (2) \qquad k = n, \quad r = 0. $

Dla ustalonej wartości $k \in \{1,\ldots, n-1\}$ istnieje $2k$ wartości $r \in \rangle 0; 1)$ , dla których $2kr$ jest całkowite (mianowicie ułamki $j/(2k)$ , $j = 0,1,\ldots, 2k-1$ ). Wobec tego liczba par $(k, r)$ spełniających warunki (1) wynosi $2 + 4 + \ldots + +2(n -1) = n^2 - n$ . Warunki (2) spełnia tylko jedna taka para. Wszystkich liczb $x$ spełniających warunki zadania jest więc $n^2 - n + 1$ .

XL OM - I - Zadanie 3

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Trójkąty $ABC$ i $ABC'$ mają równo obwody, a dwusieczne kątów zewnętrznych przy wierzchołkach $C$ i $C'$ przecinają się w punkcie $O$ . Dowieść, że kąty $AOC$ i $BOC'$ są równe.

Rozwiązanie

Sumy $|AC| + |BC|$ i $|AC'| + |BC'|$ są równe; oznaczmy ich wspólną wartość przez $s$ . Na przedłużeniach odcinków $AC$ i $BC$ odkładamy odcinki $CD$ i $CE$ tak, by

$ (1) \qquad |AD| = |BE| = s. $

Trójkąty $BCD$ i $AC'E$ są równoramienne, a punkt $O$ leży na osi symetrii każdego z nich (rysunek 1). Zatem

$ (2) \qquad |OB| = |OD|, \quad |OA| = |OE| $

oraz

$ (4) \qquad |\measuredangle AOC| + |\measuredangle BOC| = |\measuredangle BOC'| + |\measuredangle AOC'|. $

Wykażemy teraz, że

$ (5) \qquad \textrm{punkty $A$ i $B$ leżą w obszarze kąta wypukłego $COC'$}. $

Weźmy pod uwagę zbiór $\mathcal{E}$ złożony z wszystkich punktów, których suma odległości od $A$ i $B$ równa się $s$ . Jest to elipsa. Warunek, który ją określa, jest spełniony w szczególności przez punkty $C$ i $C'$ . Zatem $C,C' \in \mathcal{E}$ .

Zauważmy, że proste $OC$ i $OC'$ są styczne do elipsy $\mathcal{E}$ . Gdyby na przykład prosta $OC$ nie była do niej Styczna, wówczas moglibyśmy znaleźć na tej prostej punkt $Y$ taki, że $|AY| + |BY| <s$ . Ale $|BY| = |DY|$ (bo $OC$ jest symetralną odcinka $BD$ ). Otrzymalibyśmy więc nierówność $|AY| + |DY| < s = |AD|$ , która jest niemożliwa.

Podobnie dowodzimy styczności prostej $OC'$ do elipsy $\mathcal{E}$ .

Ogniskami $\mathcal{E}$ są punkty $A$ i $B$ . Z uzyskanych relacji styczności wynika, że cała elipsa $\mathcal{E}$ leży w sektorze wyznaczonym przez półproste $OC^\to$ i $OC'^\to$ . Znajdują się tam więc i punkty $A$ i $B$ . Stąd słuszność stwierdzenia (5).

Konkluzją tego stwierdzenia jest równość

$ (6) \qquad |\measuredangle AOC| + |\measuredangle AOC'| = |\measuredangle BOC| + |\measuredangle BOC'|. $

Wszystkie przeprowadzone rozważania są słuszne przy każdej konfiguracji danych punktów. (Na przykład: punkty $C$ i $C'$ mogą leżeć po tej samej stronie lub po różnych stronach prostej $AB$ . Gdy leżą po tej samej stronie, odcinki $AC$ i $BC$ mogą się przecinać, mogą być równoległe, bądź też przecinają się ich przedłużenia, przy czym punkt przecięcia tych prostych może leżeć ,,nad'' lub ,,pod'' prostą $AB$ . Gdy punkty $C$ i $C'$ leżą po różnych stronach prostej $AB$ , powstaje czworokąt $ACBC'$ , który może być wypukły, wklęsły, a może też się redukować do trójkąta. Rysunek 1 przedstawia tylko jedno z możliwych usytuowań tych punktów. Proponujemy Czytelnikowi wykonanie rysunków w innych przypadkach i przekonanie się, że istotnie rozumowanie prowadzące do równości (4) oraz (6) nie jest od rysunku zależne.)

Dodając stronami równości (4) i (6) otrzymujemy (po redukcji) dowodzoną równość $|\measuredangle AOC| = |\measuredangle BOC'|$ .

XL OM - I - Zadanie 4

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Dowieść, że nie można tak pociąć kwadratu wzdłuż skończonej liczby odcinków i łuków okręgów, by z otrzymanych części można było złożyć koło (części można odwracać).

Rozwiązanie

Przypuśćmy, że podział, o jakim mowa w zadaniu, jest wykonalny. Otrzymane w jego wyniku części kwadratu oznaczmy przez $K_1,\ldots, K_n$ . Brzeg każdej figury $K_i$ składa się ze skończonej liczby odcinków oraz łuków okręgów. Spośród łuków okręgów będących fragmentami brzegu $K_i$ niektóre są zwrócone wypukłością na zewnątrz $K_i$ , inne są zwrócone wypukłością do wewnątrz $K_i$ . Sumę długości tych pierwszych łuków oznaczmy przez $a_i$ , a tych drugich - przez $b_i$ . Przyjmijmy $d_i = a_i - b_i$ .

Weźmy pod uwagę sumę $s = d_1 + \ldots + d_n$ .

Figury $K_i$ powstały z podziału kwadratu. Brzeg kwadratu składa się z odcinków linii prostych. Zatem każdy fragment okręgu będący linią podziału kwadratu jest jednocześnie podzbiorem brzegu dwóch figur $K_i$ , przy czym w jednej z tych figur jego długość wchodzi do sumy $s$ ze znakiem plus, a w drugiej --- ze znakiem minus. Tak więc $s = 0$ .

Założyliśmy, że z figur $K_i$ można złożyć koło. Niektóre z rozważanych łuków muszą być wtedy zużyte na utworzenie brzegu tego koła. Przy obliczaniu sumy $s$ długości tych łuków będą liczone jednokrotnie, stale ze znakiem plus. Natomiast długości pozostałych łuków okręgów, tworzących linie podziału koła, ulegną redukcji, jak w przypadku kwadratu. Suma $s$ będzie więc równa obwodowi koła.

Otrzymana sprzeczność ( $s = 0$ i jednocześnie $s > 0$ ) kończy dowód.

XL OM - I - Zadanie 5

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Dla danej liczby naturalnej $n$ wyznaczyć liczbę ciągów $(a_1, a_2, \ldots , a_n)$ , których wyrazy $a_i$ należą do zbioru $\{0,1,2,3,4\}$ oraz spełniają warunek $|a_i - a_{i+i}| = 1$ dla $i = 1,2,\ldots,n-1$ .

Rozwiązanie

Wszystkie ciągi spełniające podane w zadaniu warunki podzielimy na trzy rodzaje:

ciągi I rodzaju — kończące się symbolem $0$ lub $4$ ;\\
ciągi II rodzaju — kończące się symbolem $1$ lub $3$ ;\\
ciągi III rodzaju — kończące się symbolem $2$ .

Oznaczmy przez $x_n$ , $y_n$ , $z_n$ odpowiednio liczbę $n$ --wyrazowych ciągów I, II, III rodzaju. Każdy ciąg I rodzaju (długości $n$ ) można przedłużyć w jeden tylko sposób do ciągu długości $n + 1$ ; będzie to ciąg II rodzaju (bowiem po zerze może być tylko jedynka, a po czwórce może być tylko trójka). Z każdego ciągu II rodzaju (długości $n$ ) można utworzyć dwa ciągi długości $n+1$ , jeden I rodzaju i jeden III rodzaju (po jedynce zero, po trójce czwórka, bądź też, po jedynce lub trójce - dwójka). Wreszcie ciąg III rodzaju (długości $n$ ) da życie dwóm ciągom długości $n+1$ , obu II rodzaju (po dwójce - trójka lub jedynka).

Otrzymujemy więc zależność

$ (1) \qquad \left\{ \begin{split} x_{n+1} &= y_n\\ y_{n+1} &=x_n + 2z_n\\ z_{n+1} &= y_n, \end{split}\right. $

a z niej:

$ (2) \qquad \left\{ \begin{split} x_{n+2} &= y_{n+1}=x_n+2z_n\\ y_{n+2} &=x_{n+1} + 2z_{n+1}=3y_n\\ z_{n+2} &= y_{n+1}=x_n+2-z_n, \end{split} \right. $

Z wzorów (1) widać, że

$ (3) \qquad x_n = z_n \quad \textrm{dla } n \geq 2. $

Oznaczmy sumę $x_n + y_n + z_n$ (czyli liczbę wszystkich dopuszczalnych ciągów długości $n$ ) przez $s_n$ . Dodając stronami wzory (2) i uwzględniając równość (3) otrzymujemy związek:

$ (4) \qquad s_{n+2} = 3s_n \quad \textrm{dla } n \geq 2. $

Musimy jeszcze znać wartości $s_1$ $s_2$ i $s_3$ . Ciąg długości $1$ to pojedynczy symbol. Mamy do dyspozycji pięć symboli, więc $s_1 = 5$ . Wypiszmy teraz wszystkie dopuszczalne ciągi długości 2 oraz 3:

$ (01),\ (10),\ (12),\ (21),\ (23),\ (32),\ (34),\ (43) $

oraz

$ (010),\ (012),\ (101),\ (121),\ (123),\ (210),\ (212), $

$ (232),\ (234),\ (321),\ (323),\ (343),\ (432),\ (434). $

Wobec tego

$ s_1 = 5,\quad s_2 = 8, \quad s_3 = 14. $

Stąd i z wzoru rekurencyjnego (4) otrzymujemy przez oczywistą indukcję odpowiedź:

$ s_{2k} = 8 \cdot 3^{k-1} ,\quad s_{2k+1} = 14 \cdot 3^{k-1} \textrm{dla } k \geq 1. $

XL OM - I - Zadanie 6

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Obliczyć sumę szeregu $\sum_{n\in A}\frac{1}{2^n}$ , w którym sumowanie przebiega zbiór $A$ wszystkich liczb naturalnych niepodzielnych przez 2, 3, 5.

Rozwiązanie

Liczba naturalna $n$ jest niepodzielna przez $2$ , $3$ i $5$ wtedy i tylko wtedy, gdy przy dzieleniu przez 30 daje jedną z następujących ośmiu reszt:

$ r_1 = 1,\ r_2 = 7 , r_3 = 11, r_4 = 13 , r_5 = 17 , r_6 = 19 , r_7 = 23 , r_8 = 29 . $

Wobec tego suma, którą mamy obliczyć, równa się

$ (1) \qquad s = s_1 + s_2 + s_3 + s_4 + s_5 + s_6 + s_7 + s_8 , $

gdzie $s_i$ oznacza sumę analogicznego szeregu utworzonego ze składników odpowiadających tym wartościom $n$ , które mają postać

$ n = 30k + r_i,\quad k = 0, 1, 2, 3, \ldots . $

Tak więc

$ (2) \qquad s_i=\sum_{k=0}^\infty 2^{-(30k+r_i)}\quad \textrm{dla } i=1,\ldots,8. $

(Poprawność zastosowanego przekształcenia oraz słuszność równości (1) wynika z tego, że wyrazami rozważanego szeregu są liczby dodatnie; można je więc w dowolny sposób grupować i przestawiać, bez wpływu na zbieżność i wartość sumy szeregu.)

Prawa strona wzoru (2) przedstawia szereg geometryczny o ilorazie $2^{-30}$ . Jego suma równa się

$ s_i= \frac{2^{-r_i}}{1-2^{-30}}= \frac{2^{30-r_i}}{2^{30}-1}\quad \textrm{dla } i=1,\ldots, 8. $

Podstawiamy te liczby do równości (1) i otrzymujemy

$ \frac{2^{29}+2^{23}+2^{17}+2^{11}+2^7+2^1}{2^{30}-1}=\frac{545925250}{1073741823} $

Jest to poszukiwana wartość.

XL OM - I - Zadanie 7

Zawody matematyczne:

XL OM, 1988-1989

Etap:

W przestrzeni dany jest skończony zbiór punktów, z których każde cztery są wierzchołkami czworościanu o objętości mniejszej lub równej 1. Udowodnić, że istnieje czworościan o objętości nie większej niż 27, zawierający wszystkie te punkty.

Rozwiązanie

Niech $ABCD$ będzie czworościanem o maksymalnej objętości wśród wszystkich czworościanów, których wierzchołkami są punkty rozważanego zbioru. Oznaczmy przez $O$ jego środek ciężkości, to znaczy punkt przecięcia czterech odcinków, z których każdy łączy wierzchołek czworościanu ze środkiem ciężkości przeciwległej ściany. Wiadomo, że środek ciężkości czworościanu dzieli każdy z tych czterech odcinków w stosunku $3:1$ .

Niech $A'B'C'D'$ będzie obrazem czworościanu $ABCD$ w jednokładności o środku $O$ i skali $-3$ ( $A'$ - obraz punktu $A$ itd.). Zgodnie z uczynioną przed chwilą uwagą, środek ciężkości każdej ściany czworościanu przechodzi w tej jednokładności na przeciwległy wierzchołek.

W myśl założenia zadania, objętość czworościanu $ABCD$ nie przekracza $1$ . Zatem objętość czworościanu $A'B'C'D'$ nie przekracza $27$ (stosunek objętości brył podobnych równa się sześcianowi skali podobieństwa). Wykażemy, że czworościan $A'B'C'D'$ zawiera wszystkie rozważane punkty - jest więc poszukiwanym czworościanem.

Przypuśćmy, że pewien z tych punktów - nazwijmy go $P$ - leży poza czworościanem $A'B'C'D'$ . Każdy czworościan jest częścią wspólną czterech półprzestrzeni otrzymanych z podziału całej przestrzeni płaszczyznami ścian. Jeżeli więc punkt $P$ nie należy do $A'B'C'D'$ , to znaczy, że $P$ nie należy do jednej z tych półprzestrzeni; powiedzmy, do półprzestrzeni wyznaczonej przez płaszczyznę $A'B'C'$ . Innymi słowy, $P$ leży po przeciwnej stronie płaszczyzny $A'B'C'$ niż punkt $O$ . Ale płaszczyzna $A'B'C'$ , równoległa do ściany $ABC$ czworościanu $ABCD$ , przechodzi przez jego wierzchołek $D$ (bowiem, jak zauważyliśmy wyżej, wierzchołek $D$ jest obrazem środka ciężkości ściany $ABC$ w określonej na początku jednokładności).

Stąd wniosek, że odległość punktu $P$ od płaszczyzny $ABC$ jest większa niż odległość punktu $D$ od tej płaszczyzny. Co za tym idzie, objętość czworościanu $ABCP$ jest większa od objętości czworościanu $ABCD$ . A przecież czworościan $ABCD$ określiliśmy jako ten spośród wszystkich czworościanów o wierzchołkach w zadanych punktach, którego objętość jest maksymalna.

Otrzymana sprzeczność dowodzi, że wszystkie punkty danego zbioru leżą w czworościanie $A'B'C'D'$ . Dowód jest zakończony.

XL OM - I - Zadanie 8

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Dana jest liczba naturalna $n$ oraz skończony ciąg liczb rzeczywistych $A^{(1)}= (a_1^{(1)}, a_2^{(1)}, \ldots, a_n^{(1)})$ . Dla każdej liczby naturalnej $m$ wybieramy dwie liczby naturalne $i$ , $j$ spełniające warunek $1 \leq i < j \leq n$ i określamy ciąg $A^{(m+1)}= (a_1^{(m+1)}, a_2^{(m+1)}, \ldots, a_n^{(m+1)})$ , jak następuje:

$ \begin{split} a_i^{(m+1)} &= a_j^{(m+1)} = \frac{1}{2}(a_i^{(m)} + a_j^{(m)}),\\ a_k^{(m+1)} = a_k^{(m)} \quad\text{dla}\quad k\neq i, j. \end{split} $

Udowodnić, że jeżeli każda para liczb naturalnych $(i,j)$ należących do przedziału $\langle 1;n\rangle$ będzie wybrana nieskończenie wiele razy, to

$ \lim_{n\to \infty} a_k^{(m)} = \frac{1}{n}(a_1^{(1)} + \ldots + a_n^{(1)}) $

dla $k = 1,2,\ldots, n$ .

Rozwiązanie

Przyjmijmy oznaczenia:

$ u^{(m)}=\min_{1\leq k \leq n} a_k^{(m)}, \quad v^{(m)}=\max_{1\leq k \leq n} a_k^{(m)}, $

$ s^{(m)}=\sum_{k=1}^n a_k^{(m)},\quad q^{(m)}=\sum_{k=1}^n\left(a_k^{(m)}\right)^2. $

Sumę $s^{(1)}$ oznaczmy krótko przez $s$ . Teza zadania orzeka, że ciąg $\left(a_1^{(m)}\right)^\infty_{m=1}$ jest zbieżny do liczby $s/n$ , także ciąg $\left(a_2^{(m)}\right)^\infty_{m=1}$ Jest zbieżny do tej samej liczby, to samo można powiedzieć o ciągu $\left(a_3^{(m)}\right)^\infty_{m=1}$ , i tak dalej: dla każdego numeru $k \in \{1,\ldots, n\}$ ciąg $\left(a_k^{(m)}\right)^\infty_{m=1}$ jest zbieżny, a liczba $s/n$ jest wspólną granicą tych n ciągów. Sprowadza się to do wykazania, że

$ (1) \qquad \lim_{m \to \infty} u^{(m)} = \lim_{m \to \infty} v^{(m)} = \frac{s}{n} . $

Dla każdego $m$ zachodzą nierówności

$ u^{(m)} \leq \frac{s^{(m)}}{n} \leq v^{(m)} $

(średnia arytmetyczna układu liczb zawiera się między najmniejszą a największą z tych liczb). Zauważmy dalej, że opisana w zadaniu operacja nie zmienia sumy liczb: $s^{(m)} = s^{(m+1)}$ dla każdego $m$ ; a wobec tego $s^{(m)} = s$ dla wszystkich $m$ . Tak więc

$ (2) \qquad u^{(m)} \leq \frac{s^{(m)}}{n} \leq v^{(m)} $

Oczywiście $\rangle u^{(m)}, v^{(m)} \langle$ jest najmniejszym przedziałem zawierającym wszystkie liczby układu $A^{(m)}$ . Rozważana operacja nie wyprowadza poza ten przedział; układ $A^{(m+1)}$ także jest w nim zawarty. To znaczy, że

$ u^{(m)} \leq u^{(m+1)}, \quad v^{(m)} \geq v^{(m+1)}; $

ciąg $\left(u^{(m)}\right)$ jest niemalejący, a ciąg $\left(u^{(m)}\right)$ jest nierosnący. Nierówności (2) pokazują, że pierwszy z tych ciągów jest. ograniczony z góry przez liczbę $s/n$ , a drugi jest ograniczony z dołu przez tę samą liczbę. Istnieją zatem granice

$ u = \lim u^{(m)}\leq \frac{s}{n} , \quad v = \lim v^{(m)}\leq \frac{s}{n}. $

Jeśli wykażemy, że granice te są równe, to liczba $s/n$ będzie musiała być ich wspólną wartością i otrzymamy dowodzoną równość (1).

Przypuśćmy wobec tego, że $u < v$ . Mamy równość

$ \begin{split} q^{(m)}-q^{(m+1)}&= \sum_{k=1}^n \left(a_k^{(m)}\right)^2 - \sum_{k=1}^n \left(a_k^{(m+1)}\right)^2=\\ &= \left(a_i^{(m)}\right)^2 + \left(a_j^{(m)}\right)^2 - \left(a_i^{(m+1)}\right)^2 - \left(a_j^{(m+1)}\right)^2=\\ &=\left(a_i^{(m)}\right)^2+\left(a_j^{(m)}\right)^2 - 2\left(\frac{1}{2} \left(a_i^{(m)}+a_j^{(m)}\right)\right)^2=\\ &=\left(a_i^{(m)}+a_j^{(m)}\right)^2 \end{split} $

gdzie $(i,\ j)$ jest parą wskaźników wybraną w $m$ -tym kroku opisanej w zadaniu procedury (tj. przy określaniu układu liczb $A^{(m+1)}$ ). Ponieważ para ta zależy od bieżącej wartości wskaźnika $m$ , bardziej poprawnie będzie oznaczyć ją przez $(i_m,\ j_m)$ . Przepiszmy więc otrzymaną równość:

$ (3) \qquad q^{(m)}-q^{(m+1)} = \left(a_{i_m}^{(m)}+a_{j_m}^{(m)}\right)^2. $

Widać stąd, że $\left(q^{(m)}\right)$ jest nierosnącym ciągiem liczb nieujemnych, więc zbieżnym do granicy skończonej. Możemy wobec tego przejść do granicy z wyrażeniem znajdującym się po lewej stronie równości (3): ta różnica dąży do zera. Wobec tego także różnica w nawiasie po prawej stronie równości (3) musi dążyć do zera.

Założyliśmy, że $u < v$ . Oznaczmy liczbę $(v - u)/(n - 1)$ przez $d$ jest to ustalona liczba dodatnia:

$ d=\frac{v-u}{n-1}>0. $

Wyrazy ciągu zbieżnego do zera stają się od pewnego miejsca mniejsze od d. Istnieje więc taki numer $M$ , że

$ (4) \qquad \left| a_{i_m}^{(m)} - a_{j_m}^{(m)}) \right| < d \quad \textrm{dla } m\geq M. $

Weźmy pod uwagę przedział $\langle u^{(M)};\ v^{(M)} \rangle$ . Zawiera on przedział $\langle u;\ v \rangle$ , a więc ma długość nie mniejszą niż $v - u = (n - 1)d$ . Liczby $a_1^{(M)},\ldots, a_n^{(M)}$ dzielą ten przedział $n-1$ podprzedziałów (lub mniej, gdy niektóre z nich są równe). W każdym razie co najmniej jeden z tych podprzedziałów musi mieć długość nie mniejszą od $d$ . Ustalmy ten podprzedział i nazwijmy go $\langle \alpha;\ \beta \rangle$ .

Cały zbiór $\{a_1^{(M)},\ldots, a_n^{(M)}\}$ zawiera się w sumie przedziałów

$ P' = \langle u^{(M)};\ \alpha \rangle\quad \textrm{oraz} \quad P" = \langle \beta;\ v^{(M)} \rangle, $

odległych od siebie co najmniej o $d$ , przy czym w obu tych przedziałach są jakieś elementy tego zbioru. Przyjmijmy:

$ K' = \{k: a_k^{(M)} \in P'\} , $

$ K'' = \{k : a_k^{(M)} \in P''\}; $

są to niepuste zbiory wskaźników, dające w sumie zbiór $\{1,\ldots, n\}$ . Na mocy nierówności (4) (która musi zachodzić w szczególności dla $m = M$ ) wskaźniki $i_M$ , $j_M$ muszą oba należeć albo do $K'$ , albo do $K''$ . „Uśredniane" w $M$ -tym kroku liczby $a_{i_M}^{(M)}$ , $a_{j_M}^{(M)}$ obie leżą albo w przedziale $P'$ , albo w $P''$ . Ich średnia arytmetyczna także leży w tym przedziale. Tak więc

$ a_k^{(M+1)} \in P' \quad \textrm{dla } k \in K' $

$ a_k^{(M+1)} \in P'' \quad \textrm{dla } k \in K'' $

I znów, na mocy (4), wskaźniki $i_{M+1}$ i $j_{M+1}$ muszą oba należeć albo do $K'$ , albo do $K''$ . Kontynuując to rozumowanie dowodzimy indukcyjnie, że

$ \{i_m,j_m\} \subset K' \quad \textrm{lub} \quad \{i_m,j_m\} \subset K'' \quad \textrm{dla}\quad m\geq M. $

(Intuicyjny sens rozumowania jest taki: podprzedział $\langle \alpha;\ \beta \rangle$ stanowi ,,cezurę'' rozdzielającą całe ,,pole operacyjne'' na część lewą i prawą, których odległość wynosi nie mniej niż $d$ ; tymczasem nierówność (4) orzeka, że - począwszy od chwili $M$ - do ,,uśredniania'' wybiera się już tylko pary liczb odległych od siebie o mniej niż $d$ , a więc pary, których oba elementy leżą bądź w lewej, bądź w prawej części.)

Jeśli więc $(i,j)$ jest taką parą wskaźników, że $i\in K'$ , $j\in K''$ (lub odwrotnie), to $(i,j)\neq (i_m,j_m)$ dla wszystkich $m \geq M$ - wbrew warunkowi zadania mówiącemu, że każda para wskaźników pojawia się w ciągu wybranych par $(i_m,j_m)$ nieskończenie wiele razy.

Uzyskana sprzeczność pokazuje niesłuszność przypuszczenia, że $u < v$ , i tym samym kończy cały dowód.

Uwaga. Przypuśćmy, że $(i,j)$ jest parą wskaźników, która w ciągu wybranych par $(i_m,j_m)$ pojawia się nieskończenie wiele razy. Będziemy wówczas mówili, że wskaźniki $i$ oraz $j$ są stowarzyszone. Założenie zadania można wyrazić następująco: każde dwa wskaźniki $i,j \in \{1,\ldots,n\}$ są stowarzyszone. Zauważmy wszelako, że tak silne założenie nie jest nam potrzebne w dowodzie; wystarczy zakładać, że zbioru $\{1,\ldots ,n\}$ nie da się podzielić na dwa niepuste rozłączne podzbiory $K'$ i $K''$ tak, by żaden element zbioru $K'$ nie był stowarzyszony z żadnym elementem zbioru $K''$ ; udowodniona teza pozostaje w mocy, a dowód przenosi się bez żadnych zmian.

XL OM - I - Zadanie 9

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Wyznaczyć wszystkie liczby naturalne $x$ , $y$ , $z$ spełniające równanie

$ 1 = \frac{2}{x^2} + \frac{3}{y^2} + \frac{4}{z^2} $

Rozwiązanie

Z podanego równania wynika, że jeśli $x$ , $y$ , $z$ jest rozwiązaniem, to $x, y \geq 2$ , $z \geq 3$ . Rozpatrzymy trzy przypadki:

{\em Przypadek} l. $x = 2$ . Równanie przybiera postać $3y^{-2} + 4z^{-2} =\frac{1}{2}$ , czyli równoważnie: $4y^2 + 3z^2 = \frac{1}{2} y^2z^2$ , czyli jeszcze inaczej:

$ (y^2 - 6)(z^2 - 8) = 48 \quad (y \geq 2,\ z \geq 3). $

Rozważając wszystkie możliwe rozkłady liczby $48$ na czynniki całkowite (dodatnie i ujemne) stwierdzamy, że nie ma rozwiązania w tym przypadku.
{\em Przypadek} II. $y = 2$ . Równanie przybiera postać $2x^{-2} + 4z^{-2} = \frac{1}{4}$ , czyli - analogicznie jak poprzednio -

$ (x^2 - 8)(z^2 - 16) = 128 \quad (x \geq 2,y \geq 3). $

Znów rozważamy wszystkie rozkłady liczby $128$ na czynniki i znajdujemy jedyne (w tym przypadku) rozwiązanie: $x = 3$ , $z = 12$ .

{\em Przypadek} III. $x, y \geq 3$ ; także $z \geq 3$ . Tym razem musimy zauważyć, że zachodzi nierówność

$ 2x^{-2} + 3y^{-2} + 4z^{-2} \leq \frac{2}{9} + \frac{3}{9} + \frac{4}{9} = 1, $

przy czym staje się ona równością tylko dla $x = y = z = 3$ .

Rozważyliśmy wszystkie możliwości i znaleźliśmy dwie trójki $(x,y,z)$ liczb całkowitych będące rozwiązaniami danego równania: $(3,2,12)$ oraz $(3,3,3)$ .

XL OM - I - Zadanie 10

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Liczby dodatnie $\alpha$ , $\beta$ , $\gamma$ spełniają nierówności

$ \alpha+\beta+\gamma < \pi, \alpha < \beta + \gamma, \beta < \gamma + \alpha, \gamma < \alpha + \beta. $

Udowodnić, że z odcinków o długościach $\sin \alpha$ , $\sin \beta$ , $\sin \gamma$ można zbudować trójkąt i że pole tego trójkąta jest nie większe od

$ \frac{1}{8} (\sin 2\alpha + \sin 2\beta + \sin 2\gamma). $

Rozwiązanie

Wykażemy, że istnieje w przestrzeni kąt trójścienny $OABC$ taki, że

Możemy przyjąć, że $\gamma \geq \alpha$ , $\gamma\geq \alpha$ . Oczywiście $\gamma < \pi/2$ (gdyby bowiem było $\gamma \geq \pi/2$ , to mielibyśmy $\alpha+\beta< \pi - \gamma \leq \pi/2 \leq \gamma$ , wbrew założeniu). Zatem $2\gamma < \pi$ .

Weźmy pod uwagę kąt wypukły $AOB$ o rozwartości $2\gamma$ . W obszarze tego kąta (w jego płaszczyźnie) umieśćmy półproste $OA'^\rightarrow$ i $OB'^\rightarrow$ tak, by $|\measuredangle AOA' =2\beta$ , $|\measuredangle BOB'| = 2\alpha$ . Kąty wypukłe $AOA'$ i $BOB'$ mają niepustą część wspólną (bo $\alpha + \beta > \gamma$ ).

Niech $AOA''$ będzie obrazem kąta $AOA'$ w symetrii osiowej względem prostej $OA$ . Analogicznie określamy kąt $BOB''$ . Rozważamy kąty $A'O A''$ i $B'OB''$ , zawierające (odpowiednio) półproste $OA^\rightarrow$ i $OB^\rightarrow$ . Ich rozwartości wynoszą $4\beta$ i $4\alpha$ - a więc kąty te mogą nie być wypukłe. Mają one w każdym razie niepustą część wspólną, bo zawierają kąty $AOA'$ i $BOB'$ (rysunek 2).

Wychodzimy teraz z rozważaniami w przestrzeń. Obracając półprostą $OA'^\rightarrow$ wokół prostej $OA$ otrzymujemy powierzchnię obrotową, rozdzielającą przestrzeń na dwie części. Jedna z nich jest nieograniczonym stożkiem kołowym (wypukłym); drugą będziemy nazywać stożkiem wklęsłym. W szczególnym przypadku, gdy $\beta = \pi/4$ , obie te części są półprzestrzeniami (które też będziemy uważać za graniczną, ,,zdegenerowaną'' postać stożka); oczywiście rozdzielająca je powierzchnia jest w tym przypadku po prostu płaszczyzną.

Bierzemy pod uwagę ten stożek (wypukły lub wklęsły), który zawiera półprostą $OA^\rightarrow$ . Oznaczmy go przez $K_A$ . Rozwartość kąta przy wierzchołku stożka $K_A$ wynosi $4\beta$ ; płaski kąt $A'OA"$ jest jego przekrojem osiowym. Analogicznie określamy stożek $K_B$ (wypukły lub wklęsły), którego przekrojem osiowym jest kąt $B'OB"$ . Z poprzednich konkluzji wynika, że stożki $K_A$ i $K_B$ mają wspólne punkty wewnętrzne. Ich powierzchnie boczne przecinają się wzdłuż dwóch wspólnych tworzących, położonych symetrycznie względem płaszczyzny $OAB$ . Jedną z nich (dowolnie wybraną) oznaczymy przez $OC^\rightarrow$ . Tworzy ona z osią obrotu stożka $K_A$ , czyli z półprostą $OA^\rightarrow$ , kąt o mierze $2\beta$ , a z osią obrotu stożka $K_B$ , czyli z półprostą $OB^\rightarrow$ - kąt o mierze $2\alpha$ . Tak więc półproste $OA^\rightarrow$ , $OB^\rightarrow$ , $OC^\rightarrow$ tworzą poszukiwany kąt trójścienny (rysunek 2).

Możemy przyjąć, że punkty $A$ , $B$ , $C$ leżą na tych półprostych w odległości $1/2$ od punktu $O$ .

Niech M będzie środkiem odcinka AB. Wówczas

$ |\measuredangle AOM|=\gamma, \quad |AB| = 2|AM| = \sin \gamma, \quad |OM| = \frac{1}{2} \cos \gamma, $

$ \mathrm{pole}(AOB) = \frac{1}{2} |AB| \cdot |OM| = \frac{1}{8} \sin 2\gamma. $

Analogicznie

$ |BC| = \sin \alpha,\quad |CA|=\sin \beta, $

$ \mathrm{pole}(BOC) = \frac{1}{8} \sin 2\alpha , \mathrm{pole}(COA) = \frac{1}{8} \sin 2\beta . $

Zatem trójkąt $ABC$ ma boki długości $\sin \alpha$ , $\sin \beta$ , $\sin \gamma$ ; jest więc poszukiwanym trójkątem.

Rzuty dowolnych trzech ścian czworościanu na płaszczyznę czwartej ściany pokrywają tę ścianę, a pola rzutów nic są większe niż pola samych ścian. Wobec tego pole trójkąta $ABC$ nic jest większe od sumy pól trzech pozostałych ścian czworościanu $OABC$ , czyli nie przekracza wartości

$ \frac{1}{8} (\sin 2\alpha + \sin 2\beta + \sin 2\gamma) . $

To właśnie mieliśmy wykazać.

XL OM - I - Zadanie 11

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Punkty $A_1$ , $A_2$ , $A_3$ , $A_4$ leżą na powierzchni sfery, przy czym odległość każdych dwóch z nich jest mniejsza od długości krawędzi czworościanu foremnego wpisanego w tę sferę. Dowieść, że wszystkie te punkty można oświetlić jednym punktowym źródłem światła umieszczonym na zewnątrz sfery.

Rozwiązanie

Niech $C_1C_2C_3C_4$ będzie dowolnym czworościanem foremnym wpisanym w daną sferę; punkt $O$ niech będzie jej środkiem, a $r$ - długością promienia. Weźmy pod uwagę wektory

$ \mathbf{u} _k = \overrightarrow{OA_k},\quad \mathbf{u} _k = \overrightarrow{OC_k} \quad (k = 1,2,3,4) $

oraz sumę

$ (1) \qquad \mathbf{u}_1+\mathbf{u}_2+\mathbf{u}_3+\mathbf{u}_4=\mathbf{w}. $

Analogiczna suma utworzona dla wektorów $\mathbf{v}_k$ (wyznaczonych przez wierzchołki czworościanu foremnego i jego środek ciężkości) jest, rzecz jasna, wektorem zerowym:

$ (2) \qquad \mathbf{v}_1+\mathbf{v}_2+\mathbf{v}_3+\mathbf{v}_4= 0. $

Mnożymy skalarnie równość (1) stronami przez wektor $\mathbf{u}_1$ , a równość (2) przez $\mathbf{v}_1$ :

$ r^2 + \mathbf{u}_1 (\mathbf{u}_2+\mathbf{u}_3+\mathbf{u}_4) = \mathbf{u}_1 \cdot w , $

$ r^2 + \mathbf{v}_1 (\mathbf{v}_2+\mathbf{v}_3+\mathbf{v}_4) = 0 . $

Odejmując otrzymane równości stronami dostajemy

$ \mathbf{u}_1\cdot \mathbf{w} = \sum_{j=2}^4 (\mathbf{u}_1\cdot \mathbf{u}_j - \mathbf{v}_1\cdot \mathbf{v}_j). $

Zgodnie, z warunkiem zadania odległość $|A_i A_j|$ jest mniejsza od $|C_iC_j|$ dla dowolnej pary różnych wskaźników $i$ , $j$ . Wobec tego kąt między wektorami $\mathbf{u}_i$ , $\mathbf{u}_j$ jest mniejszy od kąta między wektorami $\mathbf{v}_i$ , $\mathbf{v}_j$ . To z kolei oznacza, że iloczyn skalarny $\mathbf{u}_i \cdot \mathbf{u}_j$ jest większy niż $\mathbf{v}_i \cdot \mathbf{v}_j$ dla $i \neq j$ Zatem wszystkie trzy różnice będące składnikami sumy po prawej stronie równości (3) są liczbami dodatnimi i w konsekwencji

$ \mathbf{u}_1 \cdot \mathbf{w} > 0. $

Możemy teraz powtórzyć to samo rozumowanie zastępując wektor $\mathbf{u}_1$ dowolnym spośród wektorów $\mathbf{u}_2$ , $\mathbf{u}_3$ , $\mathbf{u}_4$ . Wobec tego $\mathbf{u}_k \cdot \mathbf{w} >0$ dla $k = 1,2,3,4$ . Znaczy to, że wektory $\mathbf{u}_k$ tworzą z wektorem $\mathbf{w}$ kąty ostre. Stąd wniosek, że punkty $A_k$ leżą, wszystkie po jednej stronie płaszczyzny przechodzącej przez punkt $O$ i prostopadłej do wektora $\mathbf{w}$ - czyli leżą na jednej połówce rozważanej sfery. Można je więc oświetlić z punktu położonego poza tą sferą.

XL OM - I - Zadanie 12

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Udowodnić, że dla każdej liczby całkowitej $k\geq l$ istnieje taka liczba rzeczywista $x$ , że przy każdym całkowitym $m \geq 1$ liczba $[x^m] + 1$ dzieli się przez $k$ .

Użyjemy tożsamości

$ (3) \qquad (k + t)^m + (k-t)^m = 2 \sum_{j=0}^{[m/2]} k^{m-2}t^{2j} , $

zachodzącej dla dowolnych liczb $k$ , $t$ , a wynikającej natychmiast z wzoru dwumianowego. Zakładamy, że $k \geq 2$ jest daną w zadaniu liczbą całkowitą i przyjmujemy $t = \sqrt{k^2 - k}$ . Wówczas $t^2 = k^2 - k > (k -1)^2$ , więc

$ (4) \qquad 0 < k - t < 1. $

Po prawej stronie wzoru (3) liczba $t$ występuje tylko w parzystych potęgach. Wobec tego prawa strona (3) przedstawia liczbę całkowitą, i to będącą wielokrotnością $k$ . Lewa strona (3) ma postać sumy, której drugi składnik jest (w myśl (4)) liczbą z przedziału $(0; 1)$ . Wynika stąd, że jej pierwszy składnik ma część całkowitą o $1$ mniejszą od liczby napisanej po prawej stronie (3):

$ [(k + t)^m] + 1 = (\textrm{prawa strona} (3)) = (\textrm{wielokrotność} k). $

Wystarczy zatem przyjąć $x = k + t = k \sqrt{k^2-k}$ , by uczynić zadość postulatowi zadania.

XL OM - II etap

II etap XL Olimpiady Matematycznej

XL OM - II - Zadanie 1

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Rozwiązać równanie

$ \tg 7x - \sin 6x=\cos 4x - \ctg 7x. $

Rozwiązanie

Przepisujemy dane równanie w postaci

$ f(x) = g(x) , $

gdzie

$ f(x) = \tg 7x+\ctg 7x , \quad g(x) = \sin 6x + \cos 4x . $

Zarówno $f$ , jak i $g$ , jest funkcją okresową, o okresie $\pi$ . Wystarczy więc poszukiwać rozwiązań w zbiorze $(-\pi/2; 0) \cup (0; \pi/2)$ punkt $0$ oraz końce przedziału $(-\pi/2; \pi/2)$ zostały usunięte jako nie należące do dziedziny funkcji $f$ ).

Wyrażenie postaci $t + t^{-1}$ przyjmuje wyłącznie wartości o module nie mniejszym od $2$ ; oto uzasadnienie:

$ \left| t+ \frac{1}{t}\right| = \sqrt{\left(t+ \frac{1}{t}\right)^2}= \sqrt{\left(t- \frac{1}{t}\right)^2+4}\geq \sqrt{4}=2. $

Zatem $|f(x)| \geq 2$ dla każdego $x$ należącego do dziedziny funkcji $f$ . Jednocześnie $|g(x)| \leq | \sin 6x| +| \cos4x| \leq 2$ dlą każdego $x$ . Wobec tego równość $f(x)=g(x)$ zachodzi tylko wtedy gdy $f(x) - g(x) = 2$ lub $f(x) = g(x) = - 2$ . Z kolei równość $g(x) = \pm 2$ oznacza, że $\sin 6x = \cos 4x = \pm 1$ . Równanie $\cos 4x = -1$ ma w zbiorze $(-\pi/2;0) \cup (0;\pi/2)$ dwa rozwiązania: $x_1 = -\pi/4$ , $x_2 = -\pi/4$ ; równanie $\cos 4x = 1$ nie ma w tym zbiorze rozwiązań. Liczba $x$ spełnia przy tym równanie sin $\sin 6x =- 1$ ; liczba $x_2$ tego równania nie spełnia. Ponieważ zaś $f(\pi/4) = \tg (7\pi/4)+\ctg (7\pi/4) = -2$ , widzimy, że jedynym rozwiązaniem danego równania w rozważanym zbiorze jest liczba $\pi/4$ .

Uwzględniając wspomnianą na wstępie okresowość otrzymujemy zbiór liczb postaci

$ x=\frac{\pi}{4} + k \pi \quad (k \ \textrm{całkowite}) $

jako ogólne rozwiązanie podanego równania.

XL OM - II - Zadanie 2

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Dla losowo wybranej permutacji $\mathbf{f} = (f_1, \ldots, f_n)$ zbioru $\{1,\ldots, n\}$ oznaczmy przez $X(\mathbf{f})$ największą liczbę $k \leq n$ taką, że $f_i < f_{i+1}$ dla wszystkich numerów $i < k$ . Udowodnić, że wartość oczekiwana zmiennej losowej $X$ wynosi $\sum_{k=1}^n \frac{1}{k!}$ .

Rozwiązanie

Rozważana zmienna losowa zależy oczywiście od $n$ . Oznaczmy ją wobec tego przez $X_n$ . Znajdziemy zależność rekurencyjną między wartościami oczekiwanymi zmiennych $X_{n-1}$ i $X_n$ .

Weźmy dowolną permutację $f = (f_1, \ldots , f_n)$ zbioru $\{1,\ldots, n\}$ . Po odrzuceniu wyrazu $f_n$ otrzymujemy permutację pewnego $(n -1)$ - elementowego zbioru różnych liczb. Długość początkowego odcinka tworzącego ciąg rosnący to wartość zmiennej $X_{n-1}$ . (Nie jest bowiem istotne, czy permutowanym zbiorem jest, zgodnie z definicją $X_{n-1}$ , zbiór $\{1,\ldots, n-1\}$ , czy też dowolny inny zbiór liniowo uporządkowany przez relację mniejszości.)

Dołączamy z powrotem wyraz $f_n$ . Długość początkowego odcinka tworzącego ciąg rosnący pozostanie nie zmieniona lub zwiększy się o $1$ . Zwiększenie to nastąpi tylko w jednym przypadku: gdy permutacja $f$ jest identyczna z ciągiem $(1,2, \ldots , n)$ . Prawdopodobieństwo takiego zdarzenia wynosi $1/n!$ .

Dostajemy więc zależność

$ X_n= \left\{ \begin{array}{ll} X_{n-1} & \textrm{z prawdopodobieństwem } 1-1/n!\\ X_{n-1}+1 & \textrm{z prawdopodobieństwem } 1/n! \end{array} \right. $

Stąd natychmiast wynika wzór rekurencyjny

$ E(X_n) = E(X_{n-1}) + \frac{1}{n!} . $

Ponieważ zaś $E(X_1) = 1$ , dany do udowodnienia w zadaniu wzór otrzymujemy przez oczywistą indukcję.

XL OM - II - Zadanie 3

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Dany jest kąt trójścienny $OABC$ o wierzchołku $O$ oraz punkt $P$ w jego wnętrzu. Niech $V$ będzie objętością równoległościanu o dwóch wierzchołkach w punktach $O$ i $P$ , którego trzy krawędzie są zawarte w półprostych $OA^{\rightarrow}$ , $OB^{\rightarrow}$ , $OC^{\rightarrow}$ . Obliczyć minimalną objętość czworościanu, którego trzy ściany są zawarte w ścianach kąta trójściennego $OABC$ , a czwarta ściana zawiera punkt $P$ .

Rozwiązanie

Oznaczmy przez $\mathbf{Q}$ rozważany równołegłościan o objętości $V$ . Niech $OA$ , $OB$ , $OC$ będą jego trzema krawędziami. Prowadzimy przez punkt $P$ dowolną płaszczyznę przecinającą półproste $OA^\rightarrow$ , $OB^\rightarrow$ , $OC^\rightarrow$ odpowiednio w punktach $K$ , $L$ , $M$ (i wyznaczającą interesujący nas czworościan $OKLM$ ; jego objętość jest tą wielkością, której minimum mamy wyznaczyć).

Weźmy pod uwagę następujące trzy liczby (stosunki pól trójkątów):

$ x=\frac{\mathrm{pole}(PLM)}{\mathrm{pole}(KLM)}, \quad y=\frac{\mathrm{pole}(KPM)}{\mathrm{pole}(KLM)}, \quad z=\frac{\mathrm{pole}(KLP)}{\mathrm{pole}(KLM)}. $

Oczywiście $x, y, z > 0$ , $x + y + z = 1$ .

Oznaczmy odległości punktów $P$ i $M$ od płaszczyzny $ABC$ odpowiednio przez $d$ i $h$ , a odległości tych punktów od prostej $KL$ - przez $d'$ i $h'$ . Wobec równoległości prostej $CP$ do płaszczyzny $OAB$ zachodzi proporcja

$ \frac{|OC|}{|OM|}=\frac{d}{h}=\frac{d'}{h'}= \frac{\mathrm{pole}(KLP)}{\mathrm{pole}(KLM)}=z. $

Analogicznie można zinterpretować liczby $x$ i $y$ . Tak więc

$ (2) \qquad |OA| = x|OK| ,\quad |OB| = y|OL|, \quad |OC| = z|OM|. $

Z wzoru na objętość ostrosłupa oraz z zależności (1) i (2) otrzymujemy równość

$ \begin{split} \textrm{objętość}(OKLM) &= \frac{h}{3} \mathrm{pole}(OKL) = \frac{h}{6} |OK| \cdot |OL| \sin(\measuredangle KOL) =\\ &= \frac{h}{6}\cdot \frac{1}{x} |OA|\cdot \frac{1}{y} lOB| \sin(\measuredangle AOB) = \\ &=\frac{d}{6xyz}\cdot 2 \mathrm{pole}(OAB). \end{split} $

Podwojone pole trójkąta $OAB$ jest polem ściany równoległościanu $\mathbf{Q}$ zawartej w płaszczyźnie $\mathbf{OAB}$ ; liczba $d$ jest długością odpowiedniej wysokości tego równoległościanu. Zatem $d \cdot 2\mathrm{pole}(OAB) = \textrm{objętość}(\mathbf{Q}) = V$ . Stąd oraz z nierówności między średnią arytmetyczną i średnią geometryczną liczb $x$ , $y$ , $z$ wynika, że

$ \textrm{objętość}(OKLM) =\frac{V}{6xyz}\geq \frac{V}{6}\left( \frac{3}{x+y+z} \right)^3 = \frac{9}{2} V. $

Otrzymana nierówność staje się równością, gdy $x = y = z = 1$ , czyli gdy odcinki $OK$ , $OL$ , $OM$ są trzykrotnie dłuższe odpowiednio od $OA$ , $OB$ , $OC$ . To zaś zachodzi, gdy płaszczyzna $KLM$ jest poprowadzona przez punkt $P$ równolegle do płaszczyzny $ABC$ .

Liczba $\frac{9}{2} V$ jest więc szukanym minimum.

Uwaga. Gdy odcinki $OA$ , $OB$ , $OC$ są parami prostopadłe i mają równą długość, można je przyjąć za wersory osi kartezjańskiego układu współrzędnych. Całe rozumowanie daje się wówczas zgrabnie zapisać w języku geometrii analitycznej. Bowiem: $A = (1,0,0)$ , $B = (0,1,0)$ , $C = (0,0,1)$ , $P = (1,1,1)$ ; dowolna płaszczyzna przechodząca przez punkt $P$ dana jest równaniem postaci $ax + by + cz =$ 1, z dodatnimi współczynnikami $a$ , $b$ , $c$ dobranymi tak, by $a + b + c= 1$ . (Nietrudno zauważyć, że liczby $a$ , $b$ , $c$ - to nic innego niż liczby $x$ , $y$ , $z$ z poprzedniego sposobu rozwiązania; tym razem potrzebujemy liter $x$ , $y$ , $z$ na oznaczenie zmiennych układu współrzędnych; stąd zmiana notacji.) Rozważana płaszczyzna przecina osie układu w punktach $K = (1/a, 0,0)$ , $L= (0,1/fb,0)$ , $M = (0,0, 1/c)$ .

Równoleglościan $\mathbf{Q}$ jest teraz sześcianem; jego objętość $V$ równa się $1$ . Badany czworościan $OKLM$ ma objętość $(1/6)(1/a)(1/b)(1/c)$ . Jak poprzednio, stosując nierówność między średnimi stwierdzamy, że (przy stałej sumie $a + b + c = 1$ ) iloczyn abc osiąga maksimum, gdy $a = b = c = \frac{1}{3}$ ; .objętość czworościanu $OKLM$ osiąga wówczas minimum, równe $\frac{9}{2}$ .

Teza zadania jest więc udowodniona w bardzo szczególnym przypadku, gdy $|OA| = |OB| = |OC| = 1$ , $OA \bot OB \bot OC \bot OA$ . Ten ,,bardzo szczególny'' przypadek jest jednak, w pewnym sensie, całkiem ogólny. Powinno to być oczywiste dla wszystkich, którym nieobce jest pojęcie przekształceń afinicznych i ich najprostsze własności. Każdy równoległościan można afinicznie przekształcić na sześcian jednostkowy; zaś stosunek objętości jest niezmiennikiem przekształceń afinicznych przestrzeni trójwymiarowej. I właśnie te dwa spostrzeżenia wystarczą do tego, by z rozpatrzonego powyżej ,,bardzo szczególnego'' przypadku wydedukować tezę zadania w pełnej ogólności.

XL OM - II - Zadanie 4

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Dane są liczby całkowite $a_1, a_2, \ldots , a_{11}$ . Udowodnić, że istnieje taki niezerowy ciąg $x_1, x_2, \ldots, x_{11}$ o wyrazach ze zbioru $\{-1,0,1\}$ , że liczba $x_1a_1 + \ldots x_{11}a_{11}$ jest podzielna przez 1989.

Rozwiązanie

Każdemu $11$ - elementowemu ciągowi $(u_1,\ldots ,u_{11})$ o wyrazach równych $0$ lub $1$ przyporządkujmy liczbę $u_1a_1 + \ldots +u_{11}a_{11}$ . Wszystkich takich ciągów jest $2^{11}$ , a zatem więcej niż $1989$ . Istnieje wobec tego taka para ciągów $(u_1,\ldots, u_{11}) \neq (v_1, \ldots, v_n)$ , $u_i, v_i \in \{0,1\}$ , że przyporządkowane tym ciągom liczby

$ u_1a_1 + \ldots + u_{11}a_{11} \quad \textrm{oraz} \quad v_1a_1 + \ldots + v_{11}a_{11} $

dadzą przy dzieleniu przez $1989$ jednakowe reszty. A to znaczy, że liczba

$ (u_1 - v_1)a_1 + \ldots + (u_{11} - v_{11})a_11 $

jest podzielna przez $1989$ .

Wystarczy więc przyjąć $x_i = u_i -v_i$ dla $i = 1,\ldots , 11$ . Wyrazy ciągu $(x_1, \ldots, x_{11})$ są równe $0$ , $1$ lub $-1$ , przy czym nie wszystkie są zerami.

XL OM - II - Zadanie 5

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Dany jest ciąg $(c_n)$ liczb naturalnych określony rekurencyjnie: $c_1 = 2$ , $c_{n+1} = \left[ \frac{3}{2}c_n\right]$ . Udowodnić, że wśród wyrazów tego ciągu jest nieskończenie wiele liczb parzystych i nieskończenie wiele liczb nieparzystych.

Rozwiązanie

Wystarczy udowodnić następujące dwa stwierdzenia:

(a) Dla dowolnej liczby parzystej $p$ będącej wyrazem ciągu $(c_n)$ istnieje większa od niej liczba nieparzysta będąca wyrazem tego ciągu.

(b) Dla dowolnej liczby nieparzystej $q$ będącej wyrazem ciągu $(c_n)$ istnieje większa od niej liczba parzysta będąca wyrazem tego ciągu.

Dowód zdania (a). Niech $p = 2^km$ , $k,m \geq1$ , $m$ nieparzyste. Jeśli $p = c_n$ , to $c_{n+1} = 2^{k-1}\cdot 3m$ ; gdy $k -1 \geq 1$ , wówczas $c_{n+2} = 2^{k-2}\cdot 3^2m$ ; itd., ogólnie, dla $j \in \{1,\ldots, k\}$ mamy $c_{n-j} = 2^{k-j} \cdot 3^j m$ . W szczególności dla $j = k$ dostajemy $c_{n+k} = 3^km$ . Jest to większa niż p liczba nieparzysta.

Dowód zdania (b). Teraz $q - 1$ jest liczbą parzystą, dodatnią ( $q - 1$ nie może być zerem, bo $c_n \geq 2$ dla wszystkich $n$ ; to wynika przez natychmiastową indukcję z określenia ciągu $(c_n)$ ). Zatem $q = 2^km+1$ , $k,m \geq 1$ , $m$ nieparzyste. Jeśli $q = c_n$ , to $c_{n+1} = 2^{k-1}\cdot 3m + 1$ i ogólnie, jak poprzednio, dla $j\in \{1, \ldots, k\}$ mamy $c_{n+j} = 2^{k-j}\cdot 3^jm+1$ ; w szczególności $c_{n+k} = 3^km + 1$ . Jest to większa niż $q$ liczba parzysta.

XL OM - II - Zadanie 6

Zawody matematyczne:

XL OM, 1988-1989

Etap:

W trójkącie $ABC$ przez punkt wewnętrzny $P$ poprowadzono proste $CP$ , $AP$ , $BP$ przecinające boki $AB$ , $BC$ , $CA$ odpowiednio w punktach $K$ , $L$ , $M$ . Udowodnić, że jeśli w czworokąty $AKPM$ i $KBLP$ można wpisać koła, to w czworokąt $LCMP$ też można wpisać koło.

Rozwiązanie

Przez koło wpisane w czworokąt (wypukły lub wklęsły) będziemy rozumieli koło zawarte w tym czworokącie i styczne do czterech prostych zawierających jego boki. Warunkiem koniecznym i dostatecznym istnienia takiego koła jest równość sum długości przeciwległych boków czworokąta. Ten fakt, doskonale znany dla czworokątów wypukłych, mniej powszechnie jest znany dla czworokątów wklęsłych. Wszelako dowód w przypadku czworokąta wklęsłego otrzymuje się przez prostą adaptację zwykłego ,,podręcznikowego'' dowodu dla przypadku czworokąta wypukłego. Podamy go na końcu rozwiązania, w Uwadze.

Teza naszego zadania jest bezpośrednim wnioskiem z podanej własności: założenie zadania oznacza, że istnieją koła wpisane w czworokąty wklęsłe $PCAB$ i $PABC$ . Zatem (rysunek 3)

$ \begin{split} |PC| + |AB| = |PB| + |CA|,\\ |PA| + |BC| = |PC| + |AB|. \end{split} $

Stąd

$ |PA| + |BC| = |PB| + |CA|, $

a więc istnieje koło wpisane w czworokąt wklęsły $PBCA$ - czyli koło wpisane w czworokąt wypukły $LCMP$ .

Uwaga. Oto dowód twierdzenia mówiącego, ze w czworokąt wklęsły da się wpisać koło wtedy i tylko wtedy, gdy sumy długości przeciwległych boków są równe.

Niech $PABC$ będzie czworokątem wklęsłym; zakładamy, że punkt $P$ leży wewnątrz trójkąta $ABC$ . Przedłużenia boków $AP$ i $CP$ przecinają boki $BC$ i $AB$ odpowiednio w punktach $L$ i $K$ .

Przypuśćmy, żc istnieje koło styczne do prostych zawierających boki czworokąta $PABC$ . Jest to, mówiąc prościej, koło wpisane w czworokąt wypukły $PKBL$ . Oznaczmy przez $T$ , $U$ , $V$ , $W$ punkty styczności tego koła odpowiednio z bokami $PK$ , $KB$ , $BL$ , $LP$ (rysunek 4).

Następujące pary odcinków stycznych do rozważanego koła mają równe długości:

$ (1) \qquad \begin{split} |AU| = |WA|, \\ |PT| = |WP| \end{split} $

oraz

$ (2) \qquad \begin{split} |UB| = |BV|, \\ |CT| = |VC|. \end{split} $

Odejmujemy stronami obie równości (1):

$ |AU| - |PT| = |WA| - |WP| = |PA|. $

Dodajemy stronami równości (2):

$ |UB| + |CT| = |BV| + |VC| = |BC|. $

Dodajemy wreszcie stronami otrzymane równości i dostajemy:

$ (3) \qquad |PA| + |BC| = |AU| + |UB| + |CT| - |PT| = |AB| + |CP|, $

czyli równość, którą należało wykazać.

Pozostała do udowodnienia implikacja przeciwna: zakładając, że zachodzi równość (3), mamy dowieść, że w czworokąt wklęsły $PABC$ da się wpisać koło - czyli, że da się wpisać koło w czworokąt wypukły $PKBL$ .

Wpisujemy najpierw koło $\Omega$ w trójkąt $ABL$ . Prowadzimy z punktu $C$ prostą styczną do tego koła (różną od prostej $CB$ ), przecinającą odcinek $AB$ w punkcie $K'$ . Przypuśćmy, że punkt $K'$ nie pokrywa się z $K$ . Niech $P'$ będzie punktem przecięcia prostych $AL$ i $CK'$ ; powstaje (niezdegenerowany) trójkąt $CPP'$ (rysunek 5 przedstawia dwie możliwe konfiguracje).

Koło $\Omega$ jest wpisane w czworokąt wklęsły $PABC$ . Na mocy udowodnionej już części twierdzenia w czworokącie tym spełniona jest równość analogiczna do (3):

$ |P'A| + |BC| = |AB| + |CP'|. $

Odejmujemy tę równość stronami od (3) i stwierdzamy, że

$ |PA| - |P'A| = |CP| - |CP'|. $

Lewa strona ostatniej równości to - z dokładnością do znaku - długość odcinka $PP'$ . Uzyskujemy w ten sposób następujący związek między długościami boków trójkąta $CPP'$ :

$ |CP'| = |CP| \pm |PP'|. $

W trójkącie, który nie degeneruje się do odcinka, taka równość zachodzić nie może. Otrzymana sprzeczność jest wynikiem przypuszczenia, że $K' \ne K$ . Zatem punkt $K'$ musi pokrywać się z $K$ . A to znaczy, że koło $\Omega$ jest wpisane w czworokąt $PKBL$ ; dowód jest zakończony.

XL OM - III etap

III etap XL Olimpiady Matematycznej

XL OM - III - Zadanie 1

Zawody matematyczne:

XL OM, 1988-1989

Etap:

III

Do obrad przy okrągłym stole zasiadła parzysta liczba osób. Po przerwie obiadowej uczestnicy zajęli miejsca przy stole w sposób dowolny. Udowodnić, że istnieją dwie osoby przedzielone tą samą, co przed przerwą, liczbą osób.

Rozwiązanie

Oznaczmy liczbę osób przez $n$ . Numerujemy miejsca przy stole kolejno liczbami całkowitymi od $0$ do $n - 1$ ; miejsce nr $0$ i kierunek obiegu ustalamy dowolnie. Osoba zajmująca przed przerwą miejsce $k$ zajmuje po przerwie miejsce $m_k$ ; tak określony ciąg $(m_0,\ldots , m_{n-1})$ stanowi permutację zbioru $\{0,1,\ldots, n-1\}$ .

Przypuśćmy, że osoba z miejsca $k$ przesunęła się o $d_k$ miejsc (w ustalonym przez nas kierunku obiegu); $d_k \in \{0,1,\ldots, n - 1\}$ . Dla każdego $k$ zachodzi więc równość:

$ k + d_k = m_k \ \textrm{lub} \ k + d_k = m_k + n. $

Tę alternatywę można zapisać w postaci

$ (1) \qquad k + d_k = m_k + \epsilon_k n, \epsilon_k \in \{0,1\} , k = 0,1,\ldots, n-1. $

Dla dowodu tezy zadania wystarczy wykazać, że pewne dwie osoby przesunęły się o tyle samo miejsc, czyli, że $d_k = d_i$ dla pewnej pary różnych liczb $k$ , $l$ . Załóżmy więc, że tak nie jest. Wówczas ciąg $(d_0,d_1,\ldots, d_{n-1})$ stanowi permutację zbioru $\{0,1,\ldots, n - 1\}$ . A zatem

$ \sum_{k=0}^{n-1} d_k = \sum_{k=0}^{n-1} m_k = \sum_{k=0}^{n-1} k = \frac{n(n-1)}{2}. $

Dodając stronami $n$ równości (1) (sumowanie po $k$ od $0$ do $n-1$ ) otrzymujemy

$ \frac{n(n-1)}{2} + \frac{n(n-1)}{2} = \frac{n(n-1)}{2} + sn, \ \textrm{gdzie} s=\sum_{k=0}^{n-1} \epsilon_k. $

Stąd zaś wynika, że $s$ (liczba całkowita!) równa się $\frac{1}{2}(n-1)$ - wbrew założeniu, że $n$ jest liczbą parzystą. Sprzeczność kończy dowód.

XL OM - III - Zadanie 2

Zawody matematyczne:

XL OM, 1988-1989

Etap:

III

Na płaszczyźnie dane są trzy okręgi $k_1$ , $k_2$ , $k_3$ . Okręgi $k_2$ i $k_3$ są styczne zewnętrznie w punkcie $P$ , okręgi $k_3$ i $k_1$ — w punkcie $Q$ , okręgi $k_1$ i $k_2$ — w punkcie $R$ . Prosta $PQ$ przecina okrąg $k_1$ jeszcze w punkcie $S$ , a prosta $PR$ — w punkcie $T$ . Prosta $SR$ przecina okrąg $k_2$ również w punkcie $U$ , a prosta $TQ$ przecina $k_3$ jeszcze w punkcie $V$ . Udowodnić, że punkt $P$ leży na prostej $UV$ .

Rozwiązanie

Oznaczmy okrąg wpisany w trójkąt $O_1O_2O_3$ przez $k$ , jego środek przez $I$ , a środki okręgów $k_1$ , $k_2$ , $k_3$ - przez $O_1$ , $O_2$ , $O_3$ . Okrąg $k$ jest styczny do boków trójkąta $O_1O_2O_3$ w punktach $P$ , $Q$ , $R$ ; wymka to z równości $|O_1Q| = |O_1R|$ , $|O_2R| = |O_2P|$ , $|O_3P| = |O_3Q|$ .

Zachodzą następujące równości kątów (rysunek 6):

$ \begin{split} |\measuredangle RPQ| = \frac{1}{2} |\measuredangle RIQ| &\ \textrm{(kąt wpisany i kąt środkowy w okręgu } k);\\ |\measuredangle QSR| = \frac{1}{2}|\measuredangle QO_1R| &\ \textrm{(kąt wpisany i kąt środkowy w okręgu } h);\\ |\measuredangle QTR| = \frac{1}{2}|\measuredangle QO_1R| &\ \textrm{(kąt wpisany i kąt środkowy w okręgu } h);\\ |\measuredangle RIQ| + |\measuredangle QO_1R| = 180^\circ &\ \textrm{(przeciwległe kąty czworokąta } IQO_1R \textrm{ o pozostałych dwóch kątach prostych)}. \end{split} $

Z tych równości otrzymujemy z kolei związek

$ |\measuredangle QSR| = |\measuredangle QTR| = 90^\circ -|\measuredangle RPQ|, $

który oznacza, że trójkąty $PRS$ i $PQT$ są prostokątne: $PT \bot SU$ , $PS \bot TY$ .

Tak więc kąty $PRU$ i $PQV$ są proste. Są to kąty wpisane w okręgi $k_2$ i $k_3$ i muszą być oparte na półokręgach. Zatem odcinki $PU$ i $PV$ są średnicami tych okręgów; są wobec tego prostopadłe do wspólnej stycznej (prostej $PI$ ). Stąd wynika współliniowość punktów $U$ , $P$ , $V$ .

XL OM - III - Zadanie 3

Zawody matematyczne:

XL OM, 1988-1989

Etap:

III

Numerujemy krawędzie sześcianu liczbami od 1 do 12.
(a) Dowieść, że dla dowolnego ponumerowania istnieje co najmniej osiem trójek liczb całkowitych $(i,j,k)$ , gdzie $1\leq i< j < k\leq 12$ , takich, że krawędzie o numerach $i,j,k$ są kolejnymi bokami łamanej.
(b) Podać przykład ponumerowania, dla którego nie istnieje dziewięć trójek o własnościach wymienionych w (a).

Rozwiązanie

(a) Niech $V$ będzie dowolnym wierzchołkiem sześcianu i niech $p$ , $q$ , $r$ będą numerami krawędzi wychodzących z tego wierzchołka, przy czym $p < q < r$ . Pokażemy, że

$ \begin{split} (1) \qquad q \textrm{ jest środkowym wyrazem dwóch różnych trójek } (i,j,k) & \\ \textrm{o własnościach podanych w zadaniu}. & \end{split} $

Oznaczmy przez $W$ drugi koniec krawędzi o numerze $q$ . Numery pozostałych dwóch krawędzi wychodzących z $W$ oznaczmy przez $x$ i $y$ ; przyjmujmy, że $x < y$ .

Jeżeli $q < x$ , podane warunki spełniają trójki $(p,q,x)$ , $(p,q,y)$ .

Jeżeli $q > y$ , podane warunki spełniają trójki $(x, q, r)$ , $(y, q, r)$ .

Jeśli $x < q < y$ , dane warunki spełniają trójki $(p, q, y)$ , $(x, q, r)$ .

To dowodzi słuszności stwierdzenia (1).

Przyporządkujmy teraz każdemu z ośmiu wierzchołków sześcianu średni z trzech numerów krawędzi wychodzących z tego wierzchołka. Jedna liczba może być przyporządkowana co najwyżej dwóm wierzchołkom. Wśród przyporządkowanych liczb są więc co najmniej cztery różne. Każda z nich jest - zgodnie z (1) - środkowym wyrazem dwóch różnych trójek o żądanych własnościach. Istnieje zatem co najmniej osiem takich trójek.

(b) Cztery równoległe krawędzie numerujemy (w dowolny sposób) liczbami od $1$ do $4$ . Dalsze cztery równolegle krawędzie numerujemy liczbami od $5$ do $8$ . Wreszcie pozostałe cztery równoległe krawędzie numerujemy liczbami od $9$ do $12$ . Jeżeli trójka $(i,j,k)$ , $i < j < k$ , spełnia warunek podany w (a), to odcinki o numerach $i$ , $j$ , $k$ nie mogą leżeć w jednej płaszczyźnie (bo wówczas skrajne odcinki byłyby równoległe; ich numery byłyby oba większe albo oba mniejsze od numeru środkowej krawędzi). Muszą więc te odcinki reprezentować wszystkie trzy kierunki, a to znaczy, że $i \in \{1,2, 3,4\}$ , $j \in \{5,6, 7, 8\}$ , $k \in \{9,10,11,12\}$ . Przy tym każdy z odcinków o numerach $5$ , $6$ , $7$ , $8$ jest środkowym wyrazem dokładnie dwóch interesujących nas trójek.

Jest więc dokładnie osiem takich trójek.

XL OM - III - Zadanie 4

Zawody matematyczne:

XL OM, 1988-1989

Etap:

III

Niech $n, k$ będą liczbami naturalnymi. Wybieramy ciąg zbiorów $A_0,\ldots, A_k$ tak, że $A_0 = \{1,\ldots, n\}$ , a dla $i = 1,\ldots, k$ zbiór $A_i$ jest losowo wybranym podzbiorem $A_{i-1}$ , przy czym wybór każdego podzbioru jest jednakowo prawdopodobny. Rozpatrujemy zmienną losową równą liczbie elementów $A_k$ . Dowieść, że jej wartość oczekiwana jest równa $n2^{-k}$ .

Rozwiązanie

Wprowadzamy zmienne losowe $X_1, \ldots , X_n$ określone następująco:

$ X_i = \left\{ \begin{array}{ll} 1 & \textrm{jeśli} \ i \in A_k \\ 0 & \textrm{jeśli} \ i \not \in A_k \end{array} \right. $

\
( $i = 1,\ldots ,n$ ). Rozważana w zadaniu zmienna losowa $X$ (liczba elementów zbioru $A_k$ ) jest sumą wprowadzonych przed chwilą zmiennych:

$ X = X_1 + \ldots + X_n. $

Ustalmy liczbę $i \in A_0 = \{1, \ldots, n\}$ . Ponieważ $A_1$ jest losowo wybranym podzbiorem $A_0$ , liczba $i$ znajdzie się w zbiorze $A_1$ z prawdopodobieństwem

$ P(i \in A_1) = \frac{1}{2}; $

wynika to stąd, że zbiór $A_0$ ma tyle samo podzbiorów zawierających ustalony element $i$ , co podzbiorów nie zawierających tego elementu.

Z takim samym prawdopodobieństwem liczba $i$ trafi do zbioru $A_2$ - pod warunkiem, że wcześniej trafiła do $A_1$ :

$ P(i \in A_2 | i \in A_1) = \frac{1}{2}. $

Zatem

$ P(i \in A_2)=\left(\frac{1}{2}\right)^2. $

(Mówiąc mniej formalnie, a bardziej obrazowo: liczba $i$ znajdzie się w zbiorze $A_2$ , gdy dwa kolejne losowania okażą się dla niej ,,szczęśliwe''.) Kontynuując to rozumowanie stwierdzamy indukcyjnie, że

$ P(i \in A_j) = 2^{-j} \ \textrm{dla} \ j = 0,1,\ldots,k. $

Dla $j = k$ otrzymana równość $P(i \in A_k) = 2^{-k}$ oznacza, że zmienna losowa $X_i$ przyjmuje wartość $1$ z prawdopodobieństwem $2^{-k}$ (i wartość $0$ z prawdopodobieństwem $1-2^{-k}$ ). Stąd wynika, że jej wartość oczekiwana wynosi $2^{-k}$ .

Uzyskana konkluzja jest słuszna przy każdym wyborze $i \in \{1,\ldots, n\}$ . To znaczy, że liczba $2^{-k}$ jest wartością oczekiwaną każdej ze zmiennych losowych $X_1, \ldots , X_n$ . Wobec tego

$ E(X) = E(X_1) + \ldots + E(X_n) = n2^{-k}. $

XL OM - III - Zadanie 5

Zawody matematyczne:

XL OM, 1988-1989

Etap:

III

Na sferze o promieniu $r$ leżą trzy okręgi o promieniu $a$ , parami styczne i zawarte w jednej półsferze. Znaleźć promień okręgu leżącego na tej samej sferze i stycznego do każdego z tych trzech okręgów.

Uwaga Podobnie jak na płaszczyźnie, mówimy, że dwa okręgi leżące na sferze są styczne, jeśli mają dokładnie jeden punkt wspólny.

Rozwiązanie

Oznaczmy trzy dane okręgi (o promieniu $a$ ) przez $k_1$ , $k_2$ , $k_3$ . Załóżmy, że $k_0$ jest okręgiem o promieniu $x$ , położonym na tej samej sferze i stycznym do każdego z okręgów $k_1$ , $k_2$ , $k_3$ . Żaden z okręgów $k_1$ , $k_2$ , $k_3$ nie jest okręgiem wielkim danej sfery (dwa różne okręgi wielkie zawsze mają dwa punkty wspólne).

Niech $O$ będzie środkiem rozważanej sfery. Suma półprostych o wspólnym początku $O$ , przecinających okrąg $k_i$ , jest powierzchnią boczną nieograniczonego stożka kołowego, który oznaczymy przez $C_i$ : ( $i = 0,1,2,3$ ).

Okrąg $k_0$ może być okręgiem wielkim, brzegiem półsfery zawierającej okręgi $k_1$ , $k_2$ , $k_3$ . W takim przypadku suma półprostych o początku $O$ , wyznaczonych przez punkty okręgu $k_0$ , jest płaszczyzną. Umówmy się, że przez $C_0$ rozumiemy wówczas jedną z dwóch wyznaczonych przez tę płaszczyznę półprzestrzeni - tę, która zawiera okręgi $k_1$ , $k_2$ , $k_3$ . Mówiąc ,,stożek'' będziemy w dalszym ciągu dopuszczać także i ten przypadek, traktując półprzestrzeń jako graniczną (,,zdegenerowaną'') postać stożka.

Weźmy dwa różne numery $i, j \in \{0,1,2,3\}$ . Okręgi $k_i$ i $k_j$ mają dokładnie jeden punkt wspólny, zatem stożki $C_i$ i $C_j$ mają dokładnie jedną współną tworzącą. Mamy przy tym dwie możliwości: albo jeden z tych stożków zawiera się w drugim, albo też stożki te nie mają poza wspólną tworzącą innych punktów wspólnych. W pierwszym przypadku będziemy mówili o styczności wewnętrznej, w drugim - o styczności zewnętrznej.

Zauważmy, że dla każdej pary numerów $i, j \in \{1,2,3\}$ zachodzi ten drugi przypadek (wobec założonej równości promieni okręgów $k_1$ , $k_2$ , $k_3$ , inkluzja $C_i \subset C_j$ musiałaby być równością; okręgi $k_1$ i $k_j$ byłyby więc identyczne, wbrew temu, że mają tylko jeden punkt wspólny). Tak więc stożki $C_1$ , $C_2$ , $C_3$ są parami styczne zewnętrznie. Tworzące, wzdłuż których stożki te są styczne - to trzy różne półproste.

Wyobraźnia geometryczna ukazuje nam dwie konfiguracje:
I. Stożki $C_1$ , $C_2$ , $C_3$ są styczne wewnętrznie do $C_0$ .
II. Wszystkie cztery stożki są parami styczne zewnętrznie.

(W przypadku I okrąg $k_0$ ,,obejmuje'' trzy dane okręgi $k_1$ , $k_2$ , $k_3$ , w przypadku II jest ,,wpisany'' pomiędzy nie.)

Wykażemy, że istotnie musi zajść jedna z tych sytuacji.

Przypuśćmy, że tak nie jest. Wówczas co najmniej jeden ze stożków $C_1$ , $C_2$ , $C_3$ (na przykład $C_1$ ) jest styczny do $C_0$ wewnętrznie oraz co najmniej jeden z tych stożków (na przykład $C_2$ ) jest styczny do $C_0$ zewnętrznie. Trzeci stożek, $C_3$ , jest styczny zarówno do $C_1$ , jak i do $C_2$ (i to wzdłuż różnych tworzących). Pewne jego punkty muszą więc znajdować się wewnątrz stożka $C_0$ , a pewne - na zewnątrz. To się jednak nie da pogodzić ze stycznością $C_3$ do $C_0$ . Uzyskana sprzeczność pokazuje, że rzeczywiście nie ma innych możliwości niż I i II.

Przechodzimy do obliczeń.

Oznaczmy rozwartość kąta przy wierzchołku każdego ze stożków $C_1$ , $C_2$ , $C_3$ przez $2\alpha$ , a stożka $C_0$ - przez $2\varphi$ :

$ (1) \qquad \sin \alpha = \frac{a}{r}, \ \sin \varphi = \frac{x}{r}. $

Niech $A_i$ będzie środkiem okręgu $k_i \in (i = 0,1, 2, 3)$ . Trójkąt $A_1A_2A_3$ jest równoboczny. Długość jego boku wyznaczymy rozważając przekrój danych brył i figur płaszczyzną $OA_1A_2$ (rysunek 7):

$ |A_1 A_2 | = 2a \cos \alpha $

(na rysunkach $\pi_i$ oznacza ślad płaszczyzny okręgu $k_i$ ).

Oznaczmy przez $S$ środek trójkąta $A_1A_2A_3$ (czyli punkt będący jednocześnie środkiem okręgu wpisanego w ten trójkąt oraz środkiem okręgu opisanego na tym trójkącie). Jego odległość od wierzchołka równa się $\frac{2}{3}$ wysokości:

$ (2) \qquad |A_1S| = \frac{2}{3} \cdot \frac{1}{2} \sqrt{3} \cdot |A_1A_2| = \frac{2}{3} \sqrt{3} a \cos \alpha. $

Odcinek $OA_1$ jest wysokością trójkąta równoramiennego o dwóch bokach długości $r$ , tworzących kąt o mierze $2\alpha$ . A zatem

$ (3) \qquad |OA_1| = r \cos \alpha. $

Weźmy teraz pod uwagę przekrój płaszczyzną $OA_0A_1$ . Niech $B$ będzie punktem styczności okręgów $k_0$ i $k_1$ .

Mamy równości: $| \measuredangle SOB| = \varphi$ ; $|A_1B| = a$ , $|A_0B| = x$ . Rozwartość kąta $SOA_1$ wynosi: $\varphi - \alpha$ w przypadku I oraz $\varphi + \alpha$ w przypadku II (rysunki 8 i 9 ilustrują te dwie sytuacje). Wobec tego, zgodnie z (1),

$ (4) \qquad \sin | \measuredangle SOA_1 | = \sin (\varphi \pm \alpha) = \frac{x}{r} \sqrt{1-\frac{a^2}{r^2}} \pm \frac{a}{r} \sqrt{1-\frac{x^2}{r^2}} $

(znak minus w przypadku I, plus w przypadku II). Jednocześnie, wobec związków (2) i (3), mamy równość

$ (5) \qquad \sin |\measuredangle SOA_1| = \frac{A_1S}{OA_1} = \frac{2\sqrt{3}}{3} \cdot \frac{a}{r}. $

Przyrównując prawe strony (4) i (5) dostajemy równanie

$ (6) \qquad \frac{2\sqrt{3}}{3} \cdot \frac{a}{r} - \frac{x}{r} \sqrt{1-\frac{a^2}{r^2}} = \pm \frac{a}{r} \sqrt{1-\frac{x^2}{r^2}}, $

które - po podniesieniu stronami do kwadratu i dalszych przekształceniach - przybiera postać

$ (7) \qquad x^2 - \frac{4\sqrt{3}}{3} \cdot \frac{a}{r} \sqrt{r^2-a^2} \cdot x + \frac{a^2}{3} = 0. $

Pierwiastkami równania kwadratowego (7) są liczby

$ \begin{split} (8) \qquad x_1 = \frac{2\sqrt{3}}{3} \cdot \frac{a}{r} \left( \sqrt{r^2-a^2} + \frac{1}{2} \sqrt{3r^2 - 4a^2} \right),\\ x_2 = \frac{2\sqrt{3}}{3} \cdot \frac{a}{r} \left( \sqrt{r^2-a^2} - \frac{1}{2} \sqrt{3r^2 - 4a^2} \right); \end{split} $

wyrażenia podpierwiastkowe są nieujemne, co wynika ze związku (5): $2a \leq \sqrt{3} r$ . Liczba $x_1$ spełnia równanie pierwiastkowe (6) ze znakiem minus po prawej stronie, $x_2$ zaś - ze znakiem plus.

Stąd wynika odpowiedź:
Dla każdej trójki parami stycznych okręgów o promieniach równej długości $a$ (na półsferze o promieniu $r$ ) istnieją dwa okręgi styczne do każdego z tych trzech okręgów, usytuowane w sposób opisany powyżej (konfiguracje I i II). Ich promienie są dane wzorami (8); wartość $x_1$ odpowiada konfiguracji I, a wartość $x_2$ - konfiguracji II.

XL OM - III - Zadanie 6

Zawody matematyczne:

XL OM, 1988-1989

Etap:

III

Udowodnić, że dla dowolnych liczb dodatnich $a, b, c, d$ spełniona jest nierówność

$ \sqrt{\frac{ab+ac+ad+bc+bd+cd}{6}} \geq \sqrt{\frac{abc+abd+acd+bcd}{6}}. $

Rozwiązanie

Przyjmijmy oznaczenia:

$ \begin{split} A &= a + b + c + d,\\ B &= ab + ac + ad + bc + bd + cd, \\ C &= abc + abd + acd + bed, \\ D &= abcd. \end{split} $

Liczby $A$ , $B$ , $C$ , $D$ są współczynnikami wielomianu

$ P(x) = (x + a)(x + b)(x + c)(x + d) = x^4 + Ax^3 + Bx^2 + Cx + D. $

Jest to wielomian czwartego stopnia, mający cztery pierwiastki ujemne: $-a$ , $-b$ , $-c$ , $-d$ (jeśli któreś z tych liczb są równe, mamy pierwiastek wielokrotny).

Różniczkujemy wielomian $P$ :

$ (2) \qquad P'(x) = 4x^3 + 3Ax^2 + 2Bx + C. $

Na mocy twierdzenia Rolle'a między każdymi dwoma kolejnymi różnymi pierwiastkami wielomianu $P$ znajduje się pierwiastek pochodnej $P'$ ; ponadto, jeśli pewien punkt jest pierwiastkiem $k$ -krotnym wielomianu $P$ , to jest on pierwiastkiem ( $k-1$ )-krotnym wielomianu $P'$ . Stąd wynika, że wielomian $P'$ ma (licząc z krotnościami) co najmniej trzy pierwiastki w przedziale $\langle \beta; - \alpha \rangle$ , gdzie $\alpha$ jest najmniejszą, a $\beta$ największą z liczb $a$ , $b$ , $c$ , $d$ ; ma więc trzy pierwiastki ujemne. Oznaczmy je przez $-p$ , $-q$ , $-r$ ( $p, q, r > 0$ ). Ponieważ $P'$ jest wielomianem trzeciego stopnia, nie ma on już innych pierwiastków. Ma zatem postać

$ P'(x) = 4(x + p)(x + q)(x + r) ; $

czynnik $4$ na początku pojawia się dlatego, że współczynnik przy najwyższej potędze zmiennej w wielomianie $P'$ wynosi 4 (por.wzór (2)). Po wymnożeniu dwumianów w nawiasach otrzymujemy

$ (3) \qquad P'(x) = 4x^3 + 4(p + q + r)x^2 + 4(pq + qr + rp)x + Apqr. $

Przyrównując współczynniki wielomianów (2) i (3) dostajemy równości

$ (4) \qquad pq + qr + rp = \frac{1}{2} B, \ pqr = \frac{1}{4}C . $

Między średnią arytmetyczną 1 średnią geometryczną liczb $pq$ , $qr$ , $rp$ zachodzi nierówność

$ \frac{1}{3}(pq + qr + rp) \geq (pq \cdot qr \cdot rp)^{1/3} = (pqr)^{2/3}, $

którą, w myśl wzorów (4), możemy przepisać w postaci

$ (5) \qquad \left( \frac{1}{6}B \right)^{1/2} \geq \left( \frac{1}{4} C\right)^{1/3} . $

Jest to właśnie nierówność, którą mieliśmy udowodnić.

Uwaga 2. Rozważana w tym zadaniu nierówność jest szczególnym przypadkiem ogólniejszego twierdzenia.

Niech będą dane liczby naturalne $n$ , $k$ ( $n \geq k \geq 1$ ) oraz liczby rzeczywiste $a_1,\ldots, a_n \geq 0$ . Średnią symetryczną rzędu $k$ liczb $a_1,\ldots, a_n$ nazywamy wielkość

$ \sigma_k(a_1, \ldots, a_n) = \left( \binom{n}{k} ^{-1} \sum a_{i_1} \ldots a_{i_k} \ \right) ^{1/k}, $

gdzie sumowanie rozciągnięte jest na wszystkie $k$ -wyrazowe układy wskaźników $(i_1,\ldots, i_k)$ , $1 \leq i_1 < ... < i_k \leq n$ . Tak więc

$ \begin{split} \sigma_1(a_1, \ldots, a_n) &= \binom{n}{1}^{-1} \sum_{i=1}^n a_i = \frac{a_1 + \ldots + a_n}{n},\\ \sigma_2(a_1, \ldots, a_n) &= \left( \binom{n}{2}^{-1} \sum_{i<j} a_ia_j \right)^{1/2} = \sqrt{\frac{2a_1a_2 + \ldots}{n(n-1)}},\\ \sigma_3(a_1, \ldots, a_n) &= \left( \binom{n}{3}^{-1} \sum_{i<j<l} a_ia_ja_l \right)^{1/3} = \sqrt[3]{\frac{6(a_1a_2a_3 + \ldots)}{n(n-1)(n-2)}},\\ &\ \vdots \\ \sigma_n(a_1, \ldots, a_n) &= \left(\binom{n}{n}^{-1} a_1a_2 \ldots a_n \right)^{1/n} = \sqrt[n]{a_1a_2\ldots a_n}. \end{split} $

Teza naszego zadania mówi, że

$ (13) \qquad \sigma_2(a,b,c,d) \geq \sigma_3(a,b,c,d). $

Prawdziwe są także nierówności

$ (14) \qquad \sigma_1(a,b,c,d) \geq \sigma_2(a,b,c,d) \ \textrm{i} \ \sigma_3(a,b,c,d) \geq \sigma_4(0,b,c,d) $

(w odróżnieniu od (13), dowody nierówności (14) są całkiem prostym ćwiczeniem).

Nietrudno się domyśleć, że ogólnie, dla $n$ liczb:

$ \sigma_1(a_1,\ldots ,a_n) \geq \sigma_2(a_1,\ldots ,a_n) \geq \ldots \geq \sigma_n(a_1,\ldots, a_n). $

Są to nierówności McLaurina; dowód można znaleźć na przykład w książce: D.S.Mitrinović Analytic Inequalities, Berlin-Heidelberg-New York 1970 (rozdział 2.15, twierdzenie 4).