XLII OM - I etap

I etap XLII Olimpiady Matematycznej

XLII OM - I - Zadanie 1

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

Na brzegu jeziora w kształcie koła znajdują się cztery przystanie $K$ , $L$ , $P$ , $Q$ . Z przystani $K$ wypływa kajak kierując się do przystani $Q$ , a z przystani $L$ wypływa łódka kierując się do przystani $P$ . Wiadomo, że gdyby zachowując swe prędkości kajak popłynął w kierunku przystani $P$ , a łódka w kierunku przystani $Q$ , to doszłoby do zderzenia. Dowieść, że kajak i łódka dobiją do celu w tym samym czasie.

Rozwiązanie

Przypuśćmy, że kajak płynie z prędkością $v_k$ , a łódka płynie z prędkością $v_l$ . Oznaczmy przez $X$ punkt, w którym ,,doszłoby do zderzenia''. Długości odcinków, na które punkt $X$ dzieli cięciwy $KP$ i $LQ$ są związane zależnością $|KX| \cdot |PX| = |LX| \cdot |QX|$ (rysunek 1).

Z warunków zadania wynika, że stosunek prędkości $v_k \colon v_l = |KX| \colon |LX|$ . Z tych dwóch równości otrzymujemy proporcję $v_k \colon v_l = |QX| \colon |PX|$ .

Kąty wierzchołkowe $KXQ$ i $LXP$ są równe. Wobec tego trójkąty $KXQ$ i $LXP$ są podobne w skali $v_k \colon v_l$ , a zatem także $|KQ| \colon |LP| =v_k \colon v_l$ , czyli

$ |KQ| \colon v_k = |LP| \colon v_l. $

Lewa strona ostatniej proporcji wyraża czas zużyty przez kajak na przepłynięcie z $K$ do $Q$ ; prawa strona - to czas przepłynięcia łódki z $L$ do $P$ . Stąd teza.

XLII OM - I - Zadanie 2

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

Wyznaczyć wszystkie liczby rzeczywiste $x$ spełniające nierówność

$ 2\left| x - |x + |x-1|| \right| > \left x + |x - |x+1|| \right|. $

Rozwiązanie

Oznaczmy lewą i prawą stronę nierówności przez $L(x)$ i $P(x)$ . Tak więc

$ L(x) = 2|x-|f(x)||, \quad P(x) = |x + |g(x)||, $

gdzie

$ f(x) = x + |x-1|, \quad g(x) = x-|x + 1|. $

Zauważmy, że

$ f(x) = 1 + (x -1) + |x - 1| \geq 1, \quad g(x) = (x +1) -|x +1| - 1 \leq -1; $

funkcja $f$ przyjmuje tylko wartości dodatnie, a funkcja $g$ - tylko wartości ujemne. Zatem

$ L(x) = 2|x-f(x)|, \quad P(x) = |x-g(x)|. $

Podstawiając wyrażenia definiujące funkcje $f$ i $g$ otrzymujemy wzory

$ L(x) = 2|x-1|, \quad P(x) = |x + 1|. $

Dana w zadaniu nierówność $L(x) > P(x)$ (wiążąca liczby nieujemne) jest równoważna nierówności kwadratowej $L(x)^2 > P(x)^2$ , czyli nierówności

$ 3x^2-10x + 3 > 0. $

Pierwiastkami uzyskanego trójmianu kwadratowego są liczby $\frac{1}{3}$ i $3$ . Zatem zbiór liczb spełniających rozważaną nierówność jest sumą przedziałów

$ \left(-\infty; \ \frac{1}{3}\right) \cup (3;\infty). $

XLII OM - I - Zadanie 3

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

Liczby rzeczywiste $a$ , $x$ , $y$ , $z$ spełniają równość

$ \frac{\cos x + \cos y + \cos z}{\cos(x+y+z)} = \frac{\sin x + \sin y + \sin z}{\sin(x+y+z)} = a $

Wykazać, że

$ \cos(y+z)+\cos(z+x)+\cos(x+y) = a $

Rozwiązanie

Piszmy dla wygody $x_1$ , $x_2$ , $x_3$ zamiast $x$ , $y$ , $z$ ; przyjmijmy $x_4 = x_1$ oraz $w = x_1+x_2+x_3$ . Założenie przybiera postać:

$ \sum_{j=1}^3 \cos x_j = a \cos w, \quad \sum_{j=1}^3 \sin x_j = a \sin w. $

Stąd

$ \begin{split} \cos (y+z) + \cos (z+x) +\cos (x+y) & = \sum_{j=1}^3 \cos (x_j + x_{j+1}) = \sum_{j=1}^3 \cos (w-x_j) = \\ & = \sum_{j=1}^3 (\cos w \cos x_j + \sin w \sin x_j) = \\ & (\cos w) \sum_{j=1}^3 \cos x_j + (\sin w) \sum_{j=1}^3 \sin x_j = \\ & = a \cos^2 w + a \sin^2 w = a. \end{split} $

XLII OM - I - Zadanie 4

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

Obliczyć granicę

$ \lim_{n\to \infty} \sqrt[3n]{\sum_{k=0}^n \binom{3n}{3k}} $

Sposób I

Oznaczmy sumę występującą pod pierwiastkiem przez $a_n$ :

$ a_n = \sum_{k=0}^n \binom{3n}{3k} = 2+ \sum_{k=1}^{n-1} \binom{3n}{3k} \quad \textrm{dla} \ n \geq 2. $

Symbole dwumianowe spełniają tożsamość

$ \binom{m}{j} = \binom{m-1}{j-1} + \binom{m-1}{j} \quad \textrm{dla}\ j=1, \ldots, m-1. $

Korzystając dwukrotnie z tej tożsamości uzyskujemy dla $k = 1,\ldots,n-1$ nierówność

$ \begin{split} \binom{3n}{3k} & = \binom{3n-1}{3k-1} + \binom{3n-1}{3k} = \binom{3n-2}{3k-2} + 2\binom{3n-2}{3k-1} + \binom{3n-2}{3k} > \\ & > \binom{3n-2}{3k-2} + \binom{3n-2}{3k-1} + \binom{3n-2}{3k}. \end{split} $

Stąd

$ \begin{split} a_n -2 = \sum_{k=1}^{n-1} \binom{3n}{3k} & > \sum_{k=1}^{n-1} \binom{3n-2}{3k-2} + \binom{3n-2}{3k-1} + \binom{3n-2}{3k} = \\ & = \sum_{j=1}^{3n-3} \binom{3n-2}{j} = \sum_{j=0}^{3n-2} \binom{3n-2}{j} -2 =2^{3n-2} - 2 \end{split} $

(skorzystaliśmy z tego, że suma wyrazów $N$ -tego wiersza trójkąta Pascala równa się $2^N$ ). W połączeniu z oczywistą nierównością

$ a_n < \sum_{j=0}^{3n} \binom{3n}{j} = 2^{3n} $

daje to dwustronne oszacowanie

$ \frac{1}{4} \cdot 2^{3n} < a_n < 2^{3n}. $

Wyciągając ze wszystkich trzech członów nierówności pierwiastek stopnia $3n$ otrzymujemy związek

$ 2 \cdot \sqrt[3n]{\frac{1}{4}}< a_n < 2. $

Gdy $n$ dąży do nieskończoności, pierwiastek stopnia $3n$ z dowolnie ustalonej liczby dodatniej (w tym przypadku $\frac{1}{4}$ ) dąży do $1$ . Stąd, na mocy twierdzenia o trzech ciągach, wynika odpowiedź na postawione w zadaniu pytanie:

$ \lim_{n \to \infty} \sqrt[3n]{a_n} = 2. $

Sposób II

Suma występująca pod znakiem pierwiastka, oznaczona w poprzednim sposobie rozwiązania przez $a_n$ , daje się dość łatwo ,,zwinąć'': zachodzi mianowicie wzór

$ (1) \qquad \binom{N}{0}+\binom{N}{3}+\binom{N}{6} + \ldots + \binom{N}{3[N/3]} = \frac{1}{3} \left( 2^N + 2 \cos \frac{N \pi}{3} \right). $

Dowód można znaleźć na przykład w książce: L. Jeśmanowicz, J. Łoś {\it Zbiór zadań z algebry}, cz. I, Warszawa 1959 (Twierdzenia 1.17-1.18); także w miesięczniku {\it Delta}, numer 5 (1990) (zadanie M 563). Zachęcamy Czytelników do samodzielnego udowodnienia wzoru (1), przez indukcję albo przez rachunek na liczbach zespolonych z wykorzystaniem wzoru de Moivre'a.

Przyjmując w (1) $N= 3n$ dostajemy

$ a_n = \sum_{k=0}^n \binom{3n}{3k} = \frac{1}{3}(2^{3n} + 2\cos n\pi ) = \frac{1}{3} (2^{3n} + 2(-1)^n). $

Wyrażenie w nawiasie jest większe niż $\frac{1}{2} \cdot 2^{3n}$ , a mniejsze niż $2 \cdot 2^{3n}$ . Stąd

$ \frac{1}{6} \cdot 2^{3n} < a_n < \frac{2}{3} \cdot 2^{3n} $

i po wyciągnięciu pierwiastka:

$ 2 \cdot \sqrt[3n]{\frac{1}{6}} < \sqrt[3n]{a_n} < 2 \cdot \sqrt[3n]{\frac{2}{3}}. $

Przejście do granicy (z zastosowaniem twierdzenia o trzech ciągach) i ostateczna konkluzja - jak w sposobie poprzednim.

XLII OM - I - Zadanie 5

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

Dany jest odcinek $AD$ . Znaleźć na nim takie punkty $B$ i $C$ , by iloczyn długości odcinków $AB$ , $AC$ , $AD$ , $BC$ , $BD$ , $CD$ był maksymalny.

Rozwiązanie

Rozważamy takie położenia punktów $B$ i $C$ , przy których

$ (1) \qquad |AB| \leq |AC| \leq |AD|; $

to znaczy, przyjmujemy, że punkty $A$ , $B$ , $C$ , $D$ leżą na prostej w takim właśnie porządku (nie tracimy przez to ogólności, bowiem badany w zadaniu iloczyn nie zmienia wartości przy zamianie ról $B$ i $C$ ); słabe nierówności w (1) oznaczają, że dopuszczamy przypadki graniczne, gdy pewne z punktów $A$ , $B$ , $C$ , $D$ pokrywają się.

Przyjmijmy długość odcinka $AD$ za jednostkę: $|AD| = 1$ . Ponadto oznaczmy:

$ x = |BC|,\ y = |AB|-|CD|; \quad x \in \langle 0;1 \rangle,\ y \in \langle -1;1 \rangle. $

Wówczas $|AB| + |CD| = 1- x$ , skąd

$ \begin{split} |AB| = \frac{1}{2} (1-x + y), & \quad |CD| = \frac{1}{2}(1-x-y),\\ |AC| = |AB| + |BC| = \frac{1}{2}(1+x +y), & \quad |BD| = |BC| + |CD| = \frac{1}{2}(1 + x-y). \end{split} $

Rozważany iloczyn długości odcinków wynosi

$ \begin{split} (2) \qquad I & = \frac{1}{16}x (1-x + y)(1-x-y)(1 + x + y)(1+x-y) =\\ & = \frac{1}{16} x ((1-x)^2 - y^2) ((1+x)^2 - y^2) \leq \\ & \leq \frac{1}{16} x(1-x)^2(1+x)^2 = \frac{1}{16} x (1-x^2)^2; \end{split} $

ta nierówność staje się równością wtedy i tylko wtedy, gdy $y = 0$ - czyli gdy $|AB| = |CD|$ .

Wartość maksymalną wielomianu

$ f(x) = x(1-x^2)^2 = x^5-2x^3 + x $

na przedziale $\langle 0;\ 1\rangle$ możemy znaleźć przez różniczkowanie:

$ f'(x) = 5x^4 - 6x^2+1 = 5(x^2-1)\left(x^2-\frac{1}{5}\right) \left\{ \begin{array}{ccl} >0 & \textrm{dla} & x \in (0; \frac{1}{5} \sqrt{5}),\\ <0 & \textrm{dla} & x \in (\frac{1}{5} \sqrt{5}; 1);\\ \end{array} \right. $

widzimy, że $f$ osiąga maksimum dla $x = \frac{1}{5} \sqrt{5}$ .

[Zamiast różniczkować, można zastosować metodę bardziej elementarną (i przez to bardziej elegancką): skorzystać z nierówności między średnią geometryczną i średnią arytmetyczną piątki liczb. Tymi pięcioma liczbami będą: $4x^2$ oraz czterokrotnie powtórzona liczba $1-x^2$ . Otrzymujemy nierówność

$ \left(4 x^2 (1-x^2)^4\right)^{1/5} \leq \frac{1}{5}\left(4x^2+4(1-x^2)\right), $

czyli

$ 4^{1/5} f(x)^{2/5} \leq \frac{4}{5}, $

przy czym równość uzyskujemy, gdy uśredniane liczby są równe; to znaczy gdy
$4x^2 = 1 - x^2$ , czyli dla $x = \frac{1}{5} \sqrt{5}$ .]

Zgodnie z oszacowaniem (2) oraz następującą po nim uwagą, wyrażenie $I$ osiąga maksimum dla $x = \frac{1}{5} \sqrt{5}$ , $y = 0$ . Odpowiada to umieszczeniu odcinka $BC$ długości $x = \frac{1}{5} \sqrt{5}$ symetrycznie względem środka odcinka $AD$ - z zachowaniem porządku (1), bądź też z zamianą ról punktów $B$ i $C$ .

XLII OM - I - Zadanie 6

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

Trójkąt $ABC$ jest równoramienny, $\measuredangle BAC| = 100^{\circ}$ , dwusieczna kąta $ABC$ przecina bok $AC$ w punkcie $D$ . Dowieść, że

$ |AD| + |DB| = |BC|. $

Trójkąt równoramienny $FCD$ jest podobny do $ABC$ (wspólny kąt $C$ ), więc $|\measuredangle CFD| = 100^\circ$ . Wobec tego zachodzą równości

$ \begin{split} |\measuredangle DEF| = 80^\circ & = |\measuredangle DFE|,\\ |\measuredangle BDF| = |\measuredangle BDE| + |\measuredangle EDF|& = 60^\circ + 20^\circ = 80^\circ = |\measuredangle BFD|, \end{split} $

z których wynika, że trójkąty $DEF$ i $BDF$ są równoramienne:

$ |DE| = |DF|, \quad |BD| = |BF|. $

A zatem

$ |BC| = |BF| + |CF| = |BD| + |DE| = |BD| + |AD|. $

XLII OM - I - Zadanie 7

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

Dane są liczby rzeczywiste dodatnie $a$ , $b$ . Wyznaczyć wszystkie pary liczb rzeczywistych dodatnich $x$ , $y$ spełniające równanie

$ \frac{27xy}{(1+2ax)(1+2by)} = \frac{1}{ab} + \frac{x}{a} + \frac{y}{b} $

Rozwiązanie

Stosując trzykrotnie nierówność między średnią arytmetyczną trójki liczb oraz średnią geometryczną tych liczb stwierdzamy, że

$ \begin{split} 1+2ax & = 1 + ax + ax \geq 3 (a^2x^2)^{1/3},\\ 1+2by & = 1 + by + by \geq 3 (b^2y^2)^{1/3}, \end{split} $

oraz

$ \frac{1}{ab} + \frac{x}{a} + \frac{y}{b} \geq 3 \left(\frac{xy}{a^2b^2}\right)^{1/3} = \frac{27xy}{9(abxy)^{2/3}}. $

Mianownik ostatniego ułamka - to dokładnie iloczyn liczb znajdujących się po prawych stronach dwóch poprzednich równości. Wobec tego

$ \frac{1}{ab} + \frac{x}{a} + \frac{y}{b} \geq \frac{27xy}{(1+2ax)(1+2by)} $

(dla dowolnych liczb dodatnich $a$ , $b$ , $x$ , $y$ ). Wszystkie wypisane powyżej nierówności stają się jednocześnie równościami tylko wtedy, gdy $ax = 1$ , $by = 1$ oraz $1/ab = x/a = y/b$ - czyli gdy $x = y = 1/a = 1/b$ .

Stąd odpowiedź:

Jeśli dane liczby $a$ , $b$ są różne, równanie nie ma rozwiązań; jeśli są równe $(a=b)$ , wówczas jedynym rozwiązaniem danego równania jest $x = y = \frac{1}{a}$ .

XLII OM - I - Zadanie 8

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

Wyznaczyć największą liczbę naturalną $n$ , dla której istnieje w przestrzeni $n+1$ wielościanów $W_0, W_1, \ldots, W_n$ o następujących własnościach:

(l) $W_0$ jest wielościanem wypukłym mającym środek symetrii,

(2) każdy z Wielościanów $W_i$ ( $i = 1,\ldots, n$ ) powstaje z $W_0$ przez przesunięcie,

(3) każdy z wielościanów $W_i$ ( $i = 1,\ldots, n$ ) ma punkt wspólny z $W_0$ ,

(4) wielościany $W_0, W_1, \ldots, W_n$ mają wnętrza parami rozłączne.

Rozwiązanie

Przypuśćmy, że wielościany $W_0, W_1, \ldots ,W_n$ spełniają podane warunki. Wielościan $W_1$ jest obrazem $W_0$ w translacji o pewien wektor $\overrightarrow{\mathbf{v}}$ (warunek (2)). Oznaczmy przez $O_0$ środek symetrii wielościanu $W_0$ (warunek (1)); punkt $O_1$ będący obrazem $O_0$ w translacji o $\overrightarrow{\mathbf{v}}$ jest środkiem symetrii $W_1$ . Rysunek 3 ilustruje wariant płaski rozpatrywanego zagadnienia (przedstawienie konfiguracji przestrzennej bardzo by tę ilustrację zaciemniło); wielościany $W_0$ i $W_1$ zostały przedstawione jako środkowo-symetryczne wielokąty.

Na mocy warunku (3) wielościany $W_0$ i $W_1$ mają punkty wspólne (być może wiele). Niech $K$ będzie wspólnym punktem $W_0$ i $W_1$ (dowolnie wybranym). Oznaczmy przez $L$ obraz punktu $K$ w symetrii środkowej względem
$O_1$ ; zatem $L \in W_1$ . Niech $N$ będzie punktem takim, że $\overrightarrow{NL}=\overrightarrow{\mathbf{v}}$ i niech $M$ będzie środkiem odcinka $NK$ (rysunek 4). Tak więc $N \in W_0$ . Zgodnie z warunkiem (1), zbiór $W_0$ jest wypukły; to znaczy, że wraz z dowolnymi dwoma punktami należącymi do $W_0$ cały odcinek łączący te punkty zawiera się w $W_0$ . Skoro więc $K \in W_0$ oraz $N \in W_0$ , to także $M \in W_0$ . Odcinek $MO_1$ łączy środki odcinków $KN$ i $KL$ , a wobec tego $\overrightarrow{MO_1} = \frac{1}{2} \overrightarrow{NL} = \frac{1}{2} \overrightarrow{\mathbf{v}}$ , czyli $M$ jest środkiem odcinka $O_0O_1$ .

Oznaczmy przez $U$ obraz wielościanu $W_0$ w jednokładności o środku $O_0$ i skali 3. Wykażemy, że $W_1 \subset U$ . Weźmy dowolny punkt $P \in W_1$ : niech
$Q \in W_0$ będzie punktem takim, że $\overrightarrow{QP} =\overrightarrow{\mathbf{v}}$ i niech $S$ będzie środkiem symetrii równoległoboku $O_0O_1PQ$ . Środkowe $O_0S$ i $QM$ trójkąta $O_0O_1Q$ przecinają
się w punkcie $G$ takim, że $\overrightarrow{O_0G} = \frac{2}{3}\overrightarrow{O_0S} = \frac{1}{3}\overrightarrow{O_0P}$ (rysunek 5). To znaczy, że $P$ jest obrazem punktu $G$ w rozważanej jednokładności. A skoro $G$ jest punktem odcinka $QM$ o końcach w zbiorze (wypukłym) $W_0$ , zatem $G \in W_0$ . Wobec tego $P \in U$ i z dowolności wyboru punktu $P \in W_1$ wnosimy, że $W_1 \subset U$ .

W ten sam sposób dowodzimy, że każdy ze zbiorów $W_i (i= 1,\ldots,n)$ zawiera się w $U$ . Oczywiście także $W_0 \subset U$ . Tak więc zbiór $W_0 \cup W_1 \cup \ldots \cup W_n$ jest wielościanem zawartym w $U$ . Na mocy warunków (2) i (4) jego objętość równa się objętości $W_0$ pomnożonej przez $n+ 1$ . Natomiast objętość $U$ równa się objętości $W_0$ pomnożonej przez $27$ . Stąd $n \leq 26$ .

Pozostaje zauważyć, że wartość $n = 26$ może być osiągnięta (przykład realizacji: $27$ sześcianów $W_0, \ldots, W_{26}$ ułożonych, jak w kostce Rubika). Zatem szukana liczba równa się $26$ .

Uwaga. Ten sam wynik uzyskujemy zakładając, że $W_0, \ldots, W_n$ są dowolnymi ograniczonymi, domkniętymi bryłami wypukłymi (niekoniecznie wielościanami), o niepustych wnętrzach, spełniającymi warunki (1)-(4); rozumowanie przenosi się bez żadnych zmian. Co więcej, warunek (4) okazuje się zbędny. Udowodnił to Marcin Kasperski w pracy 27 zbiorów wypukłych bez środka symetrii, nagrodzonej złotym medalem na Konkursie Uczniowskich Prac z Matematyki w 1991 roku; skrót pracy przedstawia Delta w numerze 3 (1992).

XLII OM - I - Zadanie 9

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

Niech $f$ będzie przekształceniem płaszczyzny mającym następującą własność: dla dowolnej pary punktów $P$ , $Q$ , których odległość $|PQ|$ jest liczbą wymierną, odległość ich obrazów $P' = f(P)$ , $Q'= f(Q)$ spełnia równość $|P'Q'| = |PQ|$ . Udowodnić, że $f$ jest izometrią.

Rozwiązanie

Wykażemy najpierw, że przekształcenie $f$ jest różnowartościowe.

Przypuśćmy, że tak nie jest i że istnieją różne punkty $U$ , $V$ przekształcane na ten sam punkt $U' = f(U) = f(V) = V'$ . Weźmy dowolne liczby wymierne $q,r>0$ spełniające warunki $q + r > |UV| > q- r > 0$ . Można wówczas zbudować trójkąt $UVW$ o bokach $UW$ i $VW$ długości (odpowiednio) $q$ i $r$ . Obraz $W'$ punktu $W$ powinien - zgodnie z warunkiem zadania - leżeć w odległości $q$ od punktu $U'$ oraz w odległości $r$ od punktu $V'$ ; sprzeczność, skoro $U' = V'$ , $q > r$ .

Udowodnimy z kolei, że dla każdej pary punktów $P$ , $Q$ odległość ich obrazów $P'$ , $Q'$ nie przekracza odległości samych tych punktów:

$ (1) \qquad |P'Q'| \leq |PQ|\ \textrm{dla dowolnych}\ P,Q \quad (P' = f(P),\ Q' = f(Q)). $

Przypuśćmy, wbrew stwierdzeniu (1), że dla pewnych punktów $P$ , $Q$ odległości $d = |PQ|$ , $d' = |P'Q'|$ spełniają związek $d < d'$ . Na symetralnej odcinka $PQ$ znajdujemy punkt $R$ , którego odległość od punktu $P$ (a więc i od $Q$ ) jest liczbą wymierną większą od $d/2$ , ale mniejszą od $d'/2$ . Oznaczmy $f(R)$ przez $R'$ . W myśl założenia zadania mamy równości $|P'R'| = |PR|$ oraz $|Q'R'|= |QR|$ . W takim razie

$ |P'R'| + |Q'R'| = |PR| + |QR| < d' = |P'Q'|. $

To jednak nie jest możliwe. Otrzymana sprzeczność pokazuje, że nierówność $d < d'$ zachodzić nie może. Tym samym wykazaliśmy słuszność stwierdzenia (1).

Przypuśćmy teraz, że dla pewnych punktów $P$ , $Q$ zachodzi nierówność ostra $|P'Q'| <|PQ|$ . Na symetralnej odcinka $PQ$ obieramy dowolny punkt $X$ w odległości wymiernej od $P$ i uzupełniamy trójkąt równoramienny $PXQ$ do rombu $PXQY$ (o boku długości wymiernej). Obrazami odcinków $PX$ , $XQ$ , $QY$ , $YP$ (o jednakowej długości wymiernej) są odcinki $P'X'$ , $X'Q'$ , $Q'Y'$ , $Y'P'$ o tej samej długości; ponownie korzystamy z warunku zadania. Z różnowartościowości przekształcenia $f$ wnosimy, że punkty $X'$ i $Y'$ nie pokrywają się. Czworokąty $PXQY$ oraz $P'X'Q'Y'$ są więc rombami o tej samej długości boku. A skoro $|P'Q'| < |PQ|$ , wynika stąd, że $|X'Y'| > |XY|$ (skrócenie jednej przekątnej powoduje wydłużenie drugiej). Otrzymana nierówność stanowi jednak sprzeczność z wykazaną już własnością (1), w której rolę punktów $P$ i $Q$ grają teraz punkty $X$ i $Y$ .

Wobec tego ostra nierówność w (1) jest niemożliwa. To znaczy, że dla każdej pary punktów $P$ , $Q$ zachodzi równość $|P'Q'|=|PQ|$ . To znaczy, że przekształcenie $f$ jest izometrią.

XLII OM - I - Zadanie 10

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

Niech $(a_n)$ będzie dowolnym ciągiem liczb naturalnych spełniającym warunki:

$ a_1=1,\quad a_{n+2} = 2a_{n+1} - a_n +2 \text{ dla } n=1,2,3,\ldots. $

Dowieść, że dla każdej liczby naturalnej $n\geq 1$ iloczyn $a_na_{n+1}$ równa się pewnemu wyrazowi tego ciągu.

Rozwiązanie

Treść zadania nic nie mówi o wartości drugiego wyrazu ciągu $(a_n)$ . Oznaczmy ją więc przez $c$ ; jest to pewna liczba naturalna.

Wypiszmy kilka początkowych wyrazów ciągu $(a_n)$ , korzystając z podanego określenia rekurencyjnego i z warunków początkowych $a_1 = 1$ , $a_2 = c$ :

$ \begin{split} & a_3 = 2a_2 -a_1 + 2 = 2c-1 + 2 = 2c+1,\\ & a_4 = 2a_3 -a_2 + 2 = 2(2c + 1)-c + 2 = 3c + 4,\\ & a_5 = 2a_4 -a_3 + 2 = 2(3c + 4)-(2c+1) + 2 = 4c + 9,\\ & a_6 = 2a_5 -a_4 + 2 = 2(4c + 9)-(3c + 4) + 2 = 5c+16,\\ & a_7 = 2a_6 -a_5 + 2 = 2(5c + 16) - (4c + 9) + 2 = 6c + 25. \end{split} $

Widzimy, że dla $n=1,2,3,4,5,6,7$ zachodzi równość

$ (1) \qquad a_n = (n-1)c + (n-2)^2. $

Domyślamy się, że jest to wzór ogólny. Nasze przypuszczenie udowodnimy przez indukcję.

Zakładamy, że wzór (1) jest słuszny dla dwóch kolejnych liczb naturalnych $n = k$ oraz $n = k +1$ :

$ a_k = (k-1)c + (k-2)^2, \quad a_{k+1} = kc + (k -1 )^2. $

Zgodnie z określeniem ciągu $(a_n)$ mamy równość

$ \begin{split} a_{k+2} & = 2a_{k+1} - a_k + 2 =\\ & = 2 (kc + (k - 1)^2) - ((k - 1 )c + (k - 2)^2) + 2 =\\ & = (k+1)c + 2(k^2-2k+1)-(k^2-4k + 4) + 2 =\\ & = (k+1)c + k^2, \end{split} $

która pokazuje, że wzór (1) zachodzi także dla $n=k + 2$ . Na mocy zasady indukcji wynika stąd słuszność tego wzoru dla $n = 1,2,3,\ldots$ .

Niech $n \geq 1$ będzie dowolną liczbą naturalną. Mamy dowieść, że dla pewnego naturalnego $m \geq 1$ zachodzi równość $a_na_{n+1} =a_m$ , czyli

