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