XXXVIII OM - I etap

I etap XXXVIII Olimpiady Matematycznej

XXXVIII OM - I - Zadanie 1

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

Wielomian $P(x) = a_0+a_1x+ \ldots +a_nx_n^n$ spełnia warunki $P(1) = 0$ oraz $P(x) \geq 0$ dla każdego $x \in \mathbb{R}$ . Dowieść, że

$ a_n+2a_{n-1}+ \ldots +(n+1)a_0 = 0. $

Rozwiązanie

Wielomian $P$ ma w punkcie $x = 1$ minimum. Zatem $P'(1) = 0$ . Mamy więc równości

$ a_0+a_1+ \ldots +a_{n-1}+a_n = P(1) = 0, $

$ a_1+2a_2+ \ldots + (n-1)a_{n-1}+na_n = P'(1) = 0. $

Mnożąc pierwszą z nich stronami przez $n+1$ i odejmując drugą dostajemy

$ (n+1)a_0+na_1+ \ldots +2_a{n-1}+a_n = 0. $

XXXVIII OM - I - Zadanie 2

Zawody matematyczne:

XLVIII OM, 1996-1997

Etap:

Warunkiem koniecznym i wystarczającym na to, by liczby dodatnie $a, b, c$ były długościami boków pewnego trójkąta jest, by spełniały one nierówność $|a—b| < c < |a+b|$ . Sformułować i udowodnić analogiczne warunki konieczne i wystarczające na to, by trzy liczby dodatnie były długościami:

a) wysokości pewnego trójkąta,

b) środkowych pewnego trójkąta.

Rozwiązanie

a) Załóżmy, że liczby $h_a$ , $h_b$ , $h_c$ są długościami wysokości pewnego trójkąta. Niech $a$ , $b$ , $c$ będą długościami boków tego trójkąta ( $h_a$ — wysokość opuszczona na bok o długości $a$ itd.), a $S$ - jego polem. Z równości $2S = ah_a= bh_b = ch_c$ wynika, że liczby $h_a$ , $h_b$ , $h_c$ są - z dokładnością do czynnika $2S$ - odwrotnościami długości boków.

Skoro więc $|a-b|<c<a+b$ , to także

$ (1) \qquad \left| \frac{1}{h_a} -\frac{1}{h_b} \right| < \frac{1}{h_c} < \frac{1}{h_a} + \frac{1}{h_b} $

Na odwrót, jeśli trzy liczby dodatnie $h_a$ , $h_b$ , $h_c$ spełniają nierówność podwójną (1) , to istnieje trójkąt $T'$ o bokach długości $a' = 1/h_a$ , $b' = 1/h_b$ , $c' = 1/h_c$ . Oznaczając przez $h'_a$ , $h'_b$ , $h'_c$ długości wysokości trójkąta $T'$ , a przez $S'$ jego pole widzimy, że

$ h'_a = 2S'/a' = 2 S'h_a,\quad h'_b = 2 S'h_b, \quad h'c = 2 S'h_c. $

Trójkąt $T$ jest podobny do $T'$ w skali $1/2 S'$ ma więc wysokości o długościach $h_a$ , $h_b$ , $h_c$ .

Zatem warunek (1) jest konieczny i dostateczny na to, by liczby $h_a, h_b, h_c > 0$ były długościami wysokości pewnego trójkąta.
b) Załóżmy, że liczby $m_a$ , $m_b$ , $m_c$ są długościami środkowych pewnego trójkąta $ABC$ , poprowadzonych odpowiednio z wierzchołków $A$ , $B$ , $C$ . Niech $|BC| = a$ , $|CA| = b$ , $|AB| = c$ i niech $O$ będzie punktem przecięcia środkowych. Oznaczmy przez $M$ środek boku $AB$ , a przez $N$ - punkt symetryczny do $O$ względem punktu $M$ . Czworokąt $OANB$ jest równoległobokiem (rysunek 1), a więc trójkąt $OAN$ ma boki o długościach

$ |OA| = \frac{2}{3} m_a, \quad |AN| = |OB| = \frac{2}{3}m_b, \quad |NO| = 2|OM| = \frac{2}{3} m_c. $

Wobec tego trójkąt podobny do $OAN$ w skali $3/2$ ma boki o długościach $m_a$ , $m_b$ , $m_c$ , skąd wynika, że liczby te muszą spełniać warunek

$ (2) \qquad |m_a -m_b| <m_c< m_a+m_b. $

Na odwrót, jeśli trzy liczby dodatnie $m_a$ , $m_b$ , $m_c$ spełniają ten warunek, to istnieje trójkąt $OKL$ , w którym $|KL| = m_a$ , $|LO| = m_b$ , $|OK| = m_c$ . Oznaczmy przez $P$ i $Q$ punkty symetryczne do $K$ i $L$ względem punktu $O$ , po czym uzupełnijmy trójkąty $OLP$ i $OQK$ do równoległoboków $OLUP$ , $OQVK$ . Powstaje sześciokąt $KLUPQV$ zbudowany z sześciu trójkątów przystających do $OKL$ (rysunek 2).

Weźmy pod uwagę trójkąt $UQK$ . Oznaczmy środki jego boków $QK$ , $KU$ , $UQ$ odpowiednio przez $X$ , $Y$ , $Z$ ; są to jednocześnie środki odcinków $OV$ , $OL$ , $OP$ . Długości środkowych trójkąta $UQK$ wynoszą

$ |UX|=\frac{3}{2} |OU| =\frac{3}{2} m_a, \quad |QY|=\frac{3}{3}|OQ|=\frac{3}{2} m_b, \quad |KZ| = \frac{3}{2}|OK| = \frac{3}{2}m_c, $

Wobec tego trójkąt podobny do $UQK$ w skali $2/3$ ma środkowe o długościach $m_a$ , $m_b$ , $m_c$ .

Zatem warunek (2) jest konieczny i dostateczny na to, by liczby $m_a, m_b, m_c > 0$ były długościami środkowych pewnego trójkąta.

XXXVIII OM - I - Zadanie 3

Zawody matematyczne:

XLVIII OM, 1996-1997

Etap:

Rozwiązać w liczbach naturalnych równanie

$ 3^n+88=k^2. $

Rozwiązanie

Załóżmy, że liczby naturalne $n$ , $k$ spełniają dane równanie. Dla $n = 1$ odpowiednie $k$ nie istnieje; zatem $n > 1$ .

Lewa strona równania jest liczbą nieparzystą, więc i liczba k musi być nieparzysta.

Niech $m = [n/2]$ (część całkowita liczby $m/2$ ). Tak więc $n = 2m+r$ , gdzie $m > 1$ , a $r = 0$ lub $r = 1$ w zależności od tego, czy $n$ jest liczbą parzystą, czy nie. Rozważane równanie przekształcamy następująco:

$ k^2-3^{2m}3^r=88, $

$ k^2-3^{2m}+3^{2m}(1-3^r)=88, $

$ (k-3^m)(k+3^m)=88-3^{2m}(1-3^r). $

W ostatniej równości lewa strona dzieli się przez $4$ , jako iloczyn dwóch liczb parzystych. Zatem po prawej stronie składnik $3^{2m}(1-3^r)$ musi dzielić się przez $4$ , a to zachodzi tylko, gdy $r = 0$ . Stąd $n = 2m$ i równanie przybiera postać

$ (k^2-3^m)(k+3^m) = 88. $

Otrzymaliśmy rozkład liczby $88$ na iloczyn dwóch czynników parzystych. Istnieją dwa takie rozkłady: $88 = 2 \cdot 44$ i $88 = 4 \cdot 22$ . Różnica czynników ma być jednak liczbą postaci $2 \cdot 3^m$ . To eliminuje pierwszy z tych rozkładów. Ostatecznie więc musi być

$ k-3^m = 4, \quad k+3^m = 22, $

skąd

$ k = 13, \quad m = 2 (\text{czyli }n = 4). $

Para $n = 4$ , $k = 13$ jest rozwiązaniem danego równania.

XXXVIII OM - I - Zadanie 4

Zawody matematyczne:

XLVIII OM, 1996-1997

Etap:

Dla danej liczby naturalnej $n$ rozpatrujemy rodzinę $W$ wszystkich takich zbiorów $A$ par liczb naturalnych nie większych od $n$ , że jeżeli $(a, b) \in A$ , to $(x, y) \in A$ dla $1 \leq x \leq a$ , $1 \leq y \leq b$ .

Wykazać, że rodzina $W$ składa się z $\binom{2n}{n}$ różnych zbiorów.

Rozwiązanie

Dla dowolnej pary liczb naturalnych $(x,y)$ oznaczamy przez $Q_{xy}$ kwadrat jednostkowy o wierzchołkach $(x-1,y-1)$ , $(x,y-1)$ , $(x,y)$ , $(x-1,y)$ , zaś przez $R_{xy}$ - prostokąt o wierzchołkach $(0,0)$ , $(x,0)$ , $(x,y)$ , $(0,y)$ . Jeśli $A$ jest dowolnym zbiorem par liczb naturalnych, to symbolem $Z(A)$ będziemy oznaczać następujący podzbiór płaszczyzny:

$ Z(A)= \bigcup_{(x,y) \in A} Q_{xy}; $

przyjmujemy przy tym

$ Z(\emptyset)=\emptyset $

Zgodnie z treścią zadania, zbiór $A$ należy do rodziny $W$ wtedy i tylko wtedy, gdy zbiór $Z = Z(A)$ spełnia warunki:

$Z$ jest sumą skończonej liczby kwadratów $Q_{xy}$ ( $x,y\in \mathbb{N}$ ),
$Z \subset R_{nn}$ ,
$Q_{ab} \subset Z \Longrightarrow R_{ab} \subset Z$ .

W szczególności zbiór pusty (złożony z $0$ kwadratów jednostkowych) spełnia te warunki.

Załóżmy chwilowo, że zbiór $Z$ nie jest pusty. Implikacja (3) wyraża wówczas dokładnie tyle, że $Z$ jest sumą pewnej (skończonej, dodatniej) liczby prostokątów postaci $R_{ab}$ - czyli prostokątów o dwóch bokach położonych na dodatnich półosiach układu współrzędnych. Skończona suma takich prostokątów (zawartych w $R_nn$ ) jest wielokątem ograniczonym łamaną zamkniętą $ON_0M_1N_1\ldots M_kN_kO$ , gdzie: $k\in \mathbb{N}$ ; wszystkie wierzchołki mają współrzędne całkowite; $O$ jest początkiem układu współrzędnych; $N_0$ jest punktem odcinka $OK$ , gdzie $K = (0, n)$ ; $N_k$ jest punktem odcinka $OL$ , gdzie $L = (n, 0)$ ; wektory $\overrightarrow{N_{i-1}M_i}$ , są równoległe do osi $Ox$ i skierowane zgodnie ze zwrotem tej osi; wektory $\overrightarrow{M_iN_i}$ są równoległe do osi $Oy$ i skierowane przeciwnie do zwrotu tej osi ( $i = 1, \ldots , k$ ) (rysunek 3).

Na odwrót, każdy wielokąt $Z$ ograniczony taką łamaną spełnia warunki (1), (2), (3), a więc odpowiada pewnemu niepustemu zbiorowi $A\in W$ . Pozostaje policzyć te wielokąty.

Niech $ON_0M_1N_1\ldots M_kN_kO$ będzie wielokątem omawianej postaci. Każdy z wektorów $\overrightarrow{N_{i-1}M_i}$ jest sumą pewnej liczby wektorów jednostkowych $[1,0]$ , zaś każdy z wektorów $\overrightarrow{M_iN_i}$ , jest sumą pewnej liczby wektorów jednostkowych $[0, -1]$ . Weźmy pod uwagę łamaną $KN_0M_1N_1\ldots M_kN_kL$ (może być $K = N_0$ lub $N_k = L$ ), zorientowaną od $K$ do $L$ . Składa się ona z $2n$ wektorów jednostkowych: każdy z wektorów $[1, 0]$ i $[0, -1]$ musi wystąpić $n$ --krotnie (idąc od $K$ do $L$ musimy wykonać $n$ kroków w prawo i $n$ kroków w dół). Wielokąt $Z$ jest jednoznacznie określony przez drogę tego typu biegnącą od $K$ do $L$ .

Ponieważ założyliśmy (chwilowo), że zbiór $Z$ jest niepusty, musimy wykluczyć drogę od $K$ do $L$ złożoną kolejno z $n$ --krotnie powtórzonego wektora $[0, -1]$ , a następnie z $n$ --krotnie powtórzonego wektora $[1,0]$ (czyli łamaną $KOL$ ). Naturalne jest teraz dopuścić i tę drogę przyjmując, że odpowiada ona właśnie pustemu zbiorowi $Z$ (który też trzeba włączyć do rozważań).

Ile jest więc dopuszczalnych dróg od $K$ do $L$ ? Mamy $2n$ wektorów jednostkowych dwóch typów. Jeśli w ciągu $(1, 2, \ldots, 2n)$ ustalimy $n$ miejsc, na których umieszczamy wektor $[1, 0]$ , to na pozostałych $n$ miejscach musi wystąpić wektor $[0, -1]$ . Jest więc tyle rozważanych dróg, ile podzbiorów $n$ --elementowych zbioru $2n$ --elementowego, czyli $\binom{2n}{n}$ . Tyle samo jest wielokątów $Z$ spełniających warunki (1), (2), (3), tyle samo więc i zbiorów $A$ w rodzinie $W$ .

XXXVIII OM - I - Zadanie 5

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

Udowodnić, że jeżeli funkcja

$ f(x) = c_0+a_1 \cos x + b_1 \sin x + a_2 \sin{2x} + b_2 \sin{2x} $

ma pięć miejsc zerowych w przedziale $(0; 2\pi)$ , to $f(x) = 0$ dla każdego $x$ .

Rozwiązanie

Zgodnie z założeniem, istnieją liczby $x_i \in (0; 2\pi)$ , $i = 1, 2, 3, 4, 5$ , różne między sobą, takie, że $f(x_i) = 0$ .

Zastosujemy podstawienie $t = \ctg(x/2)$ . Gdy $x$ przebiega przedział $(0; 2\pi)$ , $t$ przebiega przedział $(-\infty; \infty)$ , przy czym różnym wartościom $x$ odpowiadają różne wartości $t$ . W szczególności liczby $t = \ctg(x_i/2)$ , $i = 1, 2, 3, 4, 5$ , są wszystkie różne.
Korzystając ze znanych wzorów

$ \begin{split} &\sin x = \frac{2t}{t^2+1}, \quad \cos x =\frac{t^2-1}{t^2+1}\\ & \sin 2x = 2\sin x \cos x = \frac{4t(t^2-1)}{(t^2+1)^2}\\ &\cos 2x = \cos^2 x - \sin^2 x =\frac{t^4-6t^2+1}{(t^2+1)^2} \end{split} $

przekształcamy wyrażenie definiujące funkcję $f$ do postaci

$ g(t) = \frac{P(t)}{(t^2+1)^2} $

gdzie $P$ jest wielomianem stopnia co najwyżej czwartego (znajomość jego współczynników nie będzie nam do niczego potrzebna).

Dokładniej, związek między funkcją $f$ (zmiennej $x$ ) i funkcją $g$ (zmiennej $t$ ) jest taki:

$ \left.\begin{array}{r} x\in (0, 2\pi)\\ t=\ctg \frac{x}{2} \end{array}\right| \Longrightarrow f(x)=g(x). $

Skoro $f(x_i) = 0$ , to $g(t_i) = 0$ , więc i $P(t_i) = 0$ dla $i = 1, 2, 3, 4, 5$ . Wielomian stopnia $4$ przyjmujący wartość $0$ w pięciu różnych punktach musi być tożsamościowo równy zeru. Zatem $f(x) = 0$ dla $x\in (0; 2\pi)$ .

Z ciągłości funkcji trygonometrycznych wynika teraz, że $f(x) = 0$ dla $x \in \langle 0; 2 \pi \rangle$ , a z ich okresowości — że $f(x) = 0$ dla wszystkich $x \in \mathbb{R}$ .

Uwaga. Nietrudno dowieść, że współczynniki $c_0$ , $a_1$ , $b_1$ , $a_2$ $b_2$ muszą być wszystkie równe zeru.

XXXVIII OM - I - Zadanie 6

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

Który z czworokątów mających trzy boki długości 1 ma największe pole?

Rozwiązanie

Skorzystamy ze wzoru (1)

$ (1) \qquad \mathrm{pole} (ABCD) = \sqrt{(p-a)(p-b)(p-c)(p-d) - abcd\cos^2 \phi}, $

gdzie

$ a = |AB|, \quad b = |BC|, \quad c = |CD|, \quad d = |DA|, $

$ p=\frac{1}{2} (a+b+c+d), \quad \phi = \frac{1}{2} (|\measuredangle A|+|\measuredangle C|). $

Wzór (1) jest słuszny dla dowolnego czworokąta, niekoniecznie wypukłego; dowód można znaleźć na przykład w książce S. Straszewicza {\em Zbiór zadań z olimpiad matematycznych} (PZWS 1956) w komentarzu do rozwiązania zadania 101 (str. 227).

Przyjmijmy, zgodnie z treścią zadania, że $a = b = c = b$ . Ustalmy $d \in (0;3)$ (dla innych wartości dnie istnieją czworokąty o bokach $1$ , $1$ , $1$ , $d$ ). Maksimum wielkości (1) (przy ustalonym $d$ ) uzyskamy biorąc $\phi = 90^\circ$ , co odpowiada temu, że czworokąt jest wpisany w koło; to zaś jest w rozważanej sytuacji ( $a = b = c= 1$ ) równoważne temu, że $ABCD$ jest trapezem równoramiennym.

Dla trapezu równoramiennego o bokach $1$ , $1$ , $1$ , $d$ mamy $p = (3+d)/2$ ; jego pole wyznaczamy z wzoru (1), a następnie szacujemy korzystając z nierówności między średnimi:

$ \begin{split} &\mathrm{pole} (ABCD) = \sqrt{\left(\frac{1+d}{2} \right)^3\left(\frac{3-d}{2} \right)} = \frac{1}{4\sqrt{3}}\sqrt{(1+d)^3(9-3d)}=\\ &\frac{1}{4\sqrt{3}}\left(\sqrt[4]{(1+d)^3(9-3d)}\right)^2\leq \frac{1}{4\sqrt{3}} \left(\frac{3(1+d)+(9-3d)}{4}\right)^2=\frac{3\sqrt{3}}{4}. \end{split} $

W oszacowaniu tym równość zachodzi jedynie wtedy, gdy cztery czynniki iloczynu pod pierwiastkiem są sobie równe, czyli gdy $1+d = 9-3d$ , czyli dla $d = 2$ .

Stąd odpowiedź: w rozważanym zbiorze czworokątów największe pole ma trapez równoramienny o bokach $1$ , $1$ , $1$ , $2$ (wynik jednoznaczny z dokładnością do izometrii).

XXXVIII OM - I - Zadanie 7

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

Dane są liczby rzeczywiste nieujemne $a_1, a_2, \ldots , a_n$ , $x_1, x_2, \ldots , x_n$ .
Przyjmujemy $a = \sum_{i=1}^n a_i$ , $c = \sum_{i=1}^n a_ix_i$ . Dowieść, że

$ \sqrt{a^2+c^2} \leq \sum_{i=1}^n \sqrt{1+x_i^2} \leq a+c $

Rozwiązanie

Sposób I

Nierówność $\sqrt{1+x^2} \leq 1+x$ jest spełniona dla wszystkich $x > 0$ (sprawdzenie przez podniesienie do kwadratu, która to operacja, wykonywana w obrębie liczb nieujemnych, daje w wyniku nierówność równoważną wyjściowej). Gdy podstawimy $x = x_i$ , pomnożymy stronami przez $a_i$ ( $i = 1, \ldots , n$ ) i przesumujemy, dostaniemy prawą z dowodzonych nierówności. Pozostaje do dowodu lewa nierówność:

$ (1) \qquad \sqrt{a^2+c^2}\leq \sum_{i=1}^{n}a_i \sqrt{1+x^2_i}. $

Pisząc $c_i = a_ix_i$ przeprowadzamy nierówność (1) do postaci równoważnej:

$ (2) \qquad \sqrt{a^2+c^2} \leq \sum_{i=1}^n \sqrt{a_i+c_i}. $

Oznaczmy lewą i prawą stronę (2) przez $L$ i $P$ . Przekształcamy:

$ \begin{split} L^2 & = \left( \sum_i a_i \right)^2 + \left( \sum_i c_i \right)^2 = \\ & = \sum_i a_i^2 + 2 \sum_{i<j} a_ia_j + \sum_i c_i^2 + 2\sum_{i<j} c_ic_j,\\ P^2 & = \sum_i \left( a_i^2 + c_i^2 \right) + 2 \sum_{i<j} \sqrt{\left( a_i^2 + c_i^2 \right)\left( a_j^2 + c_j^2 \right)}, \end{split} $

skąd

$ P^2-L^2 = 2 \sum_{i<j} (\sqrt{(a_i^2+c_i^2)(a_j^2+c_j^2)}-a_ia_j-c_ic_j). $

Ponieważ $\sqrt{(s^2+t^2)(u^2+v^2)} \geq su+tv$ dla każdej czwórki liczb nieujemnych $s$ , $t$ , $u$ , $v$ (sprawdzenie przez podniesienie do kwadratu), zatem wszystkie składniki otrzymanej sumy są nieujemne. Wobec tego $L^2 \leq P^2$ , a stąd $L \leq P$ (jako, że $L, P \geq 0$ ).

Sposób II

Nierówność (2) orzeka po prostu, że suma długości $n$ wektorów (o współrzędnych $a_i$ , $c_i$ ) nie jest mniejsza od długości wektora będącego ich sumą. Jest to uogólniona nierówność trójkąta, wynikająca przez natychmiastową indukcję ze zwykłej nierówności trójkąta (przypadek $n = 2$ ).

XXXVIII OM - I - Zadanie 8

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

Ciąg $A_1, A_2, \ldots$ punktów płaszczyzny spełnia dla każdego $n > 1$ następujące warunki: $|A_{n+1}A_n| = n$ oraz kąt skierowany $A_{n+1}A_nA_1$ jest równy $90^{\circ}$ . Udowodnić, że każda półprosta o początku $A_1$ przecina nieskończenie wiele odcinków $A_nA_{n+1}$ ( $n = 1, 2, \ldots$ ).

Rozwiązanie

Przyjmijmy oznaczenia: $|A_1A_n| = r_n$ , $|\measuredangle A_nA_1A_{n+1}| = a_n$ dla $n = 2, 3, 4, \ldots$ , a ponadto $a = r_2^2—1$ (treść zadania nie precyzuje, jaka jest długość odcinka $A_1A_2$ , tak że $a$ może być dowolną liczbą większą od $-1$ ). Z zależności w trójkącie prostokątnym $A_1A_nA_{n+1}$ otrzymujemy

$ (1) \qquad \sin \alpha_n = \frac{n}{r_{n+1}} $

oraz

$ r^2_{n+1} = r_n^2 + n^2. $

Przyjmując w ostatnim wzorze kolejno $n = 2, 3,4, \ldots$ dostajemy:

$ r_3^2 = r_2^2+2^2, \ r_4^2 = r_3^2+3^2 = r_2^2+2^3+3^2 $

i ogólnie (indukcyjnie)

$ r_{n+1}^2 = r_2^2+2^2+3^2+\ldots + n^2= a+1^2+2^2+3^2+ \ldots + n^2, $

czyli

$ (2) \qquad r_{n+1}^2 = a + \frac{1}{6} n(n+1)(2n+1). $

Niech $P$ będzie dowolnym punktem płaszczyzny różnym od $A_1$ . Położenie punktu $P$ jest w pełni wyznaczone przez dwie wielkości: odległość od punktu $A_1$ oraz miarę kąta skierowanego $\measuredangle (\overrightarrow{A_1A_2}, \overrightarrow{A_1P})$ ; miarę tę będziemy nazywać współrzędną kątową punktu $P$ . Przyjmujemy nieograniczoną skalę kątów; dwie liczby różniące się o wielokrotność 360^{\circ} będziemy uważać za miary tego samego kąta skierowanego.

Odcinki $A_2A_3$ $A_3A_4$ itd. tworzą linię przedstawioną na rysunku 7. Jeśli $P$ jest punktem poruszającym się wzdłuż tej linii, w kierunku wyznaczonym przez numerację punktów $A_n$ , to jego odległość od $A_1$ wzrasta (bo przeciwprostokątna dowolnego trójkąta prostokątnego jest dłuższa od przyprostokątnej). Gdy $P$ jest jednym z punktów $A_n$ ( $n \geq 3$ ), to suma

$ \phi_n=a_2+\ldots+a_{n-1} $

jest jego współrzędną kątową (dokładniej: jedną z możliwych wartości tej współrzędnej). Gdy $P$ jest punktem odcinka $A_nA_{n+1}$ , wybierzmy tę wartość jego współrzędnej kątowej, która należy do przedziału $\langle \phi_n; \phi_{n+1} \rangle$ i oznaczmy ją przez $\phi(P)$ . Tak więc $\phi(A_n) = \phi_n$ . Przy ruchu punktu $P$ (wzdłuż rozpatrywanej linii) $\phi(P)$ wzrasta (bo przy przebieganiu odcinka $A_nA_{n+1}$ wektor prędkości jest prostopadły do wektora wodzącego w chwili początkowej). Aby dowieść tezy zadania, wystarczy pokazać, że

$ (3) \qquad \lim_{n \to \infty} \phi_n = \infty. $

Istotnie: przypuśćmy, że to udowodniliśmy i weźmy dowolną półprostą o początku $A_1$ . Niech $\theta$ będzie współrzędną kątową punktów tej półprostej, wziętą z przedziału $\langle 0^\circ; 360^\circ\rangle$ . Wówczas każda większa miara tego samego kąta (czyli każda z wartości $\theta +k \cdot 360^\circ$ , $k = 1,2,3,\ldots$ ) należy do pewnego przedziału $\langle \phi_n; \phi_{n+1} \rangle$ , jest więc współrzędną kątową pewnego punktu odcinka $A_nA_{n+1}$ . Przy tym różnym wartościom $k$ odpowiadają różne wartości $n$ (bo $\phi_{n+1}-\phi_n = a_n < 90^\circ$ ). Znaczy to, że rozważana półprostą przecina nieskończenie wiele odcinków $A_nA_{n+1}$ .

(Intuicyjny sens powyższych rozważań jest taki: rozpatrywana linia okrąża spiralnie punkt $A_1$ ; chcemy dowieść, że okrąża go nieskończenie wiele razy, i to właśnie wyraża relacja graniczna (3)).

Pozostaje więc udowodnić, że $\phi_n \to \infty$ .

Przypuśćmy, że (3) nie zachodzi. Ciąg ( $\phi_n$ ) jest rosnący. Istnieje więc skończona granica $\lim \phi_n=\psi$ .

Weźmy numer $m$ taki, że $\phi_m > \psi - 90^\circ$ (wróciliśmy do stopniowej miary kątów). Półprostą o początku $A_1$ , której punkty mają współrzędną kątową $\psi$ , przecina półprostą $A_mA_{m+1}^\to$ w punkcie, który oznaczymy przez $B$ (rysunek 8).

Wszystkie punkty $A_n$ o numerach $n \geq m$ leżą w obrębie kąta wypukłego $A_mA_1B$ . Pokażemy, że muszą one leżeć w trójkącie prostokątnym $A_mA_1B$ . Uzasadnienie jest indukcyjne. Oznaczmy ten trójkąt przez $\Delta$ . Oczywiście $A_m \in \Delta$ . Załóżmy, że $A_n$ jest (dla pewnego $n\geq m$ ) punktem trójkąta $\Delta$ . Punkt $A_{n+1}$ leży między półprostymi $A_1A_n^\to$ i $A_1B^\to$ . Gdyby leżał poza trójkątem $\Delta$ , kąt $A_1A_nA_{n+1}$ byłby rozwarty - wbrew warunkowi zadania, w myśl którego kąt ten jest prosty. Zatem $A_{n+1} \in \Delta$ . Na mocy zasady indukcji wszystkie punkty $A_n$ ( $n \geq m$ ) leżą w trójkącie $\Delta$ .

Ich odległości od $A_1$ muszą więc tworzyć ciąg ograniczony. Tymczasem z wzoru (2) widać, że $r_n\to \infty$ .

Otrzymana sprzeczność dowodzi słuszności warunku (3), więc i tezy zadania.

XXXVIII OM - I - Zadanie 9

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

W pięciokącie wypukłym $KLMNP$ prowadzimy przekątne, które przecinając się wyznaczają rozłączne odcinki: na przekątnej $KM$ w kolejności od $K$ do $M$ odcinki o długościach $a_1, b_1, c_1$ ; podobnie $a_2, b_2, c_2$ na przekątnej $LN$ , $a_3, b_3, c_3$ na przekątnej $MP$ , $a_4, b_4, c_4$ na przekątnej $NK$ , $a_5, b_5, c_5$ na przekątnej $PL$ . Dowieść, że

$ \prod_{i=1}^5 \frac{c_i}{b_i+c_i} = \prod_{i=1}^5 \frac{a_i}{a_i+b_i} $

Rozwiązanie

Zmieniamy oznaczenie wierzchołków $L$ , $M$ , $N$ , $P$ , $K$ odpowiednio na $A_1$ , $A_2$ , $A_3$ , $A_4$ , $A_5$ . Wprowadzamy dalsze oznaczenia (rysunek 9):

$ B_i = \textrm{punkt przecięcia przekątnych $A_{i-2}A_{i+1}$ i $A_{i-1}A_{i+2}$}, $

$ \phi_i = |\measuredangle A_{i-2}B_iB_{i+1} | = |\measuredangle A_{i-2}B_iB_{i-1} |. $

$ \psi_i=|\measuredangle A_{i-2}A_iA_{i+2} | $

dla $i = 1, 2, 3, 4, 5$ ; dodawanie $i\pm 1$ , $i\pm 2$ w indeksach należy wszędzie rozumieć modulo $5$ .

Wówczas

$ a_i = |A_{i-1}B_{i+2}|, \quad b_i = |B_{i+2}+B_{i-2}|, \quad c_i = |B_{i-2}A_{i+1}|. $

Ze wzoru sinusów zastosowanego do trójkątów $B_{i-2}A_iB_{i+2}$ otrzymujemy (rysunek 10):

$ (1) \qquad \frac{a_{i+1}}{\sin \phi_{i+2}} = \frac{c_{i-1}}{\sin \phi_{i-2}} \quad \textrm{dla } i= 1, 2, 3, 4, 5. $

Z tego samego wzoru zastosowanego do trójkątów $A_{i-1}B_iA_{i+1}$ mamy

$ (2) \qquad \frac{b_{i-1}+c_{i-2}}{\sin \psi_{i+1}} = \frac{a_{i+2}+b_{i+2}}{\sin \psi_{i-1}} \quad \textrm{dla } i= 1, 2, 3, 4, 5. $

Mnożąc stronami pięć równości (1) oraz pięć równości (2) dostajemy

$ \prod_{i=1}^5 a_i = \prod_{i=1}^5 c_i \quad \textrm{oraz} \quad \prod_{i=1}^5 (b_i+c_i)=\prod_{i=1}^5 (a_i+b_i) $

skąd natychmiast wynika teza zadania.

XXXVIII OM - I - Zadanie 10

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

Niech $n = 4^k \cdot 5^m$ ( $k$ , $m$ — liczby naturalne). Udowodnić, że każda liczba naturalna mniejsza od $n$ jest dzielnikiem liczby $n$ lub sumą różnych dzielników liczby $n$ .

Rozwiązanie

Uwaga. Przez liczbę naturalną rozumiemy w tym zadaniu liczbę całkowitą dodatnią. Dla $k = 0$ teza jest - jak łatwo zauważyć - nieprawdziwa.

Niech $k \geq 1$ i $m \geq 1$ będą ustalone i niech $s < 4^k5^m$ będzie liczbą naturalną. Dzielimy $s$ przez $5^m$ otrzymując iloraz $a$ i resztę $r$ :

$ s = 5^mq+r; \quad 0 \leq q < 4^k \quad 0 \leq r < 5^m. $

Zapiszmy liczby $q$ i $r$ w układach pozycyjnych o podstawach $2$ i $5$ (odpowiednio) :

$ q=\sum_{i=0}^{2k-1} \alpha_i2^i,\ \alpha_i\in \{ 0,1\} \quad q=\sum_{i=0}^{m-1} xb_i2^i,\ \beta_i\in \{ 0, 1, 2, 3, 4\} \quad $

i rozpatrzmy następujące zbiory indeksów:

$ I_c = \{i: 0 \leq i < 2k-1, \alpha_i = c\};\quad c = 0, 1; $

$ J_c = \{j: 0 < j < m-1, \beta_i = c\}; \quad c = 0, 1, 2, 3, 4. $

Wówczas

$ \begin{split} s&=5^m \sum_{i\in I_1}2^i + \sum_{j\in J_1}5^j +\sum_{j\in J_2}2 \cdot 5^j+\sum_{j\in J_3}3 \cdot 5^j+\sum_{j\in J_4}4 \cdot 5^j=\\ &= \sum_{i\in I_1}5^m2^i + \sum_{j\in J_1}5^j +\sum_{j\in J_2}2 \cdot 5^j+\sum_{j\in J_3} 5^j+\sum_{j\in J_3}2 \cdot 5^j+\sum_{j\in J_4}4 \cdot 5^j \end{split} $

Wszystkie składniki otrzymanej sumy są dzielnikami liczby $4^k5^m$ , i to różnymi, bo zbiory $J_c$ są parami rozłączne. Teza jest więc udowodniona.

XXXVIII OM - I - Zadanie 11

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

Udowodnić, że kulę można oświetlić czterema punktowymi źródłami światła umieszczonymi poza nią, a nie można oświetlić trzema.

Rozwiązanie

Rozumowanie będzie oparte na spostrzeżeniu, że mniejszą z dwóch czasz, na które dzieli sferę dowolna płaszczyzna przecinająca wnętrze kuli, ale nie przechodząca przez jej środek, można oświetlić pojedynczym punktowym źródłem światła umieszczonym poza kulą; nie może natomiast takie źródło oświetlić całej półsfery.

Wpisujemy w kulę czworościan tak, by środek kuli znalazł się w jego wnętrzu. Niech $S_1$ , $S_2$ , $S_3$ , $S_4$ będą ścianami tego czworościanu. Płaszczyzna ściany $S_i$ dzieli sferę na dwie czasze; mniejszą z nich oznaczmy przez $C_i$ ( $i = 1, 2, 3, 4$ ). Zbiory $C_i$ pokrywają całą powierzchnię kuli; jeśli bowiem $P$ jest dowolnym punktem na powierzchni kuli, to odcinek łączący $P$ ze środkiem kuli przecina którąś ze ścian $S_i$ i wówczas $P$ należy do odpowiedniej czaszy $C_i$ . Jak zauważyliśmy, każdą z czasz $C_i$ można oświetlić punktowym źródłem światła. Zatem cztery źródła wystarczą do oświetlenia całej kuli.

Aby pokazać, że trzy takie źródła nie wystarczą, zauważmy, że każdy łuk koła wielkiego zawarty w obszarze oświetlonym przez pojedyncze źródło światła jest krótszy od półokręgu. Wynika stąd, że do oświetlenia każdego koła wielkiego konieczne są co najmniej trzy punktowe źródła światła poza kulą. Przypuśćmy teraz, że kula jest oświetlona przez trzy takie źródła $A$ , $B$ , $C$ . Istnieje koło wielkie leżące poza zasięgiem światła z punktu $A$ . Całe to koło jest więc oświetlone z punktów $B$ i $C$ , wbrew poprzedniej konkluzji. Dowodzi to drugiej części tezy zadania.

XXXVIII OM - I - Zadanie 12

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

