XXI OM

XXI Olimpiada Matematyczna

Opracowanie rozwiązań: Jerzy Browkin

XXI OM - I etap

I etap XXI Olimpiady Matematycznej

XXI OM - I -Zadanie 1

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

Rozwiązać w liczbach całkowitych równanie

$ \frac{1}{x^2} + \frac{1}{xy} + \frac{1}{y^2} = 1. $

Rozwiązanie

Jeśli $|x| \geq 2$ i $|y| \geq 2$ , to

$ \frac{1}{x^2} + \frac{1}{xy} + \frac{1}{y^2} \leq \frac{1}{x^2} + \frac{1}{|xy|} + \frac{1}{y^2} \leq \frac{1}{4} + \frac{1}{4} + \frac{1}{4} < 1. $

Zatem, jeśli para liczb całkowitych $x$ , $y$ jest rozwiązaniem równania (1), to $|x| = 1$ lub $|y| = 1$ . Jeżeli $|x| = 1$ , to równanie to przyjmuje postać $1 + \frac{1}{xy} + \frac{1}{y^2}= 1$ , czyli $\frac{x+y}{xy^2} = 0$ . Wobec tego $x + y = 0$ . Wynika stąd, że jeśli $x = 1$ , to $y = - 1$ i jeśli $x = - 1$ , to $y = 1$ .

Rozpatrując podobnie przypadek $|y| = 1$ otrzymujemy, że jeśli $y = \pm 1$ , to $x = \mp 1$ . Równanie (1) ma więc dwa rozwiązania $(-1, 1)$ i $(1, -1)$ w liczbach całkowitych.

XXI OM - I -Zadanie 2

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

Dany jest ciąg $\{c_n\}$ określony wzorami $c_1=\frac{a}{2}$ , $c_{n+1}=\frac{a+c_n^2}{2}$ gdzie $a$ jest daną liczbą spełniającą nierówność $0 < a < 1$ . Dowieść, że dla każdego $n$ zachodzi nierówność $c_n < 1 - \sqrt{1 - a}$ Wykazać zbieżność ciągu $\{c_n\}$ i obliczyć jego granicę.

Rozwiązanie

Z określenia ciągu $\{c_n\}$ wynika, że wszystkie jego wyrazy są dodatnie. Stosując metodę indukcji wykażemy, że dla każdej liczby naturalnej $n$ zachodzi nierówność

$ (1) \qquad c_n < 1 - \sqrt{1-a}. $

Stwierdzamy najpierw, że $c_1 < 1 - \sqrt{1 - a}$ , tzn., że

$ (2) \qquad \frac{a}{2} < 1 - \sqrt{1-a}. $

Mianowicie mamy

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

Wynika stąd (2).

Jeśli zaś dla pewnej liczby naturalnej $n$ zachodzi nierówność

$ \begin{split} c_n & < 1 - \sqrt{1-a}, \textrm{ to } c_{n+1} = \frac{a + c^2_n}{2} < \frac{a}{2} + \frac{1}{2} (1 - \sqrt{1-a})^2 =\\ &= \frac{a}{2} + \frac{1}{2} (1 - 2 \sqrt{1-a} + 1 -a) = \frac{a}{2} + 1 - \frac{a}{2} - \sqrt{1-a} = 1 - \sqrt{1-a}. \end{split} $

Na mocy indukcji nierówność (1) jest więc prawdziwa dla każdej liczby naturalnej $n$ .

Udowodnimy, że ciąg $\{c_n\}$ jest rosnący, tzn., że dla każdej liczby naturalnej $n$ zachodzi nierówność

$ (3) \qquad c_{n+1} > c_n. $

Obliczamy, że

$ \begin{split} c_{n+1} - c_n &= \frac{a+c_n^2}{2} - c_n = \frac{a+c_n^2 - 2c_n}{2}= \frac{(c_n-1)^2 - (1-a)}{2} =\\ &=\frac{(c_n-1)^2 - (\sqrt{1-a})^2}{2} = \frac{(c_n-1-\sqrt{1-a})(c_n-1+\sqrt{1-a})}{1}. \end{split} $

Dowiedliśmy, że $c_n < 1 - \sqrt{1 - a}$ , a więc tym bardziej $c_n < 1 + \sqrt{1 - a}$ . Wobec tego $c_n - 1 + \sqrt{1 -a} < 0$ i $c_n - 1 - \sqrt{1 - a} < 0$ . Zatem $c_{n+1} - c_n > 0$ . Wykazaliśmy więc, że ciąg $\{c_n\}$ jest rosnący i ograniczony z góry.

Jak wiadomo, każdy ciąg rosnący i ograniczony z góry jest zbieżny. Oznaczmy $\displaystyle \lim_{n \to \infty} c_n = g$ .

Z równości $c_{n+1} = \frac{a + c_n^2}{2}$ wynika, że $g = \frac{a + g^2}{2}$ , czyli $g^2 - 2g + a = 0$ . Otrzymujemy stąd, że

$ g = \frac{2\pm \sqrt{4-4a}}{2} = 1 \pm \sqrt{1-a}. $

Ponieważ jednak wszystkie wyrazy ciągu $\{c_n\}$ są mniejsze od liczby $1 - \sqrt{1 - a}$ , a $1- \sqrt{1 - a} < 1 + \sqrt{1 - a}$ , więc liczba $1 + \sqrt{1 - a}$ nie jest granicą ciągu $\{c_n\}$ . Wobec tego $\displaystyle \lim_{n \to \infty} c_n = 1 - \sqrt{1 - a}$ .

XXI OM - I -Zadanie 3

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

Na bokach $\overline{BC}$ , $\overline{CA}$ , $\overline{AB}$ trójkąta $ABC$ obrano odpowiednio punkty $K, L, M$ w taki sposób, że odcinki $\overline{AK}$ , $\overline{BL}$ , $\overline{CM}$ przecinają się w punkcie o lezącym wewnątrz trójkąta i $\frac{AS}{SK}=\frac{BS}{SL}=\frac{CS}{SM}$ . Dowieść, że $S$ jest środkiem ciężkości trójkąta.

Rozwiązanie

Z danej równości stosunków wynika, że trójkąty $KLM$ i $ABC$ (rys. 3) są jednokładne względem punktu $S$ , wobec czego proste $KL$ , $LM$ , $MK$ są odpowiednio równoległe do prostych $AB$ , $BC$ , $CA$ . Stosując twierdzenie Talesa kolejno do kątów $\measuredangle A$ , $\measuredangle B$ , $\measuredangle C$ otrzymujemy

$ \frac{AM}{BM} = \frac{AC}{CL} $

$ (1) \qquad \frac{BM}{AM} = \frac{BK}{CK} $

$ (2) \qquad \frac{CK}{BK} = \frac{CL}{AL}. $

Mnożąc te równości stronami otrzymujemy, że $\frac{CK}{BK} = \frac{BK}{CK}$ . Zatem $CK^2 = BK^2$ , czyli $CK = BK$ . Podstawiając $CK = BK$ do (1) i (2) otrzymujemy, że $AM = BM$ i $AL = CL$ . Oznacza to, że punkty $K$ , $L$ , $M$ są odpowiednio środkami odcinków $\overline{BC}$ , $\overline{AC}$ i $\overline{AB}$ . Wobec tego $S$ jest środkiem ciężkości trójkąta $ABC$ .

XXI OM - I -Zadanie 4

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

