LIV OM

LIV Olimpiada Matematyczna

LIV OM - I etap

I etap LV Olimpiady Matematycznej

Załącznik	Wielkość
LIV OM I etap - Zadania [1]	97.1 KB
LIV OM I etap - Zadania z rozwiązaniami [2]	143.67 KB

LIV OM - I - Zadanie 1

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

Znaleźć wszystkie pary liczb całkowitych dodatnich $x$ , $y$ spełniających równanie

$ (x + y)^2 - 2(xy)^2 = 1. $

Rozwiązanie

Dla dowolnych liczb rzeczywistych $x,y \geq 2$ mamy

$ (1) \qquad xy = x \cdot \frac{y}{2} + y \cdot \frac{x}{2} \geq x + y. $

Zatem dla liczb rzeczywistych $x,y \geq 2$ prawdziwe są nierówności

$ 2(xy)^2 + 1 > (xy)^2 \geq (x + y)^2 , $

co oznacza, że dane równanie nie ma rozwiązań w liczbach naturalnych (a nawet rzeczywistych) $x,y \geq 2$ .

Wobec tego, jeśli para $(x,y)$ liczb całkowitych dodatnich spełnia dane w treści zadania równanie, to jedna z liczb $x$ , $y$ musi być równa 1. Przyjmijmy ze względu na symetrię, że tą liczbą jest $x$ . Dane równanie przyjmuje wówczas postać $(y + 1)^2 - 2y^2 = 1$ . Po uproszczeniu dostajemy $y^2 - 2y = 0$ , skąd $y = 2$ .

Równanie ma więc dwa rozwiązania: $x = 1$ , $y = 2$ oraz $x = 2$ , $y = 1$ .

Uwaga: Kluczem do rozwiązania zadania jest nierówność $xy \geq x + y$ prawdziwa dla dowolnych liczb rzeczywistych $x,y \geq 2$ . Jej krótki dowód został przedstawiony w powyższym rozwiązaniu w linijce (1). Inny, równie krótki dowód to:

$ x,y \geq 2 \Rightarrow (x - 1)(y - 1) \geq 1 \Leftrightarrow xy \geq x + y. $

LIV OM - I - Zadanie 2

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

Dana jest liczba rzeczywista $a_1 > 1$ . Definiujemy ciąg $(a_n)$ wzorem

$ a_{n+1} = a_n^2 - a_{n} + 1 \ \textrm{dla}\ n \geq 1. $

Dowieść, że dla każdej liczby naturalnej $n$ zachodzi nierówność

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

Rozwiązanie

Niech $b_n = a_n - 1$ . Wówczas daną w treści zadania zależność rekurencyjną możemy przepisać w postaci

$ b_{n+1} = b_n(b_n + 1) \ \textrm{dla}\ n \geq 1. $

Z powyższego wzoru oraz z nierówności $b_1 > 0$ uzyskujemy przez indukcję nierówność $b_n > 0$ dla dowolnego $n \geq 1$ . Ponadto

$ \frac{1}{b_{n}}-\frac{1}{b_{n+1}}=\frac{1}{b_{n}}-\frac{1}{b_{n}(b_n+1)}=\frac{b_n+1-1}{b_{n}(b_n+1)}=\frac{1}{b_n+1}=\frac{1}{a_n}. $

Stąd otrzymujemy

$ \begin{array}{l} \frac{1}{a_1}+\frac{1}{a_2}+\ldots+\frac{1}{a_n} =\\ \qquad=\left(\frac{1}{b_1} - \frac{1}{b_2} \right) + \left(\frac{1}{b_2} - \frac{1}{b_3} \right)+\left(\frac{1}{b_3} - \frac{1}{b_4}\right)+\ldots +\left(\frac{1}{b_n} - \frac{1}{b_{n+1}} \right) =\\ \qquad= \frac{1}{b_1} - \frac{1}{b_{n+1}} = \frac{1}{a_1-1} - \frac{1}{b_{n+1}}< \frac{1}{a_1-1}, \end{array} $

czego należało dowieść.

LIV OM - I - Zadanie 3

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

Trzy różne punkty $A$ , $B$ , $C$ leżą na okręgu $o$ . Proste styczne do okręgu $o$ w punktach $A$ i $B$ przecinają się w punkcie $P$ . Prosta styczna do okręgu $o$ w punkcie $C$ przecina prostą $AB$ w punkcie $Q$ . Udowodnić, że

$ PQ^2 = PB^2 + QC^2. $

Rozwiązanie

Niech $M$ będzie środkiem odcinka $AB$ (rys. 1). Wówczas trójkąt $PMQ$ jest prostokątny. Na mocy twierdzenia Pitagorasa oraz podobieństwa trójkątów $QBC$ i $QCA$ otrzymujemy

$ \begin{array}{rcl} PQ^2 &=& PM^2 + QM^2 = PB^2 - MB^2 + QM^2 \\ &=& PB^2 + (QM-MB )(QM+MB) \\ &=& PB^2 + QB \cdot QA = PB^2 + QC^2, \end{array} $

