XIX OM

XIX Olimpiada Matematyczna

Opracowanie rozwiązań: Stefan Straszewicz

XIX OM - I etap

I etap XIX Olimpiady Matematycznej

XIX OM - I - Zadanie 1

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

Rozwiązać układ równań

$ (1) \qquad \begin{cases} |x + y| &= 1 \\ |x| + |y| &= 1. \end{cases} $

Rozwiązanie

Układ równań (1) jest równoważny układowi

$ (2) \qquad |x + y| = 1,\ |x + y|= |x| + |y|. $

Drugie równanie układu (2) jest spełnione wtedy i tylko, wtedy, gdy liczby $x$ i $y$ są tego samego znaku, lub gdy któraś z nich jest zerem, tzn. gdy $xy \geq 0$ . Układ (2) jest więc równoważny układowi

$ (3) \qquad |x + y| = 1,\ xy \geq 0. $

Układ (3) jest równoważny alternatywie

$ (4) \qquad x+y=1, \ xy \geq 0 $

lub

$ (5) \qquad x + y = - 1,\ xy \geq 0. $

Układy (4) i (5) są odpowiednio równoważne układom

$ (6) \qquad y = 1 - x, \ x(1 - x) \geq 0, $

$ (7) \qquad y = - 1-x,\ x (- 1 - x) \geq 0. $

Ponieważ $x(1 - x) \geq 0 \Longleftrightarrow 0 \leq x \leq 1$ , a $x(- 1 - x) \geq 0 \Longleftrightarrow - 1 \leq x \leq 0$ , więc układy (6) i (7) są odpowiednio równoważne układom

$ (8) \qquad 0 \leq x \leq 1,\ y=1-x, $

$ (9) \qquad - 1 \leq x \leq 0,\ y= -1 - x. $

Okazało się, że para liczb $(x, y)$ jest rozwiązaniem układu (1) wtedy i tylko wtedy, gdy spełnia układ warunków (8) lub układ warunków (9). A zatem:

Rozwiązaniami układu równań (1) są te i tylko te pary liczb $(x,y)$ , w których $x$ jest dowolną liczbą przedziału $-1 \leq x \leq 1$ , a $y = 1 - x$ , gdy $x \geq 0$ oraz $y = - 1 - x$ , gdy $x \leq 0$ .

Wynik ten możemy również uzyskać przez rozważenie wykresów równań (1). Wykresem pierwszego równania są dwie proste równoległe $y = 1 - x$ i $y = - 1 - x$ , a wykresem drugiego równania jest obwód kwadratu o wierzchołkach $(1,0)$ , $(0,1)$ , $(-1,0)$ , $(0,-1)$ . Rozwiązania układu (1) przedstawiają punkty dwóch odcinków wspólnych obu wykresom (rys. 1).

XIX OM - I - Zadanie 2

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

Niech $p(n)$ oznacza liczbę liczb pierwszych nie większych od liczby naturalnej $n$ . Dowieść, że jeżeli $n \geq 8$ , to $p(n) < \frac{n}{2}$

Rozwiązanie

Jeżeli $n$ jest liczbą parzystą, to w zbiorze liczb naturalnych od $1$ do $n$ jest $\frac{n}{2}-1$ liczb parzystych różnych od $2$ , a więc złożonych, oraz co najmniej jedna liczba nieparzysta, mianowicie $1$ , która nie jest liczbą pierwszą. Liczby pierwsze należą do zbioru pozostałych $\frac{n}{2}$ liczb, więc $p(n) \leq \frac{n}{2}$ .

Jeżeli $n$ jest liczbą nieparzystą co najmniej równą $9$ , to w zbiorze liczb naturalnych od $1$ do $n$ znajduje się $\frac{n-1}{2}-1$ liczb parzystych różnych od $2$ oraz są w nim co najmniej dwie liczby nieparzyste, mianowicie $1$ i $9$ , nie będące liczbami pierwszymi. Liczby pierwsze należą do zbioru pozostałych $n - \left(\frac{n-1}{2}-1 \right) - 2 = \frac{n-1}{2}$ liczb, więc $p(n)< \frac{n}{2}$ .

Zatem dla każdego naturalnego $n$ :

$ n \geq 8 \Longrightarrow p(n) \leq \frac{n}{2}. $

XIX OM - I - Zadanie 3

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

Na dwóch prostych skośnych leżą odcinki $AB$ i $CD$ , których środkami są odpowiednio punkty $M$ i $N$ . Dowieść, że

$ MN < \frac{1}{2}(AD + BC). $

Rozwiązanie

Niech $P$ będzie środkiem odcinka $AC$ (rys. 2). Punkt $P$ nie może leżeć na prostej $MN$ , gdyż wówczas proste $AB$ i $CD$ leżałyby w płaszczyźnie wyznaczonej przez proste $AC$ i $MN$ , więc nie byłyby skośne. W takim razie

$ (1) \qquad MN < MP + PN. $

W trójkącie $ABC$ odcinek $MP$ łączący środki boków $AB$ i $AC$ jest równy połowie boku $BC$ :

$ (2) \qquad MP = \frac{1}{2} BC. $

Analogicznie

$ (3) \qquad PN = \frac{1}{2} AD. $

Ze związków (1), (2), (3) wynika, że

$ MN < \frac{1}{2}(AD + BC). $

XIX OM - I - Zadanie 4

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

Na płaszczyźnie dane są proste równoległe $a$ i $b$ oraz punkt $M$ leżący na zewnątrz pasa ograniczonego tymi prostymi. Wyznaczyć na prostych $a$ i $b$ odpowiednio punkty $A$ i $B$ w taki sposób, żeby odcinek $AB$ był prostopadły do $a$ i $b$ , a przy tym kąt $AMB$ był największy.

Rozwiązanie

Niech $AB$ będzie odcinkiem o końcach $A \in a$ i $B \in b$ , prostopadłym do prostych $a$ i $b$ , a $N$ - punktem symetrycznym do punktu $M$ względem prostej równoległej do prostych $a$ i $b$ i od nich równoodległej (rys. 4).

Okrąg o średnicy $AB$ leży w pasie ograniczonym prostymi $a$ i $b$ , więc punkt $M$ leży na zewnątrz tego okręgu, wobec czego $\measuredangle AMB = \alpha$ jest mniejszy od $90^\circ$ . W takim razie maksimum kąta $\alpha$ zachodzi równocześnie z maksimum $\sin \alpha$ , gdyż dla kątów od $0^\circ$ do $90^\circ$ sinus kąta rośnie wraz z kątem.

Gdy odcinek $AB$ leży na prostej $MN$ , wówczas $\sin \alpha = 0$ .

Gdy punkty $A$ , $B$ , $M$ są wierzchołkami trójkąta, a $r$ oznacza promień okręgu opisanego na tym trójkącie, to $\sin \alpha = \frac{AB}{2r}$ . Odcinek $MN$ jest cięciwą tego okręgu, więc $MN \leq 2r$ , zatem

$ \sin \alpha \leq \frac{AB}{MN}. $

Stąd wynika, że maksimum $\sin \alpha$ , więc też maksimum $\alpha$ zachodzi wtedy, gdy $\sin \alpha = \frac{AB}{MN}$ tj. gdy

$ 2r = MN, $

co oznacza, że punkty $A$ i $B$ leżą na okręgu o średnicy $MN$ .

XIX OM - I - Zadanie 5

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

Dany jest zbiór $2n$ ( $n \geq 2$ ) różnych liczb. Jak podzielić ten zbiór na pary, żeby suma iloczynów liczb poszczególnych par była a) najmniejsza, b) największa?

Rozwiązanie

Przez podział zbioru liczb $Z$ na pary rozumiemy taki zbiór par liczb zbioru $Z$ , że każda liczba zbioru $Z$ należy do jednej i tylko jednej pary.

Oznaczmy dane liczby literami $a_1, a_2, \ldots, a_{2n}$ w taki sposób, że

$ (1) \qquad a_1< a_2< \ldots < a_{2n}. $

Liczba wszystkich podziałów zbioru liczb (1) na pary jest skończona, więc istnieje taki podział $P$ , dla którego suma iloczynów liczb poszczególnych par ma najmniejszą wartość. Oznaczmy tę sumę literą $S_P$ .

Jednym z wyrazów sumy $S_P$ musi być iloczyn $a_1a_{2n}$ . W sumie $S_P$ występuje bowiem wyraz $a_1a_k$ , którego jednym czynnikiem jest $a_1$ . Gdyby było $a_k \ne a_{2n}$ , wówczas suma $S_P$ miałaby inny wyraz z czynnikiem $a_{2n}$ , np. $a_la_{2n}$ , gdzie $l \ne k$ i $l \ne 1$ . Wtedy

$ \begin{split} a_1 a_k + a_la_{2n} & = a_1 a_{2n} + a_k a_l + (a_1 a_k - a_1 a_{2n}) + (a_l a_{2n} - a_k a_l) = \\ & = a_1 a_{2n} + a_1 (a_k - a_{2n}) + a_l(a_{2n} - a_k) = \\ & = a_1 a_{2n} + a_k a_l + (a_{2n} - a_k)(a_l - a_1), \end{split} $

więc na mocy (1) zachodziłaby nierówność

$ (2) \qquad a_1 a_k + a_l a_{2n} > a_1 a_{2n} + a_k a_l. $

W takim razie zastępując pary $(a_1, a_k)$ i $(a_l, a_{2n})$ podziału $P$ parami $(a_1, a_{2n})$ i $(a_k, a_l)$ otrzymalibyśmy taki podział $Q$ danych liczb na pary, przy których suma $S_Q$ iloczynów liczb poszczególnych par spełniałaby na skutek (2) nierówność

$ S_Q< S_P $

wbrew założeniu, że najmniejszą taką sumą jest $S_P$ .

Tak samo stwierdzamy, że suma $S_P - a_1a_{2n}$ musi mieć wyraz $a_2a_{2n-1}$ , suma $S_P -a_1a_{2n} - a_2a_{2n-1}$ - wyraz $a_3a_{2n-2}$ itd.

Zatem

$ S_P = a_1a_{2n} + a_2a_{2n-1} + \ldots + a_na_{n-1} $

tj. w podziale $P$ występują pary $(a_1 a_{2n}), (a_2, a_{2n-1}), \ldots, (a_n, a_{n-1})$ .

W analogiczny sposób dowodzi się, że największa suma $S_T$ iloczynów liczb poszczególnych par występuje przy podziale $T$ danego zbioru na pary $(a_1 a_2), (a_3, a_4),\ldots ,(a_{2n-1}, a_{2n})$ , tj. że

$ ST = a_1a_2 + a_3a_4 + \ldots + a_{2n-1} a_{2n}. $

XIX OM - I - Zadanie 6

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

Dowieść, że jeżeli wielomian $F(x)$ o współczynnikach całkowitych ma pierwiastek $\frac{p}{q}$ , gdzie $p$ i $q$ są liczbami całkowitymi względnie pierwszymi, to $p - q$ jest dzielnikiem liczby $F(1)$ , a $p + q$ jest dzielnikiem liczby $F(-1)$ .

Rozwiązanie

Wprowadźmy zamiast $x$ zmienną $y = qx$ . Równość (1) otrzymuje postać

$ F \left( \frac{y}{q} \right) = a_0 \left( \frac{y}{q} \right)^n + a_1 \left( \frac{y}{q} \right)^{n-1} + \ldots + a_n. $

Rozważmy wielomian

$ q^n F \left( \frac{y}{q} \right) = a_0y^n + a_1 q y^{n-1} + \ldots + a_nq^n, $

którego współczynniki są liczbami całkowitymi. Ma on pierwiastek całkowity $y=p$ , wobec czego

$ q^n F \left( \frac{y}{q} \right) = (y~-p)Q(y), $

gdzie $Q(y)$ jest wielomianem o współczynnikach całkowitych*).

Podstawiając do tej równości $y = q$ otrzymujemy

$ q^n F (1) = (q-p)Q(p). $

Otóż liczby $q^n$ i $q -p$ są względnie pierwsze; gdyby bowiem jakaś liczba pierwsza była wspólnym dzielnikiem liczb $q^n$ i $q-p$ , byłaby ona również wspólnym dzielnikiem liczb $q$ i $q - p$ , a więc też wspólnym dzielnikiem liczb $q$ i $q-(q-p)=p$ wbrew założeniu.

W takim razie liczba $q-p$ jest dzielnikiem liczby $F(1)$ , c.n.d.

Uwaga. Jeszcze krótsze rozwiązanie zadania uzyskamy opierając się na twierdzeniu następującym:

Jeżeli wielomian $F(x)$ o współczynnikach całkowitych ma pierwiastek wymierny $\frac{q}{p}$ ( $p$ , $q$ - liczby całkowite względnie pierwsze), to iloraz wielomianu $F(x)$ przez $x - \frac{p}{q}$ jest wielomianem o współczynnikach całkowitych.

Udowodnimy to twierdzenie. Niech

$ (*) \qquad F(x) = a_0x^n + a_1x^{n-1} + \ldots + a_n= \left( x - \frac{p}{q} \right) (c_0x^{n-1} + c_1x^{n-2} + \ldots + c_{n-1}), $

gdzie liczby $a_0, a_1, \ldots,a_n$ są całkowite. Mamy dowieść, że liczby $c_0, c_1, \ldots, c_{n-1}$ są całkowite.

Współczynniki przy $x^n$ po obu stronach równości (*) są równe, więc $c_0 = a_0$ .

Zauważmy, że

$ a_0 \left( \frac{p}{q} \right)^{n} +a_1 \left( \frac{p}{q} \right)^{n-1} + \ldots + a_n =0, \textrm{ więc } a_0 p^n + a_1p^{n-1} q + \ldots + a_1 q^n = 0, $

skąd wynika, że $a_0$ , zatem również $c_0$ jest podzielne przez $q$ . Dowód twierdzenia przeprowadzimy metodą indukcji.

Gdy $n = 1$ , teza twierdzenia jest oczywista, iloraz $F(x)$ przez $x - \frac{p}{q}$ jest wtedy równy $c_0$ .

Przypuśćmy, że teza twierdzenia jest prawdziwa dla pewnego $n$ i niech

$ F(x) = a_0x^{n+1} + a_1x^n + \ldots + a_{n+1} = \left( x - \frac{p}{q}\right) (c_0x^n + c_1x^{n-1} + \ldots + c_n). $

Utwórzmy wielomian stopnia $n$

$ F(x) - \left(x - \frac{p}{q} \right) c_0 x^n = \left( a_1 - \frac{p}{q} c_0 \right) x^n + a_2 x^{n-1} + \ldots + a_{n+1} = \left(x - \frac{p}{q} \right) (c_1x^{n-1} + \ldots + c_n). $

Ponieważ liczba $c_0 = a_0$ jest podzielna przez $q$ , więc jest to wielomian o współczynnikach całkowitych. Według założenia indukcyjnego liczby $c_1, c_2, \ldots, c_n$ są całkowite, tzn. teza twierdzenia jest prawdziwa dla wielomianów stopnia $n + 1$ .

Twierdzenie zostało udowodnione.

Rozwiązanie poprzedniego zadania jest teraz natychmiastowe. Jeśli bowiem

$ F(x) = \left(x - \frac{p}{q} \right) Q(x) $

i wielomian $F(x)$ ma współczynniki całkowite, to wielomian $Q(x)$ ma również współczynniki całkowite i

$ F(1) = \left(x1- \frac{p}{q} \right) Q(1), $

zatem

$ qF(1)= (q-p)Q(1), $

skąd wynika, że liczba $p - q$ jest dzielnikiem liczby $F(1)$ .

XIX OM - I - Zadanie 7

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

Punkty $D, E, F$ są środkami boków trójkąta $ABC$ . Dowieść, że jeżeli okręgi opisane na trójkątach $ABC$ i $DEF$ są styczne, to punkt styczności jest jednym z punktów $A$ , $B$ , $C$ i trójkąt $ABC$ jest prostokątny.

Rozwiązanie

Przypuśćmy, że okrąg $c$ opisany na trójkącie $ABC$ i okrąg $k$ opisany na trójkącie $DEF$ są styczne w punkcie $T$ (rys. 5).

Trójkąt $DEF$ leży wewnątrz okręgu $c$ , więc styczność okręgów $c$ i $k$ jest wewnętrzna i środek $S$ okręgu $k$ leży na półprostej $TO$ . Trójkąt $DEF$ jest podobny do trójkąta $ABC$ w stosunku $1 \colon 2$ , więc promień $TS$ okręgu $k$ jest dwa razy mniejszy od promienia $TO$ okręgu $c$ ; zatem punkt $S$ jest środkiem odcinka $TO$ , z $TO$ - średnicą okręgu $k$ .

Punkty $D$ , $E$ , $F$ okręgu $k$ są różne, więc co najwyżej jeden z nich może się pokrywać z punktem $O$ . Przypuśćmy, że np. punkty $D$ i $E$ są różne od punktu $O$ .

Cięciwa $BC$ okręgu $c$ , której środkiem jest punkt $D$ , jest prostopadła do prostej $OD$ , więc jeden z kątów $ODB$ i $ODC$ jest wpisany w okrąg $k$ , wobec czego punkt $B$ albo punkt $C$ znajduje się w końcu $T$ średnicy $OT$ okręgu $k$ . Tak samo jeden z końców cięciwy $AC$ leży w punkcie $T$ . Zatem w punkcie $T$ znajduje się wierzchołek $C$ trójkąta $ABC$ . W takim razie środek $F$ boku $AB$ leży w punkcie $O$ . Gdyby bowiem punkt $F$ był różny od punktu $O$ , wówczas cięciwa $AB$ okręgu $c$ byłaby prostopadła do prostej $OF$ , więc jeden z kątów prostych $OFA$ i $OFB$ byłby wpisany w okrąg $k$ , wobec czego punkt $A$ lub punkt $B$ znajdowałby się w punkcie $T$ , tzn. pokrywałby się z punktem $C$ , co jest niemożliwe.

Kąt $C$ trójkąta $ABC$ jest kątem wpisanym w okrąg $c$ , którego ramiona przechodzą przez końce średnicy $AB$ tego okręgu, czyli jest kątem prostym.

XIX OM - I - Zadanie 8

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

Dany jest czworościan $ABCD$ , w którym $AB = BC = CD = DA = 1$ . Dowieść, że objętość $V$ czworościanu $ABCD$ spełnia nierówność

$ V\leq \frac{2}{27} \sqrt{3}. $

Rozwiązanie

Z równości boków czworokąta $ABCD$ wynika, że płaszczyzna przechodząca przez prostą $BD$ i przez środek $M$ odcinka $AC$ jest płaszczyzną symetrii czworościanu $ABCD$ . Istotnie, środkowa $DM$ trójkąta równoramiennego $ADC$ jest prostopadła do jego podstawy $AC$ , tak samo $BM$ jest prostopadłe do $AC$ ; zatem prosta $AC$ prostopadła do dwóch różnych prostych $BM$ i $DM$ płaszczyzny $BMD$ jest prostopadła do tej płaszczyzny. Ponieważ zaś $AM = MC$ , więc punkty $A$ i $C$ są symetryczne względem płaszczyzny $BMD$ . Stąd wynika, że czworościany $ABMD$ i $CBMD$ , na które płaszczyzna $BMD$ rozcina czworościan $ABCD$ są symetryczne względem tej płaszczyzny (rys. 6).

Objętość $V$ czworościanu $ABCD$ jest zatem równa podwojonej objętości czworościanu $ABMD$ o podstawie $BMD$ i wysokości $AM$ :

$ (1) \qquad V = 2 \cdot \frac{1}{3} (\textrm{pole } BMD) AM. $

Niech $AM = x$ , wtedy $BM = MD = \sqrt{AB^2 -AM^2} = \sqrt{ 1 - x^2}$ , $\textrm{pole } BMD = \frac{1}{2} BM \cdot MD \cdot \sin \measuredangle BMD \leq \frac{1}{2} BM \cdot MD = \frac{1}{2} (1 - x^2)$ , więc według (1)

$ (2) \qquad V \leq \frac{1}{3} (1 - x^2) x,\ \textrm{gdzie } 0 < x < 1. $

Znajdziemy maksimum funkcji $y =(1 - x^2)x$ w przedziale $(0,1)$ . Zadanie to można sprowadzić do wyznaczenia maksimum iloczynu trzech czynników, których suma jest stała. W tym celu zauważmy, że iloczyn $(1 - x^2) x = (1 + x)(1 - x) x$ osiąga maksimum dla tych samych wartości $x$ , co proporcjonalny doń iloczyn $(m + mx) (n - nx) x$ , gdzie $m$ i $n$ oznaczają dowolne liczby dodatnie.

Suma czynników tego drugiego iloczynu równa się $m + n + (m - n + 1) x$ . Gdy $m$ i $n$ spełniają równanie

$ (3) \qquad m - n + 1 = 0, $

suma ta wynosi $m + n$ , więc jest niezależna od $x$ . Wiemy zaś, że maksimum iloczynu $(m + mx) (n - nx) x$ o stałej sumie czynników zachodzi wówczas, gdy czynniki te są równe, tj. gdy

$ (4) \qquad m + mx = n - nx = x. $

Liczby $x$ , $m$ , $n$ spełniają prócz tego nierówności

$ (5) \qquad x >0,\ m >0,\ n > 0. $

Stwierdzamy za pomocą łatwego rachunku, że układ warunków (3), (4), (5) ma dokładnie jedno rozwiązanie

$ x = \frac{\sqrt{3}}{3},\ m = \frac{\sqrt{3}-1}{2},\ x = \frac{\sqrt{3}+1}{2}. $

Na mocy przytoczonego wyżej twierdzenia o maksimum iloczynu wartość iloczynu $(1 - x^2)x$ jest największa, gdy $x = \frac{\sqrt{3}}{3}$ , tzn.

$ (6) \qquad (1-x^2)x \leq (1 -\frac{1}{3}) \cdot \frac{\sqrt{3}}{3} = \frac{2\sqrt{3}}{9} $

dla każdego $x$ z przedziału $(0,1)$ .

Z (6) i (2) wynika, że

$ V \leq \frac{2\sqrt{3}}{27}, \textrm{ c.n.d.} $

Uwaga 1. Maksimum funkcji $y = (1 - x^2)x$ w przedziale $0 < x < 1$ znajdziemy znacznie prościej za pomocą rachunku różniczkowego. Pochodna $y' = 1 - 3x^2$ przybiera w tym przedziale wartość $0$ tylko dla $x = \frac{\sqrt{3}}{3}$ . Ponieważ druga pochodna $y'' = - 6x$ jest dla $x = \frac{\sqrt{3}}{3}$ ujemna, więc funkcja osiąga w tym punkcie maksimum lokalne, które jest zarazem największą wartością funkcji w całym przedziale $(0,1)$ .

Uwaga 2. Powyższe rozwiązanie zadania można zmodyfikować jak następuje.

Skorzystamy ze wzoru

$ (*) \qquad V = \frac{1}{3} (\textrm{pole } ABC)h, $

gdzie $h$ jest wysokością czworościanu $ABCD$ z wierzchołka $D$ .

Otóż

$ \textrm{pole } ABC = AM \cdot BM = x \sqrt{1 - x^2}. $

Wysokość $h$ czworościanu jest zarazem wysokością trójkąta $BMD$ z wierzchołka $D$ , więc możemy ją wyrazić w zależności od boków $BM = DM = \sqrt{1 -x^2}$ i $BD$ .

Oznaczając $BD = 2y$ otrzymujemy

$ h = \frac{2y \sqrt{1-x^2-u^2}}{\sqrt{1-x^2}}. $

Podstawiając powyższe wartości pola $ABC$ i $h$ do wzoru (*) znajdujemy

$ V = \frac{2}{3} xy \sqrt{1 - x^2-y^2}, $

zatem

$ V^2 = \frac{4}{9} x^2y^2 (1-x^2-y^2). $

Ponieważ suma czynników $x^2$ , $y^2$ , $1 - x^2 - y^2$ iloczynu $x^2y^2(1 - x^2 - y^2)$ jest stała, a mianowicie jest równa $1$ , więc ten iloczyn jest największy wtedy, gdy te czynniki są równe, tj. gdy $x^2 = y^2 = 1 - x^2 - y^2= \frac{1}{3}$ . Zatem

$ V^2 \leq \frac{4}{9} \cdot \left( \frac{1}{3} \right)^3. $

Stąd

$ V \leq \frac{2\sqrt{3}}{27}. $

XIX OM - I - Zadanie 9

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

Dowieść, że jeżeli $a_1, a_2, \ldots, a_n$ oznaczają liczby $1, 2, \ldots, n$ ustawione w dowolnym porządku, a $n$ jest liczbą nieparzystą, to liczba $N = (a_1 - 1)(a_2 - 2) \ldots (a_n - n)$ jest parzysta.

Rozwiązanie

Gdyby iloczyn $N$ był liczbą nieparzystą, to każdy z jego $n$ czynników $a_1 - 1, a_2 - 2, \ldots, a_n - n$ byłby też liczbą nieparzystą. Przy nieparzystym $n$ suma tych czynników byłaby liczbą nieparzystą, co nie jest prawdą, gdyż

$ (a_1 - 1) + (a_2 - 2) + \ldots + (a_n - n) = (a_1 + a_2 + \ldots + a_n) -(1 +2 + \ldots + n) = 0. $

XIX OM - I - Zadanie 10

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

Dowieść, że wielomian $W$ zmiennej $x$ określony wzorem

$ (1) \qquad W(x)=(x - a)^2 (x - b)^2 + l, $

gdzie $a$ i $b$ oznaczają liczby całkowite, nie jest iloczynem dwóch wielomianów zmiennej $x$ stopnia dodatniego mających współczynniki całkowite.

Rozwiązanie

Przypuśćmy, że twierdzenie, które mamy udowodnić, nie jest prawdziwe, tj. że dla każdego $x$

$ (2) \qquad (x-a)^2(x-b)^2+1 = P(x)Q(x), $

gdzie $P(x)$ i $Q(x)$ są wielomianami stopnia dodatniego o współczynnikach całkowitych. Lewa strona wzoru (2) jest dla każdego $x$ dodatnia, więc wielomian $P(x)$ i tak samo wielomian $Q(x)$ nie ma pierwiastków (rzeczywistych), nie może być zatem stopnia nieparzystego, a ponieważ stopień $P(x)$ + stopień $Q(x)$ = stopień $P(x) \cdot Q(x) = 4$ , więc $P(x)$ i $Q(x)$ są wielomianami stopnia drugiego o wyróżnikach ujemnych. Jeśli najwyższymi wyrazami wielomianów $P(x)$ i $Q(x)$ są odpowiednio $kx^2$ i $lx^2$ ( $k$ , $l$ - licżby całkowite), to iloczyn $kx^2 \cdot lx^2$ równa się najwyższemu wyrazowi $x^4$ lewej strony wzoru (2) więc $kl = 1$ , zatem $k = l=1$ lub $k = l = - 1$ . Drugi z tych przypadków możemy sprowadzić do pierwszego zastępując wielomiany $P(x)$ i $Q(x)$ odpowiednio wielomianami $- P(x)$ i $- Q(x)$ . Założenie (2) jest zatem równoważne założeniu

$ (3) \qquad (x - a)^2(x - b)^2+ 1 = (x^2 + mx + n)(x^2 +px+q) $

dla każdego $x$ , gdzie liczby $m$ , $n$ , $p$ , $q$ są całkowite, a trójmiany $x^2 + mx + n$ i $x^2 + px+ q$ są dla każdego $x$ dodatnie. Wykażemy, że założenie to prowadzi do sprzeczności: .

Przekształćmy równość (3) podstawiając $x = y + a$ :

$ \begin{split} y^2(y + a - b)^2 + 1 = [(y + a)^2 + m(y + a) + n] [(y + a)^2 + p(y + a) + q] = \\ = [y^2 + (2a +m)y + a^2 + ma + n] [y^2 + (2a + p)y + a^2+pa+ q]. \end{split} $

Wprowadzając oznaczenia $a - b = c$ , $2a + m = r$ , $a^2 + ma + n = s$ , $2a + p = t$ , $a^2 + pa + q = u$ otrzymujemy stąd dla każdego $y$ równość

$ (4) \qquad y^2(y + c)^2+1= (y^2 + ry + s)(y^2 + ty + u), $

gdzie liczby $c$ , $r$ , $s$ , $t$ , $u$ są według założenia (3) całkowite, a przy tym liczby $s$ i $u$ są dodatnie.

Porównując współczynniki przy jednakowych potęgach $y$ po obu stronach równości (4) otrzymujemy

$ (5) \qquad r + t = 2c $

$ (6) \qquad s + u + rt = c^2 $

$ (7) \qquad ru + st = 0. $

$ (8) \qquad su=1. $

Ponieważ liczby $s$ i $u$ są całkowite i dodatnie, więc z (8) wynika, że $s = u = 1$ , wobec czego na mocy (7) i (5) $r + t = 0$ , $c = 0$ , zatem według (6) $2 - r^2 = 0$ , co nie jest prawdą, gdyż $r$ jest liczbą całkowitą. Zatem rozkład (3) nie istnieje.

XIX OM - I - Zadanie 11

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

Na płaszczyźnie dany jest wielokąt, którego wszystkie kąty są równe. Dowieść, że suma odległości dowolnego punktu leżącego w wielokącie od prostych zawierających boki wielokąta jest stała.

Rozwiązanie

Dla wielokąta foremnego teza twierdzenia jest prawdziwa. Istotnie, odległość $x_i$ punktu $P$ wielokąta $A_1A_2\ldots A_n$ od prostej $A_iA_{i+1}$ (rys.7) jest równa ilorazowi podwojonego pola $S_i$ trójkąta $A_iP A_{i+1}$ *) przez długość boku $A_iA_{i+1}$ wielokąta. Gdy wszystkie boki mają tę samą długość a, to

$ \sum_{i=1}^n x_i = \sum_{i=1}^n \frac{2S_i}{a} = \frac{2}{a} \sum_{i=1}^n S_i = \frac{2}{a} \cdot S, $

gdzie $S$ oznacza pole wielokąta.

Niech $W$ będzie dowolnym wielokątem o równych kątach, a punkty $A_1, A_2, \ldots,A_n$ - jego wierzchołkami. Wielokąt $W$ jest wypukły, gdyż w wielokącie niewypukłym kąty wklęsłe są większe od wypukłych. Można wyznaczyć taki wielokąt foremny $W_1$ o wierzchołkach $B_1, B_2,\ldots, B_n$ zawierający w swym wnętrzu wielokąt $W$ , że dla każdego $i$ bok $B_iB_{i+1}$ wielokąta $W_1$ jest równoległy do boku $A_iA_{i+1}$ wielokąta $W$ i leży po przeciwnej stronie prostej $A_iA_{i+1}$ niż wielokąt $W$ . Aby taki wielokąt skonstruować, wystarczy wykreślić dowolny okrąg zawierający wielokąt $W$ i opisać na nim wielokąt foremny $W_1$ o $n$ bokach obierając jego pierwszy bok $B_1B_2$ na tej stycznej do okręgu równoległej do prostej $A_1A_2$ , która leży po przeciwnej stronie prostej $A_1A_2$ niż wielokąt $W$ (rys. 8).

