LV OM - III etap

III etap LV Olimpiady Matematycznej

Załącznik	Wielkość
LV OM III etap - Zadania [1]	77.22 KB
LV OM III etap - Zadania z rozwiązaniami [2]	135.37 KB

LV OM - III - Zadanie 1

Zawody matematyczne:

LV OM, 2003-2004

Etap:

III

Punkt $D$ leży na boku $AB$ trójkąta $ABC$ . Okręgi styczne do prostych $AC$ i $BC$ odpowiednio w punktach $A$ i $B$ przechodzą przez punkt $D$ i przecinają się po raz drugi w punkcie $E$ . Niech $F$ będzie punktem symetrycznym do punktu $C$ względem symetralnej odcinka $AB$ . Wykazać, że punkty $D$ , $E$ i $F$ leżą na jednej prostej.

Rozwiązanie

Przypuśćmy, że punkt $E$ leży wewnątrz trójkąta $ABC$ . Wówczas

$ \measuredangle AED = 180^\circ - \measuredangle BAC \ \textrm{oraz} \ \measuredangle BED = 180^\circ -\measuredangle ABC. $

Dodając równości te stronami mamy $180^\circ > \measuredangle AEB = 180^\circ + \measuredangle ACB > 180^\circ$ . Otrzymana sprzeczność dowodzi, że punkty $C$ i $E$ leżą po przeciwnych stronach prostej $AB$ (rys. 1).

Z równości $\measuredangle AEB = \measuredangle AED+\measuredangle DEB = \measuredangle BAC+\measuredangle ABC = 180^\circ - \measuredangle ACB$ wynika zatem, że punkty $A$ , $E$ , $B$ , $C$ leżą, w tej właśnie kolejności, na jednym okręgu $o$ . Stąd wniosek, że punkt $F$ leży również na okręgu $o$ , czyli

$ \measuredangle FEB = \measuredangle FAB = \measuredangle CBD = \measuredangle BED. $

Równość ta oznacza, że punkty $D$ , $E$ i $F$ leżą na jednej prostej.

LV OM - III - Zadanie 2

Zawody matematyczne:

LV OM, 2003-2004

Etap:

III

Niech $W$ będzie wielomianem o współczynnikach całkowitych, przyjmującym dla pewnych dwóch różnych liczb całkowitych wartości względnie pierwsze. Dowieść, że istnieje nieskończony zbiór liczb całkowitych, dla których wielomian $W$ przyjmuje wartości parami względnie pierwsze.

Rozwiązanie

Ciąg różnych liczb całkowitych $x_0, x_1, x_2, \ldots$ taki, że wartości $W(x_i)$ są parami względnie pierwsze, zbudujemy indukcyjnie. Dwa początkowe wyrazy $x_0 = a, x_1 = b$ to liczby, których istnienie jest dane w założeniach.

Przyjmijmy, że zostały już określone różne liczby $x_0, x_1, \ldots, x_n$ dla których wartości $y_i = W(x_i)$ są parami względnie pierwsze. Liczba $y_0$ jest względnie pierwsza z iloczynem $y_1 y_2 \ldots y_n$ ; istnieją zatem takie liczby całkowite $k$ , $m$ , że $ky_0 + my_1y_2 \ldots y_n = 1$ . Określamy kolejny wyraz ciągu:

$ x_{n+1} = b + (a - b)ky_0 + zy_0 y_1 \ldots y_n, $

gdzie $z$ jest liczbą naturalną tak dużą, żeby liczba $x_{n+1}$ była różna od liczb $x_0,x_1,\ldots ,x_n$ . Oczywiście

$x_{n+1} \equiv b\ (\mathrm{mod}\ y_0); $

a z przekształcenia $x_{n+1} = b + (a - b)(1 - my_1 y_2 \ldots y_n)+zy_0 y_1 \ldots y_n$ widać, że

$ x_{n+1} \equiv a\ (\textrm{mod}\ y_1 y_2 \ldots y_n). $