$ ((n - 1 )c + (n - 2)^2) (nc + (n - 1)^2) = (m - 1 )c + (m - 2)^2. $

Przepiszmy tę zależność w postaci

$ (2) \qquad m^2 + (c-4)m + (4-c)-((n-1)c + (n-2)^2)(nc + (n-1)^2) = 0. $

Traktując to jako równanie kwadratowe względem $m$ znajdujemy pierwiastki:

$ m_1 = 2 - nc - (n - 1)(n - 2), \quad m_2 = 2 + (n - 1)c + (n - 1)(n - 2). $

Drugi z nich równa się $a_n +n$ , zgodnie z wzorem (1); jest to liczba całkowita dodatnia. Zatem dla $m = a_n + n$ spełniona jest równość (2), a więc i równoważna jej postulowana równość $a_na_{n+1} = a_m$ .

Wykazaliśmy, że iloczyn wyrazów o numerach $n$ i $n + 1$ równa się wyrazowi o numerze $m = a_n + n$ .

XLII OM - I - Zadanie 11

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

Dla danej liczby naturalnej $n>10^3$ oraz każdego $k \in \{1,\ldots, n\}$ rozważamy resztę $r_k$ z dzielenia $2^n$ przez $k$ . Dowieść że $r_1+\ldots r_n > 2n$ .

Rozwiązanie

Dla $j = 0,1,2,3,4$ oznaczmy przez $K_j$ zbiór tych liczb całkowitych dodatnich, które nie przekraczają $n$ , dzielą się przez $2^j$ , ale nie przez $2^{j+1}$ , oraz mają co najmniej jeden dzielnik nieparzysty większy od $1$ . Tak więc

$ \begin{split} & K_0 = \{k \colon k \ \textrm{nieparzyste}, 3 \leq k \leq n \},\\ & K_1 = \{k \colon k = 2m,\ m\ \textrm{nieparzyste}, 3 \leq m \leq [n/2]\}.\\ & K_2 = \{k \colon k = 4m,\ m\ \textrm{nieparzyste}, 3 \leq m \leq [n/4]\},\\ & K_3 = \{k \colon k = 8m,\ m\ \textrm{nieparzyste}, 3 \leq m \leq [n/8]\},\\ & K_4 = \{k \colon k = 16m,\ m\ \textrm{nieparzyste}, 3 \leq m \leq [n/16]\}. \end{split} $

Ustalmy $j \in \{0,1,2,3,4\}$ i weźmy pod uwagę dowolną liczbę $k \in K_j$ . Zatem $k= 2^jm$ , $m$ nieparzyste, $m \geq 3$ . Niech $q_k$ i $r_k$ będą ilorazem i resztą z dzielenia $2^n$ przez $k$ :

$ 2^n = kq_k + r_k = 2^jmq_k + r_k. $

Stąd

$ r_k = 2^j(2^{n-j}-mq_k). $

Liczba w nawiasie jest dodatnia (bo reszta $r_k$ nie może być zerem). Wobec tego prawa strona nie jest mniejsza niż $2^j$ .

Wykazaliśmy więc, że

$ r_k \geq 2^j \quad \textrm{dla}\ k \in K_j. $

Zbiór $K_j$ ma tyle elementów, ile jest liczb nieparzystych $m$ spełniających warunki $3 \leq m \leq [n/2^j]$ - a więc nie mniej niż $\frac{1}{2} [n/2^j] - 1$ .

Niech $s_j$ oznacza sumę liczb $r_k$ , gdy $k$ przebiega zbiór $K_j$ . Wobec znalezionych oszacowań dostajemy nierówność

$ s_j = \sum_{k \in K_j} r_k \geq 2^j \left( \frac{1}{2} \left[ \frac{n}{2^j} \right]-1 \right) > 2^j \left( \frac{1}{2} \left( \frac{n}{2^j}-1 \right)-1 \right) = \frac{n-3 \cdot 2^j}{2} $

(skorzystaliśmy z tego, że $[x] > x - 1$ ).

Zbiory $K_0$ , $K_1$ , $K_2$ , $K_3$ , $K_4$ są rozłącznymi podzbiorami zbioru $\{1,\ldots,n\}$ . Wobec tego

$ \sum_{k=1}^n r_k \geq s_0+s_1+s_2+s_3+s_4 > \sum_{j=0}^4 \frac{n-3 \cdot 2^j}{2} = \frac{5n-93}{2}. $

Pozostaje zauważyć, że dla $n > 93$ (a tym bardziej dla $n > 10^3$ ) otrzymana w wyniku liczba $\frac{1}{2}(5n -93)$ przekracza $2n$ .

XLII OM - I - Zadanie 12

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

Dla dowolnej liczby naturalnej $n$ rozważamy prostopadłościan $K_n$ o krawędziach długości $1,1,n$ oraz zbiór $R_n$ złożony z $4n+1$ punktów: wierzchołków prostopadłościanu $K_n$ oraz punktów dzielących jego dłuższe krawędzie na odcinki długości jednostkowej. Wybieramy ze zbioru $R_n$ losowo trzy różne punkty. Niech $p_n$ będzie prawdopodobieństwem tego, że wybrane punkty są wierzchołkami trójkąta rozwartokątnego. Obliczyć $\lim_{n\to \infty} p_n$ .

Uwaga: Trzy punkty współliniowe nie tworzą trójkąta.

Rozwiązanie

Oznaczmy przez $Q(n)$ liczbę wszystkich trójelementowych podzbiorów zbioru $R_n$ , przez $T(n)$ - liczbę niezdegenerowanych trójkątów o wierzchołkach w zbiorze $R_n$ , a przez $P(n)$ - liczbę trójkątów rozwartokątnych. Badane prawdopodobieństwo jest ułamkiem $p_n = P(n)/Q(n)$ . Zauważmy, że

$ Q(n) =\binom {4n+4}{3}, \quad T(n) = \binom{4n+4}{3} - 4\binom {n+1}{3}. $

(Uzasadnienie drugiej równości: od liczby wszystkich trójek odejmujemy liczbę trójek punktów współliniowych - czyli trójek punktów leżących na dowolnej z czterech krawędzi, z których każda zawiera po $n +1$ punktów zbioru $R_n$ .)

Po rozpisaniu symboli Newtona otrzymujemy wzory

$ \begin{split} & Q(n) = \frac{(4n+4)(4n+3)(4n+2)}{6} = \frac{32}{3}n^3 + \textrm{(składniki niższych stopni)},\\ & T(n) = Q(n) - 4 \cdot \frac{(n+1)n(n-1)}{6} = 10n^3 + \textrm{(składniki niższych stopni)}. \end{split} $

Podzielmy zbiór $R_n$ na czteroelementowe ,,warstwy'' $H_0, H_1,\ldots, H_n$ : wierzchołki jednej z kwadratowych ścian prostopadłościanu $K_n$ tworzą warstwę $H_0$ , wierzchołki drugiej - warstwę $H_n$ ; warstwa $H_k$ składa się z punktów zbioru $R_n$ odległych od płaszczyzny warstwy $H_0$ o $k$ jednostek.

Skoro interesuje nas graniczne (przy $n \to \infty$ ) zachowanie rozważanych wielkości, możemy założyć, że $n \geq 4$ .

Ustalmy liczbę naturalną $r$ , $3 \leq r \leq n-1$ , i wybierzmy dowolne numery $k,m \in \{0,1,\ldots,n\}$ takie, że $m - k = r + 1$ . Między warstwami $H_k$ a $H_m$ jest więc $r$ warstw. Wybierając dowolnie punkty $A \in H_k$ , $C \in H_m$ oraz $B \in H_l$ , gdzie $l \in \{k + 1,\ldots,m-1\}$ , otrzymujemy albo trójkąt rozwartokątny albo współliniową trójkę punktów (bo $m-k \geq 4$ ). Mamy $16$ możliwości usytuowania pary punktów $A$ i $C$ oraz $4r$ możliwych położeń punktu $B$ - łącznie $64r$ możliwości; $4r$ spośród nich daje trójki współliniowe. Pozostaje $60r$ trójkątów rozwartokątnych.

Ponieważ numery $k$ , $m$ (o danej różnicy $r+1$ ) można ustalić na $n-r$ sposobów, zatem liczba $P(n)$ wszystkich możliwych do utworzenia trójkątów rozwartokątnych jest nie mniejsza niż suma

$ \begin{split} S(n) & = \sum_{r=3}^{n-1} 60r(n-r) = 60 \left( \sum_{r=1}^{n-1} (nr-r^2)-(3n-5) \right)=\\ & 60 \left( n \cdot \frac{(n-1)n}{2} - \frac{(n-1)n(2n-1)}{6} -3n+5 \right)= \\ & = 10n^3 +(\textrm{składniki niższych stopni}). \end{split} $

Mamy więc dwustronne oszacowanie

$ S(n) \leq P(n) \leq T(n). $

Wielkości $Q(n)$ , $T(n)$ , $S(n)$ są wielomianami trzeciego stopnia (zmiennej $n$ ). Współczynnik przy $n^3$ w $Q(n)$ równa się $32/3$ , natomiast w $T(n)$ i w $S(n)$ współczynnik przy $n^3$ równa się $10$ . Zatem

$ \lim_{n \to \infty} \frac{S(n)}{Q(n)} = \frac{10}{\frac{32}{3}} = \frac{15}{16}, \quad \lim_{n \to \infty} \frac{T(n)}{Q(n)} = \frac{10}{\frac{32}{3}} = \frac{15}{16} $

i na mocy twierdzenia o trzech ciągach

$ \lim_{n \to \infty} p_n = \lim_{n \to \infty} \frac{P(n)}{Q(n)} = \frac{15}{16}. $