W kwadracie $ABCD$ , którego bok ma długość 1, leży czworokąt wypukły o polu większym od $\frac{1}{2}$ . Dowieść, że w tym czworokącie mieści się odcinek o długości $\frac{1}{2}$ równoległy do $\overline{AB}$ .

Rozwiązanie

Prowadzimy przez wierzchołki danego czworokąta proste równoległe do prostej $AB$ (rys. 4). W przypadku, gdy proste te są różne, czworokąt zostaje podzielony na $3$ części: trójkąt o podstawie $p$ i wysokości $h_1$ , trapez o podstawach $p$ i $q$ i wysokości $h_2$ oraz trójkąt o podstawie $q$ i wysokości $h_3$ . Z założenia pole czworokąta $P$ jest większe od $\frac{1}{2}$ . Z drugiej strony

$ P = \frac{1}{2} ph_1 + \frac{1}{2} (p + q)h_2 + \frac{1}{2} qh_3. $

Zatem

$ \frac{1}{2} ph_1 + \frac{1}{2} (p + q)h_2 + \frac{1}{2} qh_3 > \frac{1}{2}. $

Stąd

$ p(h_1 + h_2) + q(h_2 + h_3) > 1. $

Ponieważ $h_1 + h_2 \leq 1$ i $h_2 + h_3 \leq 1$ , więc otrzymujemy stąd, że $p + q \geq p(h_1 + h_2) + g(h_2 + h_3) > 1$ .

Zatem co najmniej jedna z liczb $p$ i $q$ jest większa od $\frac{1}{2}$ .

Przy szczególnych położeniach danego czworokąta rozważane trójkąty lub trapez mogą degenerować się do odcinka, tzn. może być $h_1 = 0$ lub $h_2 = 0$ lub $h_3 = 0$ . Jednak również w takim przypadku powyższe rozumowanie pozostaje w mocy.

Uwagi

1. Zadanie to można uogólnić na przypadek dowolnych figur wypukłych: Jeśli pole pewnej figury wypukłej zawartej w kwadracie $ABCD$ o boku $1$ jest większe od $\frac{1}{2}$ , to w tej figurze mieści się odcinek o długości $\frac{1}{2}$ równoległy do $\overline{AB}$ .

2. Analogicznie twierdzenie jest prawdziwe również w przypadku czworokąta niewypukłego; jednak już dla sześciokąta niewypukłego podobne twierdzenie nie zachodzi.

XXI OM - I -Zadanie 5

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

Dane są liczby rzeczywiste $M$ , $a_1, a_2, \ldots, a_10$ . Udowodnić, że jeżeli $a_1x_1 + a_2x_2 + \ldots + a_{10}x_{10} \leq M$ dla wszystkich takich $x_i$ , że $|x_i| = 1$ ( $i = 1, 2, \ldots, 10$ ), to

$ \sqrt{a_1^2 + a_2^2 + \ldots + a_{10}^2} \leq M. $

Rozwiązanie

Jeśli $a_i \geq 0$ , to podstawiamy do danej nierówności $x_i = 1$ , a jeśli $a_i < 0$ , to podstawiamy $x_i = - 1$ przy $i = 1, 2, \ldots, 10$ . Otrzymamy wtedy

$ |a_1| + |a_2| + \ldots + |a_{10}| \leq M. $

Z nierówności tej wynika, że $|a_i| \leq M$ dla $i = 1, 2, \ldots, 10$ . Stąd $|a_i|^2 \leq |a_i|M$ i wobec tego

$ \sum_{i=1}^{10} a_i^2 = \sum_{i=1}^{10} |a_i|^2 \leq \sum_{i=1}^{10} |a_i| M = M \sum_{i=1}^{10} |a_i| \leq M^2. $

Zatem

$ \sqrt{\sum_{i=1}^{10} a_i^2} \leq M. $

XXI OM - I -Zadanie 6

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

Udowodnić, że liczba rzeczywista $a$ jest wymierna wtedy i tylko wtedy, gdy istnieją takie liczby całkowite $p > n > m \leq 0$ , że $a + m, a + n, a + p$ tworzą ciąg geometryczny.

Rozwiązanie

Niech $a$ będzie liczbą wymierną. Obieramy taką liczbę naturalną $m$ , że $a + m > 0$ . Wtedy

$ a + m = \frac{r}{q}, $

gdzie $r$ i $q$ są liczbami naturalnymi.

Rozpatrzmy ciąg geometryczny o ilorazie $1 + q$ i pierwszym wyrazie $\frac{r}{q}$ . Zatem kolejnymi wyrazami ciągu będą r

$ \frac{r}{q} = a + m, $

$ \frac{r}{q} (1 + q) = \frac{r}{q} + r = a + m + r, $

$ \frac{r}{q} (1 + q)^2 = \frac{r}{q} (1 + 2q + q^2) = \frac{r}{q} +2r + rq = a + m + 2r + rq. $

Przyjmując więc $n = m + r$ i $p = m + 2r + rq$ stwierdzamy, że $m$ , $n$ , $p$ są liczbami całkowitymi spełniającymi warunek $0 \leq m < n < p$ . Ponadto liczby $a + m$ , $a + n$ , $a + p$ tworzą ciąg geometryczny.

Na odwrót przypuśćmy, że liczby całkowite $m$ , $n$ , $p$ spełniają warunek $0 \leq m< n <p$ oraz, że dla pewnej liczby rzeczywistej $a$ liczby $a + m$ , $a + n$ , $a + p$ tworzą ciąg geometryczny.

Oznaczmy przez $1 + q$ iloraz tego ciągu. Wtedy

$ a + n = (a + m)(1 + q) = (a + m) + ( a + m)q, $

$ a + p = (a + m)(1 + q)^2 = (a + m) + 2(a + m)q + (a + m)q^2. $

Wobec tego

$ (1) \qquad (a + m)q = n - m $

$ (2) \qquad (a + m)q^2 = p-m - 2(a + m)q = p-m-2(n-m)=p+m-2n. $

Ponieważ $n > m$ , więc z (1) wynika, $a + m \ne 0$ i $q \ne 0$ . Dzieląc stronami (2) i (1) otrzymujemy, że

$ q = \frac{p+m-2n}{n-m}, \textrm{ a więc } q \textrm{ jest liczbą wymierną}. $

Wobec tego z (1) wynika, że $a = \frac{n-m}{q} -m$ jest również liczbą wymierną.

XXI OM - I -Zadanie 7

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

W równoległoboku $ABCD$ połączono punkt $A$ ze środkiem $A'$ boku $\overline{BC}$ , punkt $B$ ze środkiem $B'$ boku $\overline{CD}$ , punkt $C$ ze środkiem $C'$ boku $\overline{DA}$ oraz punkt $D$ ze środkiem $D'$ boku $\overline{AB}$ . Udowodnić, że punkty przecięcia prostych $AA'$ i $BB'$ ; $BB'$ i $CC'$ ; $CC'$ i $DD'$ ; $DD'$ i $AA'$ są wierzchołkami czworokąta o polu 5 razy mniejszym od pola równoległoboku $ABCD$ .

Rozwiązanie

Rozpatrzmy trójkąty $ADD'$ i $CBB'$ (rys. 5). Są one przystające, ponieważ $AD' = CB'$ , $AD = CB$ i $\measuredangle D'AD = \measuredangle B'CB$ .

