XLI OM - I etap

I etap XLI Olimpiady Matematycznej

XLI OM - I - Zadanie 1

Zawody matematyczne:

XLI OM, 1989-1990

Etap:

Wyznaczyć w zależności od stałych rzeczywistych $a$ , $b$ liczbę rzeczywistych pierwiastków równania

$ \sqrt{(x-a)\cdot|x-b|} = (a-b)^2. $

Rozwiązanie

Oznaczmy lewą stronę równania przez $f(x)$ ; ma ona sens liczbowy dla $x \leq a$ . Określona w ten sposób funkcja $f \colon \langle a;\infty ) \to \mathbb{R}$ dana jest więc wzorem

$ f(x)=\sqrt{|F(x)|} \quad \textrm{dla} x \geq a, $

gdzie

$ F(x) = (x-a)(x-b). $

Rozważymy dwa przypadki.

Przypadek I. Gdy $a \geq b$ , funkcja $f$ jest ściśle rosnąca oraz ciągła w całej swej dziedzinie, czyli w przedziale $\langle a; \infty)$ . Skoro $f(a) = 0$ , $\lim_{x \to \infty} f(x) = \infty$ , zatem dla każdej wartości $c \geq 0$ równanie $f(x) = c$ ma dokładnie jedno rozwiązanie (istnienie tego rozwiązania wynika z ciągłości funkcji $f$ , a jedyność - z jej ścisłej monotoniczności). Przyjmując w szczególności $c = (a - b)^2$ dostajemy wniosek, że rozważane równanie ma (w tym przypadku) jeden pierwiastek rzeczywisty.

Przypadek II. Gdy $a < b$ , funkcja kwadratowa $F$ osiąga minimum równe
$- \frac{1}{4} (b-a)^2$ w punkcie $x_0 = \frac{1}{2}(a+b)$ ; jest malejąca w przedziale $\langle a;x_0 \rangle$ , a rosnąca w $\langle x_0;\infty)$ . Zatem funkcja $f = \sqrt{|F|}$ osiąga w punkcie $x_0$ lokalne maksimum równe $\frac{1}{2}(b-a)$ ; jest rosnąca w przedziałach $\langle a;x_0 \rangle$ i $\langle b;\infty \rangle$ , a malejąca w $\langle x_0;b \rangle$ . Liczba pierwiastków równania $f(x) = (a- b)^2$ wynosi więc trzy, dwa lub jeden - w zależności od tego, czy liczba $(a - b)^2$ jest mniejsza, równa, czy większa od $\frac{1}{2}(b-a)$ . W rozważanym obecnie przypadku $(a<b)$ te trzy sytuacje są odpowiednio równoważne temu, że różnica $b-a$ jest mniejsza, równa bądź większa od $\frac{1}{2}$ .

Biorąc pod uwagę konkluzje rozważań w przypadkach I i II możemy sformułować odpowiedź na postawione w zadaniu pytanie:

Liczba rzeczywistych pierwiastków równania $f(x) = (a-b)^2$ wynosi:

$ \begin{array}{rl} \textrm{trzy - gdy} & 0<b-a< \frac{1}{2},\\ \textrm{dwa - gdy} & b - a= \frac{1}{2},\\ \textrm{jeden - gdy} & b-a> \frac{1}{2} \ \textrm{lub}\ b-a \leq 0. \end{array} $

XLI OM - I - Zadanie 2

Zawody matematyczne:

XLI OM, 1989-1990

Etap:

Udowodnić, że jeżeli liczby $A$ , $B$ są różne od zera, to funkcja

$ f(x) = A\sin x+B \sin(\sqrt{2}\cdot x) $

nie jest okresowa.

Rozwiązanie

Sposób I. Przypuśćmy, wbrew tezie, że funkcja $f$ jest okresowa i niech $T$ będzie okresem:

$ f(x + T) = f(x) = f(x-T) \quad \textrm{dla wszystkich} \ x \in \mathbb{R}. $

Zachodzi więc równość

$ f(x + T)-f(x-T) = 0 \quad \textrm{dla} \ x \in \mathbb{R}, $

którą możemy przekształcić następująco, stosując znane tożsamości trygonometryczne:

$ \begin{split} & A\sin (x + T)-A\sin (x-T) + B\sin(\sqrt{2} \cdot x + \sqrt{2} \cdot T)-B\sin (\sqrt{2} \cdot x-\sqrt{2} \cdot T) = 0,\\ & (1) \qquad 2A\cos x\sin T+2B \cos(\sqrt{2}\cdot x)\sin(\sqrt{2} \cdot T) = 0 \quad \textrm{dla} x \in \mathbb{R}. \end{split} $

Podstawiając $x = 0$ otrzymujemy stąd równość

$ (2) \qquad 2A\sin T + 2B\sin(\sqrt{2} \cdot T) = 0; $

natomiast podstawiając w (1) $x = \pi/2$ dostajemy

$ 2B\cos (\pi/\sqrt{2})\sin (\sqrt{2} \cdot T) = 0. $

Czynnik $cos(\pi/ \sqrt{2})$ nie jest zerem. Także $B \ne 0$ , zgodnie z założeniem. Zatem

$ (3) \qquad \sin (\sqrt{2} \cdot T) = 0. $

Z równości (2) i (3) wnosimy (uwzględniając założenie $A \ne 0$ ), że

$ (4) \qquad \sin T = 0. $

Otrzymane równości (3) i (4) nie dadzą się jednak pogodzić: wynikałoby z nich, że zarówno liczba $T$ , jak i $\sqrt{2} \cdot T$ , musi być całkowitą wielokrotnością $\pi$ . To zaś nie jest możliwe, wobec niewymierności liczby $\sqrt{2}$ . Sprzeczność dowodzi, że funkcja $f$ nie jest okresowa.

XLI OM - I - Zadanie 3

Zawody matematyczne:

XLI OM, 1989-1990

Etap:

Na zewnątrz trójkąta ostrokątnego $ABC$ zbudowano trójkąty równoboczne $ABC'$ , $BCA'$ , $CAB'$ . Dowieść, że odcinki $AA'$ , $BB'$ , $CC'$ przecinają się w jednym punkcie i są równej długości.

Rozwiązanie

Weźmy pod uwagę obrót płaszczyzny o $60^\circ$ wokół punktu $B$ , w takim kierunku, by punkt $A$ przeszedł na $C'$ , a punkt $A'$ - na $C$ . Trójkąt $ABA'$ nałoży się wówczas na trójkąt $C'BC$ . Zatem $|AA'| = |CC'|$ , przy czym proste $AA'$ i $CC'$ tworzą kąt $60^\circ$ . Oznaczmy punkt ich przecięcia przez $T$ . Mamy więc równości kątów:

(rysunek 1). Z równości tych wynika, że punkt $T$ leży na każdym z trzech okręgów opisanych na trójkątach $ABC'$ , $BCA'$ , $CAB'$ . Oczywiście jest to ich jedyny punkt wspólny, bowiem okręgi te przecinają się - poza punktem $T$ - tylko parami, w trzech różnych punktach $A$ , $B$ , $C$ .

Udowodniliśmy więc, że okręgi opisane na trzech dorysowanych trójkątach równobocznych mają dokładnie jeden punkt wspólny $T$ (zwany jest on punktem Toricellego trójkąta $ABC$ ). Zauważmy, że przy takiej charakteryzacji punktu $T$ rola każdego z wierzchołków $A$ , $B$ , $C$ jest taka sama, żaden nie jest wyróżniony. Wykazaliśmy ponadto, że odcinki $AA'$ i $CC'$ mają równą długość i przecinają się właśnie w punkcie $T$ .

Możemy powtórzyć to samo rozumowanie startując na przykład z pary odcinków $AA'$ , $BB'$ (jeden z nich nałoży się na drugi przy obrocie o kąt $60^\circ$ wokół punktu $C$ ). Otrzymamy równość $|AA'| = |BB'|$ oraz stwierdzimy, że punkt Toricellego $T$ jest punktem przecięcia także i tej pary odcinków.

Zatem wszystkie trzy odcinki $AA'$ , $BB'$ , $CC'$ przecinają się w punkcie $T$ i mają równą długość.

XLI OM - I - Zadanie 4

Zawody matematyczne:

XLI OM, 1989-1990

Etap:

Z szachownicy o wymiarach $8 \times 80$ polach pokolorowanych w zwykły sposób usunięto dwa poła różnych kolorów. Udowodnić, że pozostałe $62$ pola można pokryć 31 prostokątami o wymiarach $2\times 1$ .

Rozwiązanie

Oznaczmy przez $R$ najmniejszy prostokąt zawierający oba usunięte pola $A$ i $B$ . Ponieważ pola te są różnych kolorów i leżą w przeciwległych narożnikach prostokąta $R$ , zatem długości boków $R$ są liczbami naturalnymi różnej parzystości. Nie tracąc ogólności możemy przyjąć, że prostokąt $R$ tworzy $k$ rzędów pionowych i $l$ rzędów poziomych, przy czym $k$ jest liczbą parzystą, a $l$ - nieparzystą (rysunek 2).

Pokażemy, żę prostokąt $R$ bez pól $A$ i $B$ można pokryć płytkami o wymiarach $2 \times 1$ . Gdy $l = 1$ , mamy do pokrycia pasek o długości $k - 2$ i szerokości $1$ ; sposób pokrycia jest oczywisty. Gdy $l> 1$ , wówczas każdy ze skrajnych rzędów pionowych (bez pola $A$ , względnie $B$ ) ma wymiary $(l- 1) \times 1$ i wobec nieparzystości $l$ da się pokryć płytkami $2 \times 1$ , ustawionymi pionowo. Pozostała część prostokąta $R$ jest prostokątem o wymiarach $(k-2) \times l$ (ewentualnie zbiorem pustym, gdy $k = 2$ ) i da się pokryć płytkami ułożonymi poziomo.

Pozostaje do pokrycia reszta szachownicy. Proste zawierające pionowe boki prostokąta $R$ odcinają dwa pasy prostokątne, biegnące przez całą wysokość szachownicy; w szczególnych przypadkach jeden z nich (lub oba) może być zbiorem pustym. Każdy z tych pasów pokrywamy pionowymi płytkami $2 \times 1$ ; jest to możliwe, bo $8$ jest liczbą parzystą.

Część szachownicy pomiędzy wspomnianymi prostymi, po usunięciu z niej prostokąta $R$ , rozpada się na dwa prostokąty (górny i dolny), każdy o szerokości $k$ ( znów: jeden z nich - lub oba - może być zbiorem pustym). Ponieważ $k$ jest liczbą parzystą, potrafimy i te obszary pokryć płytkami $2 \times 1$ , ułożonymi poziomo.

W ten sposób pokryliśmy płytkami $2 \times 1$ całą szachownicę bez pól $A$ i $B$ . Nie jest to jedyny możliwy sposób; istnieje wiele innych. Zauważmy jeszcze, że opisana tu metoda jest skuteczna w przypadku dowolnej szachownic o wymiarach parzystych.

XLI OM - I - Zadanie 5

Zawody matematyczne:

XLI OM, 1989-1990

Etap:

Dowieść, że krawędzi sześcianu nie da się ponumerować liczbami od 1 do 12 tak, by suma numerów krawędzi wychodzących z każdego wierzchołka była taka sama.

Czy można spełnić ten warunek numerując krawędzie dwunastoma różnymi liczbami ze zbioru $\{1,2,\ldots,13\}$ ?

Rozwiązanie

Przypuśćmy, że istnieje sposób ponumerowania, o jakim mowa w pierwszym zdaniu. Każda krawędź przylega swymi dwoma końcami do dwóch wierzchołków. Podwojona suma numerów wszystkich krawędzi powinna więc być równa $8s$ , gdzie $s$ oznacza sumę numerów krawędzi wychodzących z jednego wierzchołka (wartość wspólna dla wszystkich krawędzi sześcianu). Wynikałaby stąd równość $8s = 2(1 + \ldots +12) = 12 \cdot 13$ ; sprzeczność, bo $s$ powinno być liczbą całkowitą.

Jeśli natomiast wolno do numerowania użyć dowolnych dwunastu różnych liczb ze zbioru $\{1,2,\ldots,13\}$ , to uzyskanie równych sum przy wszystkich wierzchołkach jest możliwe, i to wieloma sposobami. Przykład realizacji ukazuje rysunek 3.

XLI OM - I - Zadanie 6

Zawody matematyczne:

XLI OM, 1989-1990

Etap:

Niech $M$ będzie dowolnym punktem czworościanu $ABCD$ . Oznaczmy pola ścian $BCD$ , $ACD$ , $ABD$ , $ABC$ odpowiednio przez $S_A$ , $S_B$ , $S_C$ , $S_D$ objętość zaś czworościanu przez $V$ . Udowodnić, że

$ S_A\cdot |MA| + S_B\cdot |MB| + S_C\cdot |MC| + S_D\cdot|MD| \geq 9V. $

Rozwiązanie

Czworościan $ABCD$ jest sumą czterech czworościanów o rozłącznych wnętrzach: $MBCD$ , $MACD$ , $MABD$ , $MABC$ (w przypadku, gdy punkt $M$ leży na brzegu $ABCD$ , niektóre z wymienionych czworościanów mogą degenerować się do trójkątów). Oznaczmy przez $d_A$ , $d_B$ , $d_C$ , $d_D$ odległości punktu $M$ od płaszczyzn ścian $BCD$ , $ACD$ , $ABD$ , $ABC$ . Objętości czterech wymienionych czworościanów wynoszą (odpowiednio):

$ V_A = \frac{1}{3} d_A \cdot S_A,\quad V_B = \frac{1}{3} d_B \cdot S_B,\quad V_C = \frac{1}{3} d_C \cdot S_C,\quad V_D = d_D \cdot S_D. $

Objętość czworościanu $ABCD$ można wyrazić w dowolnej z następujących czterech postaci:

$ V = \frac{1}{3}h_A \cdot S_A = \frac{1}{3}h_B \cdot S_B = \frac{1}{3}h_C \cdot S_C = \frac{1}{3}h_D \cdot S_D =, $

gdzie $h_A$ , $h_B$ , $h_C$ , $h_D$ są wysokościami czworościanu $ABCD$ opuszczonymi z odpowiednich wierzchołków. Wobec oczywistych nierówności

$ h_A \leq d_A + |M_A|,\ h_B \leq d_B + |M_B|,\ h_C \leq d_C + |M_C|,\ h_D \leq d_D + |M_D| $

dochodzimy do oszacowań

$ \begin{array}{ll} V \leq V_A + \frac{1}{3} S_A \cdot |MA|, & V \leq V_B + \frac{1}{3} S_B-|MB|,\\ V \leq V_C + \frac{1}{3} S_C \cdot |MC|, & V \leq V_D + \frac{1}{3} S_D-|MD|. \end{array} $

Po dodaniu stronami i uwzględnieniu równości $V_A + V_B + V_C + V_D = V$ otrzymujemy nierówność

$ 4V \leq V + \frac{1}{3} (S_A \cdot |MA| + S_B \cdot |MB| + S_C |MC| + S_D \cdot |MD|), $

równoważną nierówności danej do udowodnienia w zadania.

XLI OM - I - Zadanie 7

Zawody matematyczne:

XLI OM, 1989-1990

Etap:

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

$ \binom{2n}{n}\cdot \sqrt{3n} < 4^n $

Rozwiązanie

\spos{I} Udowodnimy nierówność silniejszą (patrz Uwaga 1):

$ (1) \qquad \binom{2n}{n} \cdot \sqrt{3n+1} \leq 4^n. $

Oczywiście nierówność dana w zadaniu wynika z (1) natychmiast.

Dowód będzie indukcyjny. Dla $n = 1$ nierówność (1) zachodzi (w postaci równości).
Przyjmijmy słuszność (1) dla pewnej liczby naturalnej $n$ . Chcemy wykazywać, że

$ (2) \qquad \binom{2n+2}{n+1} \cdot \sqrt{3(n+1)+1} \leq 4^{n+1}. $

Korzystając z założenia indukcyjnego, przekształcamy lewą stronę (2), jak następuje:

$ \begin{split} \binom{2n+2}{n+1} \cdot \sqrt{3n+4} & = \binom{2n}{n} \cdot \frac{(2n+1)(2n+2)}{(n+1)(n+1)} \cdot \sqrt{3n+4} =\\ & = \frac{2(2n+1)}{n+1} \cdot \binom{2n}{n} \cdot \sqrt{3n+1} \cdot \sqrt{\frac{3n+4}{3n+1}} \leq \\ & \leq \frac{2(2n+1)}{n+1} \cdot 4^n \cdot \sqrt{\frac{3n+4}{3n+1}}. \end{split} $

Nierówność (2) będzie udowodniona, gdy pokażemy, że

$ (3) \qquad \frac{2n+1}{n+1} \cdot \sqrt{\frac{3n+4}{3n+1}} \leq 2. $

Podnosząc (3) stronami do kwadratu otrzymujemy nierówność

$ (4) \qquad \frac{(2n+1)^2(3n+4)}{(n+1)^2(3n+1)} \leq 4, $

która jest równoważna (3). Przekształcamy (4) dalej, stosując przejścia równoważne:

$ \begin{split} & (4n^2+4n+1)(3n+4) \leq 4(n^2 + 2n+1)(3n+1),\\ & 12n^3 + 28n^2 + 19n+4 \leq 12n^3 + 28n^2+20n+4,\\ & 0 \leq n. \end{split} $

Ostatnia nierówność jest prawdziwa, a przy tym równoważna nierówności (4) - a więc i (3). To zaś wystarczy do udowodnienia tezy indukcyjnej (2).

Na mocy zasady indukcji nierówność (1) zachodzi dla każdej liczby naturalnej $n$ .

Uwaga 1. Gdybyśmy próbowali przeprowadzić dowód indukcyjny nierówności danej w zadaniu w jej oryginalnej postaci, spotkałoby nas niepowodzenie. Przy dowodzeniu twierdzeń przez indukcję nierzadko zdarza się, że wzmocnienie tezy ułatwia problem, bowiem w kroku indukcyjnym jest moment, gdy teza staje się założeniem. Omawiane zadanie stanowi typowy przykład takiej właśnie sytuacji.

XLI OM - I - Zadanie 8

Zawody matematyczne:

XLI OM, 1989-1990

Etap:

Udowodnić, że istnieje nieskończenie wiele liczb naturalnych $n$ , dla których każda z liczb $n-1$ , $n$ , $n+1$ jest sumą kwadratów dwóch liczb całkowitych.

Rozwiązanie

Dla dowolnej liczby naturalnej $k$ przyjmijmy $n_k = (2k^2 + 1)^2$ . Dostajemy nieskończony, ściśle rosnący ciąg liczb naturalnych $n_1,n_2,n_3,\ldots$ , z których każda spełnia podany w zadaniu warunek:

$ \begin{split} n_k-1 & = (2k^2)^2 + (2k)^2,\\ n_k & = (2k^2 + 1)^2 + 0^2,\\ n_k + 1 = (2k^2 + 1)^2 + 1^2. \end{split} $

XLI OM - I - Zadanie 9

Zawody matematyczne:

XLI OM, 1989-1990

Etap:

Rozstrzygnąć, czy istnieje taki wielomian $W(x)$ o współczynnikach wymiernych, że dla każdego całkowitego $k$ wartość $W(3k+1)$ jest liczbą całkowitą nieparzystą, a $W(3k+2)$ — liczbą całkowitą parzystą.

Rozwiązanie

Przypuśćmy, że

$ W(x)=\sum_{j=0}^n a_j x^j $

jest wielomianem, o jakim mowa w zadaniu. Zgodnie z postawionym warunkiem, każdy ze współczynników $a_j$ jest liczbą wymierną:

$ a_j = \frac{p_j}{q_j} \quad (p_j, q_j \ \textrm{całkowite}, q > 0). $

Mianownik $q_j$ zapiszmy w postaci

$ q_j=2^{\alpha_j} m_j \left( \begin{array}{rl} \alpha \geq 0 & \textrm{całkowite}, \\ m_j > 0 & \textrm{całkowite meparzyste}. \end{array} \right) $

Przyjmijmy $m = m_0 m_1 \ldots m_n$ oraz ustalmy liczbę naturalną $\alpha$ większą od wszystkich wykładników $\alpha_0,\alpha_1,\ldots,\alpha_n$ . Weźmy pod uwagę liczbę

$ M = m \cdot (W(2^{\alpha+1}) - W(2^\alpha)). $

Dokładnie jedna spośród liczb $2^\alpha, 2^{\alpha+1}$ daje przy dzieleniu przez $3$ resztę $1$ , druga zaś - resztę $2$ . W myśl warunku zadania, wartości $W(2^\alpha)$ , $W(2^{\alpha+1})$ są więc liczbami całkowitymi różnej parzystości. Wobec tego $M$ jest liczbą całkowitą nieparzystą.

Zachodzi wszelako równość

$ \begin{split} M & = m \cdot \sum_{j=0}^n \frac{p_j}{m_j} 2^{-\alpha_j} ((2^{\alpha+1})^j-(2^\alpha)^j) =\\ & = \sum_{j=0}^n p_j \cdot \frac{m}{m_j} (2^{j\alpha+j}-\alpha_j - 2^{j\alpha-\alpha_j}) \end{split} $

Dla $j = 0$ wyrażenie w ostatnim nawiasie jest zerem; dla $j > 0$ wyrażenie to jest różnicą dwóch potęg dwójki o wykładnikach całkowitych dodatnich, a więc różnicą liczb parzystych. Czynniki $p_j$ oraz $m/m_j$ są całkowite. Wynikałoby stąd, że $M$ jest liczbą parzystą - wbrew temu, co wykazaliśmy chwilę wcześniej.

Otrzymana sprzeczność dowodzi, że wielomian o podanych własnościach nie istnieje.

XLI OM - I - Zadanie 10

Zawody matematyczne:

XLI OM, 1989-1990

Etap:

Dla danej liczby naturalnej $n \geq 1$ wyznaczyć liczby dodatnie $x_1,\ldots,x_n$ o sumie równej $1$ , dla których iloczyn

$ x_1^1\cdot x_2^2 \cdot \ldots \cdot x_n^n $

osiąga wartość maksymalną.

Rozwiązanie

Niech $x_1,\ldots,x_n$ będą dowolnymi liczbami dodatnimi o sumie równej $1$ . Przepiszmy tę równość, jak następuje:

$ (1) \qquad x_1 + (\frac{x_2}{2} + \frac{x_2}{2}) + (\frac{x_3}{3}+\frac{x_3}{3} +\frac{x_3}{3}) + \ldots + (\frac{x_n}{n} + \ldots + \frac{x_n}{n})=1. $

Po otwarciu nawiasów, lewa strona (1) przybiera postać sumy $N$ składników, gdzie

$ N=1+2+\ldots+n = \frac{n(n+1)}{2}. $

Średnia arytmetyczna tych $N$ liczb równa się $1/N$ i jest nie mniejsza od ich średniej geometrycznej:

$ 1/N \geq \left( x_1 \cdot \frac{x_2}{2} \cdot \frac{x_2}{2} \cdot \frac{x_3}{3} \cdot \frac{x_3}{3} \cdot \frac{x_3}{3} \cdot \ldots \cdot \frac{x_n}{n} \cdot \ldots \cdot \frac{x_n}{n} \right)^{1/N} == \left( \frac{x_1^2 \cdot x_2^2 \cdot \ldots \cdot x_n^n}{1^1 \cdot 2^2 \cdot \ldots \cdot n^n} \right)^{1/N}. $

Stąd

$ (2) \qquad x_1^1 \cdot x_2^2 \cdot \ldots \cdot x_n^n \leq \frac{1^1 \cdot 2^2 \cdot \ldots \cdot n^n}{N^N}. $

Nierówność między średnią arytmetyczną oraz średnią geometryczną ( $N$ liczb) staje się równością wtedy i tylko wtedy, gdy liczby te są równe. Zatem w nierówności (2) znak równości ma miejsce wtedy i tylko wtedy, gdy każdy z $N$ składników sumy (1) (bez nawiasów) równa się $1/N$ - czyli gdy

$ x_k = \frac{k}{N} = \frac{2k}{n(n+1)} \quad \textrm{dla} \ k=1, \ldots, n. $

Dla tych liczb iloczyn napisany po lewej stronie (2) osiąga swą wartość maksymalną.

XLI OM - I - Zadanie 11

Zawody matematyczne:

XLI OM, 1989-1990

Etap:

W urnie znajduje się n kartek ponumerowanych liczbami od 1 do $n$ . Wyciągamy z urny bez zwracania kolejno $k$ kartek; $n$ i $k$ są ustalonymi liczbami naturalnymi, $1 \leq k \leq n$ . Niech $x_i$ będzie numerem $i$ -tej wyciągniętej kartki. Obliczyć prawdopodobieństwo tego, że w ciągu $(0,x_1,\ldots, x_k, 0)$ jest dokładnie jedno maksimum lokalne.

Uwaga. Wyraz ciągu nazywamy maksimum lokalnym, jeśli jest liczbą większą od obu wyrazów sąsiednich.

Rozwiązanie

Zajmiemy się najpierw przypadkiem szczególnym, w którym wyciągnięte kartki noszą numery od $1$ do $k$ (w pewnym porządku). Zakładamy więc, że zachodzi równość zbiorów $\{ x_1, \ldots, x_k \} = \{ 1, /ldots, k \}$ . Kolejność pojawiania się tych kartek w opisanym doświadczeniu wyznacza permutację $(x_1 ,\ldots,x_k)$ zbioru $\{ 1, /ldots, k \}$ .

Największą liczbą w tym zbiorze jest liczba $k$ . Jeśli w ciągu $(0,x_1,\ldots,x_k,0)$ ma wystąpić dokładnie jedno maksimum lokalne, musi nim być właśnie liczba $k$ . Wyrazy wcześniejsze, tj. występujące w danej permutacji przed $k$ , muszą utworzyć ciąg rosnący; wyrazy późniejsze - ciąg malejący. (Oczywiście, gdy $k = x_1$ , wówczas pierwszy z tych ciągów jest pusty; gdy zaś $k = x_k$ - drugi jest pusty.)

Zatem ustalenie zbioru liczb poprzedzających w danej permutacji liczbę $k$ w pełni identyfikuje permutację (mającą jedyne maksimum lokalne); kolejność, w jakiej te oraz pozostałe liczby muszą wystąpić jest już zdeterminowana przez warunek nieistnienia więcej niż jednego lokalnego maksimum.

Zbiór liczb poprzedzających $k$ może być dowolnym podzbiorem zbioru $\{1,\ldots,k-1\}$ (może być w szczególności zbiorem pustym lub zbiorem, którego dopełnienie jest puste).

Mamy więc wzajemnie jednoznaczną odpowiedniość między podzbiorami zbioru $\{1,\ldots,k - 1\}$ a rozważanymi permutacjami. Liczba podzbiorów zbioru $(k - 1)$ -elementowego wynosi $2^{k-1}$ , tyle samo jest też więc permutacji zbioru $\{1,\ldots,k\}$ , w których występuje dokładnie jedno maksimum lokalne.

Ponieważ zaś liczba wszystkich permutacji zbioru $k$ -elementowego równa się $k!$ , zatem prawdopodobieństwo wystąpienia dokładnie jednego maksimum lokalnego, przy założeniu równości $\{x_1,\ldots,x_k\} = \{1,\ldots,k\}$ , wynosi $2^{k-1}/(k!)$ .

Zauważmy teraz, że to założenie w gruncie rzeczy nie ogranicza ogólności rozważań. Niech $K$ będzie dowolnie ustalonym $k$ -elementowym podzbiorem zbioru $\{1,\ldots,n\}$ i przypuśćmy, że właśnie $K$ jest zbiorem numerów wylosowanych kartek. Kolejność wyciągania kartek wyznacza permutację zbioru $K$ . Liczba permutacji mających tylko jedno maksimum lokalne (którym z konieczności musi być największa liczba zbioru $K$ ) wynosi $2^{k-1}$ , tak samo, jak w przypadku zbioru $K = \{1,\ldots,k\}$ . Liczba wszystkich permutacji zbioru $K$ wynosi $k!$ . Prawdopodobieństwo, że losowo wybrana permutacja zbioru $K$ ma dokładnie jedno maksimum lokalne, równa się $2^{k-1}/(k!)$ .

Ponieważ dla każdego zbioru K otrzymujemy ten sam wynik, zatem otrzymana we wszystkich przypadkach wartość $2^{k-1}/(k!)$ jest odpowiedzią na postawione w zadaniu pytanie. Ta konkluzja, intuicyjnie jasna, może być uzasadniona w sposób bardziej formalny:

Niech $K_1,\ldots,K_m$ będzie ciągiem wszystkich $k$ -elementowych podzbiorów zbioru $\{1,\ldots,n\}$ ; kolejność ich numeracji jest bez znaczenia. (Oczywiście $m = \binom{n}{k}$ .) Ze zbioru $\{1,\ldots,n\}$ wybieramy kolejno bez powtórzeń $k$ elementów $x_1,\ldots,x_k$ . Rozważamy zdarzenia:

