XVIII OM - III etap

III etap XVIII Olimpiady Matematycznej

XVIII OM - III - Zadanie 1

Zawody matematyczne:

XVIII OM, 1966-1967

Etap:

III

Znaleźć najwyższą potęgę liczby 2 będącą dzielnikiem liczby

$ L_n = (n+1)(n+2)\ldots 2n, $

gdzie $n$ jest liczbą naturalną.

Rozwiązanie

\spos{1} Zauważmy, że $n!L_n = (2n)!$ . Zatem

$ L_n = \frac{(2n)!}{n!} = \frac{1 \cdot 2 \cdot 3 \cdot \ldots \cdot 2n}{1 \cdot 2 \cdot 3 \cdot \ldots \cdot n} = 1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2n - 1) \cdot \frac{2 \cdot 4 \cdot 6 \cdot \ldots \cdot 2n}{1 \cdot 2 \cdot 3 \cdot \ldots \cdot n} = 1 \cdot 3 \cdot 5 \cdot \ldots \cdot (2n - 1) \cdot 2^n. $

Stąd wynika, że $L_n$ jest podzielne przez $2^n$ , ale nie jest podzielne przez $2^{n+1}$ .

XVIII OM - III - Zadanie 2

Zawody matematyczne:

XVIII OM, 1966-1967

Etap:

III

Dowieść, że jeżeli punkty $A_1, B_1, C_1$ leżące odpowiednio na bokach $BC, CA, AB$ trójkąta $ABC$ są rzutami prostokątnymi pewnego punktu $P$ trójkąta na te boki, to

$ (1) AC_1^2 + BA_1^2 + CB_1^2 = AB_1^2 + BC_1^2 + CA_1^2. $

Rozwiązanie

Z trójkątów prostokątnych $APB_1$ , $BPC_1$ , $CPA_1$ (rys. 11) otrzymujemy odpowiednio równości

$ (2) \qquad \begin{array}{c} AB_1^2 = AP^2 - PB^2_1,\\ BC_1^2 = BP^2 - PC^2_1,\\ CA_1^2 = CP^2 - PA^2_1, \end{array} $

a z trójkątów prostokątnych $APC_1$ , $BPA_1$ , $CPB_1$ odpowiednio równości

$ (3) \qquad \begin{array}{c} AC^2_1 = AP^2 - PC^2_1,\\ BA^2_1 = BP^2 - PA^2_1,\\ CB^2_1 = CP^2 - PB^2_1. \end{array} $

Suma prawych stron równości (2) jest równa sumie prawych stron równości (3). Istotnie więc zachodzi równość (1).

Uwaga. Łatwo uzyskać twierdzenie znacznie ogólniejsze od powyższego. Równości (2) i (3), z których wynika równość (1) są mianowicie słuszne przy założeniach o wiele słabszych od tych, które były podane w tekście twierdzenia. Na przykład równość $AB^2_1 = AP^2- PB^2_1$ zachodzi, gdy punkty $A$ , $P$ , $B$ są różne, a proste $AB_1$ i $PB_1$ są prostopadłe lub gdy choć jeden z punktów $A$ i $P$ pokrywa się z punktem $B_1$ . To samo dotyczy innych równości z układów (2) i (3). Wobec tego prawdziwe jest twierdzenie:

Jeżeli $A$ , $B$ , $C$ , $P$ są punktami przestrzeni, z których pierwsze trzy są różne, a $A_1$ , $B_1$ , $C_1$ są odpowiednio rzutami prostokątnymi punktu $P$ na proste $BC$ , $CA$ , $AB$ , to zachodzi równość (1).

Dla przypadku, gdy punkty $A$ , $B$ , $C$ są niewspółliniowe zachodzi również twierdzenie odwrotne:

Jeżeli punkty $A$ , $B$ , $C$ są wierzchołkami trójkąta, a punkty $A_1$ , $B_1$ , $C_1$ leżące odpowiednio na prostych $BC$ , $CA$ , $AB$ spełniają warunek (1), to $A_1$ , $B_1$ , $C_1$ są rzutami prostokątnymi pewnego punktu $P$ odpowiednio na proste $BC$ , $CA$ , $AB$ .

Dowód. Poprowadźmy w płaszczyźnie $ABC$ przez punkt $A_1$ prostopadłą do prostej $BC$ , a przez punkt $B_1$ prostopadłą do prostej $AC$ ; przetną się one w pewnym punkcie $P$ . Niech $C_2$ będzie rzutem prostokątnym punktu $P$ na prostą $AB$ . Według udowodnionego poprzednio twierdzenia

$ (4) \qquad AC_2^2 +BA_1^2 +CB_1^2 = AB_1^2 +BC_2^2 +CA_1^2. $

Odejmując równości (1) i (4) otrzymujemy

$ (5) \qquad AC_1^2 -AC_2^2 = BC_1^2 -BC_2^2 . $

Z równości (5) wywnioskujemy, że punkt $C_2$ pokrywa się z punktem $C_1$ . Najdogodniej posłużyć się w tym celu rachunkiem wektorowym.

Równość (5) zapiszemy w postaci wektorowej

$ \overrightarrow{AC^2_1} - \overrightarrow{AC_2^2} = \overrightarrow{BC_1^2} - \overrightarrow{BC_2^2}. $

Stąd otrzymujemy kolejno

$ (\overrightarrow{AC_1} - \overrightarrow{AC}) (2 \overrightarrow{AC_1} + \overrightarrow{AC_2}) = (\overrightarrow{BC_1}-\overrightarrow{BC_2}) (\overrightarrow{BC_1} + \overrightarrow{BC_2}), $

$ \overrightarrow{C_2C_1} (\overrightarrow{AC_1}+\overrightarrow{AC_2}) = \overrightarrow{C_2C_1} (\overrightarrow{BC_1} + \overrightarrow{BC_2}), $

$ \overrightarrow{C_2C_1} (\overrightarrow{AC_1} - \overrightarrow{BC_1} + \overrightarrow{AC_2} - \overrightarrow{BC_2}) = 0, $

$ \overrightarrow{C_2C_1} (\overrightarrow{AB} + \overrightarrow{AB}) = 0, $

$ \overrightarrow{C_2C_1} \cdot \overrightarrow{AB} = 0. $

Ponieważ wektory $\overrightarrow{AB}$ i $\overrightarrow{C_2C_1}$ nie są prostopadłe (punkty $C_1$ i $C_2$ leżą na prostej $AB$ ), a wektor $\overrightarrow{AB}$ jest według założenia różny od zera, więc z powyższej równości wynika, że

$ \overrightarrow{C_2C_1} = 0, $

tzn. punkty $C_1$ i $C_2$ pokrywają się, wobec czego $A_1$ , $B_1$ , $C_1$ są rzutami prostokątnymi punktu $P$ na proste $BC$ , $CA$ , $AB$ c.n.d. Tę samą własność ma każdy punkt prostej prostopadłej do płaszczyzny $ABC$ w punkcie $P$ .

XVIII OM - III - Zadanie 3

Zawody matematyczne:

XVIII OM, 1966-1967

Etap:

III

Na sali znajduje się 100 osób, z których każda zna co najmniej 67 innych. Dowieść, że jest na tej sali taka czwórka osób, w której każde dwie osoby się znają. Zakładamy, że jeśli osoba $A$ zna osobę $B$ , to również osoba $B$ zna osobę $A$ .

Rozwiązanie

W zbiorze $M$ osób znajdujących się na sali są co najwyżej $32$ osoby nie znające jakiejś określonej osoby $A$ (przyjmujemy, że osoba $A$ zna sama siebie).

Jeżeli $A$ , $B$ , $C$ są trzema dowolnymi osobami zbioru $M$ , to w zbiorze $M$ jest taka osoba $D$ , różna od $A$ , $B$ i $C$ która zna te trzy osoby. Istotnie, jeśli z sali wyjdą wszystkie osoby nie znające $A$ , wszystkie osoby nie znające $B$ oraz wszystkie osoby nie znające $C$ , to wyjdzie razem co najwyżej $3 \cdot 32 = 96$ osób. Każda z pozostałych osób zna wówczas $A$ , $B$ i $C$ , a ponieważ tych osób jest co najmniej $100-96 = 4$ , więc co najmniej jedna z nich jest różna od $A$ , $B$ i $C$