Stosując do obu stron każdej z tych dwóch kongruencji wielomian $W$ (co jest dozwolone, skoro kongruencje o wspólnym module można dodawać i mnożyć), dostajemy związki

$ W (x_{n+1}) \equiv W (b) \ (\mathrm{mod}\ y_0), \quad W (x_{n+1}) \equiv W (a) \ (\mathrm{mod}\ y_1y_2 \ldots y_n). $

To znaczy, że dla pewnych liczb całkowitych $s$ , $t$ zachodzą równości

$ W (x_{n+1}) = W (b) + sy_0,\quad W (x_{n+1}) = W (a) + ty_1y_2 \ldots y_n. $

A ponieważ wartość $W(b) = y_1$ jest względnie pierwsza z $y_0$ , zaś wartość $W (a) = y_0$ jest względnie pierwsza z iloczynem $y_1y_2 \ldots y_n$ , zatem z uzyskanych równości wynika, że wartość $W(x_{n+1})= y_{n+1}$ jest względnie pierwsza zarówno z $y_0$ , jak i z $y_1 y_2 \ldots y_n$ .

Kontynuując to postępowanie otrzymujemy nieskończony ciąg $(x_i)$ dający wartości $y_i = W(x_i)$ parami względnie pierwsze.

LV OM - III - Zadanie 3

Zawody matematyczne:

LV OM, 2003-2004

Etap:

III

W pewnym turnieju wzięło udział $n$ zawodników $(n \geq 3)$ . Każdy grał z każdym dokładnie jeden raz, nie było remisów. Trójelementowy zbiór zawodników nazwiemy trójką remisową, jeśli można tak ponumerować tych trzech zawodników, że pierwszy wygrał z drugim, drugi z trzecim, a trzeci z pierwszym. Wyznaczyć największą liczbę trójek remisowych, jaka mogła się pojawić w turnieju.

Rozwiązanie

Zamiast wyznaczać największą liczbę trójek remisowych, wyznaczymy najmniejszą liczbę trójek, które nie są remisowe.

Ponumerujmy zawodników liczbami od 1 do $n$ i przyjmijmy, że zawodnik o numerze $i$ wygrał $x_i$ razy. Wówczas liczba wszystkich rozgrywek wynosi

$ x_1 + x_2 +\ldots + x_n = {n \choose 2}. $

Każda nieremisowa trójka jest wyznaczona jednoznacznie przez zawodnika, który wygrał z dwoma innymi zawodnikami tej trójki. Zatem zawodnik o numerze $i$ wyznacza $x_i \choose 2$ nieremisowych trójek, a liczba wszystkich nieremisowych trójek w turnieju wynosi

$ {x_{1}\choose 2} + {x_{2}\choose 2} + \ldots + {x_{n}\choose 2} =\frac{1}{2} \left(\sum_{i=1}^{n}x_{i}^{2} - \sum_{i=1}^{n}x_{i}\right) = \frac{1}{2} \left(\sum_{i=1}^{n}x_{i}^{2} - {n\choose 2} \right). $

W dalszej części rozwiązania rozpatrzymy dwa przypadki:

Liczba $n$ jest nieparzysta, tzn. $n = 2k + 1$ . Wówczas na mocy nierówności pomiędzy średnią kwadratową a średnią arytmetyczną uzyskujemy

$ (1)\qquad \frac{1}{2} \left(\sum_{i=1}^{n}x_{i}^{2} - {n\choose 2} \right) \geq \frac{1}{2} \left( \frac{1}{n} \left(\sum_{i=1}^{n}x_{i}\right)^{2} - {n\choose 2} \right) = \frac{n(n-1)(n-3)}{8}. $

Zatem liczba trójek remisowych nie przekracza

$ {n \choose 3}-\frac{n(n-1)(n-3)}{8}=\frac{n(n^{2}-1)}{24}. $

Powyższa liczba trójek remisowych wystąpi jedynie wtedy, gdy każdy zawodnik wygra dokładnie $k$ razy (w nierówności (1) zachodzi wtedy równość). Taki układ wyników rozgrywek możemy uzyskać w następujący sposób. Sadzamy zawodników przy okrągłym stole i zakładamy, że każdy z nich wygrał tylko z tymi zawodnikami, którzy siedzą po jego prawej stronie w odległości nie większej niż $k$ miejsc. Przy takim układzie rozgrywek każdy zawodnik wygrał dokładnie $k$ razy.
Liczba $n$ jest parzysta, tzn. $n = 2k$ . Wówczas $(x_i - k)(x_i - k + 1) \geq 0$ dla $i = 1,2,\ldots,n$ , skąd otrzymujemy $x_i^2 \geq (2k - 1)x_i - k(k - 1)$ . Zatem

$ (2) \frac{1}{2}\left(\sum_{i=1}^{n}x_{i}^{2} - {n\choose 2} \right) \geq \frac{1}{2}\left((2k-1)\sum_{i=1}^{n}x_{i}-nk(k-1)-{n \choose 2} \right) = \frac{n(n-2)^{2}}{8}. $

Stąd wynika, że liczba trójek remisowych nie przekracza

$ {n \choose 3}-\frac{n(n-2)^2}{8}=\frac{n(n^{2}-4)}{24}. $

Powyższa liczba trójek remisowych wystąpi jedynie wtedy, gdy każdy zawodnik wygra $k$ lub $k-1$ razy (w nierówności (2) zachodzi wtedy równość). Taki układ wyników rozgrywek możemy uzyskać w następujący sposób. Tak jak wyżej, sadzamy zawodników przy okrągłym stole i przyjmujemy, że każdy z nich wygrał z zawodnikami, którzy siedzą po jego prawej stronie w odległości nie większej niż $k-1$ miejsc. Wynik rozgrywki pomiędzy zawodnikami siedzącymi naprzeciwko siebie ustalamy dowolnie. W ten sposób każdy zawodnik wygrał $k$ lub $k-1$ razy.

Reasumując: największa liczba trójek remisowych, jaka może się pojawić w turnieju wynosi $\frac{1}{24}n(n^2 - 1)$ , jeśli $n$ jest liczbą nieparzystą oraz $\frac{1}{24}n(n^2 -4)$ , jeśli $n$ jest liczbą parzystą.

LV OM - III - Zadanie 4

Zawody matematyczne:

LV OM, 2003-2004

Etap:

III

Udowodnić, że jeżeli $a$ , $b$ , $c$ są liczbami rzeczywistymi, to

$ \begin{array}{l} \sqrt{2(a^{2}+b^{2})}+\sqrt{2(b^{2}+c^{2})}+\sqrt{2(c^{2}+a^{2})}\geq \\ \qquad \qquad \qquad \geq\sqrt{3(a+b)^{2}+3(b+c)^{2}+3(c+a)^{2}}. \end{array} $

Rozwiązanie

Podnosząc zadaną nierówność stronami do kwadratu, dostajemy do udowodnienia nierówność równoważną, której lewa strona jest równa

$ 4(a^{2}+b^{2}+c^{2})+4\sqrt{(a^{2}+b^{2})(b^{2}+c^{2})}+4\sqrt{(b^{2}+c^{2})(c^{2}+a^{2})}+4\sqrt{(c^{2}+a^{2})(a^{2}+b^{2})}, $

natomiast prawa wynosi $6(a^2 + b^2 + c^2) + 6(ab+bc+ca)$ . Po redukcji wyrazów podobnych i podzieleniu stronami przez 2 pozostaje do wykazania, że

$ \begin{array}{l} 2\sqrt{(a^{2}+b^{2})(b^{2}+c^{2})}+2\sqrt{(b^{2}+c^{2})(c^{2}+a^{2})}+2\sqrt{(c^{2}+a^{2})(a^{2}+b^{2})}\geq\\ \qquad\qquad\qquad\geq a^{2}+b^{2}+c^{2}+3(ab+bc+ca). \end{array} $

Na mocy nierówności $\sqrt{2x^2 + 2y^2} \geq |x + y|$ , prawdziwej dla dowolnych liczb rzeczywistych $x$ , $y$ (sprawdzenie przez podniesienie do kwadratu), dostajemy

$ 2\sqrt{(a^{2}+b^{2})(b^{2}+c^{2})}\geq|(a+b)(b+c)|\geq b^{2}+(ab+bc+ca). $

Analogicznie uzyskujemy

$ 2\sqrt{(b^{2}+c^{2})(c^{2}+a^{2})}\geq c^{2}+(ab+bc+ca), 2\sqrt{(c^{2}+a^{2})(a^{2}+b^{2})}\geq a^{2}+(ab+bc+ca). $

Sumując stronami trzy ostatnie nierówności otrzymujemy tezę.

LV OM - III - Zadanie 5

Zawody matematyczne:

LV OM, 2003-2004

Etap:

III

Wyznaczyć największą liczbę prostych w przestrzeni, przechodzących przez ustalony punkt i takich, że każde dwie przecinają się pod jednakowym kątem.

Rozwiązanie

Niech $\ell_1,\ldots,\ell_n$ będą prostymi, o jakich mowa, przechodzącymi przez wspólny punkt $O$ . Para przecinających się prostych wyznacza na zawierającej je płaszczyźnie cztery kąty: dwa kąty wierzchołkowe o mierze $\alpha \leq 90^\circ$ i pozostałe dwa kąty o mierze $180^\circ - a$ . Zgodnie z założeniem, wartość $a$ jest dla każdej pary $\ell_i, \ell_j$ taka sama.

Weźmy pod uwagę sferę $S$ o środku $O$ i dowolnym promieniu, i oznaczmy przez $A_i$ , $B_i$ punkty przecięcia prostej $\ell_i$ z tą sferą. Każdy z odcinków $A_iA_j$ , $A_iB_j$ , $B_iB_j$ (dla $i \neq j$ ) jest cięciwą sfery $S$ , wyznaczoną przez kąt środkowy o mierze $\alpha$ lub $180^\circ - \alpha$ . Zatem te odcinki mają co najwyżej dwie różne długości $a$ i $b$ .

Ustalmy oznaczenia tak, by $\measuredangle A_iOA_n = \alpha$ dla $i = 1,\ldots,n-1$ . Wówczas punkty $A_1, \ldots, A_{n-1}$ leżą na jednym okręgu (położonym w płaszczyźnie prostopadłej do prostej $\ell_n$ ). Niech $A_1C$ będzie średnicą tego okręgu. Każdy z punktów $A_2,\ldots,A_{n-1}$ leży w odległości $a$ lub $b$ od punktu $A_1$ ; wobec tego na każdym z dwóch półokręgów o końcach $A_1$ i $C$ leżą co najwyżej dwa punkty ze zbioru $\{A_2,\ldots ,A_{n-1}\}$ . Stąd wniosek, że jest to zbiór co najwyżej czteroelementowy; a to znaczy, że $n \leq 6$ .

Z drugiej strony, jeśli $n = 6$ , to możemy umieścić punkty $A_1,A_2,\ldots,A_5$ w wierzchołkach pięciokąta foremnego, zaś płaszczyznę tego pięciokąta umieścić w takiej odległości od punktu $A_6$ , aby te sześć punktów, wraz z antypodycznymi do nich punktami $B_1,\ldots,B_6$ , były wierzchołkami dwudziestościanu foremnego. Odcinki $A_iB_i$ (średnice sfery $S$ ) łączą przeciwległe wierzchołki tego dwudziestościanu i każde dwa z nich tworzą jednakowy kąt. Zatem $n = 6$ jest największą możliwą liczbą prostych $\ell_i$ .

