XXIX OM - II etap

II etap XXIX Olimpiady Matamatycznej

XXIX OM - II - Zadanie 1

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

Dowieść, że jeżeli $0 < x \leq \frac{1}{2}$ , $0 < y \leq \frac{1}{2}$

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

Rozwiązanie

\spos{1} Ponieważ na mocy warunków zadania liczby $x$ , $y$ , $1-x$ , $1-y$ są dodatnie, więc mnożąc stronami podaną w zadaniu nierówność przez $xy (1 -x) (1 -y)$ otrzymamy nierówność równoważną

$ (1 -x)(1 -y)(x+y)^2 \geq xy(2-x-y)^2. $

Wymnażając nawiasy i przenosząc wszystkie wyrazy na stronę lewą otrzymamy

$ x^2 + y^2 - 2xy - x^3 - y^3 + x^2y + xy^2 \geq 0, $

czyli $(x - y)^2(1 - x - y) \geq 0$ . Ta ostatnia nierówność równoważna nierówności podanej w zadaniu jest prawdziwa, ponieważ $x + y \leq \frac{1}{2} + \frac{1}{2} = 1$ , czyli $1 - x - y \geq 0$ . Zatem nierówność podana w zadaniu też jest prawdziwa.

XXIX OM - II - Zadanie 2

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

Na płaszczyźnie dany jest zbiór $M$ punktów o następujących własnościach:
1. Punkty zbioru $M$ nie leżą na jednej prostej,
2. Jeżeli punkty $A, B, C, D$ są wierzchołkami równoległoboku oraz $A, B, C \in M$ , to $D \in M$ ,
3. Jeżeli $A, B \in M$ , to $AB \geq 1$ .
Udowodnić, że istnieją takie dwie rodziny prostych równoległych, że $M$ jest zbiorem wszystkich punktów przecięcia prostych pierwszej rodziny z prostymi drugiej rodziny.

Rozwiązanie

Udowodnimy najpierw trzy lematy.
Lemat 1. Z warunku $3^\circ$ wynika, że każde koło zawiera tylko skończoną liczbę punktów zbioru $M$ .

Dowód. Niech $K$ będzie kołem o środku w punkcie $O$ i promieniu długości $r$ , a $K'$ - kołem o tym samym środku i promieniu długości $r+ \frac{1}{2}$ . Z warunku $3^\circ$ wynika, że dowolne dwa koła o środkach w punktach zbioru $M$ i promieniach długości $\frac{1}{2}$ mają rozłączne wnętrza. Wobec tego, jeżeli rozpatrzymy rodzinę $R$ kół o środkach w punktach zbioru $M$ należących do koła $K$ i promieniach długości $\frac{1}{2}$ , to koła te będą miały parami rozłączne wnętrza i będą zawarte w kole $K'$ . Wobec tego suma pól kół rodziny $R$ nie przekracza pola koła $K'$ . Wynika stąd, że rodzina $R$ jest skończona, a więc i zbiór punktów zbioru $M$ należących do $K$ jest skończony.

Wniosek. Każda figura ograniczona na płaszczyźnie zawiera tylko skończoną liczbą punktów zbioru $M$ .

Dowód. Każda figura ograniczona na płaszczyźnie jest zawarta w pewnym kole.

Lemat 2. Jeżeli $A, B \in M$ i $\varphi$ jest przesunięciem o wektor $\overrightarrow{AB}$ , to $\varphi(M) = M$ .

Dowód. Jeżeli $C \in M$ i punkty $A$ , $B$ , $C$ są niewspółliniowe, to istnieje taki punkt $D$ , że $ABDC$ jest równoległobokiem. Oczywiście $D = \varphi(C)$ , a na mocy warunku $2^\circ$ mamy $D \in M$ . Zatem $\varphi(C) \in M$ .