Czwórkę osób zbioru $M$ znających się wzajemnie możemy wobec tego wyszukać w prosty sposób. Mianowicie $A$ może być którąkolwiek osobą tego zbioru, $B$ osobą znającą $A$ i różną od $A$ , $C$ osobą znającą $A$ i $B$ , a różną od $A$ i od $B$ , wreszcie $D$ osobą znającą $A$ , $B$ i $C$ , różną od $A$ , od $B$ i od $C$ .

Uwaga. W analogiczny sposób można udowodnić twierdzenie ogólniejsze: Jeżeli na sali znajduje się $n$ osób, z których każda zna co najmniej $\left[ \frac{2n}{3} \right] +1$ pozostałych osób, to jest na tej sali czwórka osób, w której każde dwie osoby się znają.

Aby tego dowieść, stwierdzamy najpierw, że liczba osób nie znających jakiejś określonej osoby wynosi co najwyżej $n - \left[ \frac{2n}{3} \right] -2$ . Liczba osób nie znających choćby jednej z trzech osób $A$ , $B$ , $C$ wynosi zatem co najwyżej $m = 3n-3 \left[ \frac{2n}{3} \right]-6$ . Ponieważ $\left[ \frac{2n}{3} \right] > \frac{2n}{3} -1$ , więc $3 \left[ \frac{2n}{3} \right] > 2n - 3$ , wobec czego $3 \left[ \frac{2n}{3} \right] \geq 2n-2$ , zatem $m \leq 3n - (2n-2) - 6 = n-4$ . Liczba osób znających $A$ , $B$ , $C$ jest więc co najmniej równa $n-m \geq 4$ , zatem co najmniej jedna z tych osób jest różna od $A$ , od $B$ i od $C$ Dalszy ciąg dowodu pozostaje ten sam co poprzednio.

XVIII OM - III - Zadanie 4

Zawody matematyczne:

XVIII OM, 1966-1967

Etap:

III

Dowieść, że wielomian $x^3 + x + 1$ jest dzielnikiem wielomianu $P_n(x) = x^{n + 2} + (x+l)^{2n+1}$ dla każdego całkowitego $n \geq 0$ .

Rozwiązanie

Stosujemy indukcję zupełną. Dla $n = 0$ twierdzenie jest prawdziwe, gdyż $P_0(x) = x^2+ x + 1$ . Załóżmy, że dla pewnego naturalnego $n$ wielomian $P_n (x)$ jest podzielny przez $x^2+x+1$ . Utwórzmy wielomian

$ \begin{split} P_{n+1}(x) - xP_n(x) &= x^{n+3} + (x+1)^{2n+3} - [x^{n + 3} + x( x+ 1)^{2n+1}] =\\ & = x^{2n+1} [(x+1)^2-x] = x^{2n+1}(x^2 + x+1). \end{split} $

Stąd

$ P_{n+1}(x) = x \cdot P_n(x) + x^{2n+1} (x^2 + x+1). $

Wobec tej równości z założenia indukcyjnego wynika, że wielomian $P_{n+1}(x)$ jest podzielny przez $x^2+x+1$ ; wypowiedziane wyżej twierdzenie jest więc prawdziwe.

XVIII OM - III - Zadanie 5

Zawody matematyczne:

XVIII OM, 1966-1967

Etap:

III

Dowieść, że jeżeli wielokąt o nieparzystej liczbie boków wpisany, w okrąg ma wszystkie kąty równe, to wielokąt ten jest foremny.

Rozwiązanie

Załóżmy, że wielokąt $W$ o kolejnych wierzchołkach $A_1, A_2, \ldots, A_n$ , gdzie $n$ jest liczbą nieparzystą, ma wszystkie kąty równe i jest wpisany w okrąg $O(r)$ . Gdy $n = 3$ , teza twierdzenia jest oczywista, przyjmiemy więc, że $n \geq 5$ .

Niech $A_{i-1}, A_i, A_{i+1}$ będą trzema kolejnymi wierzchołkami wielokąta $W$ i niech w tym wielokącie $\measuredangle A_{i-1}A_iA_{i+1} = \alpha$ (rys. 13); ponieważ $n \geq 5$ , więc $\alpha \geq 108^\circ$ .