Zatem $\measuredangle AD'D = \measuredangle CB'B$ . Wynika stąd, że proste $DD'$ i $BB'$ są równoległe. Analogicznie dowodzimy, że proste $AA'$ i $CC'$ też są równoległe. Zatem czworokąt $PQRS$ jest równoległobokiem. Rozpatrzmy trójkąty $APD'$ i $AQB$ . Są one podobne ponieważ $\measuredangle PAD' = \measuredangle QAB$ (kąt wspólny) oraz $\measuredangle AD'P = \measuredangle ABQ$ (kąty odpowiadające).

Wobec tego

$ (1) \qquad \frac{D'P}{BQ} = \frac{AD'}{AB} = \frac{1}{2}. $

Stosując twierdzenie Talesa do kąta $\measuredangle B'BC$ otrzymujemy

$ (2) \qquad \frac{BQ}{QR} = \frac{BA'}{A'C} = 1. $

Stosując twierdzenie Talesa do kąta $\measuredangle ADP$ otrzymujemy

$ (3) \qquad \frac{PS}{SD} = \frac{AC'}{C'D} = 1. $

Z (1) i (2) wynika, że $D'P = \frac{1}{2} BQ = \frac{1}{2} QR$ .

Wiemy ponadto z (3), że $PS = SD$ oraz, że $QR = PS$ , ponieważ $PQRS$ jest równoległobokiem.

Wobec tego $D'D = D'P + PS + SD = \frac{1}{2} QR + QR + QR = \frac{5}{2} QR = \frac{5}{2}$ .

Stąd $S_{DD'BB'} = \frac{5}{2} S_{PQRS}$ , ponieważ równoległoboki $DD'BB'$ i $PQRS$ mają jednakowe wysokości, a podstawa pierwszego z nich jest $\frac{5}{2}$ razy większa niż podstawa drugiego.

Analogicznie stwierdzamy, że $S_{DD'BB'} = \frac{1}{2} S_{ABCD}$ . Z ostatnich dwóch równości otrzymujemy, że

$ S_{PQRS} = \frac{1}{5} S_{ABCD}. $

XXI OM - I -Zadanie 8

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

Na stole bilardowym w kształcie kwadratu znajduje się kula. Kulą pchnięto tak, że odbiła się od bandy (kąt padania równa się kątowi odbicia) pod kątem $\alpha$ . Dowieść, że kula będzie sią poruszać po łamanej zamkniętej wtedy i tylko wtedy, gdy $\tan \alpha$ . jest liczbą wymierną. Siłę tarcia oraz wymiary kuli pomijamy.

Rozwiązanie

Załóżmy dla uproszczenia, że stół bilardowy jest kwadratem o wierzchołkach w punktach $A(0, 0)$ , $B(1, 0)$ , $C(1, 1)$ , $D(0, 1)$ (rys. 6). Niech w chwili początkowej kula znajduje się w punkcie $P(a, b)$ , gdzie $0 < a < 1$ , $0 < b < 1$ .

Oznaczmy przez $v$ prędkość, z jaką się ona porusza w chwili początkowej, a przez $\alpha$ - kąt, jaki tworzy kierunek jej ruchu z osią $x$ . Bez zmniejszenia ogólności możemy założyć, że $0^\circ \leq \alpha \leq 90^\circ$ . Jeśli $\alpha = 0^\circ$ lub $\alpha = 90^\circ$ , to kula porusza się po odcinku równoległym do osi $x$ lub $y$ . Załóżmy więc, że $0^\circ < \alpha < 90^\circ$ .

Rozpatrzmy rzuty $P_x = P_x (t)$ i $P_y = P_y (t)$ odpowiednio na oś $x$ i $y$ punktu, w którym znajduje się kula w chwili $t$ . Z warunków zadania wynika, że punkt $P_x$ porusza się ruchem jednostajnym z prędkością $v_1 = v \cos \alpha$ po odcinku $\langle 0,\ 1 \rangle$ na osi $x$ z tym, że po każdym odbiciu kuli od boku $\overline{BC}$ lub $\overline{AD}$ kierunek ruchu punktu $P_x$ zostaje zmieniony na przeciwny. Zatem w chwili $t_1 = \frac{2}{v_1} = \frac{2}{v \cos \alpha}$ punkt $P_x$ po dwukrotnym obiegu odcinka $\langle 0,\ 1 \rangle$ na osi $x$ znajdzie się w punkcie początkowym i kierunek jego ruchu będzie taki sam, jak na początku.

Ogólnie, w chwili $t_n = \frac{2n}{v \cos \alpha}$ , gdzie $n = 1, 2, \ldots$ , punkt $P_x$ będzie się znajdował w punkcie początkowym i kierunek jego ruchu będzie taki sam, jak na początku.

Analogicznie dowodzimy, że w chwili $t_m' = \frac{2m}{v_1} = \frac{2m}{v \sin \alpha}$ , gdzie $m = 1,2, \ldots$ , punkt $P_y$ , znajdzie się w punkcie początkowym i kierunek jego ruchu będzie taki sam, jak na początku.

Wobec tego kula powróci do punktu początkowego i kierunek jej ruchu będzie taki sam, jak w chwili początkowej wtedy i tylko wtedy, gdy istnieje taka chwila $t$ , że zarówno punkt $P_x$ , jak i $P_y$ będą w tej chwili znajdowały się w położeniu początkowym i kierunek ich ruchu będzie taki sam, jak na początku. Jest to równoważne temu, że istnieją takie liczby naturalne $n$ i $m$ , że $t = t_n$ i $t = t'_m$ , tzn.

$ (1) \qquad \frac{2n}{v \cos \alpha}= \frac{2m}{v \sin \alpha} $

Stąd $\tg \alpha = \frac{m}{n}$ jest liczbą wymierną.

Na odwrót, gdy $\tg \alpha = \frac{p}{q}$ jest liczbą wymierną, to wystarczy przyjąć $n = p$ i $m = q$ i wtedy warunek (1) będzie spełniony.

XXI OM - I -Zadanie 9

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

Udowodnić, że dla każdej liczby nieparzystej $n > 1$ istnieje taka liczba naturalna $d < n$ , że liczba $2^d - 1$ jest podzielna przez $n$ .

Rozwiązanie

Żadna z liczb $2, 2^2, \ldots, 2^n$ nie daje reszty $0$ z dzielenia przez $n$ , ponieważ $n > 1$ i $n$ jest liczbą nieparzystą.

Ponieważ liczb tych jest $n$ , a możliwych reszt różnych od zera jest $n - 1$ , więc dwie liczby $2^r$ i $2^s$ , gdzie $1 \leq r < s \leq n$ , dają tę samą resztę z dzielenia przez $n$ . Zatem $2^s - 2^r$ dzieli się przez $n$ i wobec tego liczba $2^r (2^{s-r} - 1)$ dzieli się przez $n$ . Ponieważ liczba $n$ jest nieparzysta, więc wynika stąd, że liczba $2^{s-r} - 1$ dzieli się przez $n$ . Wobec tego liczba $d = s - r$ spełnia warunki zadania.

XXI OM - I -Zadanie 10

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

Znaleźć największą liczbę naturalną $k$ o następującej własności : istnieje $k$ takich różnych podzbiorów zbioru $n$ -elementowego, że każde dwa mają niepustą część wspólną.

Rozwiązanie