Jeżeli zaś $C' \in M$ i punkty $A$ , $B$ , $C$ są współliniowe, to na mocy warunku $1^\circ$ istnieje taki punkt $C \in M$ , że punkty $A$ , $B$ , $C$ nie są współliniowe. Na mocy już rozpatrzonego przypadku mamy $\varphi(C) \in M$ i proste $C \varphi (C)$ oraz $AC'$ są różne. Wobec tego punkty $C$ , $\varphi(C)$ , $C'$ nie są współliniowe. Istnieje więc taki punkt $D'$ , że $C \varphi(C)D'C'$ jest równoległobokiem i mamy oczywiście $D' = \varphi(C')$ . Z warunku $2^\circ$ wynika, że $D' \in M$ , a więc $\varphi (C') \in M$ .

Udowodniliśmy zatem, że $\varphi(M) \subset M$ . Rozpatrując przesunięcie $\psi$ o wektor $\overrightarrow{BA}$ , które jest przekształceniem odwrotnym do $\varphi$ stwierdzamy analogicznie, że $\psi(M) \subset M$ . Stąd $M = \varphi(\psi(M)) \subset \varphi(M)$ . Zatem $M = \varphi (M)$ .

Lemat 3. Istnieją takie punkty $A, B, C, D \in M$ , że $ABCD$ jest równoległobokiem i jedynymi punktami zbioru $M$ należącymi do tego równoległoboku są jego wierzchołki.

Dowód. Na mocy wniosku z lematu 1 do każdego odcinka należy tylko skończona liczba punktów zbioru $M$ . Istnieją więc takie dwa punkty $A, B \in M$ , że do wnętrza odcinka $\overline{AB}$ nie należy żaden punkt zbioru $M$ .

Na mocy warunku $1^\circ$ istnieje taki punkt $P \in M$ , że punkty $A$ , $B$ , $P$ są niewspółliniowe. Oznaczmy przez $Q$ taki punkt, że $ABQP$ jest równoległobokiem (rys. 11). Na mocy wniosku z lematu 1 do równoległoboku $ABQP$ należy tylko skończona liczba punktów zbioru $M$ . Niech $C$ będzie punktem równoległoboku $ABQP$ należącym do zbioru $M$ i różnym od $A$ i $B$ . Ponieważ liczba takich punktów jest skończona, więc możemy wybrać punkt $C$ tak, że jego odległość od prostej $AB$ jest minimalna, to znaczy nie ma punktów zbioru $M$ należących do $ABQP$ różnych od $A$ i $B$ , których odległość od $AB$ jest mniejsza niż odległość punktu $C$ od $AB$ .

Niech $D$ będzie takim punktem, że $ABCD$ jest równoległobokiem. Na mocy warunku $2^\circ$ mamy $D \in M$ . Wykażemy, że równoległobok $ABCD$ nie zawiera punktów zbioru $M$ różnych od $A$ , $B$ , $C$ i $D$ .

Gdyby punkt zbioru $M$ należał do wnętrza odcinka $\overline{CD}$ , to stosując przesunięcie o wektor $\overrightarrow{DA}$ otrzymalibyśmy na mocy lematu 2 punkt zbioru $M$ należący do wnętrza odcinka $\overline{AB}$ . Otrzymana sprzeczność dowodzi, że wewnętrz odcinka $\overline{CD}$ nie ma punktów zbioru $M$ .

Wobec tego, jeżeli pewien punkt $E$ zbioru $M$ różny od $A$ , $B$ , $C$ i $D$ należy do równoległoboku $ABCD$ , to jego odległość od prostej $AB$ jest mniejsza od odległości punktu $C$ od prostej $AB$ . Z minimalności tej ostatniej odległości wynika, że punkt $E$ nie należy do równoległoboku $ABQP$ . Wtedy jednak punkt $\varphi (E)$ , gdzie $\varphi$ jest przesunięciem o wektor $\overrightarrow{AB}$ , należy do równoległoboku $ABQP$ (rys. 11) i na mocy lematu 2 należy do $M$ . Przy tym odległość punktu $\varphi(E)$ od prostej $AB$ jest równa odległości punktu $E$ od tej prostej.