W turnieju uczestniczy $n$ graczy. Każdy z nich rozgrywa z każdym dokładnie jeden mecz. W każdym meczu gracz zdobywa 0, 1 lub 2 punkty w zależności od tego, czy przegra, zremisuje lub wygra. Ciąg $(a_1, a_2, \ldots , a_n)$ nazywamy wynikiem turnieju, jeśli możliwy jest przebieg rozgrywek, przy którym $a_i$ jest sumą punktów zdobytych przez $i$ -tego gracza ( $i = 1, 2, \ldots, n$ ). Wykazać, że ciąg liczb całkowitych nieujemnych $(b_1, b_2, \ldots, b_n)$ jest wynikiem turnieju wtedy i tylko wtedy, gdy $\sum_{i=1}^n b_i = n(n—l)$ oraz dla każdego niepustego podzbioru $A$ zbioru liczb $\{1, 2, \ldots, n\}$ spełniona jest nierówność:

$ \sum_{i\in A} b_i \geq k_A(k_A-1), $

gdzie $k_A$ jest liczbą elementów zbioru $A$ .

Rozwiązanie

Ciąg liczb całkowitych $(b_1, \ldots ,b_n$ ) spełniający podane warunki:

$ (1) \qquad \sum_{i=1}^n b_i =n(n-1), $

$ (2) \qquad \sum_{i\in A} b_i \geq k_A(k_A-1) \quad \textrm{dla } A\subset \{1,\ldots, n \},\ A\neq \emptyset. $

będziemy nazywać ciągiem dopuszczalnym (długości $n$ ); zauważmy, że warunek (2) pociąga za sobą nieujemność liczb $b_i$ (wystarczy wziąć pod uwagę jednoelementowe zbiory $A$ ).

Mamy dowieść, że ciąg jest wynikiem turnieju wtedy i tylko wtedy, gdy jest dopuszczalny. Implikacja ,,tylko wtedy'' jest oczywista: jeśli ciąg $(b_1, \ldots ,b_n)$ jest wynikiem turnieju, to spełnia podane warunki; warunek (1) wynika z ... warunek (2) zaś z tego, że w samych tylko meczach między zawodnikami o numerach $i \in A$ rozdzielono $2 \cdot k_A(k_A -1)/2$ punktów. Przedstawimy kilka dowodów implikacji przeciwnej:

Twierdzenie. Każdy ciąg dopuszczalny jest wynikiem turnieju.

W dowodach będziemy się czasem posługiwali ,,tabelą wyników''. Rozpatrujemy turniej z udziałem $n$ graczy. Dla $i,j \in \{1, \ldots, n\}$ , $i \neq j$ , niech $r_{ij}$ oznacza liczbę punktów zdobytych przez gracza $i$ w meczu z graczem $j$ .

Tablicę (macierz) kwadratową (bez przekątnej)

