XXIV OM - III etap

III etap XXIV Olimpiady Matematycznej

XXIV OM - III - Zadanie 1

Zawody matematyczne:

XXIV OM, 1972-1973

Etap:

III

Udowodnić, że każdy wielomian jest różnicą dwóch wielomianów rosnących.

Rozwiązanie

Niech $F(x)$ będzie funkcją pierwotną dla funkcji $\displaystyle \frac{1}{2} (f'(x)^2 + f'(x) + 1)$ spełniającą warunek $F(0) = f(0)$ i niech
$G(x)$ będzie funkcją pierwotną dla funkcji $\displaystyle \frac{1}{2} (f'(x)^2 - f'(x) + 1)$ spełniającą warunek $G(0) = 0$ .

Oczywiście $F$ i $G$ są wielomianami. Są to wielomiany rosnące, ponieważ $F'(x)= \displaystyle \frac{1}{2} (f'(x)^2 + f'(x) + 1) > 0$ i $G' (x) = \displaystyle \frac{1}{2} (f'(x)^2 - f'(x) + 1) > 0$ . Wielomiany $t^2 + t + 1$ i $t^2 - t + 1$ przybierają bowiem tylko wartości dodatnie.

Ponadto $(F - G)' = F' - G' = f'$ . Zatem $F(x) - G(x) = f(x) + C$ , gdzie $C$ jest pewną stałą. Porównując wartości obu stron tej równości w punkcie $x = 0$ otrzymujemy, że $C = 0$ . Zatem $F - G = f$ .

XXIV OM - III - Zadanie 2

Zawody matematyczne:

XXIV OM, 1972-1973

Etap:

III

Niech $p_n$ będzie prawdopodobieństwem, że w ciągu $n$ rzutów monetą pojawi się seria kolejnych 100 orłów. Dowieść, że ciąg liczb $p_n$ jest zbieżny i obliczyć jego granicę.

Rozwiązanie

Liczba zdarzeń elementarnych jest równa liczbie ciągów $n$ -elementowych o dwóch wartościach: orzeł i reszka, tzn. liczbie $2^n$ . Zdarzeniem sprzyjającym jest ciąg zawierający $100$ kolejnych orłów. Oszacujemy z góry liczbę zdarzeń niesprzyjających, tzn. liczbę ciągów nie zawierających stu kolejnych orłów.

Niech $n= 100 k + r$ , gdzie $k \geq 0$ i $0 \leq r < 100$ . Każdy ciąg $n$ -elementowy składa się więc z $k$ ciągów $100$ -elementowych i ciągu $r$ -elementowego. Wszystkich ciągów $100$ -elementowych o dwóch wartościach jest $2^{100}$ ; zatem po wyłączeniu ciągu złożonego ze stu orłów pozostanie $2^{100} - 1$ ciągów $100$ -elementowych. Każdy ciąg $n$ -elementowy nie zawierający stu kolejnych orłów składa się więc z $k$ takich ciągów $100$ -elementowych i z pewnego ciągu $r$ -elementowego. Stąd liczba zdarzeń niesprzyjających jest nie większa od $(2^{100} - 1)^k \cdot 2^r$ . Wobec tego

$ (1) \qquad 1 \geq p_n \geq 1 - \frac{(2^{100} - 1)^k \cdot 2^r}{2^{100k+r}} = 1 - \left( 1 - \frac{1}{2^{100}} \right)^k. $

Jeżeli $n$ dąży do nieskończoności, to oczywiście również $k$ dąży do nieskończoności. Ponieważ dla $0 < q < 1$ mamy $\displaystyle \lim_{k \to \infty} q^k = 0$ , więc $\displaystyle \lim_{k \to \infty} \left( 1 - \frac{1}{2^{100}} \right)^k = 0$ . Zatem z (1) na mocy twierdzenia o trzech ciągach wynika, że $\displaystyle \lim_{k \to \infty} q^k = 0$ , więc $\displaystyle \lim_{n \to \infty} p_n = 1$ .

XXIV OM - III - Zadanie 3

Zawody matematyczne:

XXIV OM, 1972-1973

Etap:

III

Wielościan $W$ ma następujące własności:
a) posiada środek symetrii,
b) część wspólna wielościanu W z dowolną płaszczyzną zawierającą środek symetrii i którąkolwiek krawędź wielościanu jest równoległobokiem,
c) istnieje wierzchołek wielościanu $W$ , który należy do dokładnie trzech krawędzi.
Dowieść, że wielościan $W$ jest równoległościanem.

Rozwiązanie