Uzyskana sprzeczność dowodzi, że taki punkt $E$ nie istnieje, tzn. równoległobok $ABCD$ nie zawiera punktów zbioru $M$ różnych od $A$ , $B$ , $C$ i $D$ .

Przystępujemy teraz do rozwiązania zadania. Niech $ABCD$ będzie równoległobokiem spełniającym warunki lematu 3. Oznaczmy przez $\varphi$ przesunięcie o wektor $\overrightarrow{AB}$ , a przez $\psi$ - przesunięcie o wektor $\overrightarrow{AD}$ . Dla dowolnej liczby całkowitej $n$ niech $\varphi^n$ będzie przesunięciem o wektor $n \cdot \overrightarrow{AB}$ i analogicznie $\psi^n$ - przesunięciem o wektor $n \cdot \overrightarrow{AD}$ . Wtedy obrazy równoległoboku $ABCD$ przy przesunięciach $\varphi^k \circ \psi^m$ , gdzie $k$ i $m$ są dowolnymi liczbami całkowitymi, pokrywają całą płaszczyznę.

Wykażemy, że zbiór $M$ jest równy zbiorowi punktów postaci

$ (1) \qquad (\varphi^k \circ \psi^m)(A),\ \textrm{gdzie}\ k \ \textrm{i} \ m \ \textrm{są całkowite}. $

Z lematu 2 wynika, że każdy punkt postaci (1) należy do zbioru $M$ . Na odwrót niech pewien punkt $P$ należy do zbioru $M$ . Ten punkt należy też do równoległoboku będącego obrazem równoległoboku $ABCD$ przy pewnym przesunięciu $\varphi^k \circ \psi^m$ . Stosując przesunięcie odwrotne $\varphi^{-k} \circ \psi^{-m}$ stwierdzamy, że punkt $Q = (\varphi^{-k} \circ \psi^{-m})(P)$ należy do $M$ i do równoległoboku $ABCD$ . Na mocy lematu 3 punkt $Q$ jest więc jednym z wierzchołków równoległoboku $ABCD$ . Zatem $Q = A$ , $Q = B = \varphi(A)$ , $Q = D = \psi(A)$ lub $Q = C = (\varphi \circ \psi)(A)$ . Wobec tego $P = (\varphi^k \circ \psi^m)(Q)$ jest obrazem punktu $A$ przy pewnym przesunięciu postaci $\varphi^r \circ \psi^s$ . Zatem punkt $P$ należy do zbioru (1).

Zbiór (1) jest oczywiście zbiorem wszystkich punktów przecięcia następujących dwóch rodzin prostych równoległych:

$ \psi^m(AB)\ (k \textrm{ - całkowite})\ \textrm{oraz} \ \varphi^m(AD) (m \textrm{ - całkowite}). $

Uwaga. Warunek $3^\circ$ można oczywiście zastąpić warunkiem:

Jeżeli $A, B \in M$ i $A \ne B$ , to $AB \geq a$ , gdzie $a$ jest ustaloną liczbą dodatnią.

Warunku $3^\circ$ nie można jednak opuścić. Rozpatrzmy bowiem zbiór $M$ punktów postaci

$ (2) \qquad (a + b\sqrt{2}, c + b\sqrt{3}), $

gdzie $a$ , $b$ , $c$ są dowolnymi liczbami całkowitymi. Łatwo sprawdzić, że ten zbiór $M$ spełnia warunki $1^\circ$ i $2^\circ$ . Wykażemy, że nie spełnia on tezy zadania.

Przypuśćmy, że istnieją takie dwie rodziny prostych równoległych, że $M$ jest zbiorem wszystkich punktów przecięcia prostych należących do tych rodzin.

Niech $L_1$ i $L_2$ będą prostymi należącymi odpowiednio do pierwszej i do drugiej rodziny zawierającymi punkt $(0,0) \in M$ . Ponieważ punkty $(1,0)$ , $(0, 1)$ , $(\sqrt{2}, \sqrt{3})$ należą do $M$ , więc istnieją takie punkty $P, P_1, P_2 \in L_1$ oraz $Q, Q_1, Q_2 \in L_2$ należące do $M$ , że

$ \begin{split} (1,0)& = P + Q \\ (3) \qquad (0,1) &= P_1 + Q_1 \\ (\sqrt{2}, \sqrt{3}) &= P_2 + Q_2. \end{split} $

Wobec tego

$ \begin{split} (0, 0) &= (\sqrt{2}, \sqrt{3}) - \sqrt{2}(1, 0) - \sqrt{3} (0,1) =\\ &= (P_2 -\sqrt{2}P- \sqrt{3}P_1) +(Q_2-\sqrt{2}Q- \sqrt{3}Q_1). \end{split} $

Ponieważ w ostatniej sumie pierwszy składnik należy do prostej $L_1$ , a drugi - do prostej $L_2$ i ich suma jest równa $(0, 0)$ , więc wynika stąd, że oba te składniki są równe $(0, 0)$ , to znaczy

$ P_2 = \sqrt{2}P + \sqrt{3}P_1,\ Q_2 = \sqrt{2}Q + \sqrt{3}Q_1. $

Niech $P= (x+y\sqrt{2},z+y\sqrt{3})$ , $P_1 = (x_1+y_1\sqrt{2}, z_1+y_1\sqrt{3})$ , gdzie $x$ , $y$ , $z$ , $x_1$ , $y_1$ , $z_1$ są liczbami całkowitymi. Wtedy

$ \begin{split} \sqrt{2}P + \sqrt{3}P_1 = (x\sqrt{2} + 2y + x_1 \sqrt{3} +y_1 \sqrt{6},\\ z\sqrt{2} + y\sqrt{6} + z_1\sqrt{3} + 3y_1). \end{split} $

Wynika stąd, że $x_1 = y_1 = 0$ , $z = y = 0$ oraz $x = z_1$ . Zatem $P = (x, 0)$ , $P_1 = (0, x)$ . Ponadto, jak wiemy, punkty $(0, 0)$ , $P$ , $P_1$ są współliniowe. Wobec tego $x = 0$ , czyli $P = P_1= (0, 0)$ .

Wtedy z (3) wynika, że $Q = (1, 0)$ , $Q_1 = (0,1)$ . Jest to niemożliwe, ponieważ punkty $(0,0)$ , $Q$ , $Q_1$ są współliniowe.

Uzyskana sprzeczność dowodzi, że zbiór $M$ określony wzorem (2) nie jest zbiorem wszystkich punktów przecięcia żadnych dwóch rodzin prostych równoległych.

XXIX OM - II - Zadanie 3

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

Dany jest taki ciąg liczb naturalnych $(a_i)$ , że dla każdej liczby naturalnej $n$ suma tych wyrazów ciągu, które są nie większe od $n$ , jest liczbą nie mniejszą od $n$ . Udowodnić, że dla każdej liczby naturalnej $k$ można wybrać z ciągu $(a_i)$ ciąg skończony o sumie wyrazów równej $k$ .

Rozwiązanie

Zastosujemy indukcję względem $k$ . Rozpatrzmy przypadek $k = 1$ . Z założenia suma tych wyrazów danego ciągu, które są nie większe od $1$ (a więc są równe $1$ ), jest liczbą nie mniejszą od $1$ . Istnieje więc w danym ciągu wyraz równy $1$ . Wobec tego suma wyrazów ciągu jednowyrazowego złożonego z tego właśnie wyrazu jest równa $1$ .

Z kolei niech $k$ będzie ustaloną liczbą naturalną i załóżmy, że dla każdej liczby naturalnej i nie większej od $k$ z danego ciągu można wybrać ciąg skończony o sumie wyrazów równej $i$ . Udowodnimy, że z danego ciągu można wybrać ciąg skończony o sumie wyrazów równej $k + 1$ .

Na mocy założenia indukcyjnego z danego ciągu można wybrać ciąg skończony

$ (1) \qquad (a_{i_1}, a_{i_2}, \ldots, a_{i_r}) $

o sumie wyrazów równej $k$ . Niech $a_m$ będzie najmniejszym wyrazem danego ciągu, który nie występuje w ciągu (1).

Ponieważ na mocy warunków zadania suma wszystkich wyrazów danego ciągu, które nie przekraczają $k + 1$ , jest nie mniejsza od $k + 1$ , a suma wyrazów ciągu (1) jest równa $k$ , więc pewien wyraz danego ciągu nie większy od $k + 1$ nie występuje w ciągu (1). Zatem $a_m \leq k+1$ .

Jeżeli $a_m = 1$ , to suma wyrazów ciągu $(a_{i_1}, a_{i_2}, \ldots, a_{i_r}, a_m)$ jest równa $k + 1$ .

Jeżeli $a_m > 1$ , to $1 \leq a_m - 1 \leq k$ . Wobec tego na mocy założenia indukcyjnego liczba $a_m - 1$ jest sumą pewnych wyrazów danego ciągu. Wszystkie te wyrazy występują w ciągu (1), ponieważ najmniejszym wyrazem danego ciągu nie występującym w (1) jest $a_m$ . Niech

$ a_m - 1 = a_{i_1} + a_{i_2} + \ldots + a_{i_s}, $

gdzie $s \leq r$ . Wtedy suma wyrazów ciągu

$ (a_{i_{s+1}}, a_{i_{s+2}}, \ldots, a_{i_r}, a_m) $

jest równa

$ (a_{i_1} + a_{i_2} + \ldots + a_{i_r})-(a_{i_1} + a_{i_2} + \ldots + a_{i_s} + a_m = k - (a_m - 1 ) + a_m = k+1. $

Na mocy zasady indukcji dla każdej liczby naturalnej $k$ można więc wybrać z danego ciągu ciąg skończony o sumie wyrazów równej $k$ .

XXIX OM - II - Zadanie 4

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

Spośród wierzchołków $2n$ -kąta foremnego wybrano losowo 3 różne punkty. Niech $p_n$ będzie prawdopodobieństwem zdarzenia, że trójkąt o wierzchołkach w wybranych punktach jest ostrokątny. Obliczyć $\lim_{n\to \infty} p_n$ .
Uwaga. Zakładamy, że wszystkie wybory trzech różnych punktów są jednakowo prawdopodobne.

Rozwiązanie

Niech $A_1, A_2, \ldots , A_{2n}$ będą kolejnymi wierzchołkami $2n$ -kąta foremnego, a $O$ - środkiem koła opisanego na tym wielokącie. Zbadamy, ile jest takich trójkątów $A_1A_iA_j$ , gdzie $i < j$ , że kąt $\measuredangle A_iA_1A_j$ nie jest ostry.

Ponieważ kąt wpisany w koło ma miarę dwa razy mniejszą niż kąt środkowy oparty na tym samym łuku, więc

$ \measuredangle A_iA_1A_j = \frac{1}{2} \measuredangle A_iOA_j = \frac{j-i}{2} \cdot \frac{2\pi}{2n} = \frac{j-i}{n} \cdot \frac{\pi}{2}. $

Zatem $\measuredangle A_iA_1A_j$ nie jest ostry wtedy i tylko wtedy, gdy $j - i \geq n$ . Obliczymy więc, ile jest takich par $(i, j)$ , że

$ (1) \qquad 2 \leq i <j \leq 2n \ \textrm{oraz}\ j - i \geq n. $

Z nierówności tych wynika, że $i \leq j - n \leq 2n - n = n$ . Dla każdego $i$ spełniającego $2 \leq i \leq n$ mamy $n - i + 1$ wartości na $j$ spełniających (1), mianowicie $j = i + n, i+ n + 1, \ldots, 2n$ . Zatem poszukiwana liczba par jest równa

$ \sum_{i=2}^n (n-i+1) = (n-1) + (n- 2)+ \ldots + 2+ 1 = \frac{n(n-1)}{2}. $

Udowodniliśmy więc, że liczba trójkątów nieostrokątnych $A_1A_iA_j$ , w których kąt $\measuredangle A_iA_1A_j$ jest nieostry, jest równa $\frac{n(n-1)}{2}$ . Ponieważ w trójkącie co najwyżej jeden kąt jest nieostry, więc liczba wszystkich trójkątów nieostrokątnych $A_iA_jA_k$ jest równa

$ 2n \cdot \frac{n(n-1)}{2} = n^2 (n-1). $

Liczba wszystkich trójkątów $A_iA_jA_k$ jest równa liczbie podzbiorów trójelementowych zbioru $2n$ -elementowego $\{A_1, A_2, \ldots , A_{2n} \}$ , to znaczy liczbie

$ \binom{2n}{3} = \frac{2n (2n-1)(2n-2)}{6} = \frac{2n (n-1)(2n-1)}{3}. $

Wobec tego

$ p_n = 1 - \frac{n^2(n-1)}{ \binom{2n}{3}} = 1 - \frac{3n}{2(2n-1)} = 1 - \frac{3}{4-\frac{2}{n}}. $

Zatem $\displaystyle \lim_{n \to \infty} p_n = 1 - \frac{3}{4} = \frac{1}{4}$ .

Uwaga. Trójkąt $A_1A_iA_j$ , gdzie $1 n$ oraz $j - i < n$ . Przyporządkowując trójkątowi $A_1A_iA_j$ punkt $(i,j)$ widzimy, że trójkątom ostrokątnym odpowiadają punkty kratowe położone w zakreskowanym trójkącie (rys. 12), a dowolnym trójkątom - punkty kratowe należące do trójkąta $AOB$ . Stosunek liczby punktów kratowych w trójkącie zakreskowanym do liczby wszystkich punktów kratowych w trójkącie $AOB$ dąży przy $n \to \infty$ do stosunku pól tych trójkątów. Ten stosunek pól jest równy $\frac{1}{4}$ .

XXIX OM - II - Zadanie 5

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

Dowieść, że nie istnieje taka równia pochyła, że każdy czworościan dowolnie przyłożony pewną ścianą do równi nie przewróci się. Znaczy to, co następuje. Dana jest płaszczyzna $\pi$ i prosta $l$ nie prostopadła do niej. Dowieść, że istnieje taki czworościan $T$ , że dla każdej jego ściany $S$ istnieje w płaszczyźnie $\pi$ trójkąt $ABC$ przystający do $S$ oraz istnieje taki punkt $D$ , że czworościan $ABCD$ przystaje do $T$ i prosta równoległa do $l$ przechodząca przez środek ciężkości czworościanu $ABCD$ nie przecina trójkąta $ABC$ .
Uwaga. Środkiem ciężkości czworościanu nazywamy punkt przecięcia odcinków łączących środki ciężkości ścian tego czworościanu z przeciwległymi wierzchołkami (wiadomo, że punkt taki zawsze istnieje).

Rozwiązanie

Udowodnimy, że dla każdej równi pochyłej istnieje taki czworościan, że dla każdej jego ściany można go tak przyłożyć tą ścianą do równi pochyłej, że czworościan się przewróci.

Rozpatrzmy czworościan $ABCD$ , którego wierzchołki mają współrzędne $A = (-1, 0, a)$ , $B = (1, 0, a)$ , $C = (0, 1, -a)$ , $D = = (0, -1, -a)$ , gdzie $a$ jest pewną liczbą dodatnią. Niech $P$ i $Q$ będą środkami krawędzi $\overline{AB}$ i $\overline{CD}$ odpowiednio, tzn. $P = (0, 0, a)$ , $Q = (0, 0, -a)$ .

Łatwo zauważyć, że dla dowolnych dwóch ścian czworościanu $ABCD$ istnieje taka izometria tego czworościanu, która przeprowadza jedną z tych ścian na drugą.

XXIX OM - II - Zadanie 6

Zawody matematyczne:

XXIX OM, 1977-1978

Etap: