XXXVIII OM

XXXVIII Olimpiada Matematyczna

Opracowanie rozwiązań: Marcin E. Kuczma

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).

XXXVIII OM - II etap

II etap XXXVIII Olimpiady Matematycznej

XXXVIII OM - II - Zadanie 1

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

Z urny zawierającej jedną kulę oznaczoną numerem 1, dwie kule oznaczone numerem 2, ..., $n$ kul oznaczonych numerem $n$ wyciągamy bez zwracania dwie kule. Przyjmujemy, że wyciągnięcie każdej kuli z urny jest jednakowo prawdopodobne. Obliczyć prawdopodobieństwo tego, że obie wyciągnięte kule mają ten sam numer.

Rozwiązanie

Aby treść zadania miała sens, trzeba przyjąć, że $n \geq 2$ .

Razem w urnie jest $N = 1+2+ ... +n = n(n+1)/2$ kul. Dwie kule można wybrać spośród $N$ kul na $q$ sposobów, gdzie

$ (1) \qquad \begin{split} q= \binom{N}{2}&=\frac{1}{2}N(N-1)=\frac{1}{2}\cdot \frac{1}{2}\cdot \frac{n(n+1)}{2}\cdot \frac{n^2+n-2}{2}=\\ &=\frac{1}{8}n(n+1)(n-1)(n+2). \end{split} $

Ustalmy $k \in \{2, \ldots,n\}$ . Spośród $k$ kul oznaczonych numerem $k$ możemy wybrać parę kul na $\binom{k}{2}$ sposobów. Łączna liczba możliwości wyboru pary kul o jednakowym numerze (spośród wszystkich $N$ kul) wynosi

$ (2) \qquad \sum{k=2}{n} \binom{k}{2}=\binom{n+1}{3}=\frac{1}{6}(n+1)n(n-1). $

A oto indukcyjny dowód wzoru (2): wzór jest słuszny dla $n = 2$ ; zakładając jego prawdziwość dla pewnego $n \geq 2$ mamy dla $n+1$

$ \sum_{k=2}^{n+1} \binom{k}{2} = \sum_{k=2}^{n} \binom{k}{2}+\binom{n+1}{2}=\binom{n+1}{3}+\binom{n+1}{2}=\binom{n+2}{3}; $

wzór (2) jest więc udowodniony.
Szukane prawdopodobieństwo jest ilorazem znalezionej liczby (wzór(2)) przez $q$ (wzór (1)), czyli równa się $\dfrac{4}{3(n+2)}$ .

XXXVIII OM - II - Zadanie 2

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

Udowodnić, że suma kątów płaskich przy każdym z wierzchołków danego czworościanu wynosi $180^{\circ}$ wtedy i tylko wtedy, gdy wszystkie jego ściany są przystające.

Rozwiązanie

Rozcinamy powierzchnię rozważanego czworościanu $ABCD$ wzdłuż krawędzi $AD$ , $BD$ , $CD$ i kładziemy ściany $BCD$ , $CAD$ , $ABD$ na płaszczyznę trójkąta $ABC$ . Otrzymujemy siatkę tego czworościanu, czyli sześciokąt $AMBKCL$ , w którym trójkąty $BCK$ , $CAL$ , $ABM$ są odpowiednio przystające do wymienionych trzech ścian (rysunek 11).

Załóżmy, że suma miar kątów płaskich przy każdym wierzchołku czworościanu wynosi $180^\circ$ . Wtedy w sześciokącie $AMBKCL$ kąty przy wierzchołkach $A$ , $B$ , $C$ są półpełne i sześciokąt staje się trójkątem $KLM$ . Ponieważ $|AL| = |AD| = |AM|$ , punkt $A$ jest środkiem boku $LM$ ; podobnie punkty $B$ i $C$ są środkami boków $MK$ i $KL$ trójkąta $KLM$ . Zatem obwód trójkąta $ABC$ dzieli trójkąt $KLM$ na cztery trójkąty przystające, a to znaczy, że ściany czworościanu $ABCD$ są trójkątami przystającymi.

Przechodzimy do dowodu implikacji przeciwnej. Załóżmy, że ściany czworościanu są przystające. Pokażemy, że wówczas każde dwie skośne krawędzie czworościanu mają równą długość. Przypuśćmy bowiem, że na przykład $|AB| = x$ , $|CD| = y$ , $x \neq y$ . Ściana $ABD$ musi mieć co najmniej jeden bok długości $y$ , a więc z wierzchołka $D$ wychodzą co najmniej dwie krawędzie długości $y$ (bo jedną jest już krawędź $CD$ ). Te dwie krawędzie obramowują ścianę, której dwa boki mają długość $y$ , a więc trzeci bok musi mieć długość $x$ . Jest to jeden z odcinków $BC$ , $CA$ . Tak więc ściana $ABC$ ma dwa boki długości $x$ . Skoro pewna ściana ma dwa boki długości $y$ , inna ma dwa boki długości $x$ , a wszystkie są przystające, otrzymujemy wniosek, że $x = y$ , wbrew przypuszczeniu.

Zatem $|AD| = |BC|$ , $|BD| = |CA|$ , $|CD| = |AB|$ , a stąd

$ \triangle ABC \equiv \triangle DCB \equiv \triangle CDA \equiv \triangle BAD; $

zapis $\triangle PQR \equiv \triangle XYZ$ oznacza tu, że trójkąt $PQR$ przystaje do trójkąta $XYZ$ , przy czym wierzchołkowi $P$ odpowiada w tym przystawaniu wierzchołek $X$ , wierzchołkowi $Q$ - wierzchołek $Y$ , a wierzchołkowi $R$ - wierzchołek $Z$ . Wobec tego

$ |\measuredangle BDC| + |\measuredangle CDA| + |\measuredangle ADB| = |\measuredangle CAB|+|\measuredangle ABC| + |\measuredangle BCA| = 180^\circ. $

Pokazaliśmy, że suma miar kątów płaskich przy wierzchołku $D$ wynosi $180^\circ$ . Z symetrii założeń wynika analogiczne stwierdzenie dla kątów płaskich przy każdym z pozostałych wierzchołków.

XXXVIII OM - II - Zadanie 3

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

Na szachownicy o wymiarach 1000 na 1000 i polach pokolorowanych w zwykły sposób na biało i czarno jest dany zbiór A złożony z 1000 pól. Każde dwa pola zbioru A można połączyć ciągiem pól zbioru A tak, by kolejne pola miały wspólny bok. Dowieść, że w zbiorze A jest co najmniej 250 pól białych.

Rozwiązanie

Skończony ciąg pól szachownicy (o dowolnych wymiarach) mający tę i własność, że każde dwa kolejne pola mają wspólny bok, będziemy nazywali drogą, a liczbę pól w tym ciągu zmniejszoną o $1$ - długością drogi (pojedyncze pole stanowi drogę długości $0$ ).

Niepusty zbiór $A$ złożony z dowolnej liczby pól szachownicy i taki, że każde jego dwa pola łączy droga w nim zawarta, będziemy nazywali spójnym.

Udowodnimy przez indukcję względem $n$ , że liczba białych pól w dowolnym spójnym zbiorze $A$ złożonym z $n$ pól jest nie mniejsza niż $(n-1)/4$ . Dla $n = 1000$ wyniknie stąd teza zadania.

Gdy $n = 1$ , podana wartość wynosi $0$ , więc nie ma czego dowodzić.

Ustalmy liczbę naturalną $n > 1$ i załóżmy, że każdy $m$ -polowy zbiór spójny, gdzie $m$ jest dowolną liczbą mniejszą od n, ma co najmniej $(m-1)/4$ pól białych. Niech będzie dany zbiór spójny $A$ złożony z $n$ pól i niech $b$ będzie liczbą białych pól zbioru $A$ . Mamy dowieść, że

$ (1) \qquad 4b \geq n-1. $

Jeśli to wykażemy, dowód naszego stwierdzenia będzie zakończony, na mocy zasady indukcji.

Nierówność (1) udowodnimy dwoma sposobami.

Wybierzmy ze zbioru $A$ jedno pole białe (jego istnienie wynika z tego, że $n > 1$ ),
nazwijmy je $P$ i usuńmy je ze zbioru $A$ . Otrzymany zbiór $n-1$ pól oznaczmy przez $A'$ . Jeśli $Q$ jest dowolnie ustalonym polem w $A'$ , to zbiór wszystkich pól zbioru $A'$ , które dadzą się połączyć z $Q$ drogą zawartą w $A'$ , jest spójny. Ponieważ każde pole zbioru $A$ łączy z polem $P$ droga zawarta w $A$ , która musi przechodzić przez jedno z czterech pól sąsiadujących z $P$ , przeto każde pole zbioru $A'$ łączy z jednym z tych czterech pól droga zawarta w $A'$ .

Wynika stąd, że $A'$ jest sumą co najwyżej czterech niepustych rozłącznych zbiorów spójnych. Nazwijmy je $A_1,\ldots, A_k$ ( $1 \leq k \leq 4$ ) i przyjmijmy, że zbiór $A_j$ składa się z $m_j$ pól, w tym $b_j$ białych ( $j = 1, \ldots,k$ ).

Oczywiście

$ \sum_{j=1}^km_j=n-1, \quad \sum_{j=1}^k b_j=b-1 $

(bo pole P jest białe). Z założenia indukcyjnego

$ 4b_j \geq m_j -1 \quad \textrm{dla } q= 1, \ldots, k. $

Wystarczy dodać stronami te nierówności, by otrzymać

$ 4(b-1) \geq n-1-k. $

Dowodzona nierówność (1) natychmiast stąd wynika, bo $k \leq 4$ .

XXXVIII OM - II - Zadanie 4

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

Wyznaczyć wszystkie pary liczb rzeczywistych $a, b$ , dla których wielomiany $x^4 + 2ax^2 + 4bx + a^2$ i $x^3 + ax - b$ mają dwa różne wspólne pierwiastki rzeczywiste.

Rozwiązanie

Oznaczmy rozważane wielomiany przez $P$ i $Q$ :

$ (1) \qquad P(x) = x^4+2ax^2+4bx+a^2, \quad Q(x) = x^3+ax+b. $

Załóżmy, że wielomiany $P$ i $Q$ mają wspólne pierwiastki rzeczywiste $x_1$ , $x_2$ ( $x_1\neq x_2$ ). Liczby $x_1$ $x_2$ są wówczas także pierwiastkami wielomianu

$ T(x) = P(x)-xQ(x) = ax^2+3bx+a^2. $

Stąd $a \neq 0$ i $\Delta = 9b^2--4a^3 > 0$ .
Zgodnie z wzorami Viete'a

$ x_1+x_2=-\frac{3b}{a},\quad x_1x_2=a. $

Ponieważ $Q(x_1) = Q(x_2) = 0$ , a $x_1 \neq x_2$ , zachodzą równości

$ \begin{split} 0&=\frac{Q(x_1)-Q(x_2)}{x_1-x_2}=\frac{x_1^3-x_2^3+ax_1-ax_2}{x_1-x_2}=\\ &=x_1^2+x_1x_2+x_2^2+a=(x_1+x_2)^2-x_1x_2+a=\left(-\frac{3b}{a} \right)^2 \end{split} $

Zatem $b = 0$ i $0 < \Delta = -4a^3$ , czyli $a < 0$ .

Także i odwrotnie: jeśli spełnione są warunki $a < 0 = b$ , to wielomiany $P$ i $Q$ przybierają postać

$ P(x) = x^4+2ax^2+a^2 = (x^2+a)^2, \quad Q(x) = a^3+ax = x(x^2+a) $

i liczby $\sqrt{-a}$ , $-\sqrt{-a}$ są ich wspólnymi pierwiastkami.

Rozwiązaniem zadania są więc wszystkie pary postaci $(a, 0)$ , gdzie $a < 0$ .

XXXVIII OM - II - Zadanie 5

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

Wyznaczyć wszystkie liczby pierwsze $p$ i liczby naturalne $x, y$ , dla których $p^x—y^3 = 1$ .

Rozwiązanie

Przypuśćmy, że liczby $p$ , $x$ , $y$ spełniają podane warunki. Wtedy

$ (1) \qquad p^x =y^3+1 = (y+1)(y^2-y+1). $

Rozpatrzmy dwa przypadki:

1. $y = 1$ . Wtedy (1) sprowadza się do równania $p^x = 2$ , skąd $p = 2$ , $x = 1$ .

2. $y > 1$ . Wtedy oba czynniki iloczynu po prawej stronie (1) są liczbami większymi od $1$ i jako dzielniki potęgi liczby pierwszej $p$ muszą same być dodatnimi potęgami tejże liczby:

$ (2) \qquad y + 1 = p^k,\quad y^2-y+1 = p^l;\quad k, l > 0, k+l = x. $

Zauważmy teraz, że

$ (3) \qquad p^l=y^2-y+1 = (y+1)(y-2)+3 = p^k(p^k-3)+3. $

Zatem $3$ jest liczbą podzielną przez $p$ , co oznacza, że $p = 3$ . Równanie (3) przybiera postać

$ 3^l = 3^k(3^k-3)+3, $

czyli

$ 3^{l-1} = 3^{2k-1}-3^k+1 $

Prawa strona ostatniego równania nie dzieli się przez $3$ . Stąd $l - 1 = 0$ oraz $2k-1=k$ , czyli $k = l = 1$ i na mocy zależności (2) $x = 2$ , $y = 2$ .