Oznaczmy szukaną liczbę przez $k(n)$ . Udowodnimy, że $k(n) =2^{n-1}$ . Każdemu ciągowi $n$ -wyrazowemu o wartościach $0$ lub $1$ przyporządkowujemy zbiór takich wskaźników, że odpowiadające im wyrazy ciągu są równe $1$ . Przyporządkowanie to ustala odpowiedniość wzajemnie jednoznaczną między zbiorem wszystkich ciągów $n$ -wyrazowych o wartościach $0$ lub $1$ , a zbiorem wszystkich podzbiorów zbioru $n$ -elementowego. Wynika stąd, że wszystkich podzbiorów zbioru $n$ -elementowego jest tyle, ile ciągów o $n$ wyrazach, tzn. $2^n$ (por. zadanie przygotowawcze D, seria III).

Rozpatrzmy w $n$ -elementowym zbiorze $X$ rodzinę jego podzbiorów zawierających ustalony element $a$ . Każde dwa podzbiory w tej rodzinie mają niepustą część wspólną, należy do niej bowiem element $a$ . Liczba podzbiorów należących do tej rodziny równa jest liczbie wszystkich podzbiorów $(n -1)$ -elementowych zbioru $X - \{a\}$ , czyli $2^{n-1}$ . Zatem $k(n) \geq 2^{n-1}$ .

Z drugiej strony jeśli zbiór $A$ należy do pewnej rodziny $R$ podzbiorów zbioru $X$ , w której każde dwa podzbiory mają niepustą część wspólną, to zbiór $X - A$ do $R$ nie należy. Wobec tego liczba podzbiorów należących do rodziny $R$ nie przekracza połowy liczby wszystkich podzbiorów zbioru $X$ , czyli $k (n) \leq \frac{1}{2} \cdot 2^n = 2^{n-1}$ .

Z obu udowodnionych nierówności wynika, że $k(n) = 2^{n-1}$ .

XXI OM - I -Zadanie 11

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

Udowodnić, że przy każdym podziale płaszczyzny na trzy zbiory w co najmniej jednym z nich istnieją dwa punkty odległe o 1.

Rozwiązanie

Przypuśćmy, że twierdzenie to jest fałszywe. Rozpatrzmy trójkąty równoboczne $ABC$ i $ABD$ (rys. 7) o wspólnej podstawie $\overline{AB}$ i boku równym $1$ . Z naszego przypuszczenia wynika, że każdy z wierzchołków trójkąta $ABC$ należy do innego z trzech różnych podzbiorów, na które podzieliliśmy płaszczyznę. Podobnie każdy z wierzchołków trójkąta $ABD$ należy do innego z trzech różnych zbiorów, na które podzieliliśmy płaszczyznę. Wobec tego punkty $C$ i $D$ należą do tego samego zbioru. Odległość tych punktów równa jest $\sqrt{3}$ .

Z powyższego rozumowania wynika, że każde dwa punkty płaszczyzny odległe o $\sqrt{3}$ należą do tego samego podzbioru. Można je bowiem traktować jako wierzchołki odpowiednich trójkątów równobocznych o wspólnej podstawie i o boku $1$ .

Rozpatrzmy teraz trójkąt $PQR$ (rys. 8) o bokach $\sqrt{3}$ , $\sqrt{3}$ , $1$ . Z powyższego wynika, że punkty $P$ i $Q$ oraz $O$ i $R$ należą do tego samego zbioru. Wobec tego również punkty $P$ i $R$ należą do tego samego zbioru. Są one jednak odległe o $1$ , co przeczy naszemu pierwotnemu przypuszczeniu.

Uzyskana sprzeczność dowodzi, że rozważane twierdzenie jest prawdziwe.

XXI OM - I -Zadanie 12

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

Znaleźć najmniejszą liczbę dodatnią $r$ o tej własności, że w czworościanie foremnym o krawędzi długości 1 istnieją takie cztery punkty, że odległość dowolnego punktu czworościanu od któregoś z nich jest $\leq r$ .

Rozwiązanie

Niech $O$ będzie środkiem kuli opisanej na czworościanie foremnym $ABCD$ o krawędzi $1$ (rys. 9). Promień kuli opisanej na $ABCD$ jest równy $R = \frac{1}{4} \sqrt{6}$ . Czworościan $ABCD$ dzielimy na czworościany o wierzchołkach: $O$ , jednym z wierzchołków czworościanu, środku jednej z krawędzi wychodzących z tego wierzchołka czworościanu, spodku wysokości na jednej ze ścian zawierających tę krawędź. Ponieważ z każdego z $4$ wierzchołków czworościanu wychodzą $3$ krawędzie, a każda z nich należy do dwóch ścian czworościanu, więc liczba rozpatrywanych czworościanów równa jest $4 \cdot 3 \cdot 2 = 24$ .

Udowodnimy, że każdy z tych $24$ czworościanów jest wpisany w jedną z czterech kul o promieniu $\frac{R}{2}$ i o środkach $P_A$ , $P_B$ , $P_C$ , $P_D$ będących odpowiednio środkami odcinków $\overline{OA}$ , $\overline{OB}$ , $\overline{OC}$ , $\overline{OD}$ . Niech $E$ będzie środkiem krawędzi $\overline{AB}$ , zaś $F$ spodkiem wysokości opuszczonej z punktu $D$ na płaszczyznę trójkąta $ABC$ . Rozpatrzmy czworościan $AEFO$ . Ponieważ kąt $AFO$ jest prosty, więc $P_AF = AP_A = OP_A = \frac{R}{2}$ .

Podobnie, aby dowieść, że $P_AE = \frac{1}{2} R$ , wystarczy stwierdzić, że kąt $AEO$ jest prosty. Wynika to z faktu, że płaszczyzna wyznaczona przez punkty $D$ , $E$ , $F$ jest prostopadła do krawędzi $\overline{AB}$ , ponieważ $DE \bot AB$ , $CE \bot AB$ oraz $S \in CE$ .

W ten sposób dowodzimy, że każdy z $6$ czworościanów, których jednym z wierzchołków jest $A$ , jest zawarty w kuli o środku $P_A$ i promieniu $\frac{R}{2}$ . Z symetrii wynika, że również pozostałe czworościany są zawarte w odpowiednich kulach o promieniu $\frac{R}{2}$ .

Zatem każdy punkt czworościanu $ABCD$ jest odległy od któregoś z punktów $P_A$ , $P_B$ , $P_C$ , $P_D$ nie więcej niż o $\frac{R}{2}$ .

Przypuśćmy, że pewne punkty $Q_1$ , $Q_2$ , $Q_3$ , $Q_4$ i liczba $S$ mają tę własność, że każdy punkt czworościanu $ABCD$ jest odległy od któregoś z punktów $Q_1$ , $Q_2$ , $Q_3$ , $Q_4$ nie więcej niż o $S$ . W szczególności każdy z pięciu punktów $O$ , $A$ , $B$ , $C$ , $D$ jest odległy od któregoś z punktów $Q_1$ , $Q_2$ , $Q_3$ , $Q_4$ nie więcej niż o $S$ . Zatem dwa spośród punktów $O$ , $A$ , $B$ , $C$ , $D$ są odległe od pewnego punktu $Q_i$ nie więcej niż o $S$ . Jeśli punktami tymi są wierzchołki czworościanu, np. $A$ i $B$ , to otrzymujemy, że $1 = AB \leq AQ_i + BQ_i \leq 2S$ , czyli $S \geq \frac{1}{2}$ . Jeśli zaś punktami tymi są $O$ i jeden z wierzchołków czworościanu, np. $A$ , to otrzymujemy $R = OA \leq OQ_i+AQ_i \leq 2S$ , czyli $S \geq \frac{R}{2}$ .

