XXXIX OM - III etap

III etap XXXIX Olimpiady Matematycznej

XXXIX OM - III - Zadanie 1

Zawody matematyczne:

XXXIX OM, 1987-1988

Etap:

III

Liczby $x_1, x_2, \ldots, x_n$ należące do przedziału $\langle 0; 1\rangle$ spełniają warunek

$ \sum_{i=1}^n x_i = m+r, $

gdzie $m$ jest liczbą całkowitą, $r \in \langle 0; 1)$ . Dowieść, że

$ \sum_{i=1}^n x_i^2 \leq m+r^2 $

Rozwiązanie

Rozpatrzmy najpierw przypadek szczególny, gdy wszystkie liczby $x_1, \ldots, x_n$ , z wyjątkiem co najwyżej jednej, są równe $0$ lub $1$ . Skoro $x_1 + \ldots +x_n = m + r$ , $m$ całkowite, $0 \leq r < 1$ , to (w tym przypadku) dokładnie $m$ spośród liczb $x_i$ jest jedynkami, jedna równa się $r$ , a pózostałe są zerami. Tak więc $x_i^2+ \ldots +x_k^2 = m+r^2$ i warunek z tezy zadania jest spełniony.

Załóżmy teraz, że istnieją liczby $x_k, x_l \in (0; 1)\ (k \ne l)$ ; jeśli takich liczb jest więcej niż dwie, wybieramy dwie dowolne. Określamy nowy układ $(y_1, \ldots, y_n$ ) liczb z przedziału $\langle 0; 1 \rangle$ przyjmując:

$ \begin{split} y_i & = x_i \ \textrm{dla} \ i \ne k, l,\\ y_k & = [x_k+x_l],\\ y_1 & = x_k + x_l-[x_k + x_l] = x_k + x_l-y_k. \end{split} $

Suma liczb układu $(y_1, \ldots, y_n)$ jest taka sama, jak układu $(x_1, \ldots, x_n)$ , natomiast suma kwadratów jest większa:

$ \begin{split} \sum_{i=1}^n y_i^2&-\sum_{i=1}^k x_i^2 = y_k^2+y_l^2 - x_k^2 - x_l^2 =\\ &= y_k^2+(x_k + x_l-y_k)^2-x_k^2-x_l^2 =\\ &= 2y_k^2 + (x_k+x_l)^2-2(x_k+x_l)y_k-x_k^2-x_l^2 =\\ &= 2(y_k^2+x_k x_l-x_ky_k-x_ly_k) =\\ &= 2(x_k-y_k)(x_l-y_k) > 0; \end{split} $

ostatnia nierówność wynika z tego, że $y_k$ równa się $0$ lub $1$ , natomiast $x_k$ i $x_l$ są liczbami z przedziału $(0; 1)$ .

W układzie $(y_1, \ldots,y_n)$ jest mniej liczb z przedziału $(0; 1)$ niż w układzie $(x_1, \ldots ,x_n)$ (bo $y_k \in \{0, 1\}$ ). Jeśli nadal są co najmniej dwie takie liczby, możemy procedurę powtórzyć. Kontynuując to postępowanie, dojdziemy po skończenie wielu krokach do układu $(z_1, \ldots,z _n)$ , $z_i \in \langle 0; 1 \rangle$ , w którym co najwyżej jedna liczba jest różna od $0$ i $1$ . W każdym kroku suma kwadratów liczb nowego układu jest większa niż starego, natomiast suma liczb układu pozostaje niezmieniona. Wobec tego

$ \sum_{i=1}^n z_i = \sum_{i=1}^n x_i m+r, \quad \sum_{i=1}^n z_i^2 > \sum_{i=1}^n x_i^2. $

Układ $(z_1, \ldots, z_n)$ spełnia warunki przypadku rozpatrywanego na wstępie, a zatem

$ \sum_{i=1}^n z_i^2 = m+r^2. $

Stąd

$ \sum_{i=1}^k x_i^k \leq m + r^2 $

w każdym przypadku.

XXXIX OM - III - Zadanie 2

Zawody matematyczne:

XXXIX OM, 1987-1988

Etap:

III

Dla permutacji $P=(p_1, \ldots, p_n)$ zbioru $\{1,2,\ldots, n\}$ definiujemy $X(P)$ jako liczbę wyrazów $p_s$ permutacji $P$ mających następującą własność: dla każdego $i < s$ zachodzi nierówność $p_i < p_s$ . Zakładając, że wszystkie permutacje są jednakowo prawdopodobnymi zdarzeniami losowymi, obliczyć wartość oczekiwaną zmiennej losowej $X$ .

Rozpatrywana zmienna losowa zależy od $n$ . Oznaczmy ją więc przez $X_n$ . Oczywiście $E(X_1) = 1$ . Znajdziemy zależność między $E(X_{n-1})$ a $E(X_n)$ .

Ustalmy liczby naturalne $n > 2$ oraz $k \in \{1, \ldots, n\}$ . Weźmy pod uwagę
dowolną permutację $P = (p_1, \ldots , p_n)$ zbioru $\{1, \ldots, n\}$ taką, że $p_n = k$ . Interesują nas wyrazy $p_s$ o własności:

$ (1) \qquad p_i < p_s \ \textrm{dla wszystkich}\ i < s. $

Rozpatrzymy dwa przypadki.

1. $k = n$ . Wówczas $p_n = n$ i jest to największy wyraz w ciągu $(p_1, \ldots,p_n)$ ; ma więc omawianą własność (tzn. (1) zachodzi dla $s = n$ ). Po odrzuceniu tego wyrazu otrzymujemy permutację $P' = (p_1, \ldots, p_{n-1})$ zbioru $\{1, \ldots, n - 1\}$ , w której jest $X_{n-1}(P')$ wyrazów $p_s$ spełniających warunek (1). Zatem w tym przypadku

$ (2) \qquad X_n(P)= X_{n-1}(P') +1. $

2. $k < n$ . Wyraz $p_n$ nie ma własności (1) (bo dla pewnego $i<n$ jest $??????? n>k$ ). Układ liczb $(p_1, \ldots, p_{n-1})$ stanowi permutację zbioru $\{1, \ldots, n\} \setminus \{k \}$ ; zatem układ $P' = (p_1', \ldots, p_{n-1}')$ , gdzie

$ p_i' = \left\{\begin{array}{ll} p_i & \textrm{gdy} \ p_i<k \\ p_i-1 & \textrm{gdy} \ p_i>k \end{array} \right. $

stanowi permutację zbioru $\{1, \ldots, n - 1\}$ , a przy tym mamy równoważność

$ p_i' < p_s' \Leftrightarrow p_i < p_s \quad (\textrm{dla } i, s \in \{1, \ldots, n-1\}). $

Wobec tego w całym układzie $P$ jest tyle samo wyrazów $p_s$ o własności (1), co w układzie $P'$ . Tak więc w tym przypadku

$ (3) \qquad X_n(P)= X_{n-1}(P'). $

Dla dowolnie ustalonej wartości $k \in \{1, \ldots, n\}$ odpowiedniość między permutacjami $P$ , w których $p_n = k$ , a permutacjami $P'$ zbioru $\{1, \ldots, n\} \setminus \{k\}$ określonymi powyżej (w każdym z przypadków) jest wzajemnie jednoznaczna. Ponieważ prawdopodobieństwo zajścia przypadku 1 wynosi $1/n$ , a przypadku 2 - $(1-1/n)$ , zatem z równości (2) i (3) wynika poszukiwana zależność rekurencyjna:

$ E(X_n) =\frac{1}{2}(E(X_{n-1}) + 1) + \left( 1 - \frac{1}{n} \right) E(X_{n-1}) = E(x_{n-1}) + \frac{1}{n}. $

Stąd - przez oczywistą indukcję -

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

XXXIX OM - III - Zadanie 3

Zawody matematyczne:

XXXIX OM, 1987-1988

Etap:

III

Niech $W$ będzie wielokątem (niekoniecznie wypukłym) mającym środek symetrii. Udowodnić, że istnieje taki równoległobok zawierający $W$ , że środki boków tego równoległoboku należą do brzegu $W$ .

Rozwiązanie

Spośród wszystkich trójkątów $OAB$ , gdzie $A$ , $B$ są wierzchołkami wielokąta $W$ , a $O$ - jego środkiem symetrii, wybierzmy trójkąt o maksymalnym polu (są co najmniej cztery takie trójkąty, a może ich być więcej; wybieramy którykolwiek). Niech $OMN$ będzie wybranym trójkątem i niech $M'$ , $N'$ będą wierzchołkami wielokąta $W$ symetrycznymi (odpowiednio) do $M$ , $N$ względem $O$ . Przez punkty $M$ i $M'$ prowadzimy proste $m$ i $m'$ równoległe do $NN'$ ; przez punkty $N$ i $N'$ prowadzimy proste $n$ i $n'$ równoległe do $MM'$ (rysunek 10).

Z maksymalności pola trójkąta $OMN$ wynika, że żaden wierzchołek wielokąta $W$ nic może leżeć dalej od prostej $MM'$ niż punkt $N$ , ani też dalej od prostej $NN'$ niż punkt $M$ . Zatem wszystkie wierzchołki leżą w obrębie równoległoboku $R$ utworzonego przez proste $m$ , $m'$ , $n$ , $n'$ , a wobec tego $W \subset R$ . Środkami boków $R$ są punkty $M$ , $N$ , $M'$ , $N'$ , wierzchołki wielokąta. $R$ jest więc szukanym równoległobokiem.

XXXIX OM - III - Zadanie 4

Niech $d$ będzie liczbą całkowitą dodatnią, a $f \: \langle 0; d\rangle \to \mathbb{R}$ taką funkcją ciągłą, że $f(0) = f(d)$ . Udowodnić, że istnieje $x \in \langle 0; d-1\rangle$ takie, że $f{x) = -f(x + 1)$ .

Rozwiązanie

Rozpatrujemy funkcję $g(x) = f(x+1)-f(x)$ określoną i ciągłą w przedziale $\langle 0; d-1 \rangle$ . Suma

$ \begin{split} g(0) + & \ldots +g(d-1) = \\ & = (f(1)-f(0))+ \ldots + (f(d)-f(d-1)) = \\ & = f(d)-f(0) \end{split} $

z założenia jest zerem, a więc albo wszystkie jej składniki są równe zeru, albo pewne dwa składniki są różnych znaków. W każdym razie istnieją liczby całkowite $a, b \in \langle 0; d-1 \rangle$ takie, że $g(a) \leq 0 \leq g(b)$ . Z ciągłości funkcji $g$ wynika, że w pewnym punkcie $x_0$ należącym do przedziału o końcach $a$ , $b$ przyjmuje ona wartość $0$ (własność Darboux). Równość $g(x_0) = 0$ jest zaś równoważna temu, że $f(x_0) = f(x_0+1)$ . Znaleźliśmy więc punkt $x_0 \in \langle 0; d-1 \rangle$ , o który chodziło w zadaniu.

Uwaga: Nie jest trudno pokazać, że podane twierdzenie nie jest prawdziwe dla żadnej liczby $d > 1$ , która nie jest całkowita. Wystarczy wziąć dowolną funkcję $h \colon \mathbb{R} \to \mathbb{R}$ okresową o okresie $1$ , ciągłą i taką, że $h(0) = 0$ , $h(d) = d$ , i przyjąć $f(x) = h(x)-x$ . Tak określona funkcja spełnia warunek $f(0) = f(d)$ , ale nie spełnia równości $f(x) = f (x +1)$ dla żadnego $x$ ; równość taka bowiem oznaczałaby, że $h(x+1) = h(x) + 1$ , co jest sprzeczne z założeniem okresowości funkcji $h$ .

XXXIX OM - III - Zadanie 5

Zawody matematyczne:

XXXIX OM, 1987-1988

Etap:

III

Ciąg $(a_n)$ określony Jest warunkami $a_1 = a_2 = a_3 = 1$ , $a_{n+1} = a_{n+2}a__{n+1}+a_n$ ( $n \geq 1$ ). Wykazać, że dla każdej liczby naturalnej $r$ istnieje taka liczba $s$ , że $a_s$ jest podzielne przez $r$ .

Rozwiązanie

Gdy $r=1$ , nie ma czego dowodzić. W dalszym ciągu zakładamy, że $r \geq 2$ .

Przyjmijmy $a_0 = 0$ i rozważajmy ciąg $(a_n)$ indeksowany nieujemnymi liczbami całkowitymi. Dana w zadaniu zależność rekurencyjna jest zachowana; możemy ją przepisać w równoważnej postaci

$ (1) \qquad a_n = a_{n+3}-a_{n+1}a_{n+2} \quad \textrm{dla} \ n = 0, 1, 2, 3, \ldots. $

Zajmiemy się ciągiem $(x_0, x_1 x_2, x_3, \ldots)$ , gdzie $x_n$ jest resztą z dzielenia $a_n$ przez $r$ . Niech $Z_r^3$ będzie zbiorem wszystkich uporządkowanych trójek liczb ze zbioru $\{0, 1, \ldots, r-1\}$ . Dla każdego $n \geq 0$ trójka $T_n = (x_n, x_{n+1}, x_{n+2})$ należy do $Z_r^3$ . Ponieważ $Z_r^3$ jest zbiorem skończonym, w ciągu $(T_0, T_1, T_2, T_3, \ldots)$ muszą wystąpić powtórzenia. Innymi słowy, istnieją liczby całkowite $m \geq 0$ , $s > 0$ takie, że $T_m = T_{m+s}$ , czyli

$ (2) \qquad x_m = x_{m+s}, \quad x_{m+1} = x_{m+s+1}, \quad x_{m+2} = x_{m+s+2}. $

Niech $m \geq 0$ będzie najmniejszym numerem, dla którego istnieje $s > 0$ spełniające związki (2) (czyli równość $T_m= T_{m+s}$ ). Wykażemy, że $m = 0$ . Przypuśćmy, że jest inaczej, tzn. $m \geq 1$ . Podstawmy w (1) $n = m-1$ oraz $n = m+s- 1$ . Otrzymamy równości

$ (3) \qquad a_{m-1} = a_{m + 2} - a_ma_{m+1}, $

$ (4) \qquad a_{m + s-1} = a_{m+s+2} - a_{m +s}a_{m + s + 1}. $

Ze związków (2) wynika, że prawe strony równości (3) i (4) dają przy dzieleniu przez $r$ jednakowe reszty; wobec tego i lewe strony muszą dawać jednakowe reszty. A zatem

$ x_{m - 1} =x_{m + s -1}. $

To zaś, w połączeniu z dwiema pierwszymi równościami (2), oznacza, że trójki $T_{m-1} = (x_{m-1}, x_m, x_{m+1})$ i $T_{m-1+s} = (x_{m+1+s}, x_{m+s}, x_{m+1+s})$ są identyczne - wbrew minimalności wskaźnika $m$ . Otrzymana sprzeczność pokazuje niesłuszność przypuszczenia, że $m \geq 1$ . Zatem $m = 0$ .

Pierwsza z równości (2) przybiera teraz postać $x_0 = x_s$ . Ale $x_0 = 0$ (bo $a_0 = 0$ ). Wobec tego i $x_s = 0$ . A to znaczy, że $a_s$ dzieli się przez $r$ .

XXXIX OM - III - Zadanie 6

Zawody matematyczne:

XXXIX OM, 1987-1988

Etap:

III

Obliczyć maksymalną objętość czworościanu zawartego w półkuli o promieniu długości 1.

Rozwiązanie

Oznaczmy daną półkulę przez $H$ , całą kulę przez $K$ , a koło stanowiące płaską część brzegu $H$ przez $E$ . Niech $O$ będzie dowolnym czworościanem zawartym w $H$ . Jego wnętrze jest częścią wspólną czterech otwartych półprzestrzeni, wyznaczonych przez płaszczyzny ścian. Środek kuli $K$ nie należy do wnętrza czworościanu; zatem nie należy do co najmniej jednej z tych półprzestrzeni. Istnieje wobec tego taka ściana $S$ czworościanu $Q$ , że przeciwległy wierzchołek czworościanu oraz środek kuli $K$ leżą po przeciwnych stronach płaszczyzny tej ściany (lub, w granicznym przypadku, środek kuli leży na tej płaszczyźnie).

Tak więc $Q$ zawiera się w mniejszej z dwóch części (ewentualnie w jednej z dwóch równych części), na które płaszczyzna ściany $S$ dzieli kulę $K$ . Zatem wysokość czworościanu $Q$ opuszczona na ścianę $S$ ma długość nie większą od $1$ , tak że objętość $Q$ nie przekracza jednej trzeciej pola tej ściany. Z kolei pole ściany $S$ , będącej trójkątem, nie jest większe od pola trójkąta równobocznego wpisanego w koło będące przekrojem kuli $K$ płaszczyzną tej ściany (por. Uwaga); a tym bardziej nie większe od pola trójkąta równobocznego wpisanego w koło wielkie $E$ . To ostatnie pole równa się $3 \sqrt{3}/4$ . Zatem objętość $Q$ jest mniejsza lub równa $\sqrt{3}/4$ .

We wszystkich przytoczonych szacowaniach możemy uzyskać równość biorąc za $O$ czworościan, którego podstawą jest trójkąt foremny wpisany w $E$ , a czwarty wierzchołek jest umieszczony w najdalszym od $E$ punkcie półkuli $H$ (w ,,biegunie północnym'').

Liczba $\sqrt{3}/4$ jest szukanym maksimum.

Uwaga: Dla kompletności podamy elementarny dowód faktu, że spośród wszystkich trójkątów wpisanych w ustalone koło o promieniu $r$ największe pole ma trójkąt równoboczny.

Niech $ABC$ będzie dowolnym takim trójkątem. Umieszczając punkt $C$ w środku większego z dwóch łuków, na które punkty $A$ i $B$ dzielą okrąg opisany na trójkącie $ABC$ , otrzymujemy trójkąt równoramienny $ABC'$ , ostrokątny lub prostokątny, o polu nie mniejszym niż trójkąt $ABC$ . Szukając trójkąta o maksymalnym polu (wpisanego w dane kolo) możemy więc ograniczyć uwagę do klasy trójkątów równoramiennych bez kątów rozwartych (wpisanych w to koło).

Jeśli teraz $ABC$ jest trójkątem z tej klasy ( $|AC| = |BC|$ ), to oznaczając przez $x$ odległość boku $AB$ od środka koła dostajemy zależności: $|AB| = 2\sqrt{r^2-x^2}$ , $h_C = r+x$ (wysokość opuszczona z wierzchołka $C$ ) i wobec tego

$ \begin{split} \textrm{pole} & (ABC) = (r+x) \sqrt{r^2-x^2}= \frac{1}{\sqrt{3}} \sqrt{(r+x)^3 (3r-3x)} =\\ & = \frac{1}{\sqrt{3}} \left( \sqrt[4]{(r+x)^3 (3r-3x)}\right)^2 \leq \frac{1}{\sqrt{3}} \left( \frac{3(r+x)+(3r-3x)}{4} \right)^2 = \frac{3\sqrt{3}}{4} r^2. \end{split} $

Skorzystaliśmy tu z nierówności między średnią geometryczną i średnią arytmetyczną czterech liczb: $a_1 - a_2 = a_3 = r+ x$ , $a_4 = 3r-3x$ . Nierówność ta staje się równością wtedy i tylko wtedy, gdy te liczby są równe, czyli dla $x = r/2$ . Pozostaje zauważyć, że ostatnia równość oznacza, że trójkąt $ABC$ jest foremny.