Reasumując: rozwiązaniami $(p, x, y)$ danego równania mogą być tylko trojki $(2, 1, 1)$ oraz $(3, 2, 2)$ . Sprawdzenie, że istotnie są to rozwiązania, jest natychmiastowe.

XXXVIII OM - II - Zadanie 6

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

Dowolnemu czworokątowi $ABCD$ przyporządkowujemy środki okręgów opisanych na trójkątach $BCD$ , $CDA$ , $DAB$ , $ABC$ . Udowodnić, że jeżeli wierzchołki czworokąta wypukłego $Q$ nie leżą na okręgu, to

a) cztery punkty przyporządkowane w powyższy sposób czworokątowi Q są wierzchołkami czworokąta wypukłego. Oznaczmy ten czworokąt przez $t(Q)$ ,

b) wierzchołki czworokąta $t(Q)$ nie leżą na okręgu,

c) czworokąty $Q$ i $t(t(Q)$ są podobne.

Rozwiązanie

a) Oznaczmy wierzchołki czworokąta $Q$ kolejno przez $A$ , $B$ , $C$ , $D$ , a środki okręgów opisanych na trójkątach $BCD$ , $CDA$ , $DAB$ , $ABC$ odpowiednio przez $A'$ , $B'$ , $C'$ , $D'$ . Czworokąt $Q$ z założenia nie jest wpisany w okrąg; zatem $|\measuredangle A| + |\measuredangle B| \neq |\measuredangle C|+ |\measuredangle D|$ . Bez szkody dla ogólności możemy przyjąć, że

$ (1) \qquad |\measuredangle A| + |\measuredangle B| <180^{\circ}< |\measuredangle C|+ |\measuredangle D| $

(jeśli zachodzą nierówności przeciwne, możemy dokonać cyklicznego przesunięcia oznaczeń).

Z nierówności (1) wynika, że punkt $D$ leży wewnątrz okręgu co opisanego na trójkącie $ABC$ , natomiast punkt $C$ leży na zewnątrz okręgu a opisanego na trójkącie $DAB$ (rysunek 12). Przedłużamy odcinek $BD$ do przecięcia z okręgiem $\omega$ w punkcie, który oznaczamy przez $D_1$ Punkt przecięcia odcinka $AC$ z okręgiem $\sigma$ oznaczmy przez $C_1$ Niech $\lambda$ będzie symetralną odcinka $BD$ , a $\chi$ - symetralną odcinka $AC$ .

Środek okręgu co, czyli punkt $D'$ , leży na symetralnej odcinka $BD_1$ , a więc po tej samej stronie prostej $\lambda$ , co punkt $D$ .

Środek okręgu $\sigma$ , czyli punkt $C$ , leży na symetralnej odcinka $AC_1$ a więc po przeciwnej stronie prostej $\chi$ , niż punkt $C$ .

Zamieniając role punktów $A$ i $C$ oraz $B$ i $D$ wnosimy z symetrii założeń, że:

punkt $B'$ leży po tej samej stronie prostej $\lambda$ , co punkt $B$ ;
punkt $A'$ leży po przeciwnej stronie prostej $\chi$ , niż punkt $A$ .

Środek $A'$ okręgu opisanego na trójkącie $BCD$ leży na symetralnej boku $BD$ : $A' \in \lambda$ ; podobnie $C' \in \lambda$ , $B' \in \chi$ , $D' \in \chi$ . W takim razie punkty $B'$ i $D'$ leżą po różnych stronach prostej $A'C'$ , a punkty $A'$ i $C'$ leżą po różnych stronach prostej $B'D'$ . Stąd wynika, że punkty $A'$ , $B'$ , $C'$ , $D'$ są kolejnymi wierzchołkami czworokąta wypukłego. Jest to właśnie czworokąt $\tau(Q)$ .

b) Wykażemy, że miary kątów wewnętrznych czworokątów $\tau(Q)$ i $Q$ są związane zależnościami

$ (2) \qquad \begin{array}{ll} |\measuredangle A'|=180^\circ - |\measuredangle C|,& |\measuredangle B'|=180^\circ - |\measuredangle D|,\\ |\measuredangle C'|=180^\circ - |\measuredangle A|,& |\measuredangle D'|=180^\circ - |\measuredangle B| \end{array} $

Dowód przeprowadzimy dla jednej tylko z tych równości, na przykład ostatniej. Aby można stąd wnosić o zachodzeniu pozostałych trzech równości (2), porzucamy założenie, że kąty czworokąta $Q$ spełniają warunek (1).

Weźmy więc pod uwagę trójkąt $ABC$ i punkt $D'$ , środek okręgu opisanego. Oznaczmy środki boków $AB$ i $BC$ odpowiednio przez $M$ i $N$ . Jak poprzednio, $\chi$ oznacza symetralną odcinka $AC$ .

Rozpatrzmy trzy przypadki:

1. Kąty $CAB$ i $BCA$ są ostre (rysunek 13). Rzut punktu $B$ na prostą $AC$ trafia do wnętrza odcinka $AC$ , a więc rzuty punktów $M$ i $N$ trafiają do różnych połówek tego odcinka. Znaczy to, że punkty $M$ i $N$ leżą po przeciwnych stronach prostej a punkty $D'$ , $M$ , $B$ , $N$ są kolejnymi wierzchołkami czworokąta wypukłego o kątach prostych przy wierzchołkach $M$ i $N$ . Zachodzi więc równość

$ |\measuredangle MBN| + |\measuredangle MD'N| = 180^circ, $

czyli

$ (3) \qquad |\measuredangle ABC| + |\measuredangle MD'N| = 180^\circ. $

Punkt $A'$ leży na symetralnej boku $BC$ , czyli na prostej $ND'$ ; punkt $C'$ leży na symetralnej boku $AB$ czyli na prostej $MD'$ .

Zgodnie z rozumowaniem przeprowadzonym w części a), prosta $\chi$ rozdziela punkty $A'$ i $C'$ , albo więc leżą one odpowiednio na półprostych $D'N^\to$ i $D'M^\to$ , albo leżą oba na przedłużeniach tych półprostych. W zależności od tego, kąt $CD'A'$ albo pokrywa się z kątem $MD'N$ , albo są to kąty wierzchołkowe. Tak czy inaczej, ich miary są równe i wobec (3)

$ (4) \qquad |\measuredangle C'D'A'| = 180^\circ-|\measuredangle ABC|, $

co mieliśmy wykazać.

2. Jeden z kątów $CAB$ i $BCA$ jest prosty; niech na przykład $|\measuredangle BCA| = 90^\circ$ (rysunek 14). Punkt $D'$ pokrywa się wówczas z $M$ . Jak w poprzednim przypadku, punkty $A'$ i $C'$ muszą leżeć odpowiednio na symetralnej boku $BC$ (czyli na prostej $ND'$ ) i na symetralnej boku $AB$ ; a przy tym leżą one po różnych stronach prostej $\chi$ , co w tym przypadku jest równoważne stwierdzeniu, że leżą one po różnych stronach prostej $AB$ . Zatem kąt $C'D'A'$ jest rozwarty, o ramionach prostopadłych do ramion kąta $ABC$ ; zachodzi więc równość (4).