co należało udowodnić.

LIV OM - I - Zadanie 4

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

Rozpatrujemy zbiór wszystkich $k$ -wyrazowych ciągów o wyrazach ze zbioru $\{1, 2, 3,\ldots , m\}$ . Z każdego takiego ciągu wybieramy wyraz najmniejszy i sumujemy wybrane wyrazy. Udowodnić, że otrzymana suma jest równa

$ 1^k + 2^k + 3^k + \ldots + m^k. $

Rozwiązanie

Oznaczmy przez $L_i$ $(i =1,2,\ldots,m)$ liczbę tych $k$ -wyrazowych ciągów o wyrazach ze zbioru $\{1, 2, 3, \ldots , m\}$ , których każdy wyraz jest nie mniejszy niż $i$ . Ciągi takie to $k$ -wyrazowe ciągi o wyrazach z $(m-i+1)$ -elementowego zbioru

$ \{i, i +1, i + 2, \ldots ,m\}. $

Stąd wynika, że $L_i = (m-i+1)^k$ . Zatem liczba ciągów o najmniejszym wyrazie równym $i$ wynosi $L_i - L_{i+1} = (m - i + 1)^k - (m - i)^k$ .

Suma wszystkich wyrazów najmniejszych jest więc równa

$ \begin{array}{l} 1\cdot(m^k-(m-1)^k)+2\cdot((m-1)^k-(m-2)^k)+3\cdot((m-2)^k-(m-3)^k)+\ldots\\ \qquad\qquad\qquad\qquad\qquad \ldots+(m-1)\cdot(2^k-1^k)+m\cdot 1^k=\\ \qquad=1^k+2^k+3^k+\ldots+m^k, \end{array} $

czego należało dowieść.

LIV OM - I - Zadanie 5

Zawody matematyczne:

LIV OM, 2002-2003

Liczba naturalna $n_1$ zapisana jest w układzie dziesiętnym za pomocą 333 cyfr, z których żadna nie jest zerem. Dla $i = 1 , 2, 3, \ldots , 332$ liczba $n_{i+1}$ powstaje z liczby $n_i$ przez przeniesienie cyfry jedności na początek. Dowieść, że albo wszystkie liczby $n_1, n_2, n_3, \ldots , n_{333}$ są podzielne przez 333, albo żadna z nich.

Rozwiązanie

Niech $j_i$ $(i = 1,2,3,\ldots ,333)$ oznacza cyfrę jedności liczby $n_i$ . Wówczas dla $i =1,2,\ldots,332$ mamy

$ (1) \qquad n_{i+1}=\frac{n_i+10^{333}j_i-j_i}{10},\ \textrm{skąd}\ 10n_{i+1}=n_i+(10^{333}-1)j_i. $

Liczba $10^{333} - 1 = (10^3 - 1) \cdot (10^{330} + 10^{327} + 10^{324} +\ldots + 10^3 + 1)$ jest podzielna przez 333 oraz liczby 10 i 333 są względnie pierwsze. Z drugiej równości (1) wynika zatem, że liczba $n_i$ jest podzielna przez 333 wtedy i tylko wtedy, gdy liczba $n_{i+1}$ jest podzielna przez 333.

Jeśli liczba $n_1$ jest podzielna przez 333, to na mocy powyższego stwierdzenia uzyskujemy (indukcyjnie) podzielność przez 333 każdej z liczb $n_2, n_3, \ldots , n_{333}$ . Jeżeli natomiast liczba $n_1$ nie dzieli się przez 333, to analogicznie jak wyżej wnioskujemy, że żadna z liczb $n_2, n_3, \ldots , n_{333}$ nie dzieli się przez 333.

LIV OM - I - Zadanie 6

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

Punkty $A$ , $B$ , $C$ , $D$ leżą w tej właśnie kolejności na okręgu $o$ . Punkt $M$ jest środkiem tego łuku $AB$ okręgu $o$ , który nie zawiera punktów $C$ i $D$ ; punkt $N$ jest środkiem tego łuku $CD$ okręgu o, który nie zawiera punktów $A$ i $B$ . Dowieść, że

$ \frac{AN^2-BN^2}{AB}=\frac{DM^2-CM^2}{CD}. $

Rozwiązanie

Z twierdzenia Ptolemeusza (zob. LI Olimpiada Matematyczna, Sprawozdanie Komitetu Głównego, Dodatek D, str. 112) zastosowanego do czworokąta $AMBN$ uzyskujemy równość $BM \cdot (AN + BN) = MN \cdot AB$ . Stąd

$ \frac{AN^2-BN^2}{AB}=\frac{(AN-BN)\cdot MN}{BM}. $

Zatem zadanie sprowadza się do wykazania, że

$ (1)\qquad\frac{AN-BN}{BM}=\frac{DM-CM}{CN}. $

