LIV OM - III etap

III etap LIV Olimpiady Matematycznej

Załącznik	Wielkość
LIV OM III etap - Zadania [1]	66.22 KB
LIV OM III etap - Zadania z rozwiązaniami [2]	108.67 KB

LIV OM - III - Zadanie 1

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

III

W trójkącie ostrokątnym $ABC$ odcinek $CD$ jest wysokością. Przez środek $M$ boku $AB$ poprowadzono taką prostą przecinającą półproste $CA$ i $CB$ odpowiednio w punktach $K$ i $L$ , że $CK = CL$ . Punkt $S$ jest środkiem okręgu opisanego na trójkącie $CKL$ . Wykazać, że $SD = SM$ .

Rozwiązanie

Z twierdzenia Menelausa zastosowanego do trójkąta $ABC$ otrzymujemy

$ \frac{CK}{AK}\cdot\frac{AM}{MB}\cdot\frac{BL}{CL}=1,\ \textrm{skąd}\ AK=BL. $

Niech $E$ będzie drugim punktem przecięcia prostej $CS$ z okręgiem opisanym na trójkącie $CKL$ (rys. 1). Z równości $CK = CL$ wynika, że $EK = EL$ . Ponadto $\measuredangle AKE = 90^\circ = \measuredangle BLE$ .

Zatem trójkąty prostokątne $AKE$ oraz $BLE$ są przystające. Stąd uzyskujemy $AE = BE$ , czyli $EM \perp AB$ , a to daje $CD \parallel EM$ .

Ponieważ $S$ jest środkiem odcinka $CE$ , więc jego rzut prostokątny na prostą $AB$ pokrywa się ze środkiem odcinka $DM$ . Stąd $SD = SM$ .

LIV OM - III - Zadanie 2

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

III

Liczba $a$ jest dodatnia i mniejsza od 1. Dowieść, że dla każdego skończonego, ściśle rosnącego ciągu nieujemnych liczb całkowitych ( $k_1,\ldots,k_n$ ) zachodzi nierówność

$ \left( \sum_{i=1}^n a^{k_i} \right)^2 < \frac{1+a}{1-a} \sum_{i=1}^n a^{2k_i}. $

Rozwiązanie

Stosujemy indukcję względem $n$ . Dla $n =1$ nierówność ma postać

$ 1<\frac{1+a}{1-a} $

i oczywiście jest spełniona. Ustalmy $n \geq 2$ i załóżmy, że nierówność jest spełniona dla każdego rosnącego ciągu długości $n-1$ . Weźmy pod uwagę dowolny rosnący ciąg długości $n$ : $0 \leq k_1 <k_2 < \ldots <k_n$ . Dzieląc dowodzoną nierówność stronami przez $a^{2k_l}$ możemy bez straty ogólności przyjąć, że $k_1 = 0$ . Wówczas

$ (1) \qquad \left( \sum_{i=1}^n a^{k_i} \right)^2=\left(1 + \sum_{i=2}^n a^{k_i} \right)^2=1+ 2\sum_{i=2}^n a^{k_i}+\left( \sum_{i=2}^n a^{k_i} \right)^2. $

Z nierówności $0 <k_2 <k_3 < \ldots<k_n$ oraz $0 <a< 1$ wynika, że

$ \sum_{i=2}^n a^{k_i} \leq \sum_{j=1}^{k_n} a^j <\frac{a}{1-a}. $

Stąd, z równości (1) oraz z założenia indukcyjnego uzyskujemy

$ \left( \sum_{i=1}^n a^{k_i} \right)^2 < 1+ \frac{2a}{1-a} +\frac{1+a}{1-a} \sum_{i=2}^n a^{2k_i} = \frac{1+a}{1-a}\left(1+ \sum_{i=2}^n a^{2k_i}\right) = \frac{1+a}{1-a} \sum_{i=1}^n a^{2k_i}. $

To kończy krok indukcyjny i rozwiązanie zadania.

LIV OM - III - Zadanie 3

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

III

Wyznaczyć wszystkie wielomiany $W$ o współczynnikach całkowitych, spełniające następujący warunek: dla każdej liczby naturalnej $n$ liczba $2^n-1$ jest podzielna przez $W(n)$ .

Rozwiązanie

Niech $W(x) = a_0 + a_1x +\ldots + a_rx^r$ będzie wielomianem o współczynnikach całkowitych, spełniającym rozważany warunek. Przypuśćmy, że dla pewnej liczby naturalnej $k$ wartość $W(k)$ jest różna od $1$ i od $-1$ ; ma więc dzielnik pierwszy $p$ . Niech $m = k + p$ . Różnica $W(m) - W(k)$ jest sumą różnic postaci $a_j(m^j - k^j)$ , które są liczbami podzielnymi przez $m - k$ , czyli przez $p$ . Zatem $W(m)$ dzieli się przez $p$ .