Wielościanem nazywamy taki ograniczony zbiór punktów przestrzeni, który nie jest zawarty w jednej płaszczyźnie i jest częścią wspólną skończonej liczby półprzestrzeni. Ponieważ półprzestrzeń jest zbiorem wypukłym, a część wspólna zbiorów wypukłych jest zbiorem wypukłym, więc każdy wielościan jest zbiorem wypukłym. (Przyjmowane też są inne definicje wielościanu. Z pewnych spośród nich nie wynika, że wielościan jest zbiorem wypukłym).

Z wypukłości wielościanu wynika w szczególności, że jeżeli dwa jego wierzchołki $P$ , $Q$ oba należą do pewnych dwóch ścian wielościanu, to $\overline{PQ}$ jest jego krawędzią. Odcinek $\overline{PQ}$ jest bowiem zawarty w każdej z tych ścian, a więc i w ich części wspólnej.

Niech wierzchołek $A_0$ wielościanu $W$ należy do dokładnie trzech jego krawędzi $\overline{A_0A_1}$ , $\overline{A_0A_2}$ i $\overline{A_0A_3}$ . Ponieważ wielościan $W$ ma środek symetrii, więc wierzchołek $A_0'$ symetryczny do $A_0$ też należy do dokładnie trzech krawędzi $\overline{A'_0A'_1}$ , $\overline{A'_0A'_2}$ i $\overline{A'_0A'_3}$ , gdzie punkt $A'_i$ jest symetryczny do $A-i$ dla $i = 1, 2, 3$ . Niech $\pi_i$ będzie płaszczyzną zawierającą środek symetrii wielościanu $W$ i krawędź $A_0A_i$ , gdzie $i = 1, 2, 3$ . Zawiera więc ona również krawędź $\overline{A'_0A'_i}$ i z warunków zadania wynika, że $W \cap \pi_i$ jest czworokątem. Jest to oczywiście czworokąt $A_0A_iA'_0A'_i$ .

Dla $j \ne k, j$ , $k \in \{1, 2, 3\}$ niech $S_{jk}$ będzie ścianą wielościanu $W$ zawierającą wierzchołki $A_0$ , $A_j$ , $A_k$ i $S'_{jk}$ - ścianą do niej symetryczną. Jeżeli liczby $j$ i $k$ są różne od $i$ oraz należą do zbioru $\{1,2, 3\}$ , to płaszczyzna $\pi_i$ przecina ścianę $S_{jk}$ . Ponieważ $\pi_i \cap W$ jest czworokątem $A_0A_iA'_0A'_i$ oraz $A_0 \in S_{jk}$ , $A'_0 \not \in S_{jk}$ , i $A_i \not \in S_{jk}$ , więc $A'_i \in S_{jk}$ . Analogicznie stwierdzamy, że $A_i \in S'_{jk}$ .

Jeżeli liczby $i$ , $j$ , $k$ są różne i należą do zbioru $\{1, 2, 3\}$ , to, jak wykazaliśmy, $A_i, A'_j \in S'_{jk}$ oraz $A_i, A'_j \in S_{ik}$ . Zatem na podstawie początkowej uwagi otrzymujemy, że $\overline{A_iA'_j}$ jest krawędzią wielościanu $W$ dla $i \ne j$ . Wobec tego każdy czworokąt $A_0A_iA'_jA_k$ oraz $A'_0A'_iA_jA'_k$ jest ścianą wielościanu $W$ . Zatem $W$ ma sześć ścian i są one czworokątami. Ściany te są parami równoległe, ponieważ wielościan $W$ ma środek symetrii. Wielościan $W$ jest więc równoległościanem.

Uwaga 1. W powyższym rozwiązaniu nie korzystaliśmy z założenia, ze część wspólna wielościanu $W$ i dowolnej płaszczyzny zawierającej środek symetrii i krawędź wielościanu jest równoległobokiem. Wystarczyłoby zakładać, że ta część wspólna jest czworokątem.

Uwaga 2. Istnieją bryły niewypukłe, które są sumami wielościanów, posiadają środek symetrii i których każdy przekrój płaszczyzną przechodzącą przez środek symetrii i krawędź jest równoległobokiem. Na przykład niech w sześcianie o podstawach $ABCD$ i $A'B'C'D'$ środkami ścian $ABB'A'$ , $BCC'B'$ , $CDD'C'$ , $DAA'D'$ będą odpowiednio punkty $P$ , $Q$ , $R$ , $S$ . Odejmując od tego sześcianu czworościany $AA'PS$ , $BB'PQ$ , $CC'QR$ i $DD'RS$ otrzymamy bryłę, która jest sumą wielościanów. Można sprawdzić, że bryła ta spełnia warunki a) i b) zadania. Nie jest ona jednak równoległościanem.

XXIV OM - III - Zadanie 4

Zawody matematyczne:

XXIV OM, 1972-1973

Etap:

III

Na prostej dany jest układ odcinków o łącznej długości $< 1$ . Dowieść, że dowolny układ $n$ punktów prostej można przesunąć na niej o wektor długości $\leq \frac{n}{2}$ tak, aby po przesunięciu żaden z punktów nie leżał na żadnym z danych odcinków.

Rozwiązanie

Niech $P_i$ , gdzie $i = 1, 2, \ldots, n$ , będą danymi punktami i niech $A$ będzie sumą danych odcinków o łącznej długości mniejszej od $1$ . Dla $i = 1, 2, \ldots, n$ niech $I_i$ będzie odcinkiem długości $n$ , którego środkiem jest punkt $P_i$ .

Oczywiście $A \cap I_i$ , jest sumą odcinków o łącznej długości mniejszej od $1$ . Niech $\varphi_i$ będzie przesunięciem o wektor $\overrightarrow{P_iP_1}$ dla $i = 1, 2, \ldots, n$ . Ponieważ przesunięcie zachowuje długość odcinka oraz $\varphi_i(I_i) = I_1$ , więc zbiór

$ I = \cup_{i=1}^n \varphi_i (A \cap I_i) $

jest sumą odcinków o łącznej długości mniejszej od $n$ zawartych w $I_i$ . Jak wiemy, $I_1$ ma długość $n$ . Istnieje zatem punkt $Q$ należący do $I_1 - I$ .

Wykażemy, że przesunięcie $\varphi$ o wektor $\overrightarrow{P_1Q}$ spełnia warunki zadania. Ponieważ $Q \in I_1, P_1$ jest środkiem odcinka $I_1$ oraz długość $l_1$ równa jest $n$ , więc $P_1Q \leq \displaystyle \frac{n}{2}$ . Wobec tego dla każdego $i =1,2, \ldots, n$ mamy $\varphi (P_i) \in I_i$ .

Gdyby dla pewnego $i$ było $\varphi_ (P_i) \in A$ , to wobec $\varphi (P_i) \in I_i$ mielibyśmy $\varphi (P_i) \in A \cap I_i$ . Stąd

$ (1) \qquad \varphi_i \varphi (P_i) \in \varphi_i (A \cap I_i) \subset I. $

Przekształcenie $\varphi_i \varphi$ jest przesunięciem o wektor $\overrightarrow P_1Q + \overrightarrow{P_iP_1} = \overrightarrow{P_iQ}$ . Zatem $\varphi_i \varphi(P_i) = Q$ . Z (1) wynika więc, że $Q \in I$ . Przeczy to określeniu punktu $Q$ .

Uzyskana sprzeczność dowodzi, że dla każdego $i = 1, 2, \ldots, n$ mamy $\varphi(P_i) \not \in A$ .

XXIV OM - III - Zadanie 5

Zawody matematyczne:

XXIV OM, 1972-1973

Etap:

III

Dowieść, że każdy dodatni ułamek właściwy $\frac{m}{n}$ można przedstawić w postaci skończonej sumy odwrotności różnych liczb naturalnych.

Rozwiązanie

\spos{1} Obierzmy tak liczbę naturalną $k$ , by $n \leq 2^k$ . Niech $q$ i $r$ będą odpowiednio ilorazem i resztą z dzielenia liczby $2^km$ przez $n$ , tzn. niech $2^km = qn + r$ , gdzie $0 \leq r < n$ .

Wtedy

$ (1) \qquad \frac{m}{n} = \frac{2^km}{2^kn} = \frac{qn+r}{2^kn} = \frac{q}{2^k} + \frac{r}{2^kn}. $

Mamy $qn \leq gn + r = 2^km < 2^kn$ , ponieważ $\displaystyle \frac{m}{n} < 1$ . Stąd $q < 2^k$ . Wobec tego zapis liczby $q$ w systemie dwójkowym ma postać

$ q = q_0 + q_1 2 + q_2 2^2 + \ldots + q_{k-1}2^{k-1}, $

gdzie $q_i = 0$ lub $1$ . Stąd

$ (2) \qquad \frac{q}{2^k}= q_0 \frac{1}{2^k} + q_1 \frac{1}{2^{k-1}} + q_2 \frac{1}{2^{k-2}} + \ldots + q_{k-2} \frac{1}{2}. $

Z określenia liczb $r$ i $k$ mamy $r < n \leq 2^k$ . Wobec tego zapis liczby $r$ w systemie dwójkowym ma postać

$ r = r_0 + r_12 + r_2 2^2 + \ldots + r_{k-1} 2^{k-1}, $

gdzie $r_j = 0$ lub $1$ .

Stąd

$ (3) \qquad \frac{r}{2^kn}= r_0 \frac{1}{2^kn} + r_1 \frac{1}{2^{k-1}n} + \ldots + r_{k-2} \frac{1}{2n}. $

Przy tym dla $j = 0, 1, \ldots, k-1$ mamy

$ r_j \frac{1}{2^{k-j}n} = \frac{r_j2^j}{2^kn} \leq \frac{r}{2^kn} < \frac{1}{2^k}, $

ponieważ $r < n$ . Zatem każdy składnik niezerowy sumy (3) jest mniejszy od każdego niezerowego składnika sumy (2). Składniki te są więc różne.

Z (1), (2) i (3) otrzymujemy więc przedstawienie liczby $\displaystyle \frac{m}{n}$ w postaci sumy różnych ułamków postaci $\displaystyle \frac{1}{t}$ , gdzie $t$ jest liczbą naturalną.

XXIV OM - III - Zadanie 6

Zawody matematyczne:

XXIV OM, 1972-1973

Etap:

III

Dowieść, że dla dowolnego wielokąta wypukłego mającego środek symetrii istnieje co najwyżej jedna elipsa o najmniejszym polu zawierająca dany wielokąt.
Uwaga. Pole elipsy o półosiach długości $a$ i $b$ wyraża się wzorem $\pi ab$ .

Rozwiązanie

Niech $\varphi$ będzie odwzorowaniem płaszczyzny w siebie określonym wzorem $\varphi (x, y) = (x, ky)$ , gdzie $k$ jest ustaloną liczbą dodatnią. Odwzorowanie takie nazywamy powinowactwem prostokątnym; dokładniej - powinowactwem prostokątnym o osi $x$ i współczynniku $k$ . Oczywiście odwzorowaniem odwrotnym do powinowactwa prostokątnego o osi $x$ i współczynniku $k$ jest powinowactwo prostokątne o osi $x$ i współczynniku $\displaystyle \frac{1}{k}$ .

Jak wiadomo, jeżeli $\varphi$ jest powinowactwem prostokątnym o współczynniku $k > 0$ , a $F$ - pewną figurą, to pole $\varphi (F) = k \cdot \textrm{pole}\ F$ . Udowodnimy najpierw

Lemat. Niech $E$ będzie elipsą o równaniu

$ (1) \qquad \frac{(x-c_1)^2}{a^2} + \frac{(y-c_2)^2}{b^2} = 1, $

a $\varphi$ - powinowactwem prostokątnym o osi $x$ i o współczynniku $\displaystyle k = \frac{a}{b}$ .

Wtedy $\varphi(E)$ jest okręgiem o równaniu

$ (2) \qquad (x-c_1)^2 + (y - \frac{a}{b} c_2)^2 = a^2. $

Dowód. Niech punkt $(x, y)$ należy do elipsy $E$ , tzn. spełnia równanie (1). Wykażemy, że punkt $\varphi(x, y) = (x, \frac{a}{b} y)$ spełnia równanie (2). Mamy

$ (x-c_1)^2 + (\frac{a}{b} y - \frac{a}{b} c_2)^2 = a^2 \left( \frac{(x-c_1)^2}{a^2} + \frac{(y-c_2)^2}{b^2} \right) = a^2. $

Można analogicznie sprawdzić, że i na odwrót każdy punkt spełniający równanie (2) ma postać $\varphi (x, y)$ , gdzie $(x, y) \in E$ .

Z lematu wynika, że jeżeli $\varphi$ jest powinowactwem prostokątnym o osi $x$ i współczynniku $a/b$ , to obrazem przy odwzorowaniu $\varphi$ dowolnej elipsy, której osie symetrii są równoległe do osi układu współrzędnych, a długości półosi są równe odpowiednio $a$ i $b$ , jest okrąg o promieniu długości $a$ .

Przystępujemy teraz do rozwiązania zadania. Wykażemy najpierw, że jeżeli wielokąt $W$ ma środek symetrii i elipsa $E$ zawierająca wielokąt $W$ ma najmniejsze pole, to środek symetrii wielokąta jest środkiem symetrii elipsy.

Przypuśćmy, że środek symetrii $P$ wielokąta $W$ jest różny od środka elipsy $E$ . Niech $\Psi$ będzie symetrią o środku $P$ . Wtedy $\Psi (E)$ będzie elipsą zawierającą wielokąt $\Psi(W) = W$ różną od elipsy $E$ . Odpowiednie osie symetrii elips $E$ i $\Psi(E)$ są równoległe, ponieważ w symetrii obraz dowolnego odcinka jest równoległy do tego odcinka. Obierzmy tak układ współrzędnych, by jego osie były równoległe do osi elipsy $E$ (rys. 19).

Elipsy $E$ i $\Psi(E)$ są przystające. Zatem z lematu wynika, że istnieje takie powinowactwo prostokątne $\varphi$ o osi $x$ , że figury $\varphi(E)$ i $\varphi ( \Psi (E))$ są kołami o tym samym promieniu (rys. 20) i o środkach w punktach $O_1$ i $O_2$ . Koła te zawierają figurę (wielokąt) $\varphi(W)$ .

Niech $O$ będzie środkiem odcinka $\overline{O_1O_2}$ , a $P_1$ - jednym z punktów przecięcia tych okręgów. Koło $Q$ o środku w punkcie $O$ i promieniu $\overline{OP_1}$ zawiera oczywiście część wspólną kół $\varphi(E)$ i $\varphi(\Psi(E))$ . Ponadto $OP_1 < O_1P_1$ . Zatem pole koła $Q$ jest mniejsze od pola koła $\varphi(E)$ .

Niech $\varphi^{-1}$ będzie powinowactwem prostokątnym odwrotnym do $\varphi$ . Na mocy lematu figura $\varphi^{-1} (Q)$ jest elipsą o polu mniejszym od pola elipsy $\varphi^{-1}(\varphi(E)) = E$ . Ponieważ $Q \supset \varphi(W)$ , więc $\varphi^{-1}(Q) \supset \varphi^{-1}(\varphi(W)) = W$ . Otrzymaliśmy sprzeczność z założeniem, że elipsa $E$ ma najmniejsze pole wśród elips zawierających wielokąt $W$ . Wynika stąd, że środek symetrii wielokąta $W$ jest środkiem symetrii każdej elipsy o najmniejszym polu zawierającej wielokąt $W$ .

Przypuśćmy z kolei, że pewne dwie elipsy $E_1$ i $E_2$ zawierają wielokąt $W$ i mają najmniejsze pole wśród elips zawierających ten wielokąt. Jak wykazaliśmy, środek symetrii $P$ wielokąta $W$ jest również środkiem każdej z tych elips. Każde powinowactwo prostokątne jest przekształceniem afinicznym, a obraz elipsy przy dowolnym przekształceniu afinicznym też jest elipsą. Na mocy lematu możemy więc założyć (stosując odpowiednie powinowactwo prostokątne), że jedna z tych elips, np. $E_1$ jest kołem. Możemy też tak obrać układ współrzędnych, by punkt $P$ był jego początkiem, a osie symetrii elipsy $E_2$ - jego osiami. Wtedy równania elips $E_1$ i $E_2$ są następujące:

$ E_1 \colon x^2 + y^2 = r^2, $

$ (1) \qquad E_2 \colon \frac{x^2}{a^2} + \frac{y^2}{b^2} = 1,\ \textrm{gdzie np.}\ a > b. $

Z równości pól tych elips wynika, że $ab = r^2$ . Punkt $(x, y)$ należy więc do zbioru $E_1 \cap E_2$ wtedy i tylko wtedy, gdy

$ x^2 + y^2 \leq ab, $

$ (2) \qquad \frac{x^2}{a^2} + \frac{y^2}{b^2} \leq 1. $

Dodając stronami nierówności (2) otrzymujemy

$ \left( 1 + \frac{1}{a^2} \right) x^2 + \left( 1 + \frac{1}{b^2} \right) y^2 \leq ab+1, $

czyli po przekształceniach

$ (3) \qquad \frac{x^2}{\frac{a^2(ab+1)}{a^2+1}} + \frac{y^2}{\frac{b^2(ab+1)}{b^2+1}} \leq 1. $

Zatem zbiór $E_1 \cap E_2$ jest zawarty w elipsie (3). Następujące nierówności są równoważne

$ (4) \qquad \frac{a^2 b^2 (ab+1)^2}{(a^2+l)(b^2+1)} < a^2b^2, $

$ (ab + 1)^2 < (a^2 + 1)(b^2 + 1), $

$ 2ab < a^2 + b^2, $

$ (a - b)^2 > 0. $

Ta ostatnia nierówność jest prawdziwa, ponieważ $a > b$ . Zatem zachodzi (4). Wobec tego pole elipsy (3) jest mniejsze od pola elipsy $E_1$ . Sprzeczność ta dowodzi, że istnieje co najwyżej jedna elipsa o najmniejszym polu zawierająca wielokąt $W$ .