3. Jeden z kątów $CAB$ i $BCA$ jest rozwarty; powiedzmy, że $|\measuredangle BCA | > 90 ^\circ$ (rysunek 15). Każdy z punktów $M$ i $N$ jest wówczas położony bliżej punktu $C$ niż punktu $A$ , co oznacza, że punkty $M$ i $N$ leżą po tej samej stronie $\chi$ . Kąt $MD'N$ jest więc ostry, a przy tym ma ramiona prostopadłe do ramion kąta $ABC$ . Stąd

$ (5) \qquad |\measuredangle MD'N| = |\measuredangle ABC|. $

Jak w przypadku 1., punkty $A'$ i $C'$ leżą odpowiednio na prostych $ND'$ i $MD'$ oraz są rozdzielone przez prostą $\chi$ . Tym razem znaczy to, że nie mogą one równocześnie leżeć na półprostych $D'M^\to$ i $D'N^\to$ , ani też nie mogą równocześnie leżeć na ich przedłużeniach. Zatem kąt $C'D'A'$ jest dopełnieniem kąta $MD'N$ do kąta półpełnego i wobec (5) otrzymujemy dowodzoną równość (4).

Wszystkie równości (2) możemy uważać za udowodnione. Wynika z nich natychmiast, że

$ |\measuredangle A'| + |\measuredangle C| \neq |\measuredangle B'| + |\measuredangle D'| $

(wobec analogicznej nierówności dla czworokąta $Q$ ), a więc czworokąt $\tau(Q)$ nie jest wpisany w okrąg.

c) Zgodnie z konkluzją części b), czworokąt $\tau(\tau(Q))$ jest dobrze określony. Oznaczmy jego wierzchołki przez $A''$ , $B''$ , $C''$ , $D''$ ( $A''$ jest środkiem okręgu opisanego na trójkącie $B'C'D'$ itd.). Boki i przekątne czworokątów $Q$ i $\tau(Q)$ są związane zależnościami:

$ (6) \qquad \begin{array}{c} A'B' \bot CD,\quad B'C'\bot DA,\quad C'D' \bot AB,\quad D'A'\bot BC\\ A'C' \bot BD,\quad B'D'\bot AC, \end{array} $

wydającymi z położenia środków okręgów opisanych na trójkątach $BCD$ , $CDA$ , $DAB$ , $ABC$ na symetralnych odpowiednich odcinków.

Analogiczne relacje zachodzą między bokami i przekątnymi czworokątów $\tau(Q)$ i $\tau(\tau(Q))$ . Inaczej mówiąc, jeśli punkty $A$ , $B$ , $C$ , $D$ zastąpimy odpowiednio przez $A''$ , $B''$ , $C''$ , $D''$ , to związki (6) pozostaną w mocy. A zatem

$ (7) \qquad \begin{array}{c} A''B''\parallel AB, \quad B''C'' \parallel BC, \quad C''D''\parallel CD, \quad D''A''\parallel DA\\ A''C''\parallel AC, \quad B''D'' \parallel BD. \end{array} $

Wnosimy stąd, że trójkąt $A''B''C''$ jest podobny do trójkąta $ABC$ , a trójkąt $C''D''A''$ - do trójkąta $CDA$ . W konsekwencji czworokąt $t(t(Q))$ jest podobny do czworokąta $Q$ .

Uwaga 1. Nietrudno dostrzec, że główna trudność zadania mieści się w części b), w kwestiach dotyczących orientacji pewnych kątów. Wnioskowanie przedstawione w części c) jest prawie niezależne od tekstu poprzedzającego; korzysta z niego tylko w tym, że symbol $t(t(Q))$ ma sens.

Istotą części b) są zależności (2). Otóż, w każdej z nich występuje para kątów o ramionach wzajemnie prostopadłych (co wynika natychmiast z tego, że środki rozważanych okręgów leżą na symetralnych odpowiednich odcinków). Miary takich kątów albo dopełniają się do 180^{\circ}, albo są.równe; chodzi o to, by wykluczyć tę drugą ewentualność. Jest to wspomniana kwestia orientacji; do tego nam były potrzebne rozważania dotyczące usytuowania wierzchołków $t(Q)$ względem prostych $\chi$ i $\lambda$ .

XXXVIII OM - III etap

III etap XXXVIII Olimpiady Matematycznej

XXXVIII OM - III - Zadanie 1

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

III

W kwadracie o boku 1 znajduje się $n$ punktów ( $n > 2$ ). Dowieść, że można je ponumerować $P_1, P_2, ..., P_n$ tak, by \sum_{i=1}^n |P_{i-1}P_i|^2 \leq 4 (przyjmujemy $P_0=P_n$ ).

Rozwiązanie

Dowód oprzemy na następującym lemacie:
Lemat. W trójkącie prostokątnym $ABC$ , w którym $|AB| = |BC| = a$ , $|\measuredangle ABC| = 90^\circ$ , znajduje się $k$ punktów ( $k \geq 1$ ). Można je wówczas ponumerować $P_1, \ldots , P_k$ tak, że

$ \sum_{i=1}^{k+1}|P_{i-1}P_i|^2 \leq 2 a^2 $

(przyjmujemy $P_0 = A$ , $P_{k+1} = C$ ).

Dowód. Stosujemy indukcję. Gdy $k = 1$ , mamy jeden punkt $P$ i do udowodnienia nierówność $|AP|^2+|PC|^2 \leq 2a^2$ , która wynika z tego, że $2a^2 = |AC|^2$ , a kąt $APC$ jest nieostry.

Ustalmy liczbę naturalną $m \geq 2$ i załóżmy, że teza lematu zachodzi dla dowolnego trójkąta prostokątnego równoramiennego i dowolnego zawartego w nim zbioru Uczącego k punktów, gdzie $k$ jest dowolną liczbą naturalną mniejszą niż $m$ .

Niech będzie dany trójkąt $ABC$ ( $|AB| = |BC| = a$ , $|\measuredangle B| = 90^\circ$ ), a w nim zbiór $Z$ złożony z $m$ punktów. Niech $A_0B_0C_0$ będzie najmniejszym trójkątem o bokach równoległych do odpowiednich boków trójkąta $ABC$ , zawierającym zbiór $Z$ . (,,Konstrukcja'': każdą z trzech prostych zawierających boki trójkąta $ABC$ przesuwamy równolegle aż do napotkania pierwszego z punktów zbioru $Z$ ; przesunięte proste utworzą trójkąt $A_0B_0C_0$ , o którym mowa.)

Oznaczmy przez $E_O$ spodek wysokości opuszczonej z wierzchołka $B_0$ na przeciwprostokątną $A_0C_0$ . Oczywiście