Z warunku zadania wynika, że $p$ jest dzielnikiem liczb $2^k - 1$ oraz $2^m - 1$ ; jest więc nieparzystym dzielnikiem pierwszym liczby $2^m - 2^k = 2^k (2^p - 1)$ , czyli jest dzielnikiem liczby $2^p - 1$ . To jednak nie jest możliwe, bowiem

$ 2^p-1=1+{p \choose 1}+{p \choose 2}+\ldots+{p \choose {p-1}}, $

a wartości symbolu Newtona ${p \choose i}$ są dla $i = 1,\ldots,p- 1$ liczbami podzielnymi przez $p$ .

Sprzeczność dowodzi, że $W(n) = \pm 1$ dla każdej liczby naturalnej $n$ . Stąd wniosek, że $W$ jest wielomianem równym tożsamościowo $1$ lub równym tożsamościowo $-1$ . Oczywiście każdy z tych dwóch wielomianów spełnia postulowany warunek.

LIV OM - III - Zadanie 4

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

III

Dana jest liczba pierwsza p oraz takie liczby całkowite $x$ , $y$ , $z$ , że

$ 0 <x <y < z <p. $

Wykazać, że jeśli liczby $x^3$ , $y^3$ , $z^3$ dają takie same reszty przy dzieleniu przez $p$ , to liczba $x^2 + y^2 + z^2$ jest podzielna przez $x + y + z$ .

Rozwiązanie

Ponieważ liczba $y^3 - x^3 = (y - x)(x^2 + xy + y^2)$ jest podzielna przez $p$ oraz $0 <y - x<p$ , więc liczba $x^2 + xy + y^2$ jest podzielna przez $p$ . Podobnie liczby $y^2 + yz + z^2$ oraz $x^2 + xz + z^2$ są podzielne przez $p$ . Zatem liczba

$ (x^2 + xy + y^2) - (y^2 + yz + z^2) = (x - z)(x + y + z) $

jest również podzielna przez $p$ , co implikuje podzielność przez $p$ liczby $x+y+z$ . Liczba ta jako mniejsza od $3p$ jest więc równa $p$ lub $2p$ .

Z podzielności przez $p$ liczb $x^2+xy+y^2$ , $y^2+yz+z^2$ oraz $x^2+xz+z^2$ wynika podzielność przez $p$ ich sumy pomnożonej przez $2$ , czyli liczby

$ 2(2x^2 + 2y^2 + 2z^2 + xy + yz + xz) =3(x^2 + y^2 + z^2) + (x + y + z)^2 . $

Z danych w treści zadania nierówności wnioskujemy, że $p> 3$ , co w połączeniu z powyższą równością dowodzi podzielności przez $p$ liczby $x^2 + y^2 + z^2$ .

Zatem w przypadku $x + y + z = p$ zadanie zostało rozwiązane. Jeśli zaś $x + y + z = 2p$ , to z równości $(x + y + z)^2 = x^2 + y^2 + z^2 + 2(xy + yz + zx)$ wynika, że liczba $x^2+y^2+z^2$ jest parzysta. Jest ona również podzielna przez $p$ , a zatem dzieli się także przez $x+ y+ z$ .

LIV OM - III - Zadanie 5

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

III

Sfera wpisana w czworościan $ABCD$ jest styczna do ściany $ABC$ w punkcie $H$ . Druga sfera jest styczna do ściany $ABC$ w punkcie $O$ oraz jest styczna do płaszczyzn zawierających pozostałe ściany tego czworościanu w punktach, które do czworościanu nie należą. Dowieść, że jeżeli $O$ jest środkiem okręgu opisanego na trójkącie $ABC$ , to $H$ jest punktem przecięcia wysokości tego trójkąta.

Rozwiązanie

Oznaczmy przez $K$ i $L$ punkty styczności sfery wpisanej w czworościan $ABCD$ odpowiednio ze ścianami $ACD$ i $BCD$ . Niech ponadto $P$ i $Q$ będą punktami styczności drugiej rozważanej w treści zadania sfery, odpowiednio z płaszczyznami $ACD$ i $BCD$ . Wówczas trójkąty $KCP$ i $LCQ$ są przystające (cecha bok-bok-bok). Obróćmy trójkąt $KCP$ wokół prostej $AC$ tak, aby punkt $K$ przeszedł na punkt $H$ ; niech przy tym obrocie $P$ przejdzie na $P'$ . Podobnie, obróćmy trójkąt $LCQ$ wokół prostej $BC$ tak, aby punkt $L$ przeszedł na punkt $H$ ; niech przy tym obrocie $Q$ przejdzie na $Q'$ .