$ \begin{split} & A \colon \textrm{w ciągu} \ (0,x_1,\ldots,x_k,0)\ \textrm{jest dokładnie jedno maksimum lokalne};\\ & B_1 \colon \textrm{zbiór} \ \{ x_1, \ldots, x_k \}\ \textrm{jest identyczny ze zbiorem } K_1;\\ & B_2\colon \textrm{zbiór} \ \{ x_1, \ldots, x_k \}\ \textrm{jest identyczny ze zbiorem } K_2;\\ & \hdots \\ & B_m \colon \textrm{zbiór} \ \{ x_1, \ldots, x_k \}\ \textrm{jest identyczny ze zbiorem } K_m. \end{split} $

Na mocy poprzednich rozważań, prawdopodobieństwo warunkowe zdarzenia $A$ , pod warunkiem zajścia zdarzenia $B_i$ , jest dla każdego $i$ takie samo i równa się $2^{k-1} /(k!)$ :

$ P(A|B_i) = \frac{2^{k-1}}{k!} \quad \textrm{dla} \ i=1,\ldots,m. $

Zdarzenia $B_i$ wyczerpują wszystkie możliwości i wzajemnie się wykluczają, a więc $P(B_1) +\ldots+P(B_m) = 1$ .

Zgodnie z wzorem na prawdopodobieństwo całkowite:

$ P(A) = \sum_{i=1}^m P(A|B_i)P(B_i) = \frac{2^{k-1}}{k!} \sum_{i=1}^m P(B_i) = \frac{2^{k-1}}{k!} $

Jest to szukana wartość.

XLI OM - I - Zadanie 12

Zawody matematyczne:

XLI OM, 1989-1990

Etap:

Pięciokąt wypukły ma pole $S$ . Niech $S_1$ , $S_2$ , $S_3$ , $S_4$ , $S_5$ będą polami pięciu trójkątów odciętych przez przekątne pięciokąta (wierzchołkami każdego z tych trójkątów są trzy kolejne wierzchołki pięciokąta). Udowodnić, że suma pewnych czterech liczb $S_j$ przekracza $S$ .

Rozwiązanie

Niech $ABCDE$ będzie rozważanym pięciokątem. Ustalmy oznaczenia tak, by trójkąt $DEA$ miał minimalne pole (spośród pięciu trójkątów odciętych przez przekątne pięciokąta). Oznaczmy przez $P$ punkt przecięcia przekątnych $AC$ i $BD$ .

Weźmy pod uwagę trójkąty $EAB$ , $EAP$ , $EAD$ . Mają one wspólny bok $EA$ , pozostałe zaś wierzchołki leżą na jednej prostej, przy czym punkt $P$ leży między $B$ i $D$ (rysunek 4). Wobec tego pole trójkąta $EAP$ nie przekracza pola większego z trójkątów $EAB$ , $EAD$ . Ponieważ z założenia $\textrm{pole}(EAD) \leq \textrm{pole}(EAB)$ , zatem także

$ (1) \qquad \textrm{pole}(LAP) \leq \textrm{pole}(LAB). $

W podobny sposób (rozważając trójkąty $DEA$ , $DEP$ , $DEC$ ) wykazujemy, że

$ (2) \qquad \textrm{pole}(DEP) \leq \textrm{pole}(CDE). $

Odnotujmy ponadto oczywistą nierówność

$ (3) \qquad \textrm{pole}(PCD) < \textrm{pole}(BCD) $

(trójkąt $PCD$ jest częścią właściwą trójkąta $BCD$ ) oraz jeszcze bardziej oczywistą równość

$ (4) \qquad \textrm{pole}(ABC) = \textrm{pole}(ABC). $

Trójkąty, których pola występują po lewych stronach związków (1), (2), (3), (4), nie nakładają się na siebie i wypełnieją cały pięciokąt $ABCDE$ . Zatem dodając te związki stronami otrzymujemy nierówność

$ S = \textrm{pole}(ABCDE) < \textrm{pole}(EAB)+\textrm{pole}(ABC)+\textrm{pole}(BCD)+\textrm{pole}(CDE). $

Jest to teza zadania.