Z założenia równości kątów wielokąta $W$ wynika, że jego kąty są równe kątom wielokąta $W_1$ , np. $\measuredangle B_1B_2B_3 = \measuredangle A_1A_2A_3$ , wobec czego bok $B_2B_3$ jest równoległy do prostej $A_2A_3$ i leży na zewnątrz kąta wypukłego $A_1A_2A_3$ , a więc po przeciwnej stronie prostej $A_2A_3$ niż wielokąt $W$ . W ten sam sposób stwierdzamy kolejno, że każdy z pozostałych boków wielokąta $W_1$ ; a tym samym cały wielokąt $W_1$ spełnia postawiony mu warunek.

Niech $x_i$ oznacza odległość punktu $P$ wielokąta $W$ od prostej $A_iA_{i+1}$ , $y_i$ - odległość punktu $P$ od prostej $B_iB_{i+1}$ , a $d_1$ - odległość prostych $A_iA_{i+1}$ i $B_iB_{i+1}$ , gdzie $i= 1,2\ldots,n$ , przy czym $A_{n+1} = A_1 B_{n+1} = B_1$ . Wówczas $x_i = y_i - d_i$ , zatem

$ \sum_{i=1}^n x_i = \sum_{i=1}^n y_i - \sum_{i=1}^n d_i. $

Ponieważ $\sum_{i=1}^n y_i$ i tak samo $\sum_{i=1}^n d_i$ ma dla każdego punktu $P$ wielokąta $W$ tę samą wartość, więc to samo dotyczy sumy $\sum_{i=1}^n x_i$ , c.n.d.

XIX OM - I - Zadanie 12

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

Dany jest czworościan $A_1A_2A_3A_4$ . Udowodnić, że jeżeli punkty $P_1, P_2, P_3, P_4$ są rzutami prostokątnymi pewnego punktu $P$ przestrzeni odpowiednio na proste $A_1A_2, A_2A_3, A_3A_4, A_4A_1$ , to suma

$ A_1P_1^2 + A_2P_2^2 + A_3P_3^2 + A_4P_4^2 $

jest najmniejsza wtedy, gdy punkt $P$ jest środkiem kuli opisanej na czworościanie A $A_1A_2A_3A_4$ .

Rozwiązanie

Dla uproszczenia zapisów wprowadzimy następujące oznaczenia długości odcinków $A_iA_{i+1} = a_i$ , $PA_i = x_i$ , $P_iA_i = y_i$ ( $i = 1, 2, 3,4$ , przy czym wskaźnik $i+ 1$ dla $i = 4$ zastępujemy przez $1$ ).

Dla każdej czwórki punktów $A_i$ , $A_{i+1}$ , $P$ , $P_i$ zachodzi związek

$ (1) \qquad y_i^2 = \left( \frac{x_i^2 - x_{i+1}^2 + a_i^2}{2a_i} \right)^2. $

Istotnie, jeśli punkty $A_i$ , $A_{i+1}$ , $P$ nie są współliniowe, to według twierdzenia o kwadracie boku trójkąta (rys. 9)

$ (2) \qquad x^2_{i+1} = x^2_{i} + a^2_i- 2a_iy_i, $

gdy kąt wypukły $PA_iA_{i+1}$ jest ostry lub prosty, natomiast

$ (3) \qquad x^2_{i+1} = x^2_{i} + a^2 + 2a_iy_i, $

gdy kąt wypukły $PA_iA_{i+1}$ jest rozwarty.

Jeśli punkty $A_i$ , $A_{i+1}$ , $P$ są współliniowe, to punkt $P$ pokrywa się z punktem $P_i$ (rys. 10). Gdy punkt $P$ leży na odcinku $A_iA_{i+1}$ , wówczas

$ (4) \qquad x_{i} + x_{i+1} = a_i,\ y_i = x_{i}. $

Gdy zaś punkt $P$ leży na zewnątrz odcinka $A_iA_{i+1}$ , wtedy

$ (5) \qquad |y_i- x_{i+1}| = a_i,\ y_i=x_i. $

Otóż równość (1) wynika zarówno z każdej z równości (2) i (3), jak z każdego z układów równości (4) i (5), co stwierdzamy za pomocą prostego rachunku.

Z równości (1) otrzymujemy

$ y_i^2 = \left( \frac{(x_i^2 - x_{i+1}^2)^2 + 2a_i^2(x_i^2 - x_{i+1}^2) +a_i^4}{4a_i^2} \right)^2. $

Zatem

$ \sum_{i=1}^4 y_i^2 = \sum_{i=1}^4 \frac{(x_i^2 - x_{i+1}^2)^2}{4a_i^2} + \frac{1}{2} \sum_{i=1}^4 (x_i^2 - x_{i+1}^2) + \frac{1}{4} \sum_{i=1}^4 a_i^2. $

Ponieważ $\sum_{i=1}^4 (x_i^2 - x_{i+1}^2) = \sum_{i=1}^4 x_i^2 - \sum_{i=1}^4 x_{i+1}^2 = 0$ , więc z poprzedniej równości wynika, że

$ \sum_{i=1}^4 y_i^2 \geq \frac{1}{4} \sum_{i=1}^4 a_i^2, $

przy czym równość obu stron ma miejsce tylko wtedy, gdy $x_1= x_2 = x_3 = x_4$ , gdy zatem punkt $P$ jest środkiem kuli opisanej na czworościanie $A_1A_2A_3A_4$ , c.n.d.

Uwaga. Dowód wzoru (1) można przeprowadzić znacznie zręczniej posługując się rachunkiem wektorów. Nie trzeba wówczas rozróżniać kilku przypadków ani ułatwiać zrozumienia dowodu rysunkami. Rozumujemy jak następuje:

Dla dowolnego punktu $P$

$ \overrightarrow{A_{i+1}P} = \overrightarrow{A_iP} - \overrightarrow{A_iA_{i+1}} $

stąd

$ \begin{split} (\overrightarrow{A_{i+1}P})^2 &= (\overrightarrow{A_iP})^2 + (\overrightarrow{A_iA_{i+1}})^2 - 2 (\overrightarrow{A_iP} \cdot \overrightarrow{A_iA_{i+1}}) =\\ &= (\overrightarrow{A_iP})^2 + (\overrightarrow{A_iA_{i+1}})^2 - 2 (\overrightarrow{A_iP_i} \cdot \overrightarrow{A_iA_{i+1}}), \end{split} $

gdyż wektor $\overrightarrow{A_iP_i}$ jest rzutem prostokątnym wektora $\overrightarrow{A_iP}$ na prostą $\overrightarrow{A_iA_{i+1}}$ .

Otóż

$ \overrightarrow{A_iP_i} \cdot \overrightarrow{A_iA_{i+1}} = A_iP_i \cdot A_iA_{i+1} \cdot \cos \measuredangle P_iA_iA_{i+1}; $

Stąd i z poprzedniej równości wynika, że

$ A_iP_i \cdot \cos \measuredangle P_iA_iA_{i+1} = \frac{A_iP^2 - A_{i+1}P^2 + A_iA^2_{i+1}}{2A_iA_{i+1}}. $

Ponieważ punkty $P_i$ , $A_i$ , $A_{i+1}$ są współliniowe, więc $\cos \measuredangle P_i A_i A_{i+1}$ jest równy $1$ lub $- 1$ , zatem $\cos^2 \measuredangle P_i A_i A_{i+1}= 1$ i z poprzedniego wzoru otrzymujemy

$ A_iP_i^2 = \left( \frac{A_iP^2 - A_{i+1}P^2 + A_iA^2_{i+1}}{2A_iA_{i+1}} \right)^2. $

czyli żądany wzór (1).

XIX OM - II etap

II etap XIX Olimpiady Matematycznej

XIX OM - II - Zadanie 1

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

Dowieść, że wielomian zmiennej $x$ o współczynnikach całkowitych, którego wartość bezwzględna dla trzech różnych wartości całkowitych $x$ równa się 1, nie ma pierwiastków całkowitych.

Rozwiązanie

Załóżmy, że $f(x)$ jest wielomianem zmiennej $x$ o współczynnikach całkowitych i że

$ (1) \qquad |f(a)| = |f(b)| = |f(c)| = 1, $

gdzie $a$ , $b$ , $c$ są trzema różnymi liczbami całkowitymi.

Przypuśćmy, że $x_0$ jest pierwiastkiem całkowitym wielomianu $f(x)$ , wobec czego dla każdego $x$

$ (2) \qquad f(x) = (x - x_0)\varphi (x), $

gdzie $\varphi (x)$ jest wielomianem o współczynnikach całkowitych.

Z (1) i (2) wynika, że

$ | (a - x_0) \varphi (a)| =|a - x_0| \cdot |\varphi (a)|= 1. $

Liczba $|a - x_0|$ jest całkowita, dodatnia i jest dzielnikiem jedności, zatem $|a - x_0| = 1$ ; tak samo stwierdzamy, że $|b - x_0| = 1$ , $|c - x_0| = 1$ .

Wynika stąd, że któreś dwie z liczb $a - x_0$ , $b - x_0$ , $c - x_0$ , więc również któreś dwie z liczb $a$ , $b$ , $c$ są równe, co przeczy założeniu. Wielomian $f(x)$ nie ma więc pierwiastka całkowitego, c.n.d.

Uwaga. W rozumowaniu powyższym powoływaliśmy się na to, że współczynniki wielomianu $\varphi (x)$ są całkowite. Łatwo to wykazać.

Niech

$ f(x) = a_0 x^n+ a_1 x^{n-1} + \ldots + a_{n-1}x + a_n, $

$ \varphi(x) = c_0 x^{n-1} + c_1 x^{n-2} + \ldots + c_{n-2}x - c_{n-1}. $

Z równości $f(x) = (x - x_0) \varphi (x)$ otrzymujemy przez porównanie współczynników obu stron

$ a_0 = c_0,\ a_k = c_k - x_0 c_{k-1} \ (k = 1,2, \ldots, n- 1) $

zatem

$ c_0 = a_0,\ c_k = a_k + x_0 c_{k-1}. $

Stąd wynika, że liczba $c_0$ jest całkowita, gdy zaś $c_{k-1}$ jest całkowite ( $k = 1,2, \ldots, n - 1$ ), wtedy również $c_k$ jest całkowite. Zatem liczby $c_0, c_1, \ldots, c_{n_-1}$ są całkowite.

XIX OM - II - Zadanie 2

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

Dany jest okrąg $k$ i wewnątrz niego punkt $H$ . Wpisać w okrąg taki trójkąt, żeby punkt $H$ był punktem przecięcia wysokości trójkąta.

Rozwiązanie

Przypuśćmy, że poszukiwanym trójkątem jest trójkąt $ABC$ (rys. 11).