Bez straty ogólności przyjmijmy, że $AN < BN$ ; wtedy $DM < CM$ . Niech $A'$ będzie punktem symetrycznym do $A$ względem prostej $MN$ (rys. 2). Ponieważ $MN$ jest dwusieczną kąta $ANB$ , punkt $A'$ leży na odcinku $BN$ . Ponadto $BM = AM = A'M$ .

Analogicznie, oznaczając przez $D'$ punkt symetryczny do $D$ względem prostej $MN$ wnioskujemy, że punkt $D'$ leży na odcinku $CM$ oraz $CN = D'N$ . Na mocy równości

$ \measuredangle MBN = \measuredangle MCN , $

trójkąty równoramienne $BMA'$ i $CND'$ są podobne. Stąd

$ \frac{BA'}{BM} = \frac{CD'}{CN}, $

co jest równoważne dowodzonej równości (1).

LIV OM - I - Zadanie 7

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

U cioci Reni spotkało się (łącznie z ciocią) $n \geq 4$ osób. Każdy z obecnych podarował co najmniej jednej z pozostałych osób co najmniej jeden prezent. Okazało się, że każdy podarował trzykrotnie więcej prezentów niż sam otrzymał, z jednym wyjątkiem: ciocia Renia podarowała zaledwie $\frac{1}{6}$ liczby prezentów, które dostała. Wyznaczyć, w zależności od $n$ , najmniejszą możliwą liczbę prezentów, które mogła otrzymać ciocia Renia.

Rozwiązanie

Oznaczmy przez $x_i$ ( $i = 1,2, \ldots ,n-1$ ) liczbę prezentów otrzymanych przez $i$ -tego gościa cioci Reni oraz niech $x_R$ oznacza liczbę prezentów, które otrzymała ciocia Renia. Wówczas łączna liczba prezentów wynosi

$ (1) \qquad \sum^{n-1}_{i=1} x_i+x_R=\sum^{n-1}_{i=1} 3x_i+\frac{1}{6} x_R,\ \textrm{skąd}\ \sum^{n-1}_{i=1} x_i=\frac{5}{12}{x_R}. $

Zatem liczba $x_R$ jest podzielna przez $12$ , powiedzmy $x_R = 12k$ , gdzie $k$ jest pewną liczbą całkowitą nieujemną.

Ponieważ każda osoba podarowała co najmniej jeden prezent, więc musiała ona także otrzymać przynajmniej jeden upominek. Stąd wnioskujemy, że $x_i \geq 1$ dla $i = 1,2,\ldots ,n-1$ , co na mocy drugiej równości (1) daje $5k \geq n- 1$ . Ponieważ liczba $k$ jest całkowita, więc ostatnia nierówność jest równoważna nierówności $k \geq [(n-1+4)/5]$ , gdzie $[a]$ oznacza największą liczbę całkowitą nie większą niż $a$ . Zatem

$ x_R\geq \left[ \frac{n+3}{5} \right]. $

Pozostaje wykazać, że przy spełnieniu warunków zadania możliwe jest, aby ciocia Renia dostała dokładnie $12 [(n+3)/5]$ prezentów.

Załóżmy, że $n - 1 = 5k - r$ , gdzie $r = 0,1,2,3,4$ , zaś $k$ jest pewną liczbą całkowitą dodatnią. Podzielmy $n-1$ gości cioci Reni na (co najwyżej) trzy rozłączne grupy:

$ A_1,A_2,\ldots,A_{3k-r} , \ B_1,B_2,\ldots,B_{2k-r} , \ C_1,C_2,\ldots ,C_r . $

(Ponieważ $n \geq 4$ , więc $2k-r \geq 0$ .) Następnie posadźmy wszystkie osoby $A_i$ oraz $C_i$ przy okrągłym stole i przyjmijmy, że:

Każda osoba $A_i$ , $C_i$ daje 1 prezent osobie siedzącej po jej prawej stronie;
Każda osoba $A_i$ daje 2 prezenty cioci Reni;
Każda osoba $B_i$ daje 3 prezenty cioci Reni;
Każda osoba $C_i$ daje 5 prezentów cioci Reni;
Ciocia Renia daje po 1 prezencie każdej osobie $B_i$ oraz $C_i$ .

W ten sposób każda osoba $A_i$ oraz $B_i$ podarowała $3$ prezenty, zaś otrzymała jeden, natomiast każda osoba $C_i$ dała $6$ prezentów, a sama dostała dwa. Zatem każdy gość cioci Reni podarował trzykrotnie więcej prezentów niż sam dostał. Z kolei ciocia Renia otrzymała

$ 2(3k - r) +3(2k - r) + 5r = 12k = 12[(n+3)/5] $

prezentów, sama zaś podarowała $2k$ upominków, czyli sześciokrotnie mniej.

Odpowiedź: Ciocia Renia mogła otrzymać co najmniej 12[(n+3)/5] prezentów.

LIV OM - I - Zadanie 8

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

W czworościanie $ABCD$ punkty $M$ i $N$ są odpowiednio środkami krawędzi $AB$ i $CD$ . Punkt $P$ leży na odcinku $MN$ , przy czym $MP = CN$ oraz $NP = AM$ . Punkt $O$ jest środkiem sfery opisanej na czworościanie $ABCD$ . Dowieść, że jeżeli $O \neq P$ , to $OP \perp MN$ .