Według twierdzenia o kącie wpisanym w okrąg kąt wklęsły $A_{i-1}OA_{i+1} = 2 \alpha$ , więc kąt wypukły $A_{i-1}OA_{i+1} = 360^\circ - 2\alpha = \beta$ . Obróćmy wielokąt $W$ dokoła punktu $O$ o kąt $\beta$ , np. w kierunku wyznaczonym przez obieg $A_1A_2\ldots A_n$ wielokąta $W$ . Wierzchołek $A_{i-1}$ znajdzie się po tym obrocie w punkcie $A_{i+1}$ , tzn., każdy wierzchołek wielokąta $W$ pokryje wierzchołek o wskaźniku o $2$ większym, z tym, że za wskaźniki o $2$ większe od $n-1$ i $n$ uważamy $1$ i $2$ . A więc punkty

$ (1) \qquad A_1, A_2, A_3, \ldots, A_{n-2}, A_{n-1}, A_n $

pokryją odpowiednio punkty

$ (2) \qquad A_3, A_4, A_5, \ldots, A_n, A_1, A_2. $

Każdy odcinek łączący dwa punkty ciągu (1) pokryje odcinek łączący odpowiednie punkty ciągu (2). Zatem przy nieparzystym $n$

$ A_1A_2 = A_3A_4 = A_5A_6 = A_{n-2}A_{n-1} = A_n A_1, $

oraz

$ A_2A_3 = A_4A_5 = A_6A_7 = A_{n-1}A_{n} = A_1 A_2, $

wszystkie boki wielokąta $W$ są równe, c.n.d.

XVIII OM - III - Zadanie 6

Zawody matematyczne:

XVIII OM, 1966-1967

Etap:

III

Dana jest kula i płaszczyzna nie mająca z kulą punktów wspólnych. Znaleźć miejsce geometryczne środków okręgów styczności z kulą tych stożków opisanych na kuli, których wierzchołki leżą na danej płaszczyźnie.

Rozwiązanie

Wprowadzimy oznaczenia: $O$ - środek danej kuli, $r$ - jej promień, $M$ - rzut punktu $O$ na daną płaszczyznę $\pi$ , $A$ - dowolny punkt płaszczyzny $\pi$ różny od $M$ , $A'$ i $M'$ - środki okręgów styczności z kulą stożków opisanych na kuli, których wierzchołkami są odpowiednio $A$ i $M$ , $AT$ i $MS$ - dowolne tworzące tych stożków.

W trójkątach prostokątnych $ATO$ i $MSO$ (rys. 14).

$ OA \cdot OA' = OT^2 = r^2,\ OM \cdot OM' = OS^2 = r^2. $

Zatem

$ (1) \qquad \frac{OA}{OM} = \frac{OM'}{OA'}. $

Stąd wynika, że trójkąty $OAM$ i $OM'A'$ są podobne, wobec czego kąt $OA'M' = OMA = 90^\circ$ . Punkt $A'$ leży zatem na sferze o średnicy $OM'$ . Odwrotnie, jeśli $A'$ jest dowolnym punktem tej sfery różnym od $O$ , $A$ zaś - punktem przecięcia prostej $OA'$ z $\pi$ , to

$ (2) \qquad OA \cdot OA'= r^2. $

Istotnie, gdy $A'$ pokrywa się z $M'$ , równość (2) jest oczywista; a gdy $A' \ne M'$ , trójkąty $OAM$ i $OM'A'$ są podobne, zachodzi więc (1), zatem również (2). W takim razie dla dowolnej tworzącej $AT$ stożka o wierzchołku $A$ opisanego na kuli punkt $A'$ jest rzutem punktu $T$ na prostą $AO$ , więc $A'$ jest środkiem okręgu styczności tego stożka z kulą.

Poszukiwanym miejscem geometrycznym jest sfera o średnicy $OM'$ bez punktu $O$ .

Uwaga. Rozumowanie można skrócić korzystając z własności przekształcenia przez inwersję. Mianowicie równość $OA \cdot OA' = r^2$ zachodzi wtedy i tylko wtedy, gdy punkt $A'$ jest obrazem punktu $A$ w inwersji względem sfery $O(r)$ . Miejscem geometrycznym punktu $A'$ jest zatem obraz płaszczyzny $\pi$ w tej inwersji, tzn. sfera o średnicy $OM'$ bez punktu $O$ .