Ponieważ $\frac{R}{2} < \frac{1}{2}$ , więc w każdym przypadku otrzymujemy, że $S \geq \frac{R}{2}$ . Zatem najmniejszą liczbą dodatnią $r$ o własności podanej w zadaniu jest $r = \frac{R}{2} = \frac{1}{8} \sqrt{6}$ .

Uwaga. Można dowieść, że punkty $P_A$ , $P_B$ , $P_C$ , $P_D$ są jedynymi punktami takimi, że każdy punkt czworościanu jest odległy od któregoś z nich nie więcej niż o $\frac{\sqrt{6}}{8}$ .

XXI OM - II etap

II etap XXI Olimpiady Matematycznej

XXI OM - II -Zadanie 1

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

Udowodnić, że

$ (1) \qquad |\cos n\beta - \cos n\alpha| \leq n^2 |\cos \beta - \cos\alpha|, $

gdzie $n$ jest liczbą naturalną. Zbadać, dla jakich wartości $n$ , $\alpha$ , $\beta$ zachodzi równość.

Rozwiązanie

Udowodnimy przez indukcję, że dla każdej liczby naturalnej $n > 1$ i liczby $x \ne k\pi$ ( $k \in \mathbb{C}$ ) zachodzi nierówność

$ (2) \qquad | \sin nx | < n | \sin x |. $

Załóżmy prawdziwość (2) dla pewnej liczby naturalnej $n > 1$ ; udowodnimy prawdziwość analogicznej nierówności dla liczby $n + 1$ . Mamy

$ \begin{split} |\sin(n + 1)x| & = |\sin nx \cos x + \cos nx \sin x| \leq |\sin nx| \cdot |\cos x| + |\cos nx| \cdot |\sin x| \leq \\ & \leq |\sin nx| + |\sin x| < n |\sin x| + |\sin x| = (n + 1)|\sin x|. \end{split} $

Zatem, jeśli $\alpha + \beta \ne 2k\pi$ i $\alpha - \beta \ne 2k\pi$ i $n > 1$ , to korzystając z tożsamości

$ \cos a - \cos b = -2 \sin \frac{a+b}{2} \sin \frac{a-b}{2} $

i z nierówności (2) otrzymujemy

$ \begin{split} | \cos n \beta - & \cos n \alpha | = 2 \left|\sin n \cdot \frac{\beta + \alpha}{2} \right| \left| \sin n \cdot \frac{\beta - \alpha}{2} \right| \leq \\ & \leq 2n^2 \left| \sin \frac{\beta + \alpha}{2} \right| \left| \sin \frac{\beta - \alpha}{2} \right| = n^2 \left| -2 \sin \frac{\beta + \alpha}{2} \sin \frac{\beta - \alpha}{2} \right| = \\ & = n^2 |\cos \beta - \cos \alpha|. \end{split} $

Jeśli zaś $n = 1$ , to oczywiście w (1) zachodzi równość. Podobnie, jeśli $\alpha + \beta = 2k\pi$ lub $\alpha - \beta = 2k\pi$ , to $\cos \alpha = \cos \beta$ oraz $\cos n \alpha = \cos n \beta$ i też w (1) zachodzi równość.

XXI OM - II -Zadanie 2

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

Na bokach $n$ -kąta foremnego obrano $n + 1$ punktów dzielących obwód na równe części. Przy jakim położeniu obranych punktów pole wielokąta wypukłego o tych $n + 1$ wierzchołkach jest a) największe, b) najmniejsze?

Rozwiązanie

Oznaczmy przez $a$ $(n + 1)$ -szą część długości boku $n$ -kąta foremnego $A_1A_2 \ldots A_n$ (rys. 10), tzn. niech, długość boku tego $n$ -kąta będzie równa $(n + 1)a$ . Wtedy obwód $n$ -kąta będzie równy $n(n + 1)a$ . Wobec tego wierzchołki $(n + 1)$ -kąta dzielą obwód $n$ -kąta foremnego na części równe $na$ .

Ponieważ $na < (n + 1 )a < 2na$ , więc do każdego boku $n$ -kąta należy co najmniej jeden i co najwyżej dwa wierzchołki $(n + 1)$ -kąta. Z drugiej strony do pewnego boku, np. $\overline{A_1A_n}$ , $n$ -kąta należą co najmniej dwa wierzchołki $(n + 1 )$ -kąta, ponieważ $n + 1 > n$ .

Oznaczmy przez $B_1$ ten z wierzchołków $(n + 1 )$ -kąta należących do boku $\overline{A_1A_n}$ , który jest położony bliżej punktu $A_1$ niż pozostały
wierzchołek $(n + 1)$ -kąta należący do $\overline{A_1A_n}$ . Oznaczmy przez $x$ długość odcinka $\overline{A_1B_1}$ Z powyższego wynika, że $0 \leq x \leq a$ . Wreszcie oznaczmy przez $B_2$ wierzchołek $(n + 1)$ -kąta różny od $B_1$ należący do boku $A_1A_2$ i dalej przez $B_3, \ldots, B_{n+1}$ - kolejne wierzchołki $(n + 1)$ -kąta.

Różnica pól $n$ -kąta i $(n + 1)$ -kąta $S_n - S_{n+1}$ jest równa sumie pól trójkątów $B_1A_1B_2, B_2A_2B_3, \ldots, B_nA_nB_{n+1}$ . W każdym takim trójkącie mamy:

$ B_iA_iB_{i+1}= \alpha \textrm{ jest kątem } n \textrm{-kąta foremnego, oraz} $

$ (1) \qquad B_iA_i + A_iB_{i+1} = na \textrm{ dla } i = 1, 2, \ldots, n. $

Wobec tego pole $P_i$ trójkąta $B_iA_iB_{i+1}$ jest równe

$ (2) \qquad P_i = \frac{1}{2} B_i A_i \cdot A_i B_{i+1} \cdot \sin \alpha. $

Ponieważ

$ (3) \qquad A_iB_{i+1} + B_{i+1}A_{i+1} = A_iA_{i+1} = (n+1)a \textrm{ dla } i = 1, 2, \ldots, n - 1, $

więc z (1) i (3) otrzymujemy kolejno

$ B_1A_1 + A_1B_2 = na,\textrm{ czyli }x + A_1B_2 = na. $

Stąd $A_1B_2 = na - x$ . $A_1B_2 + B_2A2 = (n + 1)a$ i stąd
$B_2A_2 = (n + 1)a - A_1B_2 = a + x$ , $B_2A2 + A_2B_3 = na$ i stąd $A_2B_3 = na - (a + x) = (n - 1)a - x$ ,
$A_2B_2 + B_3A_3 = (n + 1)a$ i stąd $B_3A_3 = (n + 1)a - ((n - 1)a - x) = 2a + x$
i przez łatwą indukcję ogólnie

$ (4) \qquad A_iB_{i+1} = (n - i + 1)a - x \textrm{ oraz } B_iA_i = (i - 1)a + x \textrm{ dla } i = 1,\ldots, n. $

Wobec tego z (4) i (2) otrzymujemy

$ \begin{split} S_n - S_{n+1} &= \sum_{i=1}^n P_i = \sum_{i=1}^n \frac{1}{2} ((i-1) a + x) (( n-i+1)a -x) \sin \alpha =\\ & = \frac{1}{2} \sin \alpha \sum_{i=0}^{n-1} (ia + x) ((n-i)a -x) =\\ & = \frac{1}{2} \sin \alpha \sum_{i=0}^{n-1} (-x^2 + (n-2i) ax + i(n-i) a^2) =\\ & = \frac{1}{2} \sin \alpha \left[ -nx^2 + \left( n^2 - 2 \sum_{i=0}^{n-1} i \right) ax + \sum_{i=0}^{n-1} i(n - i) a^2 \right]. \end{split} $