$ |B_0E_0| = \frac{1}{2} |A_0C_0| \leq \frac{1}{2} |AC| = \frac{1}{2} \sqrt{2a}. $

Oznaczmy trójkąty (domknięte) $A_0E_0B_0$ i $B_0E_0C_0$ odpowiednio przez $\Delta'$ i $\Delta''$ , a ich część wspólną, czyli odcinek $B_0E_0$ , przez $I$ . Każdy z trójkątów $\Delta'$ i $\Delta''$ zawiera punkty zbioru $Z$ ; inaczej trójkąt $A_0B_0C_0$ nie byłby minimalny. Dzielimy teraz zbiór $Z$ na dwa niepuste podzbiory $Z'$ i $Z''$ zawarte odpowiednio w $\Delta'$ i $\Delta''$ : punkty zbioru $Z_n \cap \Delta' \setminus I$ zaliczamy do $Z'$ , punkty zbioru $Z_n \cap \Delta' \setminus I$ zaliczamy do $Z''$ , a punkty zbioru $Z \cap l$ rozdzielamy między zbiory $Z'$ i $Z''$ w dowolny sposób, z jedynym zastrzeżeniem, by powstałe zbiory $Z'$ i $Z"$ były niepuste; jest to możliwe, gdyż w myśl poprzedniej konkluzji $Z \cap \Delta' \neq\emptyset$ , $Z_n \cap \Delta'' \neq \emptyset$ , a $m \geq 2$ .

Niech $k$ będzie liczbą elementów zbioru $Z'$ , a $m-k$ liczbą elementów zbioru $Z''$ ( $0 < k < m$ ). Na mocy przesłanki indukcyjnej zastosowanej do trójkątów $\Delta'$ i $\Delta'$ oraz zawartych w nich zbiorów $Z'$ i $Z"$ można ponumerować punkty tych zbiorów odpowiednio: $P_1, \ldots, P_k$ oraz $P_{k+1}, \ldots, P_m$ tak, by

$ (1) \qquad |A_0P_1l^2+|P_1P_2|^2+\ldots+|P_kB_0|^2 \leq 2|B_0E_0|^2 \leq a^2, $

$ (2) \qquad |B_0P_{k+1}|^2+|P_{k+1}P_{k+2}^2+ \ldots +|P_mC_0| \leq 2|B_0E_0|^2 < a^2. $

Zauważmy teraz, że

$ |P_kB_0|^2+|B_0P_{k+1}|^2 \geq |P_kP_{k+1}|^2 $

(bo $|\measuredangle P_kB_0P_{k+1}| \leq 90^\circ$ ), a ponadto

$ |AP_1| \geq |A_0P_1|, \quad |P_mC| \geq |P_mC_0|| $

(rysunek 17). Wobec tego

$ \begin{split} &|AP_1|^2 \ldots +|P_kP_{k+1}|^2+ \ldots +|P_mC|^2 \leq\\ &\qquad \leq \mathrm{(suma lewych stron nierówności (1) i (2))} \leq 2a^2. \end{split} $

Znaczy to, że ponumerowanie $P_1, \ldots, P_m$ punktów zbioru $Z$ spełnia postawiony warunek. Indukcyjny dowód lematu jest tym samym zakończony.

Aby wydedukować z lematu tezę zadania, dzielimy dany kwadrat $ABCD$ (o boku długości 1) na dwa trójkąty prostokątne przekątną $AC$ . Dany zbiór $n$ punktów dzielimy na dwa podzbiory, zawarte odpowiednio w jednym i drugim trójkącie i liczące odpowiednio $k$ i $n-k$ punktów ( $0 \leq k \leq n$ ); punkty leżące na przekątnej zaliczamy do któregokolwiek z tych zbiorów.

Rozpatrzymy dwa przypadki:

1. $0 < k < n$ . Z lematu wynika możliwość ponumerowania punktów w każdym z tych zbiorów: $P_1, \ldots, P_k$ oraz $P_{k+1}, \ldots, P_k$ tak, żeby były spełnione warunki:

$ (3) \qquad |AP_1|^2+ \ldots +|P_kC|^2 \leq 2, $

$ (4) \qquad |CP_{k+1}|^2+ \ldots +|P_nAl^2\leq 2. $

Podobnie, jak w dowodzie lematu, skorzystamy z nierówności

$ |P_kC|^2+|CP_{k+1}|^2 \geq |P_kP_{k+1}|^2 \quad |P_nA|^2 + |AP_1|^2 \geq |P_nP_1|^2, $

wynikających z tego, że $|\measuredangle P_kCP_{k+1}| \leq 90^\circ$ , $|\measuredangle P_nAP_1| \leq 90^\circ$ (rysunek 18). Dostajemy nierówność

$ \begin{split} &|P_1P_2|^2 \ldots +|P_kP_{k+1}|^2+ \ldots +|P_nP_1|^2 \leq\\ &\qquad \leq \mathrm{(suma lewych stron nierówności (3) i (4))} \leq 4. \end{split} $

Zatem numeracja $P_1,\ldots, P_n$ czyni zadość warunkowi zadania.

2. $k = 0$ lub $k = n$ . Wszystkie dane punkty leżą wówczas w jednym z trójkątów $ABC$ , $CDA$ i zgodnie z lematem możemy je ponumerować $P_1, \ldots, P_n$ , tak że

$ |AP_1|^2+|P_1P_2|+ \ldots +|P_{n-1}P_n|^2+|P_nC|^2 \leq 2. $

Tym bardziej więc

$ |P_1P_2|+ \ldots +|P_{n-1}P_n|^2 \leq 2. $

co w połączeniu z oczywistą nierównością $|P_nP_1l^2 \leq 2$ daje żądany warunek

$ |P_1P_2|+ \ldots +|P_{n-1}P_n|^2+|P_nP_1|^2 \leq 4. $

XXXVIII OM - III - Zadanie 2

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

III

W okrąg o długości 1 wpisano $n$ -kąt foremny. Spośród łuków okręgu mających końce w wierzchołkach tego wielokąta losujemy ze zwracaniem pięć łuków $L_1, \ldots, L_5$ , przy czym dla wszystkich łuków prawdopodobieństwo wylosowania jest jednakowe. Wykazać, że wartość oczekiwana długości części wspólnej $L_1\cap L_2 \cap L_3 \cap L_4 \cap L_5$ nie zależy od $n$ .

Rozwiązanie

Wierzchołki wielokąta dzielą okrąg na $n$ łuków długości $1/n$ . Ponumerujmy te łuki: $J_1, \ldots, J_n$ . Oznaczmy przez $\mathcal{L}$ zbiór, z którego dokonuje się losowania. Elementami zbioru $\mathcal{L}$ są łuki danego okręgu, z których każdy ma dwa końce, będące różnymi wierzchołkami rozważanego wielokąta (patrz: Uwaga). Innymi słowy: łuk $L$ danego okręgu jest elementem zbioru $\mathcal{L}$ wtedy i tylko wtedy, gdy jest sumą m łuków $J_i$ gdzie $0 < m < n$ .