Ponieważ według założenia punkt $H$ znajduje się wewnątrz okręgu $k$ , więc trójkąt $ABC$ jest ostrokątny i punkt $H$ leży wewnątrz trójkąta $ABC$ . Nazwijmy $H'$ drugi punkt przecięcia prostej $AH$ z okręgiem $k$ ; leży on po przeciwnej stronie prostej $BC$ niż punkty $A$ i $H$ . Zauważmy, że punkty $H$ i $H'$ są symetryczne względem prostej $BC$ . Istotnie, proste $HH'$ i $BC$ są prostopadłe, a $\measuredangle HCB = \measuredangle H'CB$ , gdyż $\measuredangle H'CB = \measuredangle H'AB$ , bo są to kąty wpisane w ten sam łuk $H'CAB$ okręgu $k$ , a $\measuredangle H'AB = 90^\circ - \measuredangle ABC = \measuredangle HCB$ .

Stąd wysnuwamy następującą konstrukcję trójkąta $ABC$ (rys. 12).

Obieramy na okręgu $k$ dowolny punkt $A$ , wyznaczamy drugi punkt przecięcia $H'$ prostej $AH$ z okręgiem $k$ . Prowadzimy symetralną odcinka $HH'$ , która przecina okrąg w punktach $B$ i $C$ . Trójkąt $ABC$ spełnia warunek zadania, tzn. punktem przecięcia wysokości trójkąta $ABC$ jest punkt $H$ .

W rzeczy samej, oznaczając literami $K$ i $M$ odpowiednio punkty przecięcia prostych $AH$ i $CH$ z prostymi $BC$ i $AB$ stwierdzamy, że

$\measuredangle H'CB = \measuredangle H'AB$ (kąty wpisane w łuk $H'CAB$ okręgu $k$ ),

$\measuredangle H'CB = \measuredangle MCB$ (kąty symetryczne względem prostej $BC$ ),

zatem

$ \measuredangle MCB = \measuredangle H'AB, $

stąd zaś wynika, że trójkąty $MCB$ i $KAB$ o wspólnym kącie przy wierzchołku $B$ są podobne, więc $\measuredangle CMB = \measuredangle AKB = 90^\circ$ , tzn. $CM$ jest wysokością trójkąta $ABC$ , c.n.d.

XIX OM - II - Zadanie 3

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

Dowieść, że jeżeli przy okrągłym stole siedzi co najmniej 5 osób, to można je tak przesadzić, że każda osoba będzie miała obu sąsiadów innych niż poprzednio.

Rozwiązanie

\spos{1} Oznaczmy dane osoby znakami liczb naturalnych od $1$ do $n$ ( $n \geq 5$ ) i załóżmy, że przy stole osoba $1$ sąsiaduje z osobami $n$ i $2$ , osoba $2$ sąsiaduje z osobami $1$ i $3$ itd., wreszcie osoba $n$ sąsiaduje z osobami $n- 1$ i $1$ . Powiemy krótko, że liczby od $1$ do $n$ ustawione są w cykl

$ (1) \qquad 1, 2, 3, \ldots,n. $

Niech $n$ będzie liczbą nieparzystą. Ustawmy te same liczby w cykl

$ (2) \qquad 1, 3, \ldots, n, 2, \ldots,n- 1, $

w którym występują oddzielnie kolejne liczby nieparzyste i kolejne liczby parzyste. Łatwo stwierdzić, że w cyklu (2) każda liczba sąsiaduje z innymi liczbami, niż w cyklu (1). Mianowicie: $1^\circ$ Każda liczba nieparzysta z wyjątkiem $1$ i $n$ sąsiaduje w cyklu (1) z liczbami parzystymi, a w cyklu (2) z liczbami nieparzystymi; $2^\circ$ Każda liczba parzysta z wyjątkiem $2$ i $n-1$ sąsiaduje w cyklu (1) z liczbami nieparzystymi, a w cyklu (2) z liczbami parzystymi; $3^\circ$ liczba $1$ sąsiaduje w cyklu (1) z liczbami $n$ i $2$ , a w cyklu (2) z liczbami $n-1$ i $3$ , różnymi od $n$ i $2$ , gdyż $n \geq 5$ ; to samo dotyczy liczb $n$ , $2$ i $n-1$ .

Przyjmijmy z kolei, że $n$ jest liczbą parzystą i ustawmy liczby od $1$ do $n$ w cykl

$ 1,3,\ldots, n-1, 2,\ldots, n-2, n, $

w którym, podobnie jak w (2), występują oddzielnie kolejne liczby nieparzyste oraz kolejne liczby parzyste, a następnie przestawmy w nim liczby $n-2$ i $n$ :

$ (3) \qquad 1,3, \ldots, n-1, 2,\ldots, n, n-2. $

W cyklu (3) każda liczba sąsiaduje z innymi liczbami niż w cyklu (1), co stwierdzamy zupełnie podobnie jak w przypadku $n$ nieparzystego.

XIX OM - II - Zadanie 4

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

Dowieść, że jeżeli liczby $a, b, c$ , są długościami boków trójkąta, a suma liczb $x, y, z$ jest równa zeru, to

$ (1) \qquad a^2yz + b^2zx + c^2xy \leq 0. $

Rozwiązanie

Niech $U$ oznacza lewą stronę nierówności (1). Ponieważ $x + y + z = 0$ , więc $z = - (x + y)$ , zatem

$ U = -a^2y (x + y) - b^2x (x + y) + c^2xy, $

czyli

$ (2) \qquad U = (c^2 - a^2 - b^2) xy - a^2b^2 - b^2x^2. $

Liczby $a$ , $b$ , $c$ , spełniają nierówność

$ |a - b| < c < a + b. $

Stąd

$ (a- b)^2 < c^2 < (a+b)^2, $

więc

$ (3) \qquad - 2ab < c^2 -a^2-b^2 < 2ab. $

Jeżeli $xy > 0$ , to z (3) wynika, że

$ (c^2 - a^2 - b^2)xy < 2abxy, $

wobec czego z (2) otrzymujemy

$ U < 2abxy - a^2y^2 - b^2x^2 = - (ay - bx)^2 \leq 0. $

Jeżeli $xy < 0$ , to na mocy (3)

$ - 2abxy > (c^2 - a^2 - b^2)xy. $

Zatem z (2) wynika, że

$ U < -2abxy - a^2y^2 - b^2x^2 = - (ay + bx)^2 \leq 0. $

Jeżeli wreszcie $xy = 0$ , to z (2) otrzymujemy

$ U = - a^2y^2 - b^2x^2 \leq 0. $

We wszystkich przypadkach $U \leq 0$ , c.n.d.

XIX OM - II - Zadanie 5

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

Czworościany $ABCD$ i $A_1B_1C_1D_1$ są tak położone, że środki odcinków $AA_1$ , $BB_1$ , $CC_1$ , $DD_1$ są odpowiednio środkami ciężkości trójkątów $BCD$ , $ACD$ , $ABD$ i $ABC$ . W jakim stosunku są objętości tych czworościanów?

Rozwiązanie

Niech $M$ oznacza środek ciężkości trójkąta $BCD$ , a $S$ - środek ciężkości czworościanu $ABCD$ . Punkt $S$ leży na odcinku $AM$ i $SA = 3 SM$ . Punkt $A_1$ leży na przedłużeniu odcinka $AM$ i $AM = MA_1$ (rys. 14). Zatem punkt $S$ leży na odcinku $AA_1$ i dzieli go w stosunku

$ \frac{SA_1}{SA} = \frac{SM + MA_1}{SA} = \frac{SM + AM}{SA} = \frac{SM + 4SM}{3SM} = \frac{5}{3}. $

Tak samo stwierdzamy, że punkt $S$ dzieli każdy z odcinków $BB_1$ , $CC_1$ , $DD_1$ w stosunku $\frac{5}{3}$ . Czworościany $A_1B_1C_1D_1$ i $ABCD$ są zatem jednokładne w stosunku $\frac{5}{3}$ względem środka $S$ , wobec czego objętości tych czworościanów są w stosunku $\left( \frac{5}{3} \right)^2$ .

XIX OM - II - Zadanie 6

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

Na płaszczyźnie obrano $n \geq 3$ punktów nie leżących na jednej prostej. Prowadząc proste przez każde dwa z tych punktów otrzymano $k$ prostych. Dowieść, że $k \geq n$ .

Rozwiązanie

Udowodnimy najpierw twierdzenie:

Jeżeli $n \geq 3$ i $A_1, A_2, \ldots, A_n$ są punktami płaszczyzny nie leżącymi na jednej prostej, to istnieje taka prosta, która zawiera dwa i tylko dwa z tych punktów.

Dowód. Z założenia wynika, że pewne trójki punktów są niewspółliniowe. Gdy $A_i$ , $A_k$ , $A_l$ jest taką trójką, niech wówczas $d_{ikl}$ oznacza odległość punktu $A_i$ od prostej $A_kA_l$ . Zbiór liczb dodatnich $d_{ikl}$ jest skończony, więc istnieje w nim liczba, od której nie ma w tym zbiorze mniejszej. Możemy przyjąć, że liczbą tą jest np. $d_{123}$ , gdyż można to uzyskać przez odpowiednie oznaczenie punktów (rys. 15).

Prosta $A_2A_3$ nie zawiera wówczas żadnego z pozostałych punktów $A_i$ . Gdyby bowiem leżał na niej np. punkt $A_4$ , wówczas dwa z punktów $A_2$ , $A_3$ , $A_4$ , np. punkty $A_3$ i $A_4$ znajdowałyby się po tej samej stronie prostopadłej z punktu $A_1$ do prostej $A_2A_3$ , a wtedy zachodziłaby jedna z nierówności

$ d_{314} < d_{123} \textrm{ lub } d_{413} < d_{123}, $

co byłoby sprzeczne z określeniem liczby $d_{123}$ .

Opierając się na powyższym twierdzeniu, dowód twierdzenia podanego w tekście zadania uzyskujemy łatwo przez indukcję.

Gdy $n = 3$ , teza twierdzenia jest prawdziwa, gdyż wówczas $k = 3$ . Przypuśćmy, że teza twierdzenia jest prawdziwa dla pewnego naturalnego $n \geq 3$ . Niech $Z= \{ A_1,A_2,\ldots,A_n, A_{n + 1}\}$ będzie zbiorem punktów płaszczyzny, nie leżących na jednej prostej i niech $A_1A_{n+1}$ będzie taką prostą, która zawiera dokładnie dwa spośród punktów zbioru $Z$ . Z założenia wynika, że co najmniej w jednym ze zbiorów $n$ -punktowych $Z_1 = \{A_1, A_2, \ldots, A_n\}$ i $Z_2 = \{ A_2, A_3,\ldots, A_{n + 1}\}$ istnieją punkty niewspółliniowe. Niech na przykład punkty zbioru $Z$ nie leżą na jednej prostej. Według założenia indukcyjnego liczba prostych poprowadzonych przez każde dwa punkty zbioru $Z_1$ jest co najmniej równa $n$ . Ponieważ prosta $A_1A_{n+1}$ do tych prostych nie należy, gdyż przechodzi tylko przez jeden punkt zbioru $Z_1$ , więc liczba prostych poprowadzonych przez każde dwa punkty zbioru $Z$ jest co najmniej równa $n + 1$ . Dowód indukcyjny twierdzenia został przeprowadzony.

XIX OM - III etap

III etap XIX Olimpiady Matematycznej

XIX OM - III - Zadanie 1

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

III

Jaka jest największa liczba obszarów, na które można podzielić płaszczyznę prowadząc $n$ par prostych równoległych?

Rozwiązanie

Niech $f(n)$ oznacza największą liczbę obszarów, na jakie może podzielić płaszczyznę $n$ par prostych równoległych.

Obierzmy na płaszczyźnie $k + 1$ par prostych równoległych $(p_1,q_1), (p_2, q_2), \ldots, (p_k, q_k), (p_{k+1}, q_{k+1})$ .

Przypuśćmy, że $(p_1, q_1), (p_1, q_2),\ldots (p_k,q_k)$ dzielą płaszczyznę na $l$ obszarów, oraz że prosta $p_{k+1}$ przecina proste tych $k$ par w $r$ punktach, a prosta $q_{k+1}$ - w $s$ punktach. Wówczas $0 \leq r \leq 2k$ , $0 \leq s \leq 2k$ , przy czym równości $r = 2k$ , $s = 2k$ zachodzą dokładnie wtedy, gdy zarówno prosta $p_{k+1}$ jak prosta $q_{k+1}$ przecina każdą z prostych $p_1, q_1, p_2, q_2, \ldots, p_k,q_k$ ale nie przechodzi przez żaden punkt przecięcia tych prostych.

Owe $r$ punktów dzieli prostą $p_{k+1}$ , na $r+1$ części. Każda z tych części jest odcinkiem lub półprostą, a gdy $r = 0$ - całą prostą, leży w jednym z $l$ obszarów, na jakie proste $p_1, q_1, p_2, q_2, \ldots, p_k, q_k$ dzielą płaszczyznę (przy czym każda część leży w innym obszarze) i rozcina go na dwa obszary. Proste $p_1, q_1, p_2, q_2,\ldots,p_k, q_k$ oraz $p_{k+1}$ dzielą zatem płaszczyznę na $l + r + 1$ obszarów. Podobnie $s$ punktów prostej $q_{k+1}$ dzieli tę prostą na $s + 1$ części, z których każda rozcina jeden z poprzednich $l + r + 1$ obszarów na dwa obszary. Wszystkie proste $p_1, q_1, p_2, q_2, \ldots, p_k, q_k, p_{k+1}, q_{k + 1}$ dzielą zatem płaszczyznę na $l + r + s + 2$ obszarów.

Liczba ta jest największa wtedy, gdy wartości $l$ , $r$ i $s$ są największe, tj. gdy $l=f(k)$ , $r = 2k$ , $s = 2k$ . Zatem

$ \ne{1} f(k+1)=f(k) + 4k + 2. $

Otóż $f(1) = 3$ ; ze wzoru (1) otrzymujemy kolejne wartości $f(2) = 3 + 4 + 2=9$ , $f(3) = 9 + 8 + 2= 19$ itd.

Wartość $f(n)$ dla dowolnego naturalnego $n$ możemy obliczyć, podstawiając do (1) $k = 1, 2, \ldots, n - 1$ i dodając otrzymane równości

$ \sum_{k=1}^{n-1} f(k + 1) = \sum_{k=1}^{n-1} f(k) + 4\sum_{k=1}^{n-1} k + 2(n- 1). $

Stąd otrzymujemy

$ f(n)=f(1) + 4 \cdot \frac{1}{2} n(n- 1) + 2n-2, $

a po uproszczeniu

$ f(n) = 2n^2 + 1. $

XIX OM - III - Zadanie 2

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

III

Dowieść, że dla każdego naturalnego $n$

$ (1) \quad \frac{1}{3} + \frac{2}{3\cdot 5} + \frac{3}{3 \cdot 5 \cdot 7} + \ldost + \frac{n}{3 \cdot 5 \cdot 7 \cdot \ldots \cdot (2n+1)} < \frac{1}{2}. $

Rozwiązanie

Wprowadźmy oznaczenie

$ a_k = \frac{k}{3 \cdot 5 \cdot 7 \cdot \ldots \cdot (2k + 1)}. $

Zauważmy, że

$ \frac{1}{2} - a_1 = \frac{1}{2} - \frac{1}{3} = \frac{1}{2 \cdot 3},\ \frac{1}{2} (a_1+a_2) = \frac{1}{2} - \left(\frac{1}{3} + \frac{2}{3 \cdot 5} \right) = \frac{1}{2 \cdot 3 \cdot 5}. $

Nasuwa się przypuszczenie, że dla każdego naturalnego $n$

$ (2) \qquad \frac{1}{2} - (a_1 + a_2 + \ldots + a_n) = \frac{1}{2 \cdot 3 \cdot 5 \cdot \ldots \cdot (2n+1)}. $

Równość (2) łatwo udowodnić metodą indukcji. Z założenia, że równość (2) zachodzi, gdy $n$ równa się pewnej liczbie naturalnej $k$ wynika, że

$ \begin{split} \frac{1}{2} - (a_1 + a_2 &+ \ldots + a_k + a_{k+1}) =\\ &= \frac{1}{2 \cdot 3 \cdot 5 \cdot \ldots \cdot (2k+1)}- \frac{k+1}{3 \cdot 5 \cdot 7 \cdot \ldots \cdot (2k+3)} =\\ &=\frac{2k + 3 - 2(k+1)}{2 \cdot 3 \cdot 5 \cdot \ldots \cdot (2k+3)}= \frac{1}{2 \cdot 3 \cdot 5 \cdot \ldots \cdot (2k+3)}, \end{split} $

tzn., że równość (2) zachodzi także, gdy $n = k + 1$ . Stąd oraz z tego, że równość (2) jest prawdziwa, gdy $n = 1$ , wnioskujemy, że jest ona prawdziwa dla każdego naturalnego $n$ .

Z (2) wynika, że

$ a_1 + a_2+ \ldots +a_n < \frac{1}{2} $

dla każdego naturalnego $n$ , c.n.d.

Uwaga. Dowód nierówności (1) można również oprzeć na tym, że

$ (3) \qquad \begin{split} \frac{1}{1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2k-1)} - \frac{1}{1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2k+1)} =\\ =\frac{2k}{1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2k+1)} = 2 a_k. \end{split} $