LV OM - III - Zadanie 6

Zawody matematyczne:

LV OM, 2003-2004

Etap:

III

Dana jest liczba całkowita $m> 1$ . Nieskończony ciąg liczb całkowitych $x_0,x_1,x_2,\ldots$ jest określony przez warunki

$ x_{i}=\left\{\begin{array}{ll} 2^{i}&\textrm{dla}\ i<m,\\ x_{i-1}+x_{i-2}+\ldots+x_{i-m}&\textrm{dla}\ i \geq m. \end{array}\right. $

Wyznaczyć największą liczbę naturalną $k$ , dla której istnieje $k$ kolejnych wyrazów tego ciągu podzielnych przez $m$ .

Rozwiązanie

Wzór rekurencyjny

$ (1) \quad x_{i}-x_{i-1}-x_{i-2}-\ldots-x_{i-m}=0\ \textrm{dla}\ i \geq m $

działa zarówno do przodu, jak i do tyłu; to znaczy, że każdy odcinek $m$ kolejnych wyrazów ciągu $(x_i)$ wyznacza zarówno wszystkie wyrazy późniejsze, jak i wszystkie wyrazy wcześniejsze. Ta sama uwaga odnosi się też do ciągu $r_0,r_1 ,r_2,\ldots,$ gdzie $r_i$ jest resztą z dzielenia $x_i$ przez $m$ ; wzór (1) implikuje wzór

$ (2) \qquad r_i - r_{i-1} - r_{i-2} -\ldots - r_{i-m} \equiv 0 \ (\mathrm{mod}\ m) \ \textrm{dla}\ i \geq m. $

W ciągu $(r_i)$ każdy odcinek długości $m$ jest układem złożonym z $m$ liczb ze zbioru $\{0,1,\ldots,m-1\}$ . Ponieważ jest tylko skończenie wiele takich układów, muszą się one powtarzać: istnieją numery $s,t$ ( $s < t$ ) takie, że

$ (r_t, r_{t+1},r_{t+2},\ldots,r_{t+m-1}) = (r_s, r_{s+1}, r_{s+2},\ldots, r_{s+m-1}). $

Każdy z tych dwóch odcinków ciągu $(r_i)$ jednoznacznie wyznacza wyraz bezpośrednio go poprzedzający; na mocy wzoru (2) te wyrazy też są równe: $r_{t-1} = r_{s-1}$ . Zatem

$ (r_{t-1}, r_t, r_{t+1},\ldots,r_{t+m-2}) = (r_{s-1}, r_{s}, r_{s+1},\ldots, r_{s+m-2}). $

Cofając się w ten sposób dojdziemy do odcinka identycznego z odcinkiem początkowym:

$ (r_d, r_{d+1},r_{d+2},\ldots,r_{d+m-1}) = (r_0, r_{1}, r_{2},\ldots, r_{m-1}). $

gdzie $d = t - s$ . Tak więc

$ r_d = 1,\ r_{d+1} = 2,\ r_{d+2} = 4,\ldots ,\ r_{d+m-1} = (2^{m-1} \mathrm{mod}\ m). $

Cofając się dalej, zgodnie ze wzorem (2), stwierdzamy kolejno, że

$ r_{d-1} = 1,\ r_{d-2} = 0, r_{d-3} = 0, \ldots,\ r_{d-m} = 0, $

i mamy $m - 1$ kolejnych wyrazów $x_{d-m}, \ldots , x_{d-2}$ podzielnych przez $m$ .

Oczywiście nie istnieje $m$ kolejnych wyrazów $x_i$ podzielnych przez $m$ , bo wówczas, w myśl wzoru (1), cały ciąg $(x_i)$ składałby się z liczb podzielnych przez $m$ , wbrew temu, że $x_0 = 1$ . Zatem szukana maksymalna wartość $k$ wynosi $m - 1$ .