Dalsza część rozwiązania rozgrywa się w płaszczyźnie trójkąta $ABC$ : Trójkąty $HCP'$ i $HCQ'$ są przystające, więc $P'Q' \perp CH$ . Ponadto czworokąty $AOCP'$ i $BOCQ'$ są rombami, co implikuje $AB \parallel P'Q'$ . Zatem $CH \perp AB$ .

Analogicznie dowodzimy, że $BH \perp AC$ , a to oznacza, że $H$ jest punktem przecięcia wysokości trójkąta $ABC$ .

LIV OM - III - Zadanie 6

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

III

Niech n będzie dodatnią liczbą całkowitą parzystą. Udowodnić, że istnieje permutacja $(x_1,x_2, \ldots ,x_n)$ zbioru $\{1,2,\ldots,n\}$ , spełniająca dla każdego $i \in \{1,2,\ldots ,n\}$ warunek:

$x_{i+1}$ jest jedną z liczb $2x_i$ , $2x_i-1$ , $2x_i-n$ , $2x_i-n-1$ ,

przy czym $x_{n+1} = x_1$ .

Rozwiązanie

Przyjmijmy oznaczenia:

$f(x)= \left\{\begin{array}{ll} 2x&\textrm{gdy}\ x \leq n/2,\\ 2x-n&\textrm{gdy}\ x>n/2,\\ \end{array}\right. $

$ g(x)=f(x)-1. $

Rozważamy graf skierowany o $n$ wierzchołkach ponumerowanych $1,2,\ldots,n$ , w którym z punktu (wierzchołka) $x$ wychodzą dwie zorientowane krawędzie: do punktu $f(x)$ i do $g(x)$ . Teza sprowadza się do istnienia zamkniętej ścieżki, przechodzącej przez każdy wierzchołek dokładnie jeden raz (cyklu Hamiltona).

Startując od wierzchołka o numerze $1$ i działając funkcjami $f$ , $g$ , możemy uzyskać: w jednym kroku - punkty $1$ i $2$ ; w dwóch krokach - punkty $1$ , $2$ , $3$ , $4$ ; w trzech krokach - punkty od $1$ do $8$ ; itd. Widać, że każdy punkt jest osiągalny z wierzchołka $1$ .

Niech $S: x_1 \to x_2 \to \ldots \to x_m$ będzie najdłuższą ścieżką, przechodzącą przez różne wierzchołki, wśród których jest wierzchołek o numerze $1$ . Obie wychodzące z punktu $x_m$ krawędzie trafiają w pewne punkty ścieżki $S$ (w przeciwnym razie ścieżkę dałoby się przedłużyć). Mamy więc krawędzie $x_m \to x_k$ , $x_m \to x_\ell$ ( $k,\ell \leq m$ , $k \neq \ell$ ); niech np. $f (x_m) = x_k$ , $g(x_m) = x_\ell$ .

Przypuśćmy, że $k,\ell> 1$ . Wówczas

$ x_k \in \{f (x_{k-1}),g(x_{k-1})\},\ x_\ell \in \{f (x_{\ell-1}),g(x_{\ell-1})\}. $

Funkcja $f$ przyjmuje tylko wartości parzyste, a $g$ wartości nieparzyste. Ponadto każda z równości $f (x) = f (y)$ i $g(x) = g(y)$ implikuje $x \equiv y (\mathrm{mod}\ n/2)$ . Zatem

$ x_k=f(x_{k-1})=f(x_m),\ x_\ell=g(x_{\ell-1})=g(x_m), $

skąd $x_m \equiv x_{k-1} \equiv x_{\ell-1} (\mathrm{mod}\ n/2)$ - sprzeczność, bo $x_m, x_{k-1}, x_{\ell- 1}$ są trzema różnymi liczbami ze zbioru $\{1, 2, \ldots , n\}$ .

Zatem $k = 1$ lub $\ell =1$ , co oznacza, że $x_m \to x_1$ jest krawędzią grafu. Uzupełnia ona ścieżkę $S$ do zamkniętego cyklu. Załóżmy, że poza nią pozostały jakieś wierzchołki grafu. Są one osiągalne z wierzchołka o numerze $1$ (leżącego na ścieżce $S$ ). Zatem z pewnego punktu tej ścieżki, $x_p$ , musi wychodzić krawędź do punktu $y$ leżącego poza nią. Wtedy $x_{p+1} \to \ldots \to x_m \to x_1 \to \ldots \to x_p \to y$ jest ścieżką przechodzącą przez $m+1$ różnych wierzchołków (wśród których jest punkt $1$ ), wbrew maksymalności $m$ .

Wniosek: ścieżka $S$ , uzupełniona krawędzią $x_m \to x_1$ , jest cyklem przechodzącym przez wszystkie wierzchołki grafu.