$ (3) \qquad \begin{array}{|c|c|c|c|} \hline \vphantom{\bigg(} \times &r_{12}&\ldots&r_{1n}\\ \hline \vphantom{\bigg(} r_{21}&\times &\ldots&r_{2n}\\ \hline \vphantom{\bigg(}\vdots&\vdots&\ddots&\vdots\\ \hline \vphantom{\bigg(} r_{n1}&r_{n2}&\ldots&\times \\ \hline \end{array} \qquad \left( \begin{array}{l} r_{ij} \in \{0, 1, 2\}\\ i,j \in \{1, \ldots, n\} i \neq j\\ r_{ij}+r_{ji}=2 \end{array} \right) $

będziemy nazywali tabelą wyników turnieju. Ciąg $(a_1, \ldots, a_n)$ jest więc wynikiem turnieju wtedy i tylko wtedy, gdy istnieje tabela (3) (o wyrazach $r_{ij}$ ) spełniających podane warunki) taka, że $a_i$ jest sumą elementów z $i$ --tego wiersza:

$ (4) \qquad a_i = \sum_{\substack{j=1\\ j \neq i}}^n r_{ij} \quad \textrm{dla } i = 1, \ldots, n. $

Przystępujemy do dowodu sformułowanego wyżej twierdzenia.

Niech będzie dany dowolny ciąg dopuszczalny $(b_1, \ldots, b_n)$ (ustalonej długości $n$ ). Spośród wszystkich ciągów $(a_1, \ldots ,a_n)$ będących wynikami turnieju wybierzmy taki, dla którego wartość sumy

$ (19) \qquad \sum_{i=1}^n |a_i-b_i| $

jest możliwie najmniejsza. Należy pokazać, że ta minimalna wartość wynosi $0$ .

Przypuśćmy więc, że tak nie jest, czyli że wybrany ciąg $(a_1, \ldots, a_n)$ nie jest identyczny z ciągiem $(b_1, \ldots, b_n)$ . Ponieważ $a_1+ \ldots +a_n = b_1+ \ldots + +b_n$ , znajdzie się numer $p$ taki, że

$ (20) \qquad a_p < b_p. $

Rozważmy tabelę wyników (3), o wyrazach $r_ij$ , realizującą wynik $(a_1, \ldots, a_n)$ ; zachodzi więc wzór (4). Określimy teraz pewien zbiór numerów $A \subset \{1, \ldots, n\}$ . Do zbioru $A$ zaliczymy liczbę $p$ oraz wszystkie te numery $i \neq p$ , dla których istnieje liczba naturalna $m$ oraz ciąg różnych numerów $(i_0, \ldots, i_m)$ taki, że

$ i_0=p,\quad i_m=i $

$ r_{i_{k-1}i_k} \geq 1 \quad \textrm{dla } k=1, \ldots, m. $

Zauważmy, że jeśli $i\in A$ oraz jest numerem takim, że $r_{ij} \geq 1$ , to $j\in A$ . Zatem

$ r_{ij} = 0\quad \textrm{dla } i\in A,\ j \notin A, $

więc zgodnie z wzorem (4) mamy

$ (21) \qquad a_i= \sum_{j\in A \setminus \{i\}} r_{ij} \quad \textrm{dla } i \in A. $

W rozpatrywanym turnieju ograniczmy na chwilę uwagę tylko do meczów rozegranych między zawodnikami o numerach należących do $A$ . Tabela wyników tego mini-turnieju powstaje z tabeli (3) przez wykreślenie wierszy i kolumn o numerach spoza $A$ . Suma elementów wiersza odpowiadającego w tak zredukowanej tabeli zawodnikowi o numerze i równa się nadal $a_i$ , na mocy równości (21). Zatem suma wszystkich elementów tej tabeli wynosi $\sum_{i\in A} a_i$ . Jednocześnie suma ta równa się, $k_A(k_A-1)$ , bo tyle punktów rozdzielono w rozważanym mini-turnieju. Tak więc

$ \sum_{i\in A}a_i = k_A(k_A-1). $

Ciąg $(b_1,\ldots , b_n)$ , jako dopuszczalny, spełnia warunek (2). Wynika stąd, że

$ \sum_{i\in A}b_i \geq \sum_{i\in A}a_i. $

a skoro $a_p > b_p$ , musi zachodzić dla pewnego $q \in A$ nierówność

$ (22) \qquad a_q < b_q. $

Zgodnie z definicją zbioru $A$ istnieje ciąg numerów $(i_0, \quad , i_m)$ taki, że

$ i_0=p, \quad i_m=q, $

$ r_{i_{k-1}i_k} \geq 1 \quad \textrm{dla } k=1, \ldots, m. $

Ostatni warunek oznacza po prostu, że zawodnik o numerze $i_{k-1}$ nie przegrał w meczu z zawodnikiem o numerze $i_k$ ( $k = 1, \ldots , m$ ).

Wracamy teraz do pełnej tabeli (3) i reprezentowanego przez nią przebiegu rozgrywek, i dokonujemy w tym przebiegu zmiany następującej: dla każdego $k \in \{1, \ldots, m\}$ podwyższamy wynik meczu pomiędzy $i_{k-1}$ a $i_k$ o $1$ punkt na korzyść $i_k$ . Wyników pozostałych meczów nie zmieniamy. Oznaczając przez $(a'_1,\ldots, a'_n)$ wynik turnieju przy nowym przebiegu rozgrywek mamy

$ (23) \qquad \begin{split} &a'_p=a_p-1, \quad a'_q=a_q+1\\ &a'_i=a_i \quad \textrm{dla } i \neq p,q. \end{split} $

Istotnie; patrząc na ciąg numerów $p = i_0, i_1, i_2, \ldots, i_{m-1},i_m=q$ widzimy, że zawodnik o numerze $i_k$ ( $1 \leq k \leq m-1$ ) jest uczestnikiem dwóch meczów o zmienianych wynikach, przy czym doświadcza jednej zmiany na swoją korzyść, a jednej na niekorzyść; niezrównoważone zostają tylko zmiany u numerów skrajnych: $p$ i $q$ ; dla numerów, które w ciągu $(i_0, \ldots, i_m)$ nie występują, w ogóle nic się nie zmienia. Stąd słuszność związków (23).

Uwzględniając nierówności (20) i (22) otrzymujemy z tych związków zależności

$ \begin{split} \sum^n_{i=1} |a'_i-b_i|&=\\ &=|a'_p-b_p|+a'_q-b_q|+\sum_{i\neq p,q}|a'_i-b_i|=\\ &=|a_p-b_p-1|+|a_q-b_q+1|+\sum_{i\neq p,q}|a_i-b_i|<\\ &<|a_p-b_p|+a_q-b_q|+\sum_{i\neq p,q}|a_i-b_i|=\\ &=\sum^n_{i=1} |a_i-b_i| \end{split} $

- wbrew minimalności sumy (19).
Dowodzi to niesłuszności przypuszczenia, że minimalna wartość tej sumy jest dodatnia. Musi być ona zerem, a zatem ciąg $(b_1, \ldots ,b_n)$ jest jednym z możliwych wyników turnieju.

Uwaga 2. Śledząc podane rozwiązanie, wygodnie jest wyobrazić sobie $n$ -kąt z poprowadzonymi wszystkimi przekątnymi (tzw. graf pełny); jego wierzchołki reprezentują graczy, a boki i przekątne (krawędzie grafu) — mecze między zawodnikami. Gdy dany jest przebieg turnieju, opatrujemy te odcinki strzałkami (powstaje ,,graf skierowany''): jeśli $i$ , $j$ są numerami dwóch zawodników, a mecz między nimi zakończył się zwycięstwem zawodnika $i$ , prowadzimy strzałkę od wierzchołka $i$ (czyli wierzchołka reprezentującego zawodnika $i$ ) do wierzchołka $j$ : $i\rightarrow j$ ; remis oznaczamy strzałką dwustronną: $i \leftrightarrow j$ A zatem:

$ r_{ij}=\left\{ \begin{split} &2 \Leftrightarrow \textrm{mamy strzałkę } i\rightarrow j\\ &1 \Leftrightarrow \textrm{mamy strzałkę } i\leftrightarrow j\\ &0 \Leftrightarrow \textrm{mamy strzałkę } i\leftarrow j \end{split} \right. $

Określony w rozwiązaniu zbiór $A$ interpretuje się jako zbiór tych wierzchołków $i$ , do których można dojść z wierzchołka $p$ poruszając się wzdłuż krawędzi grafu zawsze w kierunku zgodnym z kierunkiem strzałek (po strzałkach dwustronnych można iść w obie strony.) Przeprowadzona następnie modyfikacja przebiegu turnieju polega na tym, że w ciągu krawędzi:
$p \frac{\hphantom{\to}}{\hphantom{\to}} i_1 \frac{\hphantom{\to}}{\hphantom{\to}} i_2 \frac{\hphantom{\to}}{\hphantom{\to}} \ldots \frac{\hphantom{\to}}{\hphantom{\to}}i_{m-1} \frac{\hphantom{\to}}{\hphantom{\to}} q$ każdą strzałkę $\rightarrow$ (skierowaną zgodnie z kierunkiem drogi od $p$ do $q$ ) zastępujemy strzałką $\leftrightarrow$ , a każdą strzałkę $\leftrightarrow$ zastępujemy strzałką $\leftarrow$ (skierowaną przeciwnie).