Ustalmy numer $i \in \{1, \ldots,n\}$ . Wybierzmy losowo jeden łuk $L \in \mathcal{L}$ . Prawdopodobieństwo tego, że łuk $L$ zawiera ustalony łuk $J_i$ równa się $1/2$ :

$ (1) \qquad P(L \supset J_i) = \frac{1}{2}. $

Wynika to stąd, że każda para wierzchołków wielokąta wyznacza dwa różne łuki, z których dokładnie jeden zawiera $J_i$ , a zatem te łuki $K \in \mathcal{L}$ , które zawierają nasz łuk stanowią dokładnie połowę w zbiorze $\mathcal{L}$ .

Rozważane w zadaniu doświadczenie polega na wylosowaniu pięciu łuków $L_1, L_2, L_3, L_4, L_5 \in \mathcal{L}$ , z dopuszczeniem powtórzeń. Przyjmujemy, że losowania są niezależne: prawdopodobieństwo tego, że część wspólna wylosowanych łuków zawiera ustalony łuk $J_i$ równa się iloczynowi prawdopodobieństw (1), branych kolejno dla $L = L_1, \ldots, L_5$ :

$ (2) \qquad \begin{split} &P((L_1 \cap L_2 \cap L_3 \cap L_4 \cap L5) \cap J_i) =\\ &=P((L_1 \supset J_i) \vee(L_2 \supset J_i) \vee(L_3 \supset J_i) \vee(L_4 \supset J_i) \vee(L_5 \supset J_i) ) = \left( \frac{1}{2} \right)^5 \end{split} $

Dla $i \in \{1, \ldots,n\}$ niech $X_i$ oznacza zmienną losową określoną następująco:

$ X =\left\{ \begin{array}{ll} 1& \textrm{gdy } (L_1 \cap L_2 \cap L_3 \cap L_4 \cap L5) \cap J_i\\ 0& \textrm {w przeciwnym razie} \end{array} \right. $

Wobec równości (2) wartość oczekiwana tej zmiennej wynosi

$ (3) \qquad E(X_i) = \left(\frac{1}{2}\right)^5\quad \textrm{dla } i = 1,\ldots, n. $

Część wspólna $L_1 \cap L_2 \cap L_3 \cap L_4 \cap L5$ może być zbiorem pustym, zbiorem jednopunktowym lub sumą pewnej liczby łuków $J_i$ . Jej długość - czyli badana zmienna losowa $X$ - równa się liczbie zawartych w owej sumie łuków $J_i$ , pomnożonej przez $1/n$ (wspólną długość wszystkich $J_i$ )- Zatem $X$ przyjmuje wartość $k/n$ wtedy i tylko wtedy, gdy dokładnie $k$ spośród zmiennych losowych $X_1, \ldots, X_n$ ma wartość $1$ , a reszta $0$ . Wobec tego
$X = \frac{1}{2} (X_1+ \ldots +X_n)$ i w konsekwencji wartość oczekiwana zmiennej $X$ równa się średniej arytmetycznej wartości (3), czyli

$ E(X) = \frac{1}{n}(E(X_1)+ \ldots +E(X_n)) = \left(\frac{1}{2}\right)^5. $

Otrzymana liczba, jak widać, nie zależy od $n$ .

Uwaga. Ze sformułowania treści zadania nie wynika jednoznacznie, czy słowo ,,końce'' użyte w liczbie mnogiej niesie w sobie informację, że każdy z rozważanych łuków $L$ ma dwa różne końce - a więc, czy nie są dopuszczone do rozważań łuki ,,niewłaściwe'', o końcach pokrywających się, a tym samym redukujące się do pojedynczego punktu, lub przeciwnie, będące całym okręgiem. Na pytania uczestników zawodów w tej sprawie udzielano odpowiedzi, że łuki ,,niewłaściwe'' nie są brane pod uwagę - czyli tak, jak w podanym wyżej rozwiązaniu. Warto jednak zauważyć, że wynik i całe rozumowanie nie zmieni się, gdy włączymy do zbioru $\mathcal{L}$ . łuki ,,niewłaściwe'', pod warunkiem, że przyjmiemy istnienie $n$ łuków jednopunktowych i także w łuków otrzymanych przez obieg całego okręgu (początek i koniec w którymkolwiek wierzchołku). Nadal bowiem każdy z łuków $\mathcal{L}$ , będzie zawarty dokładnie w połowie łuków z $L$ , dzięki czemu pozostanie w mocy wzór (1).

Zaznaczmy jeszcze, że również założenie niezależności kolejnych pięciu losowań jest tu przyjmowane milcząco.

XXXVIII OM - III - Zadanie 3

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

III

Dany jest wielomian $W$ o współczynnikach całkowitych nieujemnych. Określamy ciąg liczb $(p_n)$ , gdzie $p_n$ jest sumą cyfr liczby $W(n)$ . Dowieść, że pewna liczba występuje w ciągu $(p_n)$ nieskończenie wiele razy.

Rozwiązanie

Niech $W(x) = a_mx^m + \ldots +a_1x+a_0$ ( $a_i$ - całkowite nieujemne) i niech $q$ będzie liczbą cyfr w zapisie dziesiętnym największej z liczb $a_0, \ldots, a_m$ . Niech $\overline{a_i}$ oznacza $q$ -cyfrowy zapis dziesiętny liczby $a_i$ ; gdy $a_i$ ma mniej niż $q$ cyfr, piszemy na początku zera. Wówczas dla $r > q$ przedstawienie dziesiętne liczby $W(10^r)$ ma postać

$ \overline{a_m\vphantom{b}}\, \overline{b}\, \overline{a_{m-1}\vphantom{b}}\,\overline{b}\ldots \overline{b} \overline{a_1\vphantom{b}}\,\overline{b}\,\overline{a_0\vphantom{b}}, $

gdzie $\bar{b}$ jest blokiem złożonym z $r-q$ zer. Suma cyfr każdej z tych liczb równa się sumie cyfr wszystkich współczynników wielomianu $W$ . Jest to więc wspólna wartość wszystkich wyrazów ciągu $(p_n)$ o numerach $n = 10^r$ , $r \leq q$ .

XXXVIII OM - III - Zadanie 4

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

III

W zbiorze czworościanów o polu podstawy 1, polu powierzchni całkowitej 4 i mających równe kąty nachylenia ścian bocznych do podstawy znaleźć czworościan o maksymalnej objętości.

Rozwiązanie

Niech $ABCD$ będzie dowolnym czworościanem spełniającym podane warunki:

$ (1) \qquad \mathrm{pole} (ABC) = 1,\ \mathrm{pole} (BCD)+\mathrm{pole} (CDA)+\mathrm{pole}(DAB) = 3; $

$ (2) \qquad \textrm{ściana $ABC$ tworzy równe kąty dwuścienne z pozostałymi ścianami.} $

Z warunku (2) wynika, że punkt $D'$ będący rzutem punktu $D$ na płaszczyznę $ABC$ znajduje się w jednakowej odległości od prostych $BC$ , $CA$ , $AB$ (równej $r = h \ctg \phi$ , gdzie $h = |DD'|$ , a $\phi$ jest rozwartością rozważanych kątów dwu-ściennych). Ponadto, punkt $D'$ leży w obrębie trójkąta $ABC$ ; gdyby bowiem leżał na zewnątrz tego trójkąta, to wśród kątów dwuściennych, o których mowa w (2), znalazłby się co najmniej jeden kąt ostry i co najmniej jeden rozwarty - wbrew ich postulowanej równości. $A$ wobec tego punkt $D'$ jest środkiem koła wpisanego w trójkąt $ABC$ . Promień tego koła ma długość $r$ .

Wysokość każdej ze ścian bocznych opuszczona z wierzchołka $D$ ma długość $w = \sqrt{h^2+r^2}$ . Oznaczając przez p połowę obwodu trójkąta $ABC$ otrzymujemy z równości (1):

$ 1 = \mathrm{pole} (ABC) = pr \quad \textrm{więc } r = \frac{1}{p} $

oraz

$ \begin{split} 3 &=\frac{1}{2} |BC| \cdot w+ \frac{1}{2} |CA| \cdot w+ \frac{1}{2} |AB| \cdot w = pw = \\ &=p \sqrt{h^2+r^2}=p \sqrt{h^2+\frac{1}{p+2}}=\sqrt{p^2h^2+1}. \end{split} $

Stąd $p^2h^2 = 8$ , czyli $h = 2\sqrt{2} p$ . Objętość czworościanu $ABCD$ równa się zatem

$ (3) \qquad V = \frac{1}{3} h \cdot \mathrm{pole}(ABC) = \frac{1}{3} h =\frac{2\sqrt{2}}{3p}. $

Spośród wszystkich trójkątów o polu $1$ najmniejszy obwód ma trójkąt równoboczny (patrz: Uwaga 2). Na mocy (3) minimalna wartość $p$ daje maksymalną wartość $V$ . Tak więc w rozpatrywanej klasie czworościanów największą objętość ma czworościan $ABCD$ o następujących własnościach: podstawa $ABC$ jest trójkątem foremnym o polu $1$ ; spodek wysokości z $D$ pokrywa się ze środkiem koła wpisanego w trójkąt $ABC$ ; powierzchnia boczna ma pole $3$ .

Jedynym (z dokładnością do izometrii) czworościanem o tych własnościach jest czworościan foremny mający ściany o polu $1$ . Stanowi on rozwiązanie zadania.

Uwaga 1. Gdyby podany w treści zadania warunek rozumieć jako równość nachylenia ścian bocznych do płaszczyzny podstawy (a niekoniecznie do samej ściany $ABC$ ), rozumowanie wymagałoby następującej modyfikacji: punkt $D'$ , jako leżący w jednakowej odległości $r$ od prostych $BC$ , $CA$ , $AB$ , musi być środkiem koła wpisanego w trójkąt $ABC$ lub jednego z kół dopisanych. Równości $3 = p \sqrt{h^2+r^2}$ oraz $V = h/3$ zachowują moc. Dla ustalonego trójkąta $ABC$ maksymalną wartość $V$ otrzymamy więc obierając minimalną (z czterech możliwych) wartość $r$ - czyli długość promienia koła wpisanego. To znaczy, że inne możliwości można zaniedbać.

Uwaga 2. W końcowym fragmencie rozwiązania powołaliśmy się na znane twierdzenie, które mówi, że wśród wszystkich trójkątów o polu $1$ najmniejszy obwód ma trójkąt foremny. Dla kompletności podamy dowód tego faktu.

Niech $a$ , $b$ , $c$ będą długościami boków trójkąta o polu $1$ i niech $p = (a+b+c)/2$ . Mamy dowieść, że $p\geq \sqrt[4]{27}$ (połowa obwodu trójkąta foremnego o polu $1$ ). Z wzoru Herona i z nierówności między średnimi mamy

$ \frac{1}{p}=(p-a(p-b)(p-c)\leq \left(\frac{p-a+p-b+p-c}{3}\right)^3 = \left(\frac{p}{3}\right)^3 $

czyli $p^4 \geq 27$ , o co chodziło.

XXXVIII OM - III - Zadanie 5

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

III

Wyznaczyć najmniejszą liczbę naturalną $n$ , dla której liczba $n^2-n+11$ jest iloczynem czterech liczb pierwszych (niekoniecznie różnych).

Rozwiązanie

Niech $f(x) = x^2-x+11$ . Wartości przyjmowane przez funkcję $f$ dla argumentów całkowitych są liczbami całkowitymi niepodzielnymi przez $2$ , $3$ , $5$ , $7$ . Przekonujemy się o tym badając reszty z dzielenia $n$ i $f(n)$ przez te cztery początkowe liczby pierwsze:

\begin{tabular}{lllll}
&\multicolumn{4}{l}{Reszty z dzielenia:}\\
&przez 2&przez 3&przez 5&przez 7\\
$n$ &0 1&0 1 2 &0 1 2 3 4&0 1 2 3 4 5 6\\
$f(n)$ &1 1&2 2 1&1 1 3 2 3& 4 4 6 3 2 3 6
\end{tabular}

Zatem dowolna liczba $N$ będąca wartością $f$ dla argumentu naturalnego i spełniająca podany w zadaniu warunek musi mieć postać $N = p_1p_2p_3p_4$ , gdzie czynniki $p_i$ są liczbami pierwszymi $\geq 11$ .

Najmniejsza z takich liczb $N= 11^4$ prowadzi do równania kwadratowego $x^2-x+11=11^4$ o pierwiastkach niewymiernych. Ale już druga z kolei $N = 11^3 \cdot 13$ jest równa wartości $f(132)$ . Funkcja $f$ jest ściśle rosnąca w przedziale $\langle 1/2; \infty)$ wobec czego znaleziona minimalna możliwa wartość $N$ wyznacza minimalną możliwą wartość $n$ . Stąd odpowiedź: $n = 132$ .

XXXVIII OM - III - Zadanie 6

Zawody matematyczne:

XXXVIII OM, 1986-1987

Etap:

III

Płaszczyznę pokryto siatką sześciokątów foremnych o boku 1. Za drogę na siatce uważamy taki ciąg boków sześciokątów siatki, że każde dwa kolejne mają wspólny koniec. Drogę na siatce nazwiemy najkrótszą, jeżeli jej końców nie można połączyć drogą krótszą. Znaleźć liczbę najkrótszych dróg na siatce o ustalonym początku i długości 60.

Rozwiązanie

Uwaga. Użyte w treści sformułowanie: ,,kolejne boki mają wspólny koniec'' należy rozumieć w ten sposób, że rozważa się odcinki skierowane i koniec poprzedniego jest początkiem następnego (tak więc nie tworzy drogi na przykład pęk odcinków o jednym wspólnym końcu). Mimo braku precyzji, tak właśnie było to sformułowanie rozumiane przez wszystkich rozwiązujących, zgodnie z intuicyjnym sensem słowa ,,droga''.

Ustalmy na płaszczyźnie jeden z kierunków boków rozważanej siatki sześciokątów ( $\Sigma_6$ ), nazwijmy go poziomym i wyróżnijmy na nim zwroty: lewo, prawo. Z każdego węzła siatki $\Sigma_6$ wybiega dokładnie jeden bok poziomy. Oznaczmy przez $W$ zbiór tych węzłów, z których bok poziomy wybiega w prawo, a przez $W'$ zbiór pozostałych węzłów, to jest tych, z których bok poziomy biegnie w lewo. Każdy bok siatki łączy punkt zbioru $W$ z punktem zbioru $W'$ .

Niech $O$ będzie wybranym ustalonym węzłem, punktem początkowym rozpatrywanych dróg. Możemy przyjąć, że $O\in W$ . Startując z punktu $O$ , po parzystej liczbie kroków znajdziemy się w punkcie zbioru $W$ , a po nieparzystej - w punkcie zbioru $W$ . Zatem dwie drogi o wspólnym początku i końcu mają długości jednakowej parzystości; jeśli droga daje się skrócić - to co najmniej o $2$ .

Dwa różne punkty zbioru $W$ nazwiemy sąsiednimi, jeśli łączy je droga długości $2$ ; droga ta jest wówczas jedyna. Połączmy każdą parę sąsiednich punktów zbioru $W$ odcinkiem. Powstanie w ten sposób siatka $\Sigma_3$ trójkątów foremnych o boku $\sqrt{3}$ ; węzłami siatki $\Sigma_3$ są punkty zbioru $W$ . Określamy pojęcie drogi na siatce $\Sigma_3$ , długości drogi oraz pojęcie drogi najkrótszej analogicznie do odpowiednich pojęć dla siatki $\Sigma_6$ , z tym, że za jednostkę długości przyjmujemy bok siatki $\Sigma_3$ .

W dalszym ciągu będziemy rozpatrywać na siatce $\Sigma_6$ tylko drogi długości parzystej, rozpoczynające się w punkcie $O$ i spełniające następujący warunek: jeśli $OP_1P_2 \ldots P_{2k-1}P_{2k}$ jest rozpatrywaną drogą, to $P_{2i-2} \neq P_{2i}$ dla $i = 1, \ldots, k$ (przyjmujemy $P_0 = O$ ); innymi słowy, żaden bok siatki nie jest przebiegany ,,tam i z powrotem,, w dwóch kolejnych krokach, z których pierwszy ma numer nieparzysty, a drugi parzysty (oczywiście każda najkrótsza droga ten warunek spełnia). Idąc taką drogą, w każdej kolejnej parze kroków przechodzi się z punktu zbioru $W$ do sąsiedniego punktu zbioru $W$ . Zatem każda droga na siatce $\Sigma_6$ spełniająca ten warunek i mająca długość $2k$ wyznacza drogę długości $k$ na siatce $\Sigma_3$ . Jest to odpowiedniość wzajemnie jednoznaczna, bo końce każdego boku siatki $\Sigma_3$ łączy dokładnie jedna droga długości $2$ na siatce $\Sigma_6$ . Drogom najkrótszym na jednej siatce odpowiadają drogi najkrótsze na drugiej siatce.

Spróbujemy policzyć najkrótsze drogi długości $k$ na siatce $\Sigma_3$ (o początku $O$ ).

Weźmy pod uwagę sześć dróg (na siatce $\Sigma_3$ ) długości $k$ wychodzących z $O$ i biegnących po półprostych. Ich końce są wierzchołkami sześciokąta foremnego, który oznaczymy przez $H_k$ . Wychodząc z punktu $O$ i wykonując $k$ ruchów (na siatce $\Sigma_3$ ) nie wyjdziemy z pasa ograniczonego prostymi zawierającymi dowolne dwa równoległe boki sześciokąta $H_k$ - a więc nie wyjdziemy poza obręb tego sześciokąta. Możemy natomiast osiągnąć każdy punkt leżący na jego obwodzie. Przy tym każdy węzeł siatki $\Sigma_3$ leżący we wnętrzu $H_k$ należy do pewnego sześciokąta $H_j$ , gdzie $j< k$ , a więc jest osiągalny drogą długości Zatem jedynie do punktów na obwodzie $H_k$ prowadzą drogi najkrótsze długości $k$ (na siatce $\Sigma_3$ ).

Ile jest takich dróg? Dowolny bok $AB$ sześciokąta $H_k$ zawiera $k+1$ punktów zbioru $W$ , a gdy je ponumerujemy $Q_0, \ldots,Q_k$ ( $Q_0 = A$ , $Q_k = B$ ), zauważymy, że do punktu $Q_r$ prowadzi $\binom{k}{r}$ najkrótszych dróg z punktu $O$ ; wynika to przez łatwą indukcję ze spostrzeżenia, że najkrótsze drogi do dowolnego z punktów $Q_0, \ldots,Q_{k-1}$ są przedłużeniami najkrótszych dróg do dwóch sąsiednich węzłów na obwodzie sześciokąta $H_{k-1}$ zaś do punktów $A$ i $B$ prowadzi po jednej drodze długości $k$ . (Innymi słowy: pisząc w każdym węźle siatki $\Sigma_3$ liczbę najkrótszych dróg z punktu $O$ do danego węzła otrzymujemy sześć kopii trójkąta Pascala, po jednej w każdym z sześciu sektorów płaszczyzny o wierzchołku $O$ , wyznaczonych przez kierunki boków siatki $\Sigma_3$ ). Jest więc $2^k$ najkrótszych dróg łączących $O$ z punktami boku $AB$ .

Sześciokąt $H_k$ ma sześć boków. Mamy zatem $6 \cdot 2^k-6$ najkrótszych dróg do punktów na obwodzie $H_k$ ; składnik $-6$ zapobiega dwukrotnemu policzeniu dróg prowadzących do wierzchołków $H_k$ .

W zadaniu chodzi o wyznaczenie liczby najkrótszych dróg (o początku $O$ ) długości $60$ na siatce $\Sigma_6$ , czyli liczby najkrótszych dróg (o początku $O$ ) długości $30$ na siatce $\Sigma_3$ . W myśl powyższych rozważań, liczba ta wynosi $6 \cdot 2^{30}-6$ .