Dodając stronami równości (3) dla wartości $k$ od $1$ do $n$ otrzymujemy

$ (4) \qquad 2 \sum_{k=1}^n a_k = \sum_{k=1}^n \frac{1}{1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2k-1)} - \sum_{k=1}^n \frac{1}{1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2k+1)} . $

Zauważmy, że po prawej stronie równości (4) kolejne wyrazy pierwszej sumy począwszy od drugiego aż do $n$ -go są odpowiednio równe kolejnym wyrazom drugiej sumy od pierwszego do $(n - 1)$ -go; po redukcji równość (4) otrzymuje postać

$ 2 \sum_{k=1}^n a_k = 1 - \frac{1}{1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2k+1)} , $

skąd

$ (5) \qquad \sum_{k=1}^n a_k = \frac{1}{2} - \frac{1}{2 \cdot 3 \cdot 5 \cdot \ldots \cdot (2k+1)}. $

Z (5) wynika, że

$ \sum_{k=1}^n a_k < \frac{1}{2}, $

czego należało dowieść.

XIX OM - III - Zadanie 3

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

III

W czworościanie $ABCD$ krawędzie $AD$ , $BD$ , $CD$ są równe. Na płaszczyźnie $ABC$ obrano punkty niewspółliniowe $A_1, B_1, C_1$ Proste $DA_1, DB_1, DC_1$ przecinają powierzchnię kuli opisanej na czworościanie odpowiednio w punktach $A_2, B_2, C_2$ , różnych od punktu $D$ . Udowodnić, że punkty $A_1, B_1, C_1, A_2, B_2, C_2$ leżą na powierzchni pewnej kuli.

Rozwiązanie

Sfera (tj. powierzchnia kuli) $S$ opisana na czworościanie $ABCD$ przecina płaszczyznę $ABC$ wzdłuż okręgu $k$ opisanego na trójkącie $ABC$ . Z równości $DA = DB = DC$ wynika, że sfera $t$ o środku $D$ i promieniu $r = DA$ przechodzi przez punkty $B$ i $C$ , więc przecina sferę $s$ i płaszczyznę $ABC$ wzdłuż tego samego okręgu $k$ . Wobec tego rzut prostokątny $H$ punktu $D$ na płaszczyznę $ABC$ jest środkiem okręgu $k$ . Płaszczyzna $A_1HD$ zawiera zatem pewną średnicę $MN$ okręgu $k$ i przecina sferę $s$ wzdłuż okręgu $l$ przechodzącego przez punkty $M$ , $N$ i $D$ (rys. 16).

Według twierdzenia o potędze punktu względem okręgu

$ A_1 A_2 \cdot A_1D = A_1M \cdot A_1N. $

Stąd

$ (A_1 D - A_2D) \cdot A_1D = (A_1H- MH) (A_1H + MH) = A_1G^2 - MH^2, $

więc

$ A_1D \cdot A_2D = A_1D^2 - A_1H^2 + MH^2 = HD^2 + MH^2 = MD^2. $

Równość tę można zapisać w postaci

$ (1) \qquad DA_1 \cdot DA_2 = r^2. $

Analogicznie

$ (2) \qquad DB_1 \cdot DB_2 = r^2. $

Z (1) i (2) wynika

$ (3) \qquad DA_1 \cdot DA_2 = DB_1 \cdot DB_2. $

Z równości (3) oraz z tego, że pary punktów $A_1$ , $A_2$ , i $B_1$ , $B_2$ leżą na dwóch różnych półprostych o początku $D$ nie tworzących jednej prostej, łatwo wywnioskować, że punkty $A_1$ , $A_2$ , $B_1$ , $B_2$ , leżą na okręgu.

Istotnie, niech $m$ będzie okręgiem przechodzącym przez punkty niewspółliniowe $A_1$ , $A_2$ , $B_1$ (rys. 17).

Punkt $D$ leży na zewnątrz okręgu $m$ , zatem

$ (4) \qquad DA_1 \cdot DA_2 = DB_1 \cdot DX, $

gdzie $X$ jest punktem wspólnym okręgu $m$ z półprostą $DB_1$ .

Z (3) i (4) otrzymujemy

$ DX = DB_2, $

a ponieważ punkty $X$ i $B_2$ należą do tej samej półprostej o początku $D$ , więc punkt $X$ pokrywa się z punktem $B_2$ .

Analogicznie stwierdzamy, że punkty $B_1$ , $B_2$ , $C_1$ , $C_2$ leżą na pewnym okręgu $n$ .

Okręgi $m$ i $n$ mają punkty wspólne $B_1$ i $B_2$ , a przy tym leżą w rożnych płaszczyznach, gdyż według założenia punkty wspólne tych okręgów z płaszczyzną $ABC$ , tj. punkty $A_1$ , $B_1$ , $C_1$ nie są współliniowe.

Stąd wynika, że okręgi $m$ i $n$ , a tym samym punkty $A_1$ , $B_1$ , $C_1$ , $A_2$ , $B_2$ , $C_2$ leżą na jednej sferze, c.n.d.

Uwaga. Początek powyższego dowodu można znacznie skrócić, powołując się na własności przekształcenia przez inwersję. Mianowicie w inwersji względem sfery o środku $D$ i promieniu $r = DA$ przecinającej płaszczyznę $ABC$ wzdłuż okręgu $k$ obrazem płaszczyzny $ABC$ jest sfera przechodząca przez środek inwersji $D$ i przez okrąg $k$ , tj. sfera $s$ . Obrazami punktów $A_1$ , $B_1$ , $C_1$ są zatem odpowiednio punkty $A_2$ , $B_2$ , $C_2$ , wobec czego

$ DA_1 \cdot DA_2 = DB_1 \cdot DB_2 = DC_1 \cdot DC_2 = r^2. $

Dalszy ciąg dowodu pozostaje ten sam co poprzednio.

XIX OM - III - Zadanie 4

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

III

Dana jest liczba naturalna $n>2$ . Podać taki zbiór $n$ liczb naturalnych $a_1, a_2, \ldots, a_n$ , żeby w zbiorze sum

$ a_i + a_j \quad (i = 1,2, \ldots,n, \quad j= 1,2, \ldots,n, \; i\neq j) $

było możliwie najmniej liczb różnych oraz taki zbiór $n$ liczb naturalnych $b_1, b_2, \ldots, b_n$ , żeby w zbiorze sum

$ b_i + b_j \quad (i = 1,2, \ldots,n, \quad j= 1,2, \ldots,n, \; i\neq j) $

było możliwie najwięcej liczb różnych.

Rozwiązanie

Gdy $Z$ jest skończonym zbiorem liczb, umówimy się oznaczać symbolem $l(Z)$ liczbę różnych wartości, jakie mają sumy dwóch liczb należących do $Z$ .

1) Niech $A$ będzie zbiorem $n > 2$ liczb naturalnych $a_i$ ( $i = 1,2,\ldots, n$ ) tak oznaczonych, że

$ (1) \qquad a_1 < a_2 < \ldots < a_n. $

Ponieważ

$ (2) \qquad a_1 + a_2 < a_1 + a_3< \ldots < a_1 + a_n < a_2 + a_n < a_3 + a_n < \ldots < a_{n-1} + a_n, $

więc w zbiorze sum $a_i + a_j$ jest co najmniej $2n - 3$ liczb różnych, tj. $l(A) \geq 2n - 3$ .

Jeśli zatem utworzymy taki zbiór $A$ , że $l(A) = 2n - 3$ , będzie to zbiór jakiego poszukujemy. Trzeba w tym celu dobrać liczby $a_1, a_2, \ldots, a_n$ w taki sposób, żeby każda suma $a_i + a_j$ była równa którejś z sum występujących w (2), tzn. jednej z sum $a_1 + a_j$ ( $j = 2,3, \ldots,n$ ), lub jednej z sum $a_i + a_n$ ( $i = 2,3,\ldots, (n-1)$ ).

Wykażemy, że przypadek taki zachodzi, gdy liczby zbioru $A$ tworzą postęp arytmetyczny.

Załóżmy, że

$ a_2 - a_1 = a_3 - a_2 = \ldots = a_n - a_{n-1} = d > 0. $

Według znanych wzorów

$ (3) \qquad a_k = a_1 + (k-1)d= a_n- (n-k)d \textrm{ dla } k = 1,2 \ldots, n. $

Rozpatrzmy sumę $a_i + a_j$ , gdzie $1 \leq i < j \leq n$ .

Gdy $i + j \leq n$ , wtedy na mocy (3)

$ (4) \qquad a_i + a_j = a_1 + (i - 1) d + a_1 + (j- 1)d = a_1 + [a_1 + (i+j+2)d] = a_1 + a_{i+j-1}; $

gdy zaś $i + j>n$ , wtedy według (3)

$ (5) \qquad a_i + a_j = a_1 + (i - 1)d + a_n - (n - j) d = a_n + [a_1 + (i + j - n - 1)d] = a_{i+j-n} + a_n. $

Z (4) i (5) wynika, że każda suma $a_i + a_j$ jest równa jednej z sum (2), zatem $l(A) = 2n - 3$ , c.n.d.

b) Zbiór liczb naturalnych $B = \{ b_1, b_2, \ldots , b_n\}$ o możliwie największej liczbie $l(B)$ różnych wartości sum $b_i + b_j$ ( $i,j= 1,2,\ldots, n$ , $i \ne j$ ), uzyskamy wtedy, gdy wszystkie sumy $b_i + b_j$ , będą różnymi liczbami; wówczas $l (B) = \frac{1}{2} n (n - 1)$ .

Zbiorem takim jest na przykład zbiór wyrazów postępu geometrycznego

$ (6) \qquad 1, q, q^2, \ldots, q^{n-1}, $

którego iloraz $q$ jest liczbą naturalną większą od $1$ .

Przypuśćmy bowiem, że dla pewnych wyrazów ciągu (6) zachodzi równość

$ (7) \qquad q^i + q^j= g^k + q^l, \textrm{ gdzie } i < j,\ k < l; $

wtedy

$ (8) \qquad q^i (1 + q^{j-i}) = q^k (1 + q^{l-k}). $

Ponieważ liczby $1 + q^{j-i}$ i $1 + q^{l-k}$ są pierwsze względem $q$ , więc z równości (8) wynika, że $q^k$ jest podzielne przez $q^i$ , a $q^i$ przez $q^k$ . Zatem $k = i$ , a wobec (7) także $l = j$ , tzn. równość (7) nie może zachodzić, gdy $q^i$ , $q^j$ nie są tymi samymi wyrazami ciągu (6), co $q^k$ , $q^l$ .

Uwaga 1. Niech $A$ będzie zbiorem liczb $a_1 < a_2< \ldots < a_n$ ( $n > 2$ ), dla którego liczba $l (A)$ różnych wartości sum $a_i + a_j$ wynosi $2n - 3$ , czyli jest możliwie najmniejsza. Postawimy pytanie, czy ciąg $a_1, a_2, \ldots, a_n$ musi być postępem arytmetycznym?

Łatwo zauważyć, że tak nie jest, gdy $n = 3$ , ani gdy $n = 4$ . Z nierówności $a_1 < a_2 < a_3$ wynika bowiem, że $a_1 + a_2 < a_1 + a_3 < a_2 + a_3$ więc dla zbioru $A$ trzech różnych liczb zawsze $l(A) = 3$ . Aby zaś dla zbioru $A$ liczb $a_1 < a_2< a_3< a_4$ było $l(A) = 5$ , trzeba tylko, żeby zachodziła równość $a_4 - a_3 = a_2 - a_1$ .

Udowodnimy, że gdy $n \geq 5$ , wtedy każdy zbiór $A$ złożony z $n$ liczb, dla którego $l(A) = 2n - 3$ , jest zbiorem wyrazów postępu arytmetycznego.

Dla $n = 5$ teza tego twierdzenia jest prawdziwa. Istotnie, gdy dany jest zbiór $A$ pięciu liczb

$ (1) \qquad a_1 < a_2 < a_3 < a_4 < a_5, $

wtedy

$ (2) \qquad a_1 + a_2 < a_1 + a_3 < a_1 + a_4 < a_1 + a_5 < a_2 + a_5 < a_3 + a_5 < a_4 + a_5 $

$ (3) \qquad a_2 + a_3 < a_2 + a_4 < a_3 + a_4, $

więc jeśli $l(A) = 2 \cdot 5 - 3 = 7$ , to każda z sum występujących w (3) musi być równa jednej z siedmiu sum występujących w (2). Ponieważ zaś każda z sum (3) jest większa niż $a_1 + a_3$ , a mniejsza niż $a_3 + a_5$ , więc zachodzą równości

$ a_2 + a_3 = a_1 + a_4, \ a_2 + a_4 = a_1 + a_5, \ a_3 + a_4 = a_2 + a_5, $

z których wynika, że

$ a_2 - a_1 = a_4 - a_3,\ a_2 - a_1 = a_5 - a_4, a_3 - a_2 = a_5 - a_4, $

co oznacza, że ciąg (1) jest postępem arytmetycznym.

Załóżmy, że teza twierdzenia jest prawdziwa dla pewnego $n \geq 5$ . Niech $A$ będzie zbiorem liczb

$ (4) \qquad a_1 < a_2 < \ldots < a_n < a_{n+1}, $

dla którego $l(A) = 2(n + 1) - 3$ .

Weźmy pod uwagę zbiory

$ A' = \{ a_1, a_2,\ldots,a_n \}, $

$ A'' = \{ a_2, a_3,\ldots,a_n, a_{n+1} \}. $

Wykażemy, że

$ l(A') = l(A'') = 2n - 3. $

Istotnie, jeśli liczby $a_i$ , $a_j$ ( $i< j$ ) zbioru $A$ należą do zbioru $A'$ , to

$ a_i + a_j < a_{n-1} + a_{n+1} < a_n + a_{n + 1}, $

więc liczba różnych wartości sum $a_i + a_j$ jest dla zbioru $A'$ co najmniej o $2$ mniejsza niż dla zbioru $A$ , tj.

$ l(A') \leq l(A) - 2 = 2n - 3. $

Wiemy zaś, że

$ l(A') \geq 2n - 3. $

Zatem $l(A') = 2n - 3$ .

Podobnie, jeśli liczby $a_i$ , $a_j$ ( $i < j$ ) zbioru $A$ należą do zbioru $A''$ , to

$ a_i + a_j > a_1 + a_3 > a_1 + a_2, $

skąd wynika, że $l(A'') \leq l(A) - 2 = 2n - 3$ , a że $l(A'') \geq 2n - 3$ , więc $l(A'') = 2n - 3$ .

Na mocy założenia indukcyjnego ciągi $a_1, a_2, \ldots, a_n$ i $a_2, a3,\ldots, a_{n+1}$ są postępami arytmetycznymi, a wobec tego ciąg $a_1, a_2, \ldots, a_n, a_{n+1}$ jest również postępem arytmetycznym, tzn. teza twierdzenia jest prawdziwa dla zbiorów złożonych z $n + 1$ liczb. Według zasady indukcji jest ona tedy prawdziwa dla każdego naturalnego $n \geq 5$ .

Uwaga 2. Przykładów takiego zbioru $B = \{b_1, b_2,\ldots, b_n \}$ , że $l(B) = \frac{1}{2} n(n-1)$ można podać wiele. Własność tę ma np. zbiór $n$ kolejnych wyrazów ciągu Fibonacci'ego *), tj. ciągu liczb $b_n$ określonego wzorami $b_1 =0$ , $b_2 = 1$ , a dla każdego $n > 2$ $b_n = b_{n-1}+ b_{n-2}$ .

Pierwszymi wyrazami tego ciągu są zatem liczby $0, 1, 1, 2, 3, 5, 8, 13, \ldots$ .

Dowód, że każda z sum $b_i + b_j$ jest inną liczbą, łatwo przeprowadzić metodą indukcji.

XIX OM - III - Zadanie 5

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

III

Na płaszczyźnie leży $n$ punktów ( $n \geq 4$ ), z których każde cztery są wierzchołkami czworokąta wypukłego. Dowieść, że wszystkie te punkty są wierzchołkami wielokąta wypukłego.

Rozwiązanie

Zastosujemy metodę indukcji. Gdy $n = 4$ , teza twierdzenia jest prawdziwa. Załóżmy, że teza twierdzenia jest prawdziwa dla pewnego naturalnego $n \geq 4$ , i niech $A_1, A_2, \ldots, A_n, A_{n+1}$ będą takimi $n + 1$ punktami płaszczyzny, że każde cztery z nich są wierzchołkami wielokąta wypukłego. Według założenia indukcyjnego punkty $A_1, A_2, \ldots, A_n$ są wierzchołkami wielokąta wypukłego $W$ . Przyjmiemy, że są to wierzchołki kolejne, co można uzyskać przez odpowiednią numerację punktów. Punkt $A_{n+1}$ nie leży na obwodzie wielokąta $W$ , gdyż żadne trzy dane punkty nie są współliniowe. Nie leży on także wewnątrz wielokąta $W$ , gdyż każdy punkt wewnętrzny wielokąta należy do jednego z trójkątów, na jakie można podzielić wielokąt jego przekątnymi, a punkt $A_{n + 1}$ nie może się znajdować w takim trójkącie. Zatem punkt $A_{n+1}$ leży na zewnątrz wielokąta $W$ . Weźmy pod uwagę kąty wypukłe o wierzchołku $A_{n+1}$ , których ramiona przechodzą przez wierzchołki wielokąta $W$ . Zbiór tych kątów jest skończony, więc istnieje wśród nich kąt największy. Niech to będzie na przykład kąt $\alpha = A_kA_{n + 1}A_l$ . Wewnątrz kąta $\alpha$ leżą wszystkie wierzchołki wielokąta $W$ oprócz $A_k$ i $A_l$ . W trójkącie $T$ o wierzchołkach $A_k$ , $A_{n+1}$ , $A_l$ nie leży żaden z wierzchołków $A_i$ wielokąta $W$ , różnych od $A_k$ i $A_l$ , gdyż punkty $A_i$ , $A_k$ , $A_l$ , $A_{n+1}$ są według założenia wierzchołkami czworokąta wypukłego. Wobec tego $A_k$ i $A_l$ są kolejnymi wierzchołkami wielokąta $W$ , np. $l=k+1$ . W takim razie punkty $A_1, A_2 \ldots A_k, A_{n+1}, A_{k+1}, \ldots, A_n$ są kolejnymi wierzchołkami wielokąta $W_1$ , który składa się z wielokąta $W$ i z trójkąta $T$ .

Dowiedziemy, że wielokąt $W_1$ jest wypukły, tj. że każdy odcinek którego końce leżą w wielokącie $W_1$ zawiera się cały w tym wielokącie. Istotnie, jeżeli punkty $M$ i $N$ leżą w wielokącie $W_1$ , to zachodzi jeden z przypadków: a) Punkty $M$ i $N$ leżą oba w wielokącie wypukłym $W$ , albo oba w trójkącie $T$ ; wtedy cały odcinek $MN$ zawiera się w wielokącie $W$ albo w trójkącie $T$ , a tym samym zawiera się w wielokącie $W_1$ ; b) Jeden z tych punktów, np. punkt $M$ , leży w wielokącie $W$ , a punkt $N$ w trójkącie $T$ . Odcinek $MN$ przecina wtedy obwód trójkąta $T$ w pewnym punkcie $P$ . Punkt $P$ leży na tej części obwodu trójkąta $T$ , która znajduje się w kącie $\alpha$ , tj. na odcinku $A_kA_{k+1}$ . Odcinek $MP$ należy więc do wielokąta $W$ , a odcinek $PN$ - do trójkąta $T$ ; każdy z tych odcinków, zatem także ich suma $MN$ , należy do wielokąta $W_1$ . Dowód indukcyjny twierdzenia został przeprowadzony.

Uwaga. Bardzo prosty dowód twierdzenia uzyskamy opierając się na twierdzeniu następującym:

Dla każdego skończonego zbioru $Z$ punktów płaszczyzny, składającego się z $n \geq 3$ punktów nie leżących na jednej prostej, istnieje taki wielokąt wypukły $W$ , że

1. Zbiór $Z$ jest zawarty w wielokącie $W$ .

2. Każdy wierzchołek wielokąta $W$ należy do zbioru $Z$ .

Taki wielokąt $W$ nazywa się oponą zbioru $Z$ *)

Niech $Z$ będzie zbiorem $n \geq 4$ punktów płaszczyzny, którego każde $4$ punkty są wierzchołkami czworokąta wypukłego i niech wielokąt $W$ będzie oponą zbioru $Z$ . Wówczas każdy punkt zbioru $Z$ jest wierzchołkiem wielokąta $W$ . Albowiem: $1^\circ$ żaden punkt zbioru $Z$ nie leży na obwodzie wielokąta $W$ między dwoma jego wierzchołkami, gdyż w zbiorze $Z$ nie ma trzech punktów współliniowych; $2^\circ$ żaden punkt zbioru $Z$ nie leży wewnątrz wielokąta $W$ , gdyż wówczas leżałby w jednym z trójkątów, na jakie można $W$ podzielić przekątnymi, a to byłoby również sprzeczne z założeniem. Opona $W$ jest zatem tym wielokątem, którego istnienia należało dowieść.

XIX OM - III - Zadanie 6

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

III

Dany jest zbiór $n > 3$ punktów, z których żadne trzy nie są współliniowe, oraz liczba naturalna $k < n$ . Udowodnić twierdzenia:
1. Jeżeli $k \leq \frac{n}{2}$ , to każdy punkt danego zbioru można połączyć z co najmniej $k$ innymi punktami zbioru w taki sposób, że wśród poprowadzonych odcinków nie ma trzech boków tego samego trójkąta.
2. Jeżeli $k > \frac{n}{2}$ i każdy punkt danego zbioru jest połączony z $k$ innymi punktami zbioru, to wśród poprowadzonych odcinków są trzy boki tego samego trójkąta.

Rozwiązanie

$1^\circ$ . Załóżmy, że $k \leq \frac{n}{2}$ . Wybierzmy z danego zbioru $Z$ część $Z_1$ składającą się z $\left[ \frac{n}{2} \right]$ punktów*); część pozostała $Z_2$ zawiera $\left[ \frac{n}{2} \right]$ punktów, gdy $n$ jest parzyste, a $\left[ \frac{n}{2} \right]+ 1$ punktów, gdy $n$ jest nieparzyste. Ponieważ $k$ jest liczbą całkowitą, więc z warunku, że $k \leq \frac{n}{2}$ wynika, że $k \leq \left[ \frac{n}{2} \right]$ . Zatem każdy ze zbiorów $Z_1$ , $Z_2$ zawiera co najmniej $k$ punktów.

Połączmy odcinkami każdy punkt zbioru $Z_1$ z każdym punktem zbioru $Z_2$ . Wówczas każdy punkt zbioru $Z$ zostanie połączony z co najmniej $k$ innymi punktami tego zbioru. Żadne trzy z poprowadzonych odcinków nie są bokami tego samego trójkąta, gdyby bowiem taki trójkąt istniał, wtedy dwa jego wierzchołki, tj. oba końce jednego z odcinków, leżałyby w jednym ze zbiorów $Z_1$ , $Z_2$ , co jest niemożliwe, gdyż żaden taki odcinek nie został poprowadzony.

$2^\circ$ Załóżmy, że $k > \frac{n}{2}$ i że każdy punkt danego zbioru łączy $k$ odcinków z $k$ innymi punktami zbioru; niech $AB$ będzie jednym z poprowadzonych odcinków.

Z każdego z punktów $A$ i $B$ wychodzi oprócz $AB$ jeszcze $k - 1$ innych odcinków, czyli razem $2k - 2$ odcinków, których końce należą do zbioru pozostałych $n - 2$ punktów. Lecz jeśli $k > \frac{n}{2}$ , to $2k - 2 > n - 2$ ; wśród owych $2k - 2$ odcinków istnieją więc dwa odcinki o wspólnym końcu $C$ . W zbiorze poprowadzonych odcinków znajdują się zatem boki $AB$ , $AC$ i $BC$ trójkąta $ABC$ .

Uwaga. W podobny sposób można udowodnić twierdzenie ogólniejsze. Niech będą dane: zbiór $Z$ złożony z $n > 3$ punktów, z których żadne trzy nie są współliniowe, liczba naturalna $p$ spełniająca nierówności $3 \leq p < n$ oraz liczba naturalna $k < n$ . Wtedy:

$1 ^\circ$ Jeżeli $k \leq \frac{p-2}{p-1}n$ , wtedy każdy z punktów zbioru $Z$ można tak połączyć odcinkami z co najmniej $k$ innymi punktami tego zbioru, że w każdym podzbiorze zbioru $Z$ złożonym z $p$ punktów któreś dwa punkty nie są połączone odcinkiem.

$2^\circ$ Jeżeli $k > \frac{p-2}{p-1}n$ i każdy punkt zbioru $Z$ jest połączony odcinkiem z $k$ innymi punktami tego zbioru, wtedy istnieje taki podzbiór zbioru $Z$ złożony z $p$ punktów, w którym każde dwa punkty są połączone odcinkiem.