Rozwiązanie

Wprowadźmy następujące oznaczenia:

$ \alpha = \measuredangle OPM,\ a = AM = MB = NP, \ b = CN = ND = MP, x = OP. $

Wówczas na mocy twierdzenia cosinusów mamy

$ (1) \qquad OM^2 = b^2 + x^2 + 2bx \cos \alpha \ \textrm{oraz}\ ON^2 = a^2 + x^2 2ax \cos \alpha . $

Ponadto korzystając z twierdzenia Pitagorasa otrzymujemy

$ (2) \qquad OM^2 + a^2 = OA^2 = OD^2 = ON^2 + b^2. $

Odejmując stronami równości (1) oraz wykorzystując zależność (2) uzyskujemy $2(a + b)x \cos a = 0$ . Stąd $\alpha = 90^\circ$ , czyli $OP \perp MN$ .

LIV OM - I - Zadanie 9

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

Znaleźć wszystkie wielomiany $W$ o współczynnikach rzeczywistych, mające następującą własność: jeśli $x+ y$ jest liczbą wymierną, to

$ W(x) + W(y) $

jest liczbą wymierną.

Rozwiązanie

Zauważmy najpierw, że warunki zadania są spełnione przez każdy wielomian postaci $W(x) = ax + b$ , gdzie $a$ i $b$ są liczbami wymiernymi.

Udowodnimy, że są to wszystkie wielomiany o własności podanej w zadaniu.

Niech $W$ będzie wielomianem spełniającym warunki zadania. Dla liczby wymiernej $q$ rozważamy wielomian $P(x) = W(q + x) + W(q - x)$ . Wielomian $P$ przyjmuje wartości wymierne dla wszystkich argumentów rzeczywistych $x$ , jest więc wielomianem stałym równym $P(0) = 2W(q)$ . Stąd wynika, że dla dowolnej liczby całkowitej $n$ zachodzi równość $W(n - 1) + W(n +1) = 2W(n)$ , czyli

$ W(n) - W(n - 1) = W(n +1) - W(n). $

Niech $V(x) = W(x) - ax - b$ , gdzie $a = W(1) - W(0)$ oraz $b = W(0)$ . Wówczas $V(0) = V(1) = 0$ oraz dla dowolnej liczby całkowitej n zachodzi równość

$ V(n) - V(n - 1) = V(n +1) - V(n). $

Zatem wielomian $V$ przyjmuje wartość $0$ dla wszystkich argumentów całkowitych, musi więc być wielomianem zerowym, a w konsekwencji $W(x) = ax + b$ .

LIV OM - I - Zadanie 10

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

Mamy talię 52 kart. Tasowaniem będziemy nazywać wykonanie następujących czynności: dowolny podział talii na część górną i dolną, a następnie dowolne zmieszanie kart z zachowaniem porządku w obrębie każdej części. Mówiąc formalnie, tasowaniem jest dowolne przemieszanie kart, w którym $i$ -ta karta od wierzchu przechodzi na pozycję $p_i$ , przy czym istnieje takie $m\in \{ 1, 2, 3, \ldots, 51\}$ , że $p_i < p_{i+1}$ dla $i<m$ oraz dla $i > m$ .

Rozstrzygnąć, czy rozpoczynając od ustalonego początkowego uporządkowania kart, można uzyskać każde inne uporządkowanie wykonując pięć tasowań.

Rozwiązanie

Udowodnimy, że po pięciu tasowaniach nie można uzyskać porządku odwrotnego do wyjściowego.

Zauważmy, że karty, które podczas pewnego tasowania znalazły się w tej samej części, nie zmieniają wzajemnego porządku po tym tasowaniu.

Spośrod 52 kart podczas pierwszego tasowania w jednej z części znajdzie się co najmniej 26 kart. Spośród tych 26 kart co najmniej 13 znajdzie się w jednej części także podczas drugiego tasowania.

Rozumując podobnie dalej wnioskujemy, że istnieje co najmniej 7 kart, które będą się znajdowały w tej samej części przez pierwsze trzy tasowania. Co najmniej 4 z nich będą w tej samej części także przy czwartym tasowaniu, a pewne dwie po wszystkich pięciu tasowaniach. Zatem zawsze będą istniały dwie karty, które przez pięć tasowań nie zmienią wzajemnego położenia.

Nie można więc uzyskać kart w porządku odwrotnym do wyjściowego, gdyż wtedy każde dwie karty musiałyby zmienić wzajemną kolejność.

LIV OM - I - Zadanie 11

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

Dany jest czworokąt wypukły $ABCD$ . Punkty $P$ i $Q$ , różne od wierzchołków czworokąta, leżą odpowiednio na bokach $BC$ i $CD$ , przy czym $\measuredangle BAP = \measuredangle DAQ$ . Udowodnić, że trójkąty $ABP$ i $ADQ$ mają równe pola wtedy i tylko wtedy, gdy ich ortocentra leżą na prostej prostopadłej do $AC$ .

