XVIII OM - II etap

II etap XVIII Olimpiady Matematycznej

XVIII OM - II - Zadanie 1

Zawody matematyczne:

XVIII OM, 1966-1967

Etap:

Dany jest ciąg liczb $a_1, a_2, \ldots, a_n$ ( $n \geq 3$ ), w którym $a_1 = a_n = 0$ oraz $a_{k-1}+a_{k+1} \geq 2a_{k+1}$ dla $k = 2, 3, \ldots, (n - 1)$ . Dowieść, że w tym ciągu nie ma wyrazów dodatnich.

Rozwiązanie

W zbiorze skończonym liczb $a_1, a_2, \ldots, a_n$ istnieje co najmniej jedna liczba nie mniejsza od żadnej z tych liczb. Przypuśćmy, że taką liczbą jest $a_r$ , tzn. że $a_i \leq a_r$ dla $i = 1, 2, \ldots, n$ . Niech $s$ będzie najmniejszym wskaźnikiem o tej własności, że $a_s = a_r$ . Dowiedziemy, że $s=1$ . Istotnie, gdyby było $s > 1$ , to zachodziłyby nierówności

$ a_{s-1} < a_s, \textrm{ według definicji wskaźnika } s, $

$ a_{s+1} \leq a_s, \textrm{ ponieważ } a_s = a_r. $

Dodając te nierówności otrzymujemy

$ a_{s-1} + a_{s+1} < 2a_s, $

co przeczy założeniu twierdzenia.

Jeśli zaś $s = 1$ , znaczy to, że $a_r = a_1 = 0$ , zatem $a_i \leq 0$ dla $i = 1, 2, \ldots, n$ .

Uwaga. W powyższym dowodzie powołaliśmy się na twierdzenie, że w każdym skończonym zbiorze liczb $a_1, a_2, \ldots, a_n$ istnieje taka liczba $a_r$ , że $a_i \leq a_r$ dla $i = 1, 2, \ldots, n$ .

Twierdzenie to, zwane zasadą maksimum, jest łatwym wnioskiem z zasady indukcji. Odwrotnie, zasada indukcji wynika z zasady maksimum. Przeprowadzenie dowodu tej równoważności proponujemy jako ćwiczenie.

XVIII OM - II - Zadanie 2

Zawody matematyczne:

XVIII OM, 1966-1967

Etap:

Na sali znajduje się 100 osób, z których każda zna co najmniej 66 spośród pozostałych 99 osób. Dowieść, iż jest możliwe, że w każdej czwórce tych osób są takie dwie, które się nie znają. Przyjmujemy, że jeśli osoba $A$ zna osobę $B$ , to również osoba $B$ zna osobę $A$ .

Rozwiązanie

Oznaczmy osoby znajdujące się na sali literami $A_1, A_2, \ldots, A_{100}$ . Niech $M$ oznacza zbiór osób $\{A_1, A_2, \ldots, A_{33}\}$ , $N$ - zbiór osób $\{A_{34}, A_{35}, \ldots, A_{66}\}$ i $P$ - zbiór osób $\{A_{67}, A_{68}, \ldots, A_{100} \}$ . Przypadek, o którym mowa w zadaniu, zachodzi na przykład wtedy, gdy każda osoba zbioru $M$ zna te i tylko te osoby, które należą do zbioru $N$ lub do zbioru $P$ (razem $67$ osób), i podobnie każda osoba zbioru $N$ zna wszystkie osoby zbiorów $P$ i $M$ i tylko te osoby ( $67$ osób), a każda osoba zbioru $P$ zna wszystkie osoby zbiorów $M$ i $N$ i tylko te osoby ( $66$ osób). Jeśli bowiem ( $A_i, A_j, A_k, A_l$ ) jest jakąkolwiek czwórką danych osób, to któreś dwie z nich znajdują się w jednym i tym samym ze zbiorów $M$ , $N$ , $P$ , a wobec tęgo osoby te się nie znają.

Uwaga. Twierdzenie powyższe łatwo uogólnić. Załóżmy, że na sali znajduje się $N$ osób, z których każda zna co najmniej $\left[ \frac{2n}{3} \right]$ pozostałych osób. Może się wówczas zdarzyć, że w każdej czwórce tych osób są dwie takie, które się nie znają. Aby to udowodnić podzielmy zbiór $M$ wszystkich osób na $3$ zbiory $M_1$ , $M_2$ , $M_3$ zawierające odpowiednio $m_1 = \left[ \frac{n+1}{3} \right]$ , $m_2 = \left[ \frac{n+1}{3} \right]$ oraz $m_3 = n - 2 \left[ \frac{n+1}{3} \right]$ osób. Jeżeli każda osoba zbioru $M_i$ zna osoby zbiorów $M_j$ i $M_k$ ( $i, j, k = 1, 2, 3;\ i \ne j \ne k \ne i$ ) i tylko te osoby, to w każdej czwórce osób zbioru $M$ są takie dwie osoby, które należą do tego samego zbioru $M_i$ , więc się nie znają. Każda zaś osoba zbioru $M$ zna wtedy co najmniej $\left[ \frac{2n}{3} \right]$ osób. Albowiem

$ m_1 + m_2 = \left[ \frac{n+1}{3} \right] + \left[ \frac{n+1}{3} \right] = 2 \left[ \frac{n+1}{3} \right] \geq \left[ \frac{2n}{3} \right] $

$ m_1 + m_3 = m_2 + m_3 = n- \left[ \frac{n+1}{3} \right] \geq \left[ \frac{2n}{3} \right], $

co najłatwiej stwierdzić oddzielnie dla każdego z trzech możliwych przypadków: $n = 3k$ , $n = 3k+1$ , $n= 3k + 2$ .

Mianowicie

$ \textrm{gdy } n = 3k, \textrm{ to } \left[ \frac{n+1}{3} \right] = k,\ \left[ \frac{2n}{3} \right] = \left[ \frac{6k}{3} \right] = 2k, $

$ \textrm{gdy } n = 3k+1, \textrm{ to } \left[ \frac{n+1}{3} \right] = \left[ \frac{3k+2}{3} \right] = k,\ \left[ \frac{2n}{3} \right] = \left[ \frac{6k+2}{3} \right] = 2k, $

$ \textrm{gdy } n = 3k+2, \textrm{ to } \left[ \frac{n+1}{3} \right] = \left[ \frac{3k+3}{3} \right] = k+1,\ \left[ \frac{2n}{3} \right] = \left[ \frac{6k+4}{3} \right] = 2k+1, $

Widzimy stąd, że podane wyżej nierówności są spełnione dla każdego naturalnego $n$ .

XVIII OM - II - Zadanie 3

Zawody matematyczne:

XVIII OM, 1966-1967

Etap:

Dwa okręgi są styczne wewnętrznie w punkcie $A$ . Poprowadzono cięciwę $BC$ większego okręgu styczną do mniejszego w punkcie $D$ . Dowieść, że $AD$ jest dwusieczną kąta $BAC$ .

Rozwiązanie

Punkt styczności $A$ danych okręgów jest ich środkiem jednokładności. W tej jednokładności stycznej $BC$ mniejszego okręgu odpowiada styczna do większego okręgu w punkcie $E$ odpowiadającym punktowi $D$ (rys. 6). Jako proste jednokładne, styczne te są równoległe. W takim razie łuki $BE$ i $EC$ większego okręgu, wyznaczone przez styczną w punkcie $E$ i równoległą do niej cięciwę $BC$ , są równe. Stąd wynika, że kąty wpisane $BAE$ i $EAC$ są równe, tzn. $AE$ jest dwusieczną kąta $BAC$ .

XVIII OM - II - Zadanie 4

Zawody matematyczne:

XVIII OM, 1966-1967

Etap:

Rozwiązać w liczbach naturalnych równanie

$ (1) \qquad xy+yz+zx = xyz + 2. $

Rozwiązanie

Przypuśćmy, że trójka $(x, y, z)$ liczb naturalnych spełnia równanie (1) . Po podzieleniu obu stron równości (1) przez $xyz$ otrzymujemy

$ (2) \qquad \frac{1}{x} + \frac{1}{y} + \frac{1}{z} = 1 + \frac{2}{xyz}. $

Któraś z liczb $x$ , $y$ , $z$ jest mniejsza od $3$ ; gdy bowiem $x \geq 3$ , $y \geq 3$ , $z \geq 3$ , wtedy lewa strona równości (2) jest $\leq 1$ , a prawa strona jest $> 1$ .

Gdy $x < 3$ , zachodzi jeden z przypadków:

a) $x = 1$ ; z równości (1) wynika wtedy, że

$ y+z = 2, \textrm{ skąd } y = 1, z = 1. $

b) $x = 2$ ; z równości (1) otrzymujemy $2y + yz + 2z = 2 yz +2$ , skąd

$ yz - 2y - 2z = - 2, \textrm{ więc } $

$ (y-2)(z-2) = 2. $

Zatem $y-2 = 1$ , $z-2 = 2$ lub $y-2 = 2$ , $z-2 = 1$ , tzn. $y = 3$ , $z = 4$ lub $y = 4$ , $z = 3$ .

Analogiczne rozwiązania otrzymujemy zakładając, że $y = 2$ lub że $z = 2$ .

Równanie (1) ma zatem $7$ rozwiązań w liczbach naturalnych:

$ (1, 1, 1),\ (2, 3, 4),\ (2, 4, 3),\ (3, 2, 4),\ (4, 2, 3),\ (3, 4, 2),\ (4, 3, 2). $

Uwaga : Ponieważ

$ (x-1)(y-1)(z-1) = xyz - (xy + yz + zx) + (x+y+z)-1, $

więc równanie (1) jest równoważne równaniu

$ \nr{1a} (x-1)(y-1)(z-1) = x+y+z-3, $

które po podstawieniu $x-1 = X$ , $y -1=Y$ , $z-1=Z$ przybiera postać

$ \nr{Ib} XYZ = X + Y + Z. $

Rozwiązanie równania (1b) w liczbach naturalnych było tematem Nr 9 w XVII Olimpiadzie Matematycznej.

XVIII OM - II - Zadanie 5

Zawody matematyczne:

XVIII OM, 1966-1967

Etap:

Na płaszczyźnie leżą dwa trójkąty jeden na zewnątrz drugiego.
Dowieść, że istnieje taka prosta, przechodząca przez dwa wierzchołki jednego trójkąta, że trzeci wierzchołek tego trójkąta oraz drugi trójkąt leżą po przeciwnych stronach tej prostej.

Rozwiązanie

Oznaczmy wierzchołki danych trójkątów odpowiednio literami $A_1, A_2, A_3$ oraz $B_1, B_2, B_3$ . Niech $MN$ będzie takim odcinkiem, że: $1^\circ$ punkt $M$ leży na obwodzie trójkąta $A_1A_2A_3$ , $2^\circ$ punkt $N$ leży na obwodzie trójkąta $B_1B_2B_3$ , $3^\circ$ odcinek $MN$ nie jest dłuższy od żadnego z odcinków łączących punkty obwodu trójkąta $A_1A_2A_3$ z punktami obwodu trójkąta $B_1B_2B_3$ .

Odcinek $MN$ można znaleźć w sposób następujący. Dla każdej z dziewięciu par $(A_i, B_jB_k)$ , gdzie $i, j, k = 1, 2$ lub $3$ , $j \ne k$ , wybierzmy najkrótszy z odcinków łączących punkt $A_i$ z punktami odcinka $B_jB_k$ ; będzie to wysokość trójkąta $A_iB_jB_k$ z wierzchołka $A_i$ lub jeden z odcinków $A_iB_j$ , $A_iB_k$ . Podobnie dla każdej z dziewięciu par ( $B_i, A_jA_k$ ) wybierzmy najkrótszy z odcinków łączących punkt $B_i$ z punktami odcinka $A_jA_k$ . Wreszcie spośród otrzymanych w ten sposób osiemnastu odcinków (niektóre z nich mogą się pokrywać), wybierzmy najkrótszy, tj. taki, który nie jest dłuższy od żadnego innego. Jeden koniec tego odcinka, nazwiemy go $M$ , leży na obwodzie trójkąta $A_1A_2A_3$ , a drugi koniec $N$ - na obwodzie trójkąta $B_1B_2B_3$ . Odcinek $MN$ spełnia wyżej podany warunek $3^\circ$ , gdyż dla każdego odcinka łączącego punkt $K$ obwodu pierwszego trójkąta z punktem $L$ obwodu drugiego trójkąta (rys. 7) istnieje równoległy i nie dłuższy od niego odcinek łączący wierzchołek jednego trójkąta z punktem boku drugiego trójkąta, ten zaś z kolei jest nie dłuższy niż $MN$ . Zatem $MN$ jest odcinkiem o żądanych własnościach.

Poprowadźmy przez punkty $M$ i $N$ odpowiednio proste $m$ i $n$ prostopadłe do $MN$ (rys. 8). Wewnątrz pasa płaszczyzny ograniczonego prostymi $m$ i $n$ nie ma punktów żadnego z danych trójkątów. Gdyby bowiem wewnątrz tego pasa znajdował się np. punkt $P$ trójkąta $A_1A_2A_3$ , wówczas cały odcinek $PM$ leżałby w trójkącie $A_1A_2A_3$ , a ponieważ kąt $PMN$ jest ostry, więc między $P$ i $M$ istniałyby takie punkty $Q$ , że $QN < MN$ , co przeczyłoby określeniu odcinka $MN$ .

Zachodzi jeden z następujących przypadków.

a) Punkty $M$ i $N$ są wierzchołkami danych trójkątów. Przypuśćmy np., że $M$ pokrywa się z $A_1$ , a $N$ z $B_1$ (rys. 9). Weźmy pod uwagę kąty o wierzchołku $A_1$ , jakie półproste $A_1A_2$ i $A_1A_3$ tworzą z półprostymi $m_1$ i $m_2$ prostej $m$ oraz kąty o wierzchołku $B_1$ utworzone przez półproste $B_1B_2$ i $B_1B_3$ z półprostymi $n_1$ i $n_2$ . Niech najmniejszym z tych kątów będzie np. kąt $\alpha$ półprostej $A_1A_2$ z półprostą $m_1$ .

Wówczas prosta $A_1A_2$ jest prostą, jakiej poszukujemy.

Istotnie, kąt $\alpha$ jest albo ostry, albo zerowy. Jeśli $\alpha = 0$ , prosta $A_1A_2$ pokrywa się z prostą $m$ , więc punkt $A_3$ leży po jednej stronie tej prostej, a punkty $B_1, B_2, B_3$ - po drugiej. To samo zachodzi, gdy kąt $\alpha$ jest ostry i prosta $A_1A_2$ przecina prostą $n$ w punkcie $C$ . Punkt $A_3$ leży wówczas po przeciwnej stronie prostej $A_1A_2$ niż punkt $B_1$ (gdyż kąt wypukły $A_1A_3$ z $m_1$ jest $> \alpha$ ). Punkty $B_2$ i $B_3$ leżą zaś po tej samej stronie co $B_1$ . Gdyby bowiem np. punkt $B_2$ leżał po przeciwnej stronie prostej $A_1A_2$ niż punkt $B_1$ lub na prostej $A_1A_2$ , to na odcinku $B_1B_2$ znajdowałby się jakiś punkt $D$ prostej $A_1A_2$ i $\measuredangle DB_1C = \beta$ byłby wbrew założeniu mniejszy od $\alpha$ , gdyż $\measuredangle B_1CA_1 = \alpha$ byłby kątem zewnętrznym trójkąta $DB_1C$ .

b) Punkty $M$ i $N$ nie są oba wierzchołkami danych trójkątów, np. punkt $M$ leży wewnątrz boku $A_1A_2$ . W takim razie cały bok $A_1A_2$ leży na prostej $m$ i prosta $m$ oddziela punkt $A_3$ od punktów $B_1$ , $B_2$ , $B_3$ .

XVIII OM - II - Zadanie 6

Zawody matematyczne:

XVIII OM, 1966-1967

Etap:

Dowieść, ze punkty $A_1, A_2, \ldots, A_n$ ( $n \geq 7$ ) znajdujące się na powierzchni kuli leżą wtedy i tylko wtedy na okręgu, gdy płaszczyzny styczne do powierzchni kuli w tych punktach mają punkt wspólny lub są równoległe do jednej prostej.

Rozwiązanie

a) Załóżmy, że punkty $A_1, A_2, \ldots, A_n$ powierzchni kuli o środku $O$ leżą na okręgu $k$ . Niech $\alpha_1$ oznacza płaszczyznę styczną do kuli w punkcie $A_i$ ( $i= 1,2, \ldots, n$ ), a $\pi$ - płaszczyznę okręgu $k$ .

Jeżeli środkiem okręgu $k$ jest punkt $0$ , to płaszczyzna $\alpha_i$ jest prostopadła do promienia $OA_i$ , więc jest prostopadła do płaszczyzny $\pi$ zawierającej prostą $OA_i$ . Zatem płaszczyzna $\alpha_i$ jest równoległa do każdej prostej prostopadłej do $\pi$ .

Jeżeli zaś środkiem okręgu $k$ jest punkt $S$ różny od $O$ (rys. 10), to płaszczyzna $\pi$ jest prostopadła do prostej $OS$ , zatem w trójkącie $OSA_i$ kąt $S$ jest prosty, a kąt $O$ jest ostry, wobec czego prosta $OS$ przecina płaszczyznę $\alpha_i$ w pewnym punkcie $T_i$ . W trójkącie $OA_iT_i$ kąt $A_i$ jest prosty, zachodzi zatem równość $OA_i^2 = OT_i \cdot OS$ , stąd

$ OT_i = \frac{OA_i^2}{OS}. $

Odcinek $OA_i$ równa się promieniowi kuli, więc odcinek $OT_i$ ma dla każdego $i$ tę samą długość, a ponieważ wszystkie punkty $T_i$ leżą na tej samej półprostej $OS$ , więc się pokrywają.

b) Załóżmy, że wszystkie płaszczyzny $\alpha_i$ są równoległe do prostej $l$ lub wszystkie mają punkt wspólny $T$ . W pierwszym przypadku wszystkie odcinki $OA_i$ są prostopadłe do prostej $l$ , więc leżą w jednej płaszczyźnie $\pi$ , wobec czego wszystkie punkty $A_i$ leżą na okręgu $k$ , według którego płaszczyzna $\pi$ przecina powierzchnię danej kuli. W drugim przypadku prosta $TA_i$ jest dla każdego $i$ styczna do powierzchni kuli, więc jest prostopadła do promienia $OA_i$ . Niech $A_iS_i$ będzie wysokością trójkąta prostokątnego $OA_iT$ na przeciwprostokątną $OT$ ; wówczas $OA_i^2 = OT \cdot OS_i$ , zatem

$ OS_i = \frac{OA_i^2}{OT}, $

skąd wynika, że wszystkie odcinki $OS_i$ są równe. Ponieważ zaś wszystkie punkty $S_i$ leżą na odcinku $OT$ , więc się pokrywają. Zatem wszystkie odcinki $A_iS_i$ leżą w jednej płaszczyźnie $\pi$ , wobec czego wszystkie punkty $A_i$ leżą na przecięciu płaszczyzny $\pi$ z powierzchnią kuli, tj. na pewnym okręgu $k$ .