Oznaczmy przez $Ax^2 + Bx + C$ trójmian kwadratowy zapisany w ostatnim nawiasie kwadratowym. Wtedy $A = -n$ i $B = \left( n^2 - 2 \frac{n(n-1)}{2} \right) a = na$ . Otrzymujemy więc, że

$ S_n - S_{n+1} = \frac{1}{2} \sin \alpha \cdot (-nx^2 + nax + C), $

czyli

$ \begin{split} S_{n+1} & = S_n - \frac{1}{2} \sin \alpha \cdot (-nx^2 + nax + C) = \left( \frac{1}{2} \sin \alpha \cdot n \right) x^2 + \\ & + \left(- \frac{1}{2} \sin \alpha \cdot na \right) x + \left( S_n - \frac{1}{2} \sin \alpha \cdot C \right) = px^2 + qx + r. \end{split} $

Pole $(n + 1)$ -kąta $S_{n+1}$ jest więc funkcją kwadratową $S_{n+1}(x) = px^2 + qx + r$ zmiennej $x$ rozpatrywaną w przedziale $0 \leq x \leq a$ .

Ponieważ $p = \frac{1}{2} \sin \alpha \cdot n > 0$ , więc funkcja ta przyjmuje wartość najmniejszą dla $x = \frac{-q}{2p} = \frac{\frac{1}{2} \sin \alpha \cdot na}{\sin \alpha \cdot na} = \frac{a}{2}$ . Punkt $\frac{a}{2}$ jest środkiem przedziału $\langle 0,\ a \rangle$ . Wobec tego liczby $S_{n+1} (0)$ i $S_{n+1} (a)$ są równe i są to największe wartości przyjmowane przez funkcję $S_{n+1} (x)$ w przedziale $\langle 0,\ a \rangle$ .

Zatem pole $(n + 1)$ -kąta jest największe, gdy $x = 0$ lub $x = a$ , tzn. gdy jeden z jego wierzchołków jest wierzchołkiem $n$ -kąta foremnego. Pole $(n + 1)$ -kąta jest najmniejsze, gdy $x = \frac{a}{2}$ , tzn. gdy jeden z boków $(n + 1)$ -kąta leży na boku $n$ -kąta foremnego tak, że środki tych boków pokrywają się.

XXI OM - II -Zadanie 3

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

Udowodnić twierdzenie: Nie istnieje taka liczba naturalna $n > 1$ , że liczba $2^n - 1$ dzieli się przez $n$ .

Rozwiązanie

\spos{1} Załóżmy, że $n$ jest najmniejszą liczbą naturalną większą od jedności taką, że $n \mid 2^n - 1$ , zaś $k$ - najmniejszą liczbą naturalną taką, że $n \mid 2^k - 1$ . Na mocy twierdzenia danego do dowodu w zadaniu 9 na zawodach stopnia I mamy $k < n$ .

Niech $n = km + r$ , gdzie $0 \leq r < k$ . Ponieważ $n \mid 2^n - 1$ i $n \mid 2^{km} - 1$ , więc $n \mid 2^n - 2^{km} = 2^{km} (2^r - 1)$ i wobec nieparzystości $n$ otrzymujemy, że $n \mid 2^r - 1$ . Stąd wobec określenia liczby $k$ i nierówności $r < k$ , wynika, że $r = 0$ . Zatem $k \mid n$ , $k \mid 2^k - 1$ i wobec określenia liczby $n$ i nierówności $k < n$ mamy $k = 1$ . Stąd $n \mid 2^1 - 1$ , $n = 1$ i otrzymujemy sprzeczność.

%Sposób 2. Niech w będzie najmniejszą liczbą naturalną większą od jedności taką, że n | 2^n - 1, zaś k- dowolną liczbą naturalną taką, że n | 2k - 1 i k < n. Niech d będzie największym wspólnym dzielnikiem liczb n i k. Na mocy twierdzenia danego do dowodu w za-
%daniu przygotowawczym B serii II istnieją takie liczby naturalne a i b, że ąn - bk = d. Ponieważ n | 2an - 1 i n | 2ik - 1, więc n | 2an - - 2bk = 2M(2 %Zatem n j 21 - 1 i n = 1. Otrzymujemy sprzeczność.
%Sposób 3. Niech n > 1 będzie dowolną liczbą naturalną taką, że n | 2^n - 1, zaś p - jej najmniejszym dzielnikiem pierwszym. Na mocy twierdzenia danego do dowodu w zadaniu 9 na zawodach stopnia I lub na mocy małego twierdzenia Fermata mamy p | 2k - 1, gdzie k jest pewną liczbą naturalną mniejszą od p. Z określenia liczby p wynika, że liczby k i n są względnie pierwsze. Zatem na mocy twierdzenia danego do dowodu w zadaniu przygotowawczym B serii II istnieją takie liczby naturalne a i b, że an - bk - 1. Ponieważ p | 2an - 1 i p|2bk -|, więc p | 2™ - 2hk = 2bh, czyli p = 2. Otrzymaliśmy sprzeczność, ponieważ n jest liczbą nieparzystą.

XXI OM - II -Zadanie 4

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

Dowieść, że jeżeli trójkąt $T_1$ zawiera trójkąt $T_2$ , to obwód trójkąta $T_1$ jest nie mniejszy od obwodu trójkąta $T_2$ .

Rozwiązanie

W wierzchołkach trójkąta $T_2$ wystawiamy proste prostopadłe do jego boków (rys. 11). Proste te wyznaczają punkty $A_1$ , $B_1$ , $B_2$ , $C_2$ , $C_3$ , $A_3$ na brzegu trójkąta $T_1$ . Ponieważ $AB \bot AA_1$ i $AB \bot BB_1$ więc długość odcinka $\overline{AB}$ jest nie większa od długości łamanej $A_1B_1$ . Analogicznie długości odcinków $\overline{BC}$ i $\overline{CA}$ są nie większe od długości łamanych odpowiednio $B_2C_2$ i $C_3A_3$ . Tym bardziej obwód trójkąta $T_2$ jest nie większy od obwodu trójkąta $T_1$ .

XXI OM - II -Zadanie 5

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

Dany jest wielomian $P(x) = \frac{1}{2} - \frac{1}{3}x + \frac{1}{6}x^2$ . Niech $Q(x) = \sum_{k=0}^{m} b_k x^k$ będzie wielomianem określonym wzorem

$ Q(x) = P(x) \cdot P(x^3) \cdot P(x^9) \cdot P(x^{27}) \cdot P(x^{81}). $

Obliczyć $\sum_{k=0}^m |b_k|$ .

Rozwiązanie

Wykorzystamy następujące oczywiste fakty:

(1) Iloczyn wielomianów o współczynnikach dodatnich jest wielomianem o współczynnikach dodatnich.

(2) Suma współczynników wielomianu $f(x)$ równa jest $f(1)$ .

(3) Moduły odpowiednich współczynników wielomianów $f(x)$ i $f(-x)$ są równe.

Ponieważ wielomian $P(-x) = \frac{1}{2} + \frac{1}{3} x + \frac{1}{6} x^2$ ma współczynniki dodatnie, więc na podstawie (1) wielomian $R(x) = Q(-x) = P(-x) \cdot P(- x^3) \cdot P(- x^9) \cdot P(- x^{27}) \cdot P(- x^{81})$ ma współczynniki dodatnie.

Na podstawie (2) suma współczynników wielomianu $R (x)$ równa jest $R(1) = P(- 1) \cdot P(- 1) \cdot P(- 1) \cdot P(- 1) \cdot P(-1) = 1$ . Zatem na podstawie (3) suma modułów współczynników wielomianu $Q(x)$ równa jest sumie współczynników wielomianu $Q(- x) = R(x)$ , czyli $1$ .

XXI OM - II -Zadanie 6

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

Jeśli $A$ jest podzbiorem zbioru $X$ , to przyjmujemy $A^1 = A$ , $A^{-1} = X - A$ . Podzbiory $A_1, A_2, \ldots, A_k$ nazywamy wzajemnie niezależnymi, jeśli iloczyn $A_1^{\varepsilon_1} \cap A_2^{\varepsilon_2} \ldots A_k^{\varepsilon_k}$ jest niepusty dla każdego układu liczb $\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_k$ , takiego, że $|\varepsilon_2| = 1$ dla $i = 1, 2, \ldots, k$ .
Jaka jest maksymalna liczba wzajemnie niezależnych podzbiorów zbioru $2^n$ -elementowego?

Rozwiązanie

Ponieważ liczba wszystkich ciągów $n$ -wyrazowych o wartościach $-1$ i $1$ równa jest $2^n$ (patrz zadanie przygotowawcze D serii III), więc możemy przyjąć, że elementami rozważanego zbioru $2^n$ -elementowego $X$ są takie ciągi.

Oznaczmy dla $i = 1, 2, \ldots, n$ przez $A_i$ zbiór wszystkich ciągów należących do $X$ , których $i$ -ty wyraz jest $1$ . Wykażemy, że podzbiory $A_1, A_2, \ldots, A_n$ są wzajemnie niezależne.

Ciąg $(\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_n)$ , gdzie $|\varepsilon_j| = 1$ , należy do każdego ze zbiorów $A_i^{\varepsilon_i}$ dla $i = 1, 2, \ldots, n$ . Jeśli bowiem $\varepsilon_i= 1$ , to rozważany ciąg ma $i$ -ty wyraz równy $1$ , a więc należy do $A_i^{\varepsilon_i} = A_i^1$ ; jeśli zaś $\varepsilon_i = -1$ , to rozważany ciąg ma $i$ -ty wyraz równy $- 1$ , czyli należy do $X - A_i = A_i^{-1}$ . Wobec tego zbiór $A_1^{\varepsilon_1} \cap A_2^{\varepsilon_2} \cap \ldots \cap A_n^{\varepsilon_n}$ zawiera ciąg $(\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_n)$ , a więc jest niepusty.

Wykażemy z kolei, że jeśli $r > n$ i $B_1, B_2, \ldots, B_r$ są pewnymi podzbiorami zbioru $X$ , to nie są one wzajemnie niezależne. Jeśli ciągi $(\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_r)$ i $(\varepsilon'_1, \varepsilon'_2, \ldots, \varepsilon'_r)$ o wartościach $-1$ i $1$ są różne, to zbiory

$ B = B_1^{\varepsilon_1} \cap B_2^{\varepsilon_2} \cap \ldots \cap B_r^{\varepsilon_r} \textrm{ i } B' = B_1^{\varepsilon'_1} \cap B_2^{\varepsilon'_2} \cap \ldots \cap B_r^{\varepsilon'_r} $

są rozłączne. Mianowicie, jeśli np. $\varepsilon_i = 1$ , a $\varepsilon_i' = - 1$ , to mamy $B \subset B_i^{\varepsilon_i} = B_i$ oraz $B' \subset B_i^{-1} = X - B_i$ , a zbiory $B_i$ i $X - B_i$ oczywiście są rozłączne.

Zatem, gdyby zbiory $B_1, B_2, \ldots, B_r$ były wzajemnie niezależne, to wszystkie zbiory postaci $B_1^{\varepsilon_1} \cap B_2^{\varepsilon_2} \cap \ldots \cap B_r^{\varepsilon_r}$ byłyby niepuste i parami rozłączne. Zbiorów tych jest $2^r > 2^n$ . Jest to niemożliwe, ponieważ zbiór $X$ zawiera tylko $2^n$ elementów.

Udowodniliśmy więc, że $n$ jest maksymalną liczbą wzajemnie niezależnych podzbiorów zbioru $2^n$ -elementowego.

XXI OM - III etap

III etap XXI Olimpiady Matematycznej

XXI OM - III -Zadanie 1

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

III

Średnica $\overline{AB}$ dzieli okrąg na dwa półokręgi. Na jednym półokręgu obrano n punktów $P_1 P_2, \ldots, P_n$ tak, że $P_1$ leży między $A$ i $P_2$ , $P_2$ leży między $P_1$ i $P_3$ , $\ldots$ , $P_n$ leży między $P_{n-1}$ i $B$ . Jak należy wybrać punkt $C$ na drugim półokręgu, aby suma pól trójkątów $CP_1P_2, CP_2P_3, CP_3P_4, \ldots, CP_{n-1}P_n$ była największa?

Rozwiązanie

Zauważmy, że suma pól trójkątów $CP_1P_2, CP_2P_3, CP_3P_4, \ldots, CP_{n-1}P_n$ jest równa sumie pól wielokąta $P_1P_2 \ldots P_n$ oraz trójkąta $CP_1P_n$ (rys. 13). Pierwsze pole nie zależy od wyboru punktu $C$ . Drugie pole będzie maksymalne, gdy odległość punktu $C$ od prostej $P_1P_n$ będzie możliwie duża. Punkt na okręgu najbardziej oddalony od danej cięciwy leży na symetralnej tej cięciwy. Zatem jako $C$ należy wziąć punkt przecięcia symetralnej odcinka $\overline{P_1P_n}$ z drugim półokręgiem.

XXI OM - III -Zadanie 2

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

III

Dane są trzy ciągi nieskończone, których elementami są liczby naturalne:

$ \begin{split} a_1, a_2, \ldots, \\ b_1, b_2, \ldots, \\ c_1, c_2, \ldots, \end{split} $

przy czym jeżeli $i \neq j$ , to $a_i \neq a_j$ , $b_i \neq b_j$ , $c_i \neq c_j$ .
Udowodnić, że istnieje para wskaźników $k, l$ taka, że $k < l$ i $a_k < a_l$ , $b_k < b_l$ , $c_k < c_l$ .

Rozwiązanie

Ponieważ wyrazy ciągu $a_1, a_2, \ldots$ są różnymi liczbami naturalnymi, a zbiór liczb naturalnych mniejszych od $a_1$ jest skończony, więc wszystkie dostatecznie dalekie wyrazy tego ciągu są większe od $a_1$ , tzn.

$ (1) \qquad a_n > a_1 \textrm{ dla } n > n_1. $

Podobnie stwierdzamy, że

$ (2) \qquad b_n > b_1 \textrm{ dla } n > n_2 \textrm{ i} $

$ (3) \qquad c_n > c_1 \textrm{ dla } n > n_3. $

Jeśli więc $n$ jest liczbą naturalną większą od każdej z liczb $n_1, n_2, n_3$ , to nierówności (1), (2), (3) będą prawdziwe dla tej liczby naturalnej.

XXI OM - III -Zadanie 3

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

III

Udowodnić, że $n > 1$ jest liczbą pierwszą wtedy i tylko wtedy, gdy dla każdego naturalnego $k$ , takiego że $1 \leq k \leq n - 1$ , współczynnik dwumianowy

$ \binom{n}{k} = \frac{n!}{k!(n-k)!} $

dzieli się przez $n$ .

Rozwiązanie

Jeśli $n$ jest liczbą pierwszą, to dla $1 \leq k \leq n - 1$ liczby $k$ i $n - k$ są mniejsze od $n$ i wobec tego liczby $k!$ i $(n - k)!$ nie są podzielne przez $n$ .

Ze wzoru $\displaystyle \binom{n}{k} = \binom{n!}{k!(n-k)!}$ otrzymujemy

$ (1) \qquad n! = \binom{n}{k} k!(n-k)!. $

Ponieważ lewa strona (1) jest podzielna przez liczbę pierwszą $n$ , a $k!$ i $(n - k)!$ nie są podzielne przez $n$ , więc liczba $\binom{n}{k}$ jest podzielna przez $n$ .

Przypuśćmy z kolei, że $n$ jest liczbą złożoną i oznaczmy przez $p$ pewien dzielnik pierwszy tej liczby. Gdyby liczba $\binom{n}{p}$ była podzielna przez $n$ , to dla pewnej liczby naturalnej $s$ mielibyśmy $\binom{n}{p}= ns$ . Wtedy ze wzoru

$ \binom{n}{p} = \frac{n(n-1)(n-2) \ldots (n -(p-1))}{p!} $

otrzymalibyśmy $s =\frac{(n-1)(n-2) \ldots (n -(p-1))}{p!}$ , czyli

$ (1) \qquad sp! = (n- 1)(n-2)\ldots(n- (p- 1)). $

Ponieważ $p \mid n$ , więc liczby $n - 1, n - 2, \ldots, n - (p - 1)$ nie są podzielne przez $p$ . Zatem prawa strona równości (1) nie jest podzielna przez $p$ , a lewa strona jest oczywiście podzielna przez $p$ .

Otrzymana sprzeczność dowodzi, że liczba $\binom{n}{p}$ nie jest podzielna przez $n$ .

XXI OM - III -Zadanie 4

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

III

Na płaszczyźnie danych jest $n$ prostokątów o bokach odpowiednio równoległych do dwóch danych prostych prostopadłych. Udowodnić, że jeżeli każde dwa z tych prostokątów mają co najmniej jeden punkt wspólny, to istnieje punkt należący do wszystkich prostokątów.

Rozwiązanie

Obierzmy dane proste za osie układu współrzędnych (rys. 14). Wtedy wierzchołki $i$ -tego prostokąta $P_i$ będą miały współrzędne $(x_i,y_i)$ , $(x_i,y'_i)$ , $(x'_i,y'_i)$ , $(x'_i,y_i)$ , gdzie $x_i < x'_i$ , $y_i <y'_i$ . Punkt $(x, y)$ należy więc do prostokąta $P_i$ wtedy i tylko wtedy, gdy $x_i \leq x \leq x'_i$ oraz $y_i \leq y \leq y'_i$ .

Z założenia każde dwa prostokąty $P_i$ i $P_j$ mają punkt wspólny. Zatem istnieją liczby $x$ , $y$ takie, że

$ x_i \leq x \leq x'_i \textrm{ i } x_j \leq x \leq x'_j $

oraz

$ y_i \leq y \leq y'_i \textrm{ i } y_j \leq y \leq y'_j. $

Stąd

$ (1) \qquad x_i \leq x'_j \textrm{ oraz } y_i \leq y'_j \textrm{ dla } i, j = 1,2, \ldots, n. $

Oznaczmy przez $a$ największą z liczb $x_i$ , a przez $b$ - największą z liczb $y_i$ . Wtedy z określenia

$ (2) \qquad x_j \leq a \textrm{ oraz } y_j \leq b \textrm{ dla } j = 1,2, \ldots, n, $

$ (3) \qquad a \leq x'_j \textrm{ oraz } b \leq y'_j \textrm{ dla } j = 1,2, \ldots, n. $

Nierówności (2) i (3) dowodzą, że punkt $(a, b)$ należy do każdego z prostokątów $P_j$ .

Uwaga 1. W przytoczonym rozwiązaniu nie korzystaliśmy w sposób istotny z tego, że liczba danych prostokątów jest skończona. Gdyby dana była pewna nieskończona rodzina prostokątów o analogicznych własnościach, to rozwiązanie przebiegałoby podobnie, z tym, że liczby $a$ i $b$ należałoby określać jako kresy górne zbioru liczb $x_j$ i odpowiednio $y_j$ .

Uwaga 2. Podobne twierdzenie jest prawdziwe, jeśli zamiast prostokątów rozpatrywać dowolne figury wypukłe. Mianowicie zachodzi następujące

Twierdzenie Helly'ego. Jeśli na płaszczyźnie dana jest pewna niepusta rodzina zbiorów wypukłych taka, że każde trzy zbiory tej rodziny mają punkt wspólny, to istnieje punkt należący do wszystkich zbiorów tej rodziny.

XXI OM - III -Zadanie 5

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

III

Na ile sposobów zbiór złożony z dwunastu elementów można podzielić na sześć rozłączonych zbiorów dwuelementowych?

Rozwiązanie

Oznaczmy jeden z elementów zbioru $12$ -elementowego przez $a_1$ . Podzbiór dwuelementowy zawierający element $a_1$ można utworzyć na $11$ sposobów. Mianowicie należy do $a_1$ dołączyć jeden z pozostałych jedenastu elementów.

Oznaczmy przez $a_2$ jeden z elementów zbioru $10$ -elementowego, który pozostał po utworzeniu zbioru dwuelementowego zawierającego element $a_1$ . Podzbiór dwuelementowy zawierający element $a_2$ można teraz utworzyć na $9$ sposobów. Mianowicie należy do $a_2$ dołączyć jeden z pozostałych dziewięciu elementów.

Postępując dalej analogicznie stwierdzamy, że szukana liczba równa jest $11 \cdot 9 \cdot 7 \cdot 5 \cdot 3$ .

XXI OM - III -Zadanie 6

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

III

Znaleźć najmniejszą liczbę rzeczywistą $A$ taką, że dla każdego trójmianu kwadratowego $f(x)$ spełniającego warunek

$ (1) \qquad |f(x)| \leq 1 \quad \text{dla}\quad 0 \leq x \leq 1 $

zachodzi nierówność $f'(0) \leq A$ .

Rozwiązanie

Niech trójmian kwadratowy $f(x) = ax^2 + bx + c$ spełnia warunek (1). Wtedy w szczególności $|f(0)| \leq 1$ , $| f \left( \frac{1}{2} \right)| \leq 1$ i $|f(1)| \leq 1$ .

Ponieważ

$ f(0) = c,\ f(\frac{1}{2}) = \frac{a}{4} + \frac{b}{2} + c,\ f(1) = a+b+c $

oraz

$ f'(0) = b = 4 (\frac{a}{4} + \frac{b}{2} + c) - (a+b+c) - 3c, $

więc

$ | f'(0)| \leq 4 + \left( \frac{1}{2} \right)| + |f(1)| + 3|f(0)| \leq 4 + 1 + 3 = 8. $

Zatem $A \leq 8$ .

Z drugiej strony trójmian $f(x) = -8x^2 + 8x - 1$ spełnia warunek (1), co łatwo odczytać z jego wykresu (rys. 15). Ponadto $f'(0) = 8$ . Zatem $A \geq 8$ .

Poszukiwana liczba $A$ jest więc równa $8$ .