Uwaga: Ortocentrum trójkąta to punkt przecięcia wysokości.

Rozwiązanie

Oznaczmy przez $K$ , $L$ rzuty prostokątne punktów $A$ , $B$ odpowiednio na proste $BC$ , $AP$ (rys. 3). Niech ponadto $H$ oznacza ortocentrum trójkąta $ABP$ oraz niech $X$ będzie rzutem prostokątnym punktu $H$ na prostą $AC$ .

Korzystając z podobieństwa trójkątów prostokątnych $AHL$ i $APK$ otrzymujemy

$ \frac{AH}{AL}=\frac{AP}{AK}. $

Analogicznie, z podobieństwa trójkątów prostokątnych $AHX$ i $ACK$ uzyskujemy zależność

$ \frac{AH}{AX}=\frac{AC}{AK}. $

Wprowadźmy następujące oznaczenie:

$ \alpha = \measuredangle BAP = \measuredangle DAQ. $

Z nierówności $\measuredangle BAD < 180^\circ$ wynika, że $\alpha< 90^\circ$ . Zatem

$ (1) \qquad AC\cdot AX = AH\cdot AK = AP\cdot AL = AP\cdot BL\cdot \mathrm{ctg} \alpha = 2 [ABP] \cdot \mathrm{ctg}\alpha, $

gdzie $[TUW]$ oznacza pole trójkąta $TUW$ .

Oznaczmy przez $Y$ rzut prostokątny ortocentrum trójkąta $ADQ$ na prostą $AC$ . Wówczas, analogicznie jak wyżej, otrzymujemy zależność

$ (2) AC \cdot AY = 2[ADQ] \cdot \mathrm{ctg} \alpha. $

Porównując równości (1) oraz (2) wnioskujemy, że $[ABP] = [ADQ]$ wtedy i tylko wtedy, gdy $AX = AY$ . Ostatnia równość jest równoważna stwierdzeniu, że ortocentra trójkątów $ABP$ i $ADQ$ leżą na prostej prostopadłej do $AC$ , jeśli przekonamy się, że punkty $X$ i $Y$ leżą na prostej $AC$ po tej samej stronie punktu $A$ .

W tym celu wykażemy, że punkt $X$ leży na półprostej $AC^\rightarrow$ Ponieważ $\alpha< 90^\circ$ , więc punkt $H$ leży na półprostej $AK^\rightarrow$ . Ponadto trójkąt $AKC$ jest prostokątny (lub $K = C$ ), więc rzut prostokątny półprostej $AK^\rightarrow$ na prostą $AC$ pokrywa się z półprostą $AC^\rightarrow$ Stąd bezpośrednio wynika, że punkt $X$ leży na półprostej $AC^\rightarrow$ Analogicznie dowodzimy, że punkt $Y$ leży na półprostej $AC^\rightarrow$ , co kończy rozwiązanie zadania.

Uwaga: Rysunek 3 przedstawia przypadek, w którym trójkąty $ABP$ i $ADQ$ są ostrokątne. Zaprezentowane rozwiązanie pozostaje jednak w mocy dla każdej innej konfiguracji spełniającej warunki zadania.

LIV OM - I - Zadanie 12

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

Dla liczb dodatnich $a$ , $b$ , $c$ , $d$ określamy

$ A = a^3 + b^3 + c^3 + d^3, \ B = bcd + cda + dab + abc. $

Udowodnić nierówność

$ (a + b + c + d)^3 < 4A + 24B. $

Rozwiązanie

Niech $S = a + b + c + d$ . Wtedy $S^3 = A + 6B + 3Q$ , gdzie

$ \begin{array}{rcl} Q &=& a^2(b+c + d)+ b^2 (c + d+a)+ c^2 (d+a + b) + d^2(a + b+c) = \\ &=& a^2(S - a) + b^2(S - b)+ c^2(S - c) + d^2 (S - d) = \\ &=& a(Sa - a^2) + b(Sb - b^2) + c(Sc - c^2) + d(Sd - d^2). \end{array} $

Korzystając z nierówności

$ 0\leq \left(x- \frac{S}{2} \right)^2=x^2-Sx+\frac{S^2}{4} $

prawdziwej dla dowolnej liczby rzeczywistej $x$ otrzymujemy

$ Sa - a^2 \leq \frac{S^2}{4},\ Sb-b^2 \leq \frac{S^2}{4},\ Sc - c^2 \leq \frac{S^2}{4} \ \textrm{oraz} \ Sd - d^2 \leq \frac{S^2}{4}. $

Zatem

$ Q \leq (a + b+c + d) \cdot \frac{S^2}{4} = \frac{S^3}{4}, \ \textrm{skąd} \ S^3 \leq A + 6B + \frac{3S^3}{4} , $

co daje $S^3 < 4A + 24B$ , czyli nierówność, którą należało udowodnić.

LIV OM - II etap

II etap LIV Olimpiady Matematycznej

Załącznik	Wielkość
LIV OM II etap - Zadania [3]	53.91 KB
LIV OM II etap - Zadania z rozwiązaniami [4]	115.88 KB

LIV OM - II - Zadanie 1

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

Dowieść, że istnieje taka liczba całkowita $n> 2003$ , że w ciągu

$ {n \choose 0},\ {n \choose 1}, {n \choose 2},\ldots ,{n \choose 2003} $

każdy wyraz jest dzielnikiem wszystkich wyrazów po nim następujących.

Rozwiązanie

Liczba ${n \choose {k+1}}$ jest podzielna przez ${n \choose k},$ wtedy i tylko wtedy, gdy liczba

$ \frac{{n \choose {k+1}}}{{n \choose k}}=\frac{n!}{(k+1)!\cdot(n-k-1)!}\frac{k!\cdot(n-k)!}{n!} =\frac{n-k}{k+1}=\frac{n+1}{k+1}-1 $

jest całkowita. Zatem liczba $n$ spełnia warunki zadania wtedy i tylko wtedy, gdy liczba $n +1$ jest podzielna przez każdą z liczb $1, 2, 3, 4, \ldots, 2003$ . Taką liczbą jest na przykład $n = 2003! - 1$ .

LIV OM - II - Zadanie 2

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

Czworokąt $ABCD$ jest wpisany w okrąg $o$ . Dwusieczne kątów $DAB$ i $ABC$ przecinają się w punkcie $P$ , a dwusieczne kątów $BCD$ i $CDA$ przecinają się w punkcie $Q$ . Punkt $M$ jest środkiem tego łuku $BC$ okręgu $o$ , który nie zawiera punktów $D$ i $A$ . Punkt $N$ jest środkiem tego łuku $DA$ okręgu $o$ , który nie zawiera punktów $B$ i $C$ . Dowieść, że punkty $P$ i $Q$ leżą na prostej prostopadłej do $MN$ .

Rozwiązanie

Załóżmy najpierw, że proste $AD$ i $BC$ są równoległe. Wówczas czworokąt $ABCD$ jest trapezem równoramiennym. Jego podstawy $BC$ i $AD$ są prostopadłe do prostej $MN$ . Ponadto punkty $P$ i $Q$ leżą na prostej równoległej do podstaw trapezu i równoodległej od nich. Stąd teza.

Przyjmijmy z kolei, że proste $AD$ i $BC$ nie są równoległe i przecinają się w punkcie $S$ (rys. 1). Punkt $P$ jest środkiem okręgu stycznego do odcinków $AB$ , $BC$ , $DA$ , zaś punkt $Q$ jest środkiem okręgu stycznego do odcinków $CD$ , $BC$ , $DA$ . Stąd wynika, że punkty $P$ , $Q$ leżą na dwusiecznej kąta $ASB$ . Należy zatem wykazać, że dwusieczna ta jest prostopadła do prostej $MN$ .

Oznaczmy przez $K$ , $L$ odpowiednio punkty przecięcia odcinka $MN$ z prostymi $BC$ , $AD$ (rys. 2). Zadanie będzie rozwiązane, jeśli wykażemy, że trójkąt $SKL$ jest równoramienny.

Przez punkty $M$ i $N$ poprowadźmy proste styczne do danego okręgu. Proste te są równoległe odpowiednio do prostych $BC$ i $AD$ oraz wyznaczają - razem z prostą $MN$ - trójkąt równoramienny $MNX$ . Stąd

$ \measuredangle SKL = \measuredangle XMN = \measuredangle XNM = \measuredangle SLK. $

Otrzymana równość dowodzi, że trójkąt $SKL$ jest równoramienny, co kończy rozwiązanie zadania.

LIV OM - II - Zadanie 3

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

Dany jest wielomian $W(x) = x^4 - 3x^3 + 5x^2 - 9x$ . Wyznaczyć wszystkie pary różnych liczb całkowitych $a$ , $b$ spełniających równanie

$ W (a) = W (b). $

Rozwiązanie

Zauważmy, że $W(x) = (x - 1)(x - 2) (x^2 + 3) - 6$ . Dla $n> 3$ zachodzą więc nierówności

$ \begin{array}{rcl} W(n) + 6 &=& (n - 1)(n - 2)(n^2 + 3) = (n^2 - 3n + 2)(n^2 + 3) < \\ &<& (n^2 - 2n + 4)(n^2 + n) = n(n + 1)((n - 1)^2 + 3) =\\ &=& W (-n +1) + 6, \end{array} $

a ponadto

$ \begin{array}{rcl} W(-n + 1) + 6 &<& (n^2 - n)(n^2 + 2n + 4)= n(n - 1)((n + 1)^2 + 3) = \\ &=& W (n +1)+6. \end{array} $

Stąd otrzymujemy

$ (1) \qquad W (3) < W (-2) < W (4) < W (-3) < W (5) < W (-4) < W (6) \ldots . $

Zatem wartości wielomianu $W$ w punktach $-2, \pm 3, \pm 4, \ldots$ są parami różne. Bezpośrednio obliczamy, że

$ W (-1) = 18,\ W (0) = 0,\ W (1) = -6,\ W (2) = -6,\ W (3) = 18, $

zaś z nierówności (1) wnioskujemy, że wartości wielomianu $W$ w pozostałych punktach całkowitych są większe od $W(3) = 18$ . Stąd otrzymujemy łącznie cztery pary liczb spełniających warunki zadania:

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

LIV OM - II - Zadanie 4

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

Wykazać, że dla każdej liczby pierwszej $p > 3$ istnieją liczby całkowite $x$ , $y$ , $k$ spełniające warunki: $0 < 2k <p$ oraz

$ kp + 3 = x^2 + y^2 . $

Rozwiązanie

Niech $A$ będzie zbiorem liczb postaci $x^2$ , gdzie $0 \leq x<p/2$ , natomiast $B$ zbiorem liczb postaci $3 - y^2$ , gdzie $0 \leq y<p/2$ ; liczby $x$ , $y$ są całkowite. Wykażemy, że liczby ze zbioru $A$ dają różne reszty z dzielenia przez $p$ .

Przypuśćmy, że liczby $x_1^2$ , $x_2^2$ ze zbioru $A$ dają taką samą resztę z dzielenia przez $p$ . Wtedy

$ p|x_1^2-x_2^2, $

skąd mamy podzielność

$ p|(x_1-x_2)(x_1+x_2). $

Ponieważ $0 \leq x_1$ , $x_2 < p/2$ , więc $-p/2 <x_1 - x_2 <p/2$ oraz $0 \leq x_1 + x_2 < p$ . Stąd oraz z powyższej podzielności wnioskujemy, że $x_1 = x_2$ .

Zatem liczby ze zbioru $A$ dają różne reszty z dzielenia przez $p$ . Analogicznie dowodzimy, że liczby ze zbioru $B$ dają różne reszty z dzielenia przez $p$ .

Ponieważ zbiory $A$ i $B$ mają łącznie $p +1$ elementów, więc istnieją dwie liczby - jedna ze zbioru $A$ , druga ze zbioru $B$ - dające z dzielenia przez $p$ tę samą resztę. Niech $x^2$ i $3 - y^2$ będą tymi liczbami. Wówczas liczba $x^2 + y^2 - 3$ jest podzielna przez $p$ , mamy więc

$ kp + 3 = x^2 + y^2 $

dla pewnej liczby całkowitej $k$ . Ponieważ $p>3$ , więc $k$ jest liczbą dodatnią oraz

$ k=\frac{x^2+y^2-3}{p}<\frac{(p/2)^2+(p/2)^2}{p}=\frac{p}{2}. $

Warunki podane w treści zadania są więc spełnione.

LIV OM - II - Zadanie 5

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

Punkt $A$ leży na zewnątrz okręgu $o$ o środku $O$ . Z punktu $A$ poprowadzono dwie proste styczne do okręgu $o$ odpowiednio w punktach $B$ i $C$ . Pewna styczna do okręgu $o$ przecina odcinki $AB$ i $AC$ odpowiednio w punktach $E$ i $F$ . Proste $OE$ i $OF$ przecinają odcinek $BC$ odpowiednio w punktach $P$ i $Q$ . Udowodnić, że z odcinków $BP$ , $PQ$ i $QC$ można zbudować trójkąt podobny do trójkąta $AEF$ .

Rozwiązanie

Oznaczmy przez $X$ punkt styczności okręgu $o$ z prostą $EF$ (rys. 3). Z równości

$ EB = EX \ \textrm{oraz} \ \measuredangle BEP = \measuredangle XEP $

wynika, że trójkąty $BEP$ oraz $XEP$ są przystające. Zatem $BP = XP$ .

Analogicznie dowodzimy równość $CQ = XQ$ . To oznacza, że trójkąt $PQX$ jest zbudowany z odcinków $BP$ , $PQ$ oraz $QC$ .

Pozostaje wykazać, że trójkąt $PQX$ jest podobny do trójkąta $FEA$ . Oznaczmy: $\measuredangle FEA = \alpha$ , $\measuredangle EFA = \beta$ . Trójkąt $ABC$ jest równoramienny, skąd obliczamy, że $\measuredangle ABC = \frac{1}{2} (\alpha+\beta)$ . Ponadto $\measuredangle BEP = 90^{\circ} - \frac{1}{2} \alpha$ . Dwie ostatnie równości implikują

$ \measuredangle BPE = 90^\circ - \frac {1}{2}\beta, $

co daje w rezultacie

$ \measuredangle XPQ = 180^\circ - 2 \measuredangle BPE = \beta. $

Analogicznie dowodzimy, że $\measuredangle XQP = \alpha$ , co kończy rozwiązanie zadania.

LIV OM - II - Zadanie 6

Zawody matematyczne:

LIV OM, 2002-2003

Etap:

Każdej parze liczb całkowitych nieujemnych $(x,y)$ jest przyporządkowana liczba $f (x,y)$ zgodnie z warunkami:

$ \begin{array}{rcl} f (0,0) &=& 0;\\ f (2x, 2y) &=& f (2x +1,2y + 1) = f (x, y),\\ f(2x +1,2y) &=& f(2x, 2y +1)= f(x,y) + 1\ \textrm{dla}\ x,y \geq 0. \end{array} $

Niech $n$ będzie ustaloną liczbą całkowitą nieujemną i niech $a$ , $b$ będą takimi liczbami całkowitymi nieujemnymi, że $f (a,b) = n$ . Rozstrzygnąć, ile jest liczb $x$ spełniających równanie

$ f (a,x) + f (b,x) = n. $

Rozwiązanie

Udowodnimy następujący lemat dający inny opis funkcji $f$ .

Lemat

Niech $k$ będzie liczbą całkowitą dodatnią oraz niech $x$ , $y$ będą liczbami całkowitymi nieujemnymi mniejszymi od $2^k$ . Niech

$ \overline{c_{k-1} c_{k-2}\ldots c_2 c_1 c_0}_{(2)}\ \textrm{oraz}\ \overline{d_{k-1} d_{k-2}\ldots d_2 d_1 d_0}_{(2)} $

będą zapisami dwójkowymi odpowiednio liczb $x$ i $y$ , przy czym dopuszczamy zera początkowe. Wówczas

$ f(x,y)=\sum_{i=0}^{k-1} |c_i-d_i|. $

(Zatem $f (x,y)$ jest liczbą miejsc dwójkowych, na których liczby $x$ i $y$ mają różne cyfry.)

Dowód lematu

Przeprowadzimy dowód indukcyjny ze względu na $k$ . Dla $k = 1$ teza lematu wynika bezpośrednio z równości

$ f (0,0) = f (1,1) = 0 \ \textrm{oraz}\ f (0,1) = f (1,0) = 1. $

Niech $k$ będzie taką liczbą całkowitą, dla której teza lematu jest prawdziwa oraz niech $x$ , $y$ będą dowolnymi liczbami całkowitymi nieujemnymi mniejszymi od $2^{k+1}$ . Zapiszmy liczby $x$ , $y$ w układzie dwójkowym:

$ x=\overline{c_kc_{k-1} c_{k-2}\ldots c_2 c_1 c_0}_{(2)}\ \textrm{oraz}\ y=\overline{d_kd_{k-1} d_{k-2}\ldots d_2 d_1 d_0}_{(2)}. $

Z założenia indukcyjnego wynika, że teza lematu jest spełniona dla liczb

$ x_0=\overline{c_kc_{k-1} c_{k-2}\ldots c_2 c_1}_{(2)}\ \textrm{oraz}\ y_0=\overline{d_kd_{k-1} d_{k-2}\ldots d_2 d_1}_{(2)}, $

mamy więc $f (x_0, y_0) = |c_1 - d_1| + |c_2 - d_2| +\ldots + |c_k - d_k|$ . Ponadto $x = 2x_0 + c_0$ oraz $y = 2y_0 + d_0$ , skąd na mocy warunków podanych w treści zadania wynika, że $f (x,y) = f (x_0,y_0) + |c_0 - d_0|$ . Zatem

$ f(x,y)=\sum_{i=0}^{k-1} |c_i-d_i|. $

Dowód lematu został zakończony.

Przechodzimy teraz do rozwiązania zadania. Niech

$ a=\overline{a_{k-1} a_{k-2}\ldots a_2 a_1 a_0}_{(2)},\ b=\overline{b_{k-1} b_{k-2}\ldots b_2 b_1 b_0}_{(2)},\ x=\overline{c_{k-1} c_{k-2}\ldots c_2 c_1 c_0}_{(2)}\ . $

Wówczas równość $f (a,x)+ f (b,x) = f (a, b)$ jest równoważna równości

$ \sum_{i=0}^{k-1} |c_i-a_i| +|c_i-b_i| - |b_i-a_i|=0. $

$ a_i \neq b_i \ \textrm{lub}\ a_i = b_i = c_i . $

Możemy więc przy ustalonych $a$ i $b$ opisać wszystkie liczby $x$ spełniające równanie $f (a,x)+f (b,x) = f (a,b)$ . Na tych pozycjach zapisu dwójkowego, na których liczby $a$ i $b$ mają różne cyfry, liczba $x$ może mieć cyfrę dowolną. Na tych pozycjach, na których cyfry liczb $a$ i $b$ są takie same, liczba $x$ musi mieć cyfrę taką jak liczby $a$ i $b$ . Przy konstrukcji liczby $x$ możemy więc dowolnie dobrać cyfry na $f(a, b)$ pozycjach.

Liczba rozwiązań danego w zadaniu równania jest więc równa $2^n$ .

LIV OM - III etap

III etap LIV Olimpiady Matematycznej

Załącznik	Wielkość
LIV OM III etap - Zadania [5]	66.22 KB
LIV OM III etap - Zadania z rozwiązaniami [6]	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.