LVI OM

LVI Olimpiada Matematyczna

Załącznik	Wielkość
Informacja o przebiegu LVI Olimpiady Matematycznej [1]	100.31 KB

LVI OM - I etap

I etap LVI Olimpiady Matematycznej

Załącznik	Wielkość
LVI OM I etap - Zadania [2]	99.49 KB
LVI OM I etap - Zadania z rozwiązaniami [3]	189.54 KB

LVI OM - I - Zadanie 1

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

Rozwiązać w liczbach rzeczywistych $x$ , $y$ , $z$ układ równań

$ \left\{\begin{array}{l} x^{2}=yz+1\\ y^{2}=zx+2\\ z^{2}=xy+4 \end{array}\right. $

Rozwiązanie

Pierwsze równanie danego układu równań mnożymy przez $y$ , drugie przez $z$ , a trzecie przez $x$ . W ten sposób uzyskane równania dodajemy stronami otrzymując

$ (1)\qquad 0=y+2z+4x. $

Następnie mnożymy pierwsze równanie danego w treści zadania układu równań przez $z$ , drugie przez $x$ , a trzecie przez $y$ . Po dodaniu stronami dostajemy

$ (2)\qquad 0=z+2x+4y. $

Równanie (2) mnożymy przez $-2$ i dodajemy stronami do równania (1). W efekcie otrzymujemy $0 = -7y$ , czyli $y = 0$ . Wstawiając $y = 0$ do pierwszego równania uzyskujemy $x^2 = 1$ , skąd x =1 lub x = -1. Wykorzystując po raz kolejny zależność (2) mamy $z = -2x$ , czyli odpowiednio $z = -2$ lub $z = 2$ . Wykazaliśmy zatem, że jeśli trójka $(x,y,z)$ spełnia podany układ równań, to jest nią $(1,0,-2)$ lub $(-1,0,2)$ . Z drugiej strony, bezpośrednie sprawdzenie pokazuje, że obie uzyskane trójki $(x,y,z)$ są rozwiązaniami danego układu równań.

Odpowiedź: $(x,y,z) = (1,0,-2)$ lub $(x,y,z) = (-1,0,2)$ .

LVI OM - I - Zadanie 2

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

Wyznaczyć wszystkie liczby naturalne $n>1$ , dla których wartość sumy $2^{2}+3^{2}+\ldots+n^{2}$ jest potęgą liczby pierwszej o wykładniku naturalnym.

Rozwiązanie

Ze wzoru $1+2^{2}+3^{2}+ \ldots+n^{2}=\frac{1}{6}n(n+1)(2n+1)$ , prawdziwego dla dowolnej liczby naturalnej $n$ , otrzymujemy

$ 2^2+3^2+\ldots+n^2=\frac{1}{6}(n(n+1)(2n+1)-6)=\frac{1}{6}(n-1)(2n^2+5n+6). $

Zadanie sprowadza się zatem do wyznaczenia wszystkich liczb naturalnych $n>1$ , liczb pierwszych $p$ oraz liczb całkowitych dodatnich $k$ , dla których spełniona jest równość

$ (1)\qquad (n-1)(2n^{2}+5n+6)=6p^{k} $

Ponieważ czynnik $2n^2 +5n+6$ jest większy od $6$ , więc z równości (1) wynika, że jest on podzielny przez $p$ . Wykażemy, że z kolei czynnik $n-1$ nie jest podzielny przez $p$ .

Przypuśćmy, że $p|n-1$ . Ponieważ także liczba

$ (2)\qquad M=2n^{2}+5n+6=2(n-1)^{2}+9(n-1)+13 $

jest podzielna przez $p$ , więc $p$ jest dzielnikiem pierwszym liczby $13$ . Zatem $p = 13$ . Stąd $n - 1 \geq 13$ , co pociąga nierówność $M \geq 36\cdot 13$ . Z równości (1) wnioskujemy, że $M$ jest dzielnikiem liczby $6\cdot13^k$ , a skoro $M> 6\cdot13$ , to musi zachodzić podzielność $13^2 |M$ . Z zależności (2) uzyskujemy zatem, że liczba $9(n-1)+13$ jest podzielna przez $13^2$ , a więc

$ (3)\qquad \textrm{liczba } 9 \cdot \frac{1}{13}(n-1)+1 \textrm{ dzieli się przez } 13. $

Liczba $(n-1)$ jest — na mocy równości (1) — dzielnikiem liczby $6\cdot13^k-1$ i jednocześnie nie jest — na mocy podzielności (3) — podzielna przez 13. Stąd wynika, że liczba $\frac{1}{13}(n-1)$ jest równa 1, 2, 3 lub 6. Jednak w żadnym z tych czterech przypadków nie jest spełniona podzielność (3). Otrzymaliśmy sprzeczność, która dowodzi, że czynnik $n-1$ nie jest podzielny przez $p$ .

Z równości (1) wnioskujemy zatem, że czynnik $n-1$ musi być jedną z liczb: 1, 2, 3 lub 6. Stąd liczba $n$ jest równa 2, 3, 4 lub 7. Bezpośrednie sprawdzenie pokazuje, że istotnie każda z tych liczb spełnia warunki zadania:

$ 2^{2}=2^{2},2^{2}+3^{2}=13^{1},2^{2}+3^{2}+4^{2}=29^{1},2^{2}+3^{2}+4^{2}+5^{2}+6^{2}+7^{2}=139^{1}. $

Odpowiedź: Liczba $n$ jest równa 2, 3, 4 lub 7.

LVI OM - I - Zadanie 3

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

W trójkącie ostrokątnym $ABC$ punkt $D$ jest rzutem prostokątnym punktu $C$ na prostą $AB$ . Punkt $E$ jest rzutem prostokątnym punk-tu $D$ na prostą $BC$ . Punkt $F$ leży na odcinku $DE$ , przy czym

$ \frac{EF}{FD}= \frac{AD}{DB}. $

Wykazać, że proste $CF$ i $AE$ są prostopadłe.

Rozwiązanie

Przez punkt $D$ poprowadźmy prostą równoległą do prostej $AE$ , która przecina bok $BC$ w punkcie $G$ (rys. 1). Na mocy twierdzenia Talesa uzyskujemy proporcje

$ \frac{EF}{FD}= \frac{AD}{DB}= \frac{EG}{GB}, $

skąd wynika, że proste $FG$ i $DB$ są równoległe. Stąd oraz z podobieństwa trójkątów prostokątnych $CDE$ i $DBE$ otrzymujemy równości

$ \frac{FD}{GB}= \frac{ED}{EB}= \frac{CD}{DB}, $

Powyższa zależność wraz z równością $\measuredangle CDF = \measuredangle DBG$ dowodzi, że trójkąty $CDF$ i $DBG$ są podobne. Zatem $\measuredangle DAE = \measuredangle BDG = \measuredangle DCF$ . Jeśli przez $P$ oznaczymy punkt przecięcia prostych $CF$ i $AE$ , to z ostatniej zależności wynika, że punkty $A, D, C, P$ leżą na jednym okręgu. Ostatecznie mamy $\measuredangle APC = \measuredangle ADC = 90^\circ$ .

LVI OM - I - Zadanie 4

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

Dana jest dodatnia liczba całkowita $n$ oraz dodatnie liczby rzeczywiste $a$ , $b$ . Wyznaczyć największą możliwą wartość sumy

$ x_1y_1 +x_2y_2 +\ldots+x_ny_n, $

gdy $x_{1},\ x_{2},\ \ldots,\ x_{n},\ y_{1},\ y_{2},\ \ldots,\ y_{n}$ są liczbami z przedziału $\langle 0;1\rangle$ , spełniającymi warunki

$ (1)\qquad x_{1}+x_{2}+\ldots+x_{n}\leq a,\qquad y_{1}+y_{2}+\ldots+y_{n}\leq b. $

Rozwiązanie

Dla dowolnych liczb $x_{1},\ x_{2},\ \ldots,\ x_{n},\ y_{1},\ y_{2},\ \ldots,\ y_{n}$ spełniających warunki zadania zachodzą nierówności

$ \sum_{i=1}^{n} x_iy_i\leq n,\qquad \sum_{i=1}^{n} x_iy_i\leq\sum_{i=1}^{n}x_i\leq a,\qquad\sum_{i=1}^{n}x_iy_i\leq\sum_{i=1}^{n}y_i\leq b. $

Zatem

$ (2)\qquad x_{1}y_{1}+x_{2}y_{2}+\ldots+x_{n}y_{n}\leq\min(a,b,n). $

Wykażemy najpierw, że jeśli $a,\ b\geq n$ lub $[a]\neq[b]$ (symbol $[x]$ oznacza największą liczbę całkowitą nie większą od $x$ ), to liczba $\min(a,b,n)$ jest największą wartością rozpatrywanej sumy.

Jeżeli bowiem $a, b\geq n$ , to przyjmujemy $x_{i}=y_{i}=1$ dla $i=1,2, \ldots, n$ . Wówczas nierówności (1) są spełnione, a rozpatrywana suma przyjmuje wartość $n = \min(a,b,n)$ , która — na mocy mocy nierówności (2) — jest jej wartością największą.

W przypadku gdy $A=[a]\neq[b]=B$ , przyjmijmy bez straty ogólności, że $A<B$ . Aby nie rozpatrywać ponownie przypadku $a, b\geq n$ , możemy również założyć, że $A<n$ . Przyjmijmy

$ x_{1}=x_{2}=\ldots=x_{A}=1,\ x_{A+1}=a-A,\ x_{i}=0\textrm{ dla }i>A+1; $

$y_{1}=y_{2}=\ldots=y_{A+1}=1,\ y_{i}=0\textrm{ dla }i>A+1.$

Tak wybrane liczby $x_i, y_i$ należą do przedziału $\langle 0;1\rangle$ , nierówności (1) są dla nich spełnione, a rozpatrywane wyrażenie przyjmuje wartość $a = \min(a,b,n)$ , która — na mocy uzyskanej nierówności (2) — jest wartością największą rozpatrywanej sumy.

Pozostał do rozpatrzenia przypadek $A = B<n$ . Wykażemy, że wówczas największą wartością rozpatrywanej sumy jest liczba $A+(a-A)(b-A)$ , którą można uzyskać przyjmując

$ x_{1}=x_{2}=\ldots=x_{A}=1,\ x_{A+1}=a-A,\ x_{i}=0\textrm{ dla }i>A+1; $

$ y_{1}=y_{2}=\ldots=y_{A}=1,\ y_{A+1}=b-A,\ y_{i}=0\textrm{ dla }i>A+1. $

Pozostało zatem wykazać, że

$ (3)\qquad x_{1}y_{1}+x_{2}y_{2}+\ldots+x_{n}y_{n}\leq A+(a-A)(b-A). $

Jeśli $x_{1}+x_{2}+\ldots+x_{n}\leq A$ , to

$ x_{1}y_{1}+x_{2}y_{2}+\ldots+x_{n}y_{n}\leq A\leq A+(a-A)(b-A). $

Analogicznie dowodzimy nierówności (3) jeśli $y_{1}+y_{2}+\ldots+y_{n}\leq A$ . Przyjmijmy więc w dalszej części rozumowania, że

$ A<x_{1}+x_{2}+\ldots+x_{n}\leq a \ \textrm{oraz} \ A<y_{1}+y_{2}+\ldots+y_{n}\leq b. $

Przypuśćmy, że pewne dwie liczby $x_{k},\ x_{l}$ należą do przedziału $(0;1)$ . Bez straty ogólności możemy założyć, że $y_k \leq y_l$ . Zdefiniujmy $\delta=\min(x_{k}, 1-x_{l})$ oraz zmodyfikujmy ciąg $x_1,x_2,\ldots,x_n$ przyjmując

$ x_k'=x_k-\delta,\ x_l'=x_l+\delta,\ x_i'=x_i\ \textrm{dla}\ i \neq k,l. $

Wówczas $x_{k}'=0$ lub $x_{l}'=1$ , liczby $x_{1}', x_{2}', \ldots, x_{n}'$ należą do przedziału $\langle 0;1\rangle$ , $x_{1}'+x_{2}'+\ldots+x_{n}'=x_{1}+x_{2}+\ldots+x_{n}$ oraz

$ \sum_{i=1}^{n}x_{i}'y_i^-\sum_{i=1}^{n}x_iy_i =(x_k-\delta)y_k+(x_l + \delta)y_l - x_ky_k - x_ly_l =\delta(y_l-y_k)\geq 0. $

Wykazaliśmy zatem, ze zmodyfikowany ciąg $x_1', x_2', \ldots, x_n'$ zawiera mniej wyrazów różnych od 0 lub 1 niż wyjściowy ciąg $x_1, x_2, \ldots, x_n$ , a przy tym wartość rozpatrywanej sumy nie zmalała. Jeśli uzyskany ciąg $x_1', x_2', \ldots, x_n'$ zawiera co najmniej dwa wyrazy różne od 0 lub 1, to modyfikujemy go ponownie zgodnie z opisaną wyżej procedurą Po co najwyżej $n-1$ krokach uzyskujemy ciąg $a_1,a_2, \ldots ,a_n$ , który zawiera nie więcej niż jeden wyraz różny od 0 lub 1, a przy tym zachodzi nierówność

$ x_{1}y_{1}+x_{2}y_{2}+\ldots+x_{n}y_{n}\leq a_{1}y_{1}+a_{2}y_{2}+\ldots+a_{n}y_{n}. $

Następnie, ustalając liczby $a_1, a_2, \ldots, a_n$ , przeprowadzamy analogiczną modyfikację ciągu $y_1, y_2, \ldots, y_n$ . W efekcie otrzymujemy ciąg $b_1,b_2,\ldots,b_n$ , który zawiera nie więcej niż jeden wyraz różny od 0 lub 1, a ponadto

$ a_{1}y_{1}+a_{2}y_{2}+\ldots+a_{n}y_{n}\leq a_{1}b_{1}+a_{2}b_{2}+\ldots+a_{n}b_{n}. $

W każdym kroku suma modyfikowanych liczb nie ulega zmianie, więc

$ (4)\qquad A<a_{1}+a_{2}+\ldots+a_{n}\leq a \ \textrm{oraz} \ A<b_{1}+b_{2}+\ldots+b_{n}\leq b $

Niech $a_{1}', a_{2}', \ldots, a_{n}'$ będzie taką permutacją ciągu $a_1, a_2, \ldots ,a_n$ , że ciągi $a_1', a_{2}', \ldots, a_{n}'$ oraz $b_{1}, b_{2}, \ldots, b_{n}$ są jednakowo uporządkowane, tzn.

$ (a_{i}'-a_{j}')(b_{i}-b_{j})\geq 0\ \textrm{dla wszystkich}\ 1\leq i,j\leq n. $

Wówczas zachodzi nierówność

$ a_1 b_1 + a_2 b_2 + \ldots + a_n b_n \leq a_1'b_1 + a_2' b_2 + \ldots + a_n' b_n. $

(zob. Obóz Naukowy Olimpiady Matematycznej, Zwardoń 2003, Dodatek C, str. 38*). Bez straty ogólności przyjmijmy zatem, że $a_{1}'\geq a_{2}'\geq\ldots\geq a_{n}'$ oraz $b_{1}\geq b_{2}\geq\ldots\geq b_{n}$ . Z nierówności (4) wynika więc, że

$ a_{i}'=b_{i}=1 \textrm{ dla } i<A+1 \textrm{ oraz } a_{i}'=b_{i}=0 \textrm{ dla }i>A+1, $

a ponadto $a_{p}\leq a-A$ oraz $b_{p}\leq b-A$ dla $p=A+1$ . Ostatecznie otrzymujemy

$ \sum_{i=1}^{n}x_{i}y_{i}\leq\sum_{i=1}^{n}a_{i}'b_{i}=A+a_{p}b_{p}\leq A+(a-A)(b-A), $

co kończy dowód nierówności (3).

Reasumując: Największa wartość rozpatrywanego wyrażenia wynosi

$ \left\{ \begin{array}{ll} \min(a,b,n),&\textrm{ jeśli } a,b\geq n \textrm{ lub } [a]\neq[b]; \\ {}[a]+(a-[a])(b-[a]),& \textrm{ jeśli } [a]=[b]<n. \end{array}\right. $

LVI OM - I - Zadanie 5

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

Czworokąt $ABCD$ jest wpisany w okrąg, a okręgi wpisane w trójkąty $ABC$ i $BCD$ mają równe promienie. Rozstrzygnąć, czy z tych założeń wynika, że także okręgi wpisane w trójkąty $CDA$ i $DAB$ mają równe promienie.

Rozwiązanie

Odpowiedź postawiona na pytanie w treści zadania jest twierdząca.

Niech $I$ , $J$ będą środkami okręgów wpisanych odpowiednio w trójkąty $ABC$ i $BCD$ (rys. 2).

Z równości promieni okręgów wpisanych w trójkąty $ABC$ i $BCD$ wynika, że proste $BC$ i $IJ$ są równoległe. Ponadto

$ \measuredangle BIC = 180^\circ -(\frac{1}{2} \measuredangle CBA+ \frac{1}{2} \measuredangle BCA) = 90^\circ + \frac{1}{2} \measuredangle BAC. $

Analogicznie dowodzimy, że $\measuredangle BJC = 90^\circ + \frac{1}{2} \measuredangle BDC$ . Z uzyskanych zależności oraz z równości $\measuredangle BAC = \measuredangle BDC$ wnioskujemy, że na czworokącie $BCJI$ można opisać okrąg. Zatem $BCJI$ jest trapezem równoramiennym. Stąd uzyskujemy równości

$ \measuredangle ABC =2\measuredangle IBC =2\measuredangle JCB = \measuredangle DCB. $

W efekcie otrzymujemy, że czworokąt $ABCD$ jest trapezem równoramiennym o podstawach $BC$ i $AD$ . Stąd wynika, że trójkąty $CDA$ i $DAB$ są przystające, a więc okręgi wpisane w te trójkąty mają równe promienie.

Uwaga: W rozwiązaniu wykazaliśmy, że punkty $B$ , $I$ , $J$ , $C$ leżą na jednym okręgu. Nietrudno wyznaczyć środek tego okręgu: jest nim punkt $M$ przecięcia prostych $AI$ i $DJ$ , czyli środek łuku $BC$ okręgu opisanego na czworokącie $ABCD$ (rys. 3). Dowód tego faktu można znaleźć w broszurze LI Olimpiada Matematyczna, Sprawozdanie Komitetu Głównego, Warszawa 2001, Dodatek E, str. 113.

LVI OM - I - Zadanie 6

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

Rozstrzygnąć, czy istnieje nieskończony ciąg liczb naturalnych $a_1,a_2, a_3,\ldots$ spełniający równanie

$ \frac{1}{a_{n}}=\frac{1}{a_{n+1}} + \frac{1}{a_{n+2}} \textrm{ dla } n=1, 2, 3, \ldots. $

Rozwiązanie

Wykażemy, że ciąg $(a_n)$ spełniający warunki zadania nie istnieje.

Przypuśćmy, że ciąg $(a_n)$ spełnia warunki zadania. Rozumowanie przeprowadzimy na dwa sposoby.

Sposób I

Z podanej równości wynika, że ciąg $(a_n)$ jest rosnący, a ponadto

$ (1)\qquad a_{n+2}(a_{n+1}-a_{n})=a_{n}a_{n+1}. $

Liczba $a_{n+1}-a_{n}$ jest podzielna przez największy wspólny dzielnik liczb $a_n$ i $a_{n+1}$ . Z równości (1) wynika zatem, że liczba $a_{n+2}$ jest dzielnikiem liczby

$ \frac {a_{n}a_{n+1}} {\mathrm{NWD}(a_{n}, a_{n+1})} = \mathrm{NWW}(a_{n}, a_{n+1}). $

Niech $k = \mathrm{NWW}(a_1,a_2)$ . Wykażemy indukcyjnie, że dla każdego $n \geq 1$ , liczba $a_n$ jest dzielnikiem liczby $k$ .

Dla $n =1$ i $n = 2$ jest to prawda na mocy określenia liczby $k$ .

Jeśli z kolei $a_n |k$ oraz $a_{n+1} |k$ dla pewnej liczby $n \geq 1$ , to liczba $k$ jest wspólną wielokrotnością liczb $a_n$ , $a_{n+1}$ , jest więc podzielna przez najmniejszą wspólną wielokrotność liczb $a_n$ , $a_{n+1}$ . Stąd, skoro $a_{n+2} |\mathrm{NWW}(a_n,a_{n+1})$ , uzyskujemy podzielność $a_{n+2} |k$ . Dowód indukcyjny jest zakończony.

Wcześniej stwierdziliśmy, że ciąg $(a_n)$ jest rosnący. Liczba dodatnia $k$ ma zatem nieskończenie wiele dzielników. Uzyskana sprzeczność dowodzi, że nie istnieje ciąg $(a_n)$ o żądanych własnościach.

Sposób II

Niech $x_n =1/a_n$ . Wówczas ciąg $(x_n)$ jest zbieżny do 0, a daną w treści zadania równość możemy przepisać w postaci $x_{n+2}=-x_{n+1}+x_{n}$ . Stosując metodę rozwiązywania rekurencji liniowych (zob. L Olimpiada Matematyczna, Sprawozdanie Komitetu Głównego, Warszawa 2000, Dodatek A, str. 103) uzyskujemy równość

$ x_{n}=a\cdot\left(\frac{-\sqrt{5}-1}{2}\right)^{n}+b\cdot\left(\frac{\sqrt{5}-1}{2}\right)^{n}, $

gdzie $a$ , $b$ są ustalonymi liczbami rzeczywistymi zależnymi tylko od dwóch początkowych wartości $x_1$ i $x_2$ .

Wartość bezwzględna liczby $\frac{1}{2}(-\sqrt{5}-1)$ jest większa od 1, a wartość bezwzględna liczby $\frac{1}{2}(\sqrt{5}-1)$ jest mniejsza od 1. Zatem ciąg $(x_n)$ jest zbieżny do 0 wtedy i tylko wtedy, gdy a = 0. Stąd uzyskujemy

$ x_{n}=b\cdot\left(\frac{\sqrt{5}-1}{2}\right)^{n},\ \textrm{a więc}\ \frac{a_{1}}{a_{2}}=\frac{x_{2}}{x_{1}}=\frac{\sqrt{5}-1}{2}. $

Otrzymaliśmy sprzeczność, gdyż liczba $a_1/a_2$ jest wymierna, a $\frac{1}{2}(\sqrt{5}-1)$ - niewymierna.

LVI OM - I - Zadanie 7

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

Trzy sfery, parami styczne zewnętrznie, są styczne do pewnej płaszczyzny w punktach $A$ , $B$ , $C$ . Znając długości odcinków $BC = a$ , $CA = b$ , $AB = c$ , obliczyć promienie tych sfer.

Rozwiązanie

Z warunków zadania wynika, że rozpatrywane sfery leżą po jednej stronie płaszczyzny, do której są styczne.

Oznaczmy przez $r_A$ , $r_B$ i $r_C$ promienie rozważanych sfer, styczne do danej płaszczyzny odpowiednio w punktach $A$ , $B$ i $C$ . Wówczas na mocy twierdzenia Pitagorasa mamy (rys. 4)

$ (1)\qquad a^2 =(r_B +r_C )^2 -(r_B -r_C)^2 =4r_Br_C . $

Analogicznie uzyskujemy $b^2 =4r_C r_A$ oraz $c^2=4r_Ar_B$ . Mnożąc stronami dwie ostatnie równości oraz wykorzystując równość (1) otrzymujemy

$ b^{2}c^{2}=(4r_{B}r_{C})\cdot(4r_{A}^{2})=4a^{2}r_{A}^{2}, $

skąd obliczamy $r_A = bc/(2a)$ . Analogicznie dostajemy równości

$ r_{B}=\frac{ca}{2b}\ \text{oraz}\ r_{C}=\frac{ab}{2c}. $

LVI OM - I - Zadanie 8

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

Na okręgu jest umieszczonych $n$ lampek; każda może być włączona albo wyłączona. Wykonujemy serię ruchów; w każdym ruchu wybieramy $k$ kolejnych lampek i zmieniamy ich stan: wyłączone włączamy, a włączone wyłączamy (liczba $k$ nie zmienia się w trakcie tego postępowania). Na początku wszystkie lampki są wyłączone. Dla ustalonej liczby naturalnej $n$ wyznaczyć wszystkie liczby naturalne $k \leq n$ , dla których jest możliwe uzyskanie stanu z dokładnie jedną lampką włączoną.

Rozwiązanie

Załóżmy najpierw, że $k$ jest liczbą parzystą. Udowodnimy indukcyjnie, że po każdej zmianie stanu $k$ kolejnych lampek pali się parzysta liczba lampek.

Niech $x_n$ oznacza liczbę zapalonych lampek po wykonaniu n-tego ruchu. Wówczas $x_1 =k$ . Załóżmy, że $x_{n-1}$ jest liczbą parzystą. Jeżeli wykonując $n$ -ty ruch włączamy $a$ lampek, a wyłączamy $b$ , to $a+b = k$ , więc $x_n = x_{n-1} +a -b = x_{n-1} +k -2b$ .

Skoro $x_{n-1}$ i $k$ są liczbami parzystymi, to również $x_n$ jest liczbą parzystą. Dowód indukcyjny jest zakończony. Zatem jeśli $k$ jest liczbą parzystą, to nie jest możliwe uzyskanie stanu z dokładnie jedną włączoną lampką.

Przyjmijmy następnie, że liczby $n$ i $k$ mają wspólny dzielnik $d> 1$ i pomalujmy lampki cyklicznie używając d kolorów. (Ściślej mówiąc, postępujemy następująco: numerujemy lampki kolejno liczbami od 1 do $n$ poruszając się po okręgu w ustalonym kierunku, a następnie malujemy je używając $d$ kolorów, przy czym jednakowym kolorem malujemy te lampki, których numery dają z dzielenia przez $d$ taką samą resztę.)

Przypuśćmy, że po wykonaniu pewnego ruchu świeci się dokładnie $s_i$ lampek $i$ -tego koloru ( $i =1,2,\ldots,d$ ). W każdym ruchu zmieniamy stan dokładnie $l = k/d$ lampek $i$ -tego koloru. Jeśli włączamy $a_i$ lampek $i$ -tego koloru, a $b_i$ lampek i-tego koloru wyłączamy, to liczba $s_i$ wzrasta o dokładnie $a_i -b_i =l-2b_i$ . Skoro na początku żadna lampka nie jest włączona, to po każdym ruchu liczby $s_1,s_2,\ldots,s_d$ dają z dzielenia przez $2$ taką samą resztę. Nie jest zatem możliwe uzyskanie dokładnie jednej lampki włączonej (mielibyśmy wtedy $s_j = 1$ dla pewnej liczby $j$ oraz $s_i = 0$ dla wszystkich $i\neq j$ ).

Pozostał do rozpatrzenia przypadek, gdy $k$ jest taką liczbą nieparzystą, że $NWD(k,n)=1$ . Warunek ten jest równoważny równości $NWD(k,2n) = 1$ . Wykażemy, że przy pomocy rozpatrywanych ruchów można doprowadzić do sytuacji, gdy dokładnie jedna lampka jest włączona.

Stosując algorytm Euklidesa dla liczb $k$ i $2n$ wnioskujemy, że istnieje taka liczba całkowita dodatnia $x$ oraz liczba całkowita nieujemna $y$ , że

$ (1)\qquad kx-(2n)y =1 . $

Wybieramy blok $k$ kolejnych lampek i zmieniamy ich stan na przeciwny. Następnie wybieramy blok złożony z $k$ lampek przyległy do poprzedniego i zmieniamy stan tych lampek na przeciwny. Procedurę kontynuujemy poruszając się po danym okręgu w ustalonym kierunku i wykonując łącznie $x$ ruchów.

Z równości (1) wynika, że stan jednej lampki zmieni się dokładnie $2y +1$ razy, a stan każdej innej dokładnie $2y$ razy. W efekcie dokładnie jedna lampka będzie włączona, a pozostałe wyłączone.

LVI OM - I - Zadanie 9

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

Wyznaczyć wszystkie liczby rzeczywiste $a$ , dla których ciąg $(x_n)$ określony wzorami

$ x_{0}=\sqrt{3},\ x_{n+1}= \frac{1+ax_{n}}{a-x_{n}}\ \textrm{dla}\ n=0,1,2,\ \ldots $

spełnia warunek $x_{n+8} = x_n$ dla $n =0, 1, 2, \ldots$ .

Rozwiązanie

Sposób I

Aby ciąg $(x_n)$ był poprawnie określony, musi być $x_n \neq a$ dla każdego $n\geq 0$ . Niech $\alpha \in (0;\pi)$ będzie taką liczbą, że $a = \mathrm{ctg} \alpha$ . Wykażemy indukcyjnie, że

$ (1)\qquad x_n = \mathrm{ctg}( \frac {1}{6} \pi -n\alpha )\ \textrm{dla } n =0,1,2,\ldots . $

Dla $n = 0$ równość (1) jest spełniona. Przyjmijmy, że zachodzi ona dla pewnego $n$ . Jeśli $\mathrm{ctg} x \neq \mathrm{ctg} y$ , to

$ \mathrm{ctg}(x-y)=\frac{1+\mathrm{ctg} x \cdot \mathrm{ctg} y}{\mathrm{ctg} x - \mathrm{ctg} y}. $

Warunek $x_n \neq a$ implikuje, że $\mathrm{ctg}( \frac {1}{6} \pi -n\alpha ) \neq \mathrm{ctg} \alpha$ Na mocy powyższego wzoru uzyskujemy

$ x_{n+1}=\frac{1+ax_{n}}{a-x_{n}}= \frac{1+(\mathrm{ctg} \alpha) \cdot (\mathrm{ctg} (\frac {1}{6} \pi -n\alpha))}{\mathrm{ctg} \alpha - \mathrm{ctg} (\frac {1}{6} \pi -n\alpha)} = \mathrm{ctg} (\frac {1}{6} \pi -(n+1)\alpha), $

co kończy dowód indukcyjny zależności (1). Funkcja $f(x) = \mathrm{ctg} x$ jest $\pi$ -okresowa. Korzystając z równości (1) wnioskujemy, że $x_{n+8} = x_n$ dla wszystkich $n \neq 0$ wtedy i tylko wtedy, gdy istnieje taka liczba całkowita $k$ , że $8 \alpha = k\pi$ . Stąd uzyskujemy $\alpha = \frac{1}{8} k \pi$ , a ponieważ liczba $\alpha$ należy do przedziału $(0;\pi)$ , więc $k$ jest jedną z liczb: $1,2,\ldots,7$ . Zatem równość $x_{n+8} = x_n$ jest prawdziwa dla $n =0,1,2,\ldots$ wtedy i tylko wtedy, gdy a jest jedną z liczb:

$ \mathrm{ctg}(\frac{1}{8}\pi),\ \mathrm{ctg}(\frac{1}{4}\pi),\ \mathrm{ctg}(\frac{3}{8}\pi),\ \mathrm{ctg}(\frac{1}{2}\pi),\ \mathrm{ctg}(\frac{5}{8}\pi),\ \mathrm{ctg}(\frac{3}{4}\pi),\ \mathrm{ctg}(\frac{7}{8}\pi),\ $

czyli odpowiednio: $\sqrt{2}+1, 1, \sqrt{2}-1, 0, - \sqrt{2}+1, -1, - \sqrt{2}-1$ . Bezpośrednio sprawdzamy, że dla powyższych siedmiu wartości $a$ , ciąg $(x_n)$ jest poprawnie określony, tzn. $x_n \neq a$ dla $n =0, 1,2\ldots,7$ .

LVI OM - I - Zadanie 10

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

Spośród wszystkich podzbiorów ustalonego zbioru $n$ -elementowego $X$ losujemy kolejno ze zwracaniem trzy zbiory $A$ , $B$ , $C$ . Za każdym razem wylosowanie każdego spośród $2^n$ podzbiorów zbioru $X$ jest jednakowo prawdopodobne. Wyznaczyć najbardziej prawdopodobną liczbę elementów zbioru $A\cap B\cap C$ .

Rozwiązanie

Zbiór zdarzeń elementarnych $\Omega$ składa się ze wszystkich trójek $(A,B,C)$ , gdzie $A$ , $B$ i $C$ są podzbiorami danego zbioru $n$ -elementowego $S$ . Wylosowanie każdej z $(2^n)^3 =8^n$ trójek $(A,B,C)$ jest jednakowo prawdopodobne. Niech $X_k$ $(k =0,1,2,\ldots,n)$ oznacza zdarzenie polegające na tym, że trójka zbiorów $(A,B,C)$ spełnia warunek $|A\cap B\cap C|= k$ , gdzie $|F|$ oznacza liczbę elementów zbioru $F$ . Szukamy takiej liczby naturalnej $k$ , dla której prawdopodobieństwo zajścia zdarzenia $X_k$ jest największe.

Ustalmy liczbę $k\in\{0,1,2, \ldots,n\}$ . Obliczymy liczbę trójek $(A, B, C)$ , dla których $|A\cap B\cap C|=k$ .

Jeśli $(A,B,C)$ jest trójką podzbiorów zbioru $S$ , to każdy element zbioru $S$ znajduje się w dokładnie jednym spośród następujących ośmiu zbiorów

$ (1)\qquad \begin{array}{l} A\cap B\cap C,\ (A\cap B)\backslash C,\ (B\cap C)\backslash A,\ (C\cap A)\backslash B,\\ A\backslash (B\cup C),\ B\backslash (C\cup A),\ C\backslash (A\cup B),\ S\backslash (A\cup B\cup C). \end{array} $

Aby uzyskać trójkę zbiorów $(A,\ B,\ C)$ , dla których $|A\cap B\cap C|=k$ , wybieramy najpierw $k$ elementów zbioru $S$ , które umieścimy w zbiorze $A\cap B\cap C$ — możemy to uczynić na $n \choose k$ sposobów. Każdemu z pozostałych $n-k$ elementów $k$ przyporządkowujemy jedną z pozostałych siedmiu możliwości występujących w (1) — możemy to zrobić na $7^{n-k}$ sposobów. Opisane postępowanie określa jednoznacznie trójkę $(A,B,C)$ . Zatem liczba trójek $(A,B,C)$ , dla których $|A \cap B \cap C| = k$ wynosi ${n \choose k} \cdot 7^{n-k}$ . Stąd uzyskujemy

$ P(X_{k})=\frac{{n \choose k} \cdot 7^{n-k}}{8^{n}}. $

Aby wyznaczyć taką liczbę $k$ , dla której prawdopodobieństwo zajścia zdarzenia $X_k$ jest największe, obliczamy iloraz

$ \frac{P(X_{k+1})}{P(X_{k})}=\frac{n-k}{7k+7}. $

Stąd wynika, że

$ \left\{ \begin{array}{ll} P(X_{k+1})>P(X_k),&\textrm{jeśli}\ k<\frac{1}{8}(n-7);\\ P(X_{k+1})<P(X_k),&\textrm{jeśli}\ k>\frac{1}{8}(n-7);\\ P(X_{k+1})=P(X_k),&\textrm{jeśli}\ k=\frac{1}{8}(n-7).\\ \end{array}\right. $

Oznaczając $\lambda=[(n-7)/8]$ , gdzie $[x]$ jest największą liczbą całkowitą nie większą od $x$ , otrzymujemy

$ \begin{array}{l} P(X_{0})<P(X_{1})<P(X_{2})<\ldots<P(X_{\lambda})\leq P(X_{\lambda+1}),\\ P(X_{\lambda+1})>P(X_{\lambda+2})>\ldots>P(X_{n}). \end{array} $

Zatem prawdopodobieństwo $P (X_k)$ jest największe dla $k = \lambda+1 =[ \frac{1}{8} (n+1)]$ .

Jeśli $\frac{1}{8}(n-7)$ jest liczbą całkowitą, to istnieją dwie wartości $k$ , dla których liczba $P(X_k)$ jest największa, a mianowicie $k = \frac{1}{8} (n-7)$ oraz $k = \frac{1}{8} (n+1)$ .

LVI OM - I - Zadanie 11

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

Okrąg o środku $I$ jest wpisany w czworokąt wypukły $ABCD$ , przy czym punkt $I$ nie leży na prostej $AC$ . Przekątne $AC$ i $BD$ przecinają się w punkcie $E$ . Prosta przechodząca przez punkt $E$ oraz prostopadła do prostej $BD$ przecina proste $AI$ , $CI$ odpowiednio w punktach $P$ , $Q$ . Wykazać, że $PE = EQ$ .

Rozwiązanie

Niech $o_1$ będzie okręgiem o środku $P$ i stycznym do prostych $AD$ i $AB$ odpowiednio w punktach $S$ i $T$ . Analogicznie, niech $o_2$ będzie okręgiem o środku $Q$ i stycznym do prostych $CB$ i $CD$ odpowiednio w punktach $U$ i $W$ (rys. 5). Oznaczmy przez $o$ okrąg wpisany w czworokąt $ABCD$ . Bez straty ogólności przyjmijmy, że punkt $Q$ leży na odcinku $CI$ .

Korzystając z twierdzenia Menelausa dla trójkąta $PIQ$ uzyskujemy

$ \frac{PE}{EQ}=\frac{CI}{CQ}\cdot\frac{AP}{AI}=\frac{r}{r_{2}}\cdot\frac{r_{1}}{r}=\frac{r_{1}}{r_{2}}, $

gdzie $r$ , $r_1$ i $r_2$ są odpowiednio promieniami okręgów $o$ , $o_1$ i $o_2$ . Stąd

$ (1)\qquad \frac{PE}{r_{1}}=\frac{EQ}{r_{2}}=\lambda. $

Wprowadźmy następujące oznaczenia: $a=BT$ , $b=DS$ , $c=BU$ , $d=DW$ . Wówczas otrzymujemy zależności:

$ (2)\qquad \begin{array}{l} a-b=AB-AD=CB-CD=c-d,\\ a^{2}-b^{2}=PB^{2}-PD^{2}=BE^{2}-DE^{2}=QB^{2}-QD^{2}=c^{2}-d^{2}. \end{array} $

Zatem jeśli $a=b$ , to $AB =AD$ oraz $CB =CD$ ; w tym przypadku punkt $I$ leży na przekątnej $AC$ , co przeczy założeniom. Stąd mamy $a \neq b$ , a więc również $c \neq d$ . Z równości (2) otrzymujemy wówczas $a + b = c + d$ , co w połączeniu z zależnością $a-b = c-d$ daje $a = c$ i $b = d$ . Zatem

$ (3)\qquad PE^{2}-EQ^{2}=PD^{2}-QD^{2}=(r_{1}^{2}+b^{2})-(r_{2}^{2}+d^{2})=r_{1}^{2}-r_{2}^{2}. $

Równości (1) i (3) pociągają zależność $(\lambda^{2}-1)(r_{1}^{2}-r_{2}^{2})=0$ .

Przypuśćmy, że $\lambda = 1$ . Wówczas $EQ = r_2$ , a więc okrąg $o_2$ jest wpisany w trójkąt $BCD$ . Ponieważ w czworokąt $ABCD$ można wpisać okrąg, więc okrąg $\omega$ wpisany w trójkąt $ABD$ jest styczny do okręgu $o_2$ . Stąd wynika, że punkty $Q$ , $E$ oraz środek okręgu $\omega$ leżą na jednej prostej. To jednak nie jest możliwe, gdyż punkty te znajdują się odpowiednio na bokach $IC$ , $CA$ , $AI$ trójkąta $AIC$ i są różne od jego wierzchołków. Otrzymaliśmy sprzeczność, która dowodzi, że $\lambda\neq 1$ . Z uzyskanej wyżej równości wynika zatem, że $r_1 = r_2$ , czyli $PE = EQ$ .

LVI OM - I - Zadanie 12

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

Dane są funkcje

$ f(x)=2^x$ \quad \text{oraz} \quad $g(x)= f(f(f(f(f(f(f(x))))))) $

(7-krotna iteracja funkcji $f$ ). Rozstrzygnąć, czy liczba $g(3)-g(0)$ jest podzielna przez liczbę $g(2)-g(0)$ .

Rozwiązanie

Liczby $g(0)$ , $g(2)$ i $g(3)$ są odpowiednio wyrazami $a_7$ , $b_7$ i $c_7$ ciągów $(a_n)$ , $(b_n)$ i $(c_n)$ określonych rekurencyjnie wzorami

$ \left\{ \begin{array}{l} a_0=0\\ a_{n+1}=2^{a_n}, \end{array} \right. \left\{ \begin{array}{l} b_0=2\\ b_{n+1}=2^{b_n}, \end{array} \right. \left\{ \begin{array}{l} c_0=3\\ c_{n+1}=2^{c_n}, \end{array} \right. $

Wykażemy, że liczba $c_7-a_7 =g(3)-g(0)$ nie dzieli się przez $b_7-a_7 =g(2)-g(0)$ . W dowodzie skorzystamy z następującego lematu:

Lemat

Dane są takie liczby całkowite dodatnie $k$ i $l$ , że liczba $2^l-1$ jest podzielna przez $2^k -1$ . Wówczas liczba $l$ jest podzielna przez $k$ .

Dowód

Niech $l = kq +r$ , gdzie $r \in \{0,1,2,\ldots,k-1\}$ . Liczby $2^l -1$ i $2^{kq} -1$ są podzielne przez $2^k-1$ , zatem różnica tych liczb, czyli liczba $2^l -2^{kq} =2^{kq}(2^r -1)$ jest podzielna przez $2k - 1$ . Liczby $2^{kq}$ i $2^k - 1$ są względnie pierwsze, skąd wynika, że liczba $2^r -1$ jest podzielna przez $2^k -1$ . Ponieważ $r<k$ , więc podzielność ta ma miejsce jedynie wtedy, gdy $r = 0$ . To oznacza, że liczba $l$ jest podzielna przez $k$ .

Przystępujemy do rozwiązania zadania. Przypuśćmy, że $b_7 -a_7 |c_7 -a_7$ . Wtedy $2^{b_{6}}-2^{a_{6}}|2^{c_{6}}-2^{a_{6}}$ , skąd wynika, że $2^{b_{6}-a_{6}}-1|2^{c_{6}-a_{6}}-1$ . Korzystając z lematu uzyskujemy $b_{6}-a_{6}|c_{6}-a_{6}$ .

Kontynuując to rozumowanie dochodzimy do podzielności $b_0-a_0 |c_0-a_0$ , czyli 2|3, co nie jest prawdą.

LVI OM - II etap

II etap LVI Olimpiady Matematycznej

Załącznik	Wielkość
LVI OM II etap - Zadania [4]	66.89 KB
LVI OM II etap - Zadania z rozwiązaniami [5]	128.54 KB

LVI OM - II - Zadanie 1

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

Wyznaczyć wszystkie dodatnie liczby całkowite $n$ , dla których

$ n^n+1\ \textrm{oraz}\ (2n)^{2n}+1 $

są liczbami pierwszymi.

Rozwiązanie

Niech $a\geq 2$ , $m\geq 1$ będą liczbami całkowitymi. Wykażemy najpierw, że jeśli liczba $m$ ma dzielnik nieparzysty większy od 1, to liczba $a^m+1$ jest złożona. Istotnie: jeśli $l$ jest dzielnikiem nieparzystym liczby $m$ to $m=ld$ dla pewnej liczby całkowitej $d$ dodatniej oraz

$ a^{m}+1=(a^{d})^{l}+1=(a^{d}+1)\cdot((a^{d})^{l-1}-(a^{d})^{l-2}+\ldots-a^{d}+1). $

Z powyższego wzoru wynika, że liczba $a^{d}+1$ jest dzielnikiem liczby $a^{m}+1$ . Dla $l>1$ dzielnik ten jest większy od 1 i mniejszy od $a^{m}+1$ . Zatem liczba $a^{m}+1$ jest złożona.

Liczba $n=1$ spełnia warunki zadania: liczby $1^1+1=2$ , $2^{2}+1=5$ są liczbami pierwszymi. Załóżmy więc w dalszej części rozumowania, że $n\geq 2$ .

Jeśli liczba $n^{n}+1$ jest liczbą pierwszą, to $n$ nie ma dzielników nieparzystych większych od 1. Stąd wynika, że $n=2^k$ dla pewnej liczby całkowitej dodatniej $k$ . Wówczas

$ (1)\qquad n^{n}+1=2^{k\cdot 2^{k}}+1\ \text{oraz}\ (2n)^{2n}+1=2^{(k+1)\cdot 2^{k+1}}+1. $

Dla $k\geq 2$ co najmniej jedna z liczb $k\cdot 2^{k}$ , $(k+1)\cdot 2^{k+1}$ ma dzielnik nieparzysty większy od 1, a więc co najmniej jedna z liczb (1) jest złożona. Wobec tego musi być $k=1$ , czyli $n=2$ .

Pozostało upewnić się, że liczba $n=2$ spełnia warunki zadania: liczby $2^2+1=5$ oraz $4^4+1=257$ są liczbami pierwszymi.

Odpowiedź: $n=1$ lub $n=2$ .

LVI OM - II - Zadanie 2

Etap:

W czworokącie wypukłym $ABCD$ punkt $M$ jest środkiem przekątnej $AC$ . Wykazać, że jeżeli

$ \measuredangle BAD= \measuredangle BMC =\measuredangle CMD $

to na czworokącie $ABCD$ można opisać okrąg.

Rozwiązanie

Oznaczmy: $\alpha=\measuredangle BAD$ .

Jeśli $\alpha=90^{\circ}$ , to punkty $B$ , $M$ , $D$ leżą na jednej prostej. Wtedy punkty $A$ i $C$ są symetryczne względem prostej $BD$ . Stąd $\measuredangle BCD = \measuredangle BAD = 90^{\circ}$ , czyli na czworokącie $ABCD$ można opisać okrąg.

W dalszym ciągu przyjmijmy, że $\alpha \neq 90^{\circ}$ . Niech $E$ będzie punktem symetrycznym do punktu $D$ względem symetralnej odcinka $AC$ (rys. 1, 2). Wówczas $\measuredangle BMC= \measuredangle CMD =\measuredangle AME$ , skąd wynika, że punkty $B$ , $M$ , $E$ leżą na jednej prostej. Proste $AC$ i $ED$ są równoległe. Zatem gdy $\alpha<90^{\circ}$ (rys. 1), to

$ \measuredangle BAD=\measuredangle BMC = \measuredangle BED; $

natomiast jeśli $\alpha>90^{\circ}$ (rys. 2), to

$ \measuredangle BAD = \measuredangle BMC =180^{\circ}- \measuredangle BMA= 180^{\circ}-\measuredangle BED $

W obu przypadkach otrzymana równość oznacza, że punkty $A$ , $B$ , $D$ , $E$ leżą na jednym okręgu. Ponadto czworokąt o wierzchołkach $A$ , $C$ , $D$ , $E$ jest trapezem równoramiennym, a więc również punkty $A$ , $C$ , $D$ , $E$ leżą na jednym okręgu. Zatem punkty $A$ , $B$ , $C$ , $D$ leżą na jednym okręgu, co należało wykazać.

LVI OM - II - Zadanie 3

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

W przestrzeni danych jest $n$ punktów ( $n\geq 2$ ) z których żadne cztery nie leżą w jednej płaszczyźnie. Niektóre z tych punktów zostały połączone odcinkami. Niech $K$ będzie liczbą poprowadzonych odcinków ( $K\geq 1$ ), a $T$ liczbą powstałych trójkątów. Udowodnić, że

$ 9T^{2}<2K^{3}. $

Rozwiązanie

Ponumerujmy liczbami od 1 do $m$ te punkty, z których wychodzi co najmniej jeden odcinek i przyjmijmy, że z punktu o numerze $i$ ( $i=1,2,\ldots,m$ ) wychodzi dokładnie $k_i$ odcinków. Wtedy $k_i>0$ . Oznaczmy ponadto przez $t_i$ ( $i=1,2,\ldots,m$ ) liczbę tych trójkątów, których jednym z wierzchołków jest punkt o numerze $i$ Wówczas

$ (1) \qquad k_{1}+k_{2}+\ldots+k_{m}=2K\ \textrm{oraz}\ t_{1}+t_{2}+\ldots+t_{m}=3T. $

Zbiór $A_i$ tych punktów, które zostały połączone odcinkiem z punktem o numerze $i$ zawiera dokładnie $k_i$ elementów. Ponadto trójkątów mających wierzchołek w punkcie o numerze $i$ jest tyle samo, ile poprowadzonych odcinków o wierzchołkach w zbiorze $A_i$ . Zatem

$ (2)\qquad t_{i}\leq {{k_i} \choose 2} = \frac{k_{i}^{2}-k_{i}}{2} < \frac{k_{i}^{2}}{2}. $

Z drugiej strony, liczba tych odcinków jest mniejsza niż liczba wszystkich poprowadzonych odcinków. Wobec tego

$ (2)\qquad t_{i}\leq K. $

Mnożąc stronami nierówności (2) i (3) uzyskujemy $t_i^2< \frac{1}{2}k_i^2K$ . Stąd oraz z równości (1) otrzymujemy

$ 3T = \sum_{i=1}^{m}t_{i} < \sum_{i=1}^{m}\frac{k_{i}\cdot\sqrt{K}}{\sqrt{2}} = \frac{\sqrt{K}}{\sqrt{2}}\cdot\sum_{i=1}^{m}k_{i} = \frac{2K\sqrt{K}}{\sqrt{2}}. $

Podnosząc ostatnią nierówność stronami do kwadratu dostajemy tezę.

LVI OM - II - Zadanie 4

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

Dany jest wielomian $W(x)=x^2+ax+b$ , o współczynnikach całkowitych, spełniający warunek:

Dla każdej liczby pierwszej $p$ istnieje taka liczba całkowita $k$ , że liczby $W(k)$ oraz $W(k + 1)$ są podzielne przez $p$ . Dowieść, że istnieje liczba całkowita $m$ , dla której

$ W (m)= W (m +1)=0. $

Rozwiązanie

Warunek $W(m) = W(m +1) = 0$ oznacza, że $W(x)=(x-m)(x-m+1)$ , czyli $W(x)=x^{2}-(2m+1)x+m^{2}+m$ . Należy zatem wykazać, że istnieje taka liczba całkowita $m$ , że

$ a=-2m-1\ \textrm{oraz}\ b=m^{2}+m. $

Ustalmy liczbę pierwszą $p$ . Wówczas dla pewnej liczby całkowitej $k$ liczby

$ A=W(k)=k^{2}+ak+b, $

$ B=W(k+1)=k^{2}+(a+2)k+(a+b+1). $

są podzielne przez $p$ . Przez $p$ dzielą się więc kolejno następujące liczby:

$ C=B-A=2k+(a+1), $

$ D=2A-kC=(a-1)k+2b, $

$ E=(a-1)C-2D=a^{2}-4b-1. $

Liczba $E$ jest wyznaczona przez współczynniki wielomianu $W$ i nie zależy od $k$ . Przeprowadzając to rozumowanie dla każdej liczby pierwszej $p$ stwierdzamy, że liczba $E$ jest podzielna przez każdą liczbę pierwszą $p$ i w konsekwencji $E = 0$ . Stąd wynika, że liczba $a$ jest nieparzysta, tzn. $a = -2m-1$ dla pewnej liczby całkowitej $m$ , oraz $b= \frac{1}{4}(a^{2}-1)=m^{2}+m$ .

LVI OM - II - Zadanie 5

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

Dany jest romb $ABCD$ , w którym $\measuredangle BAD > 60^{\circ}$ . Punkty $E$ i $F$ leżą odpowiednio na bokach $AB$ i $AD$ , przy czym $\measuredangle ECF = \measuredangle ABD$ . Proste $CE$ i $CF$ przecinają przekątną $BD$ odpowiednio w punktach $P$ i $Q$ . Wykazać, że

$ \frac{PQ}{EF}=\frac{AB}{BD}. $

Rozwiązanie

Z równości $\measuredangle FDQ = \measuredangle PCQ$ wynika, że trójkąty $FDQ$ i $PCQ$ są podobne. Ponieważ punkty $A$ i $C$ są symetryczne względem prostej $BD$ , więc trójkąty $PCQ$ i $PAQ$ są przystające oraz

$ \measuredangle APQ = \measuredangle CPQ = \measuredangle DFQ = 180^{\circ} - \measuredangle AFQ. $

Równość ta oznacza, że punkty $A$ , $P$ , $Q$ , $F$ leżą na jednym okręgu. Podobnie dowodzimy, że punkty $A$ , $P$ , $Q$ , $E$ leżą na jednym okręgu. Istnieje więc okrąg przechodzący przez punkty $A$ , $P$ , $Q$ , $E$ i $F$ .

Z zależności $\measuredangle CPQ = \measuredangle CFE$ wnioskujemy, że trójkąty $CPQ$ i $CFE$ są podobne. Analogicznie uzyskujemy podobieństwo trójkątów $DQF$ i $DAP$ . Ponadto podobne są trójkąty $PAQ$ i $ABQ$ . Stąd

$ \frac{EF}{PQ}=\frac{FC}{PC}=\frac{FQ+AQ}{PC}=\frac{FQ}{PA}+\frac{AQ}{PA}=\frac{DQ}{AD}+\frac{BQ}{AB}=\frac{BD}{AB}, $

co należało wykazać.

LVI OM - II - Zadanie 6

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

Liczby $a$ , $b$ , $c$ należą do przedziału $\langle 0;1\rangle$ . Udowodnić, że

$ \frac{a}{bc+1}+\frac{b}{ca+1}+\frac{c}{ab+1}\leq 2. $

Rozwiązanie

Wykażemy, że dla dowolnych liczb $a$ , $b$ , $c$ należących do przedziału $\langle 0; 1\rangle$ zachodzi nierówność

$ (1) \qquad \frac{a}{bc+1}\leq\frac{2a}{a+b+c}. $

Istotnie: jeśli $a = 0$ , to powyższa nierówność jest spełniona. Dla $a>0$ zależność (1) jest równoważna nierówności $a + b + c \leq 2bc + 2$ , którą można zapisać jako

$ a \leq 1 + bc + (b- 1)(c-1). $

Ostatnia nierówność jest spełniona - wynika ona bezpośrednio z zależności $a \leq 1$ , $0 \leq bc$ , $0 \leq (b - 1)(c - 1)$ . To kończy dowód własności (1).

Analogicznie dowodzimy, że

$ (2) \qquad \frac{b}{ca+1}\leq\frac{2b}{a+b+c}\ \textrm{oraz}\ \frac{c}{ab+1}\leq\frac{2c}{a+b+c}. $

Dodając stronami nierówności (1) oraz (2) uzyskujemy tezę.

LVI OM - III etap

III etap LVI Olimpiady Matematycznej

Załącznik	Wielkość
LVI OM III etap - Zadania [6]	67.92 KB
LVI OM III etap - Zadania z rozwiązaniami [7]	129.64 KB

LVI OM - III - Zadanie 1

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

III

Wyznaczyć wszystkie trójki $(x,y,n)$ liczb całkowitych dodatnich spełniające równanie

$ (x-y)^n=xy. $

Rozwiązanie

Dla $n = 1$ podane równanie ma postać $(x + 1)(y - 1) = -1$ , więc nie ma rozwiązań w liczbach całkowitych dodatnich. Przyjmijmy zatem, że $n \geq 2$ .

Niech $z = x - y$ . Dane równanie przybiera postać $x^{2}-xz =z^{n}$ . Po przemnożeniu przez 4 i prostym przekształceniu uzyskujemy

$ (1) \qquad (2x-z)^{2}=z^{2}(1+4z^{n-2}). $

Stąd wynika, że czynnik $1+4z^{n-2}$ jest kwadratem liczby całkowitej. Ponieważ jest to liczba nieparzysta większa od 1, więc dla pewnej liczby całkowitej dodatniej $t$ mamy $1+4z^{n-2}=(2t+1)^{2}$ , czyli

$ z^{n-2}=t(t+1). $

Dla $n = 2$ uzyskujemy $1 = t(t + 1)$ , co nie może być spełnione, gdyż liczba $t(t + 1)$ jest parzysta dla każdej liczby całkowitej $t$ . Zatem jeśli $n = 2$ , to dane równanie nie ma rozwiązań w liczbach całkowitych dodatnich.

Dla $n = 3$ mamy $z = t(t+ 1)$ . Wstawiając to wyrażenie do równania (1) wyznaczamy niewiadomą $x$ . Po kilku przekształceniach otrzymujemy

$ x=t(t+1)^{2}\ \text{lub}\ x=-t^{2}(t+1). $

Ponieważ $t> 0$ , a $x$ jest liczbą dodatnią, to druga z wyznaczonych wartości $x$ odpada. Ponadto $y=x-z =t(t+1)^{2}-t(t+1)=t^{2}(t+1)$ . Znaleźliśmy w ten sposób następujące trójki:

$ (2) \qquad (x,y,n) =(t(t+1)^{2},\ t^{2}(t+1), 3),\ \textrm{gdzie}\ t =1,2,3, \ldots $

Bezpośrednio sprawdzamy, że są one rozwiązaniami danego równania.

Pozostał do rozpatrzenia przypadek $n \geq 4$ . Ponieważ liczby $t$ , $t + 1$ są względnie pierwsze, a ich iloczyn jest $(n-2)$ -gą potęgą liczby całkowitej dodatniej, to każda z tych liczb musi być $(n-2)$ -gą potęgą liczby całkowitej dodatniej. Jednak dla $n \geq 4$ nie istnieją dwie kolejne liczby całkowite dodatnie będące $(n-2)$ -gimi potęgami liczb całkowitych. Zatem jeśli $n \geq 4$ , to dane równanie nie ma rozwiązań w liczbach całkowitych dodatnich.

Reasumując: dane równanie ma rozwiązanie $(x,y)$ w liczbach całkowitych dodatnich tylko dla $n = 3$ . Wszystkie rozwiązania są dane wzorem (2).

LVI OM - III - Zadanie 2

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

III

Punkty $A$ , $B$ , $C$ , $D$ leżą, w tej właśnie kolejności, na okręgu $o$ . Punkt $S$ leży wewnątrz okręgu $o$ i spełnia warunki

$ \measuredangle SAD = \measuredangle SCB \ \textrm{oraz}\ \measuredangle SDA = \measuredangle SBC. $

Prosta zawierająca dwusieczną kąta $ASB$ przecina okrąg $o$ w punktach $P$ i $Q$ . Dowieść, że $PS = QS$ .

Rozwiązanie

Przyjmijmy, że proste $AS$ , $BS$ , $CS$ przecinają okrąg $o$ po raz drugi odpowiednio w punktach $E$ , $F$ , $G$ (rys. 1). Z danych w zadaniu równości wynika podobieństwo trójkątów $ASD$ i $CSB$ , a stąd

$ \frac{AS}{CS}=\frac{DS}{BS} \ \textrm{oraz}\ \measuredangle BSC =\measuredangle DSA, $

więc i $\measuredangle ASC = \measuredangle DSB$ . Równości te dowodzą, że trójkąty $ASC$ i $DSB$ są podobne, skąd w szczególności dostajemy $\measuredangle ACS = \measuredangle DBS$ . Stąd wniosek, że łuki $GA$ i $FD$ okręgu $o$ są równe (pisząc „łuk $XY$ " mamy na myśli łuk biegnący wzdłuż okręgu $o$ od punktu $X$ do punktu $Y$ w kierunku przeciwnym do ruchu wskazówek zegara). Analogicznie, z równości $\measuredangle SAD = \measuredangle SCB$ wnioskujemy, że łuki $GB$ i $ED$ są równe. Zatem także łuki $AB$ i $EF$ są równe.

Czworokąt $ABEF$ jest więc trapezem równoramiennym, a punkt $S$ jest punktem przecięcia jego przekątnych (rys. 2). Przyjmijmy, że punkt $P$ leży na tym łuku $AB$ okręgu $o$ , który nie zawiera punktów $C$ i $D$ . Z równości

$ \measuredangle PSA = \frac{1}{2}\measuredangle ASB =\frac{1}{2}(\measuredangle FAS+\measuredangle AFS)=\measuredangle FAS $

wynika, że prosta $PQ$ jest równoległa do prostych $BE$ i $AF$ . Stąd wniosek, że punkty $A$ , $P$ , $B$ są odpowiednio obrazami punktów $F$ , $Q$ , $E$ w symetrii względem symetralnej odcinków $AF$ i $BE$ . Zatem $PS = QS$ .

LVI OM - III - Zadanie 3

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

III

W kwadratowej tablicy o wymiarach $2n \times 2n$ , gdzie $n$ jest liczbą naturalną, znajduje się $4n^2$ liczb rzeczywistych o sumie równej 0 (na każdym polu tablicy jedna liczba). Wartość bezwzględna każdej z tych liczb jest nie większa od 1. Dowieść, że wartość bezwzględna sumy wszystkich liczb z pewnego rzędu (poziomego lub pionowego) nie przekracza $n$ .

Rozwiązanie

Ponumerujmy wiersze i kolumny danej tablicy liczbami $1,2,\ldots, 2n$ .

Niech $r_1,r_2,\ldots ,r_{2n}$ będą sumami liczb napisanych w wierszach o numerach $1,2,\ldots,2n$ , a $c_1,c_2,\ldots,c_{2n}$ sumami liczb znajdujących się w kolumnach o numerach $1,2,\ldots,2n$ . Zmieniając numerację wierszy oraz kolumn możemy założyć, że $r_1 \geq r_2 \geq \ldots \geq r_{2n}$ oraz $c_i \geq c_2 \geq \ldots \geq c_{2n}$ .

Oznaczmy przez $A$ , $B$ , $C$ , $D$ sumy liczb w czterech ćwiartkach tablicy, jak pokazuje rysunek 3.

Wówczas $A + B + C + D = 0$ , skąd wynika, że w ciągu $(A,B,C,D,A)$ istnieją dwie kolejne liczby, z których jedna jest nieujemna, a druga niedodatnia. Przyjmijmy na przykład, że $AB \leq 0$ . Rozumowanie w pozostałych przypadkach jest analogiczne.

Liczby $A$ i $B$ powstały z sumowania $n^2$ liczb rzeczywistych o wartości bezwzględnej nie większej niż 1, a więc $|A| \leq n^2$ oraz $|B| \leq n^2$ . Jedna z liczb $A$ , $B$ jest nieujemna, a druga niedodatnia, więc $|A + B| \leq max(|A|,|B|) \leq n^2$ . Stąd otrzymujemy również $|C + D| = | A + B| \leq n^2$ .

Jeżeli $r_n \geq 0$ , to liczby $r_1 ,r_2,\ldots,r_n$ są nieujemne. Wtedy ich suma $A + B$ jest też nieujemna, skąd uzyskujemy $r_1 + r_2 +\ldots + r_n = A + B \leq n^2$ . Zatem co najmniej jedna z (nieujemnych) liczb $r_1,r_2,\ldots ,r_n$ nie przekracza $n$ .

Jeżeli natomiast $r_n < 0$ , to liczby $r_{n+1},r_{n+2},\ldots, r_{2n}$ są ujemne i ich suma wynosi $C + D$ . Wtedy $|r_{n+1}| + |r_{n+2}| +\ldots + |r_{2n}| = |C + D|\leq n^2$ . Stąd wynika, że co najmniej jedna z liczb $|r_{n+1}, |r_{n+2}|,\ldots,|r_{2n}|$ nie przekracza $n$ .

To dowodzi zadania.

LVI OM - III - Zadanie 4

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

III

Dana jest liczba rzeczywista $c> -2$ . Dowieść, że jeżeli liczby $x_1, x_2,... ,x_n$ ( $n \geq 2$ ) są dodatnie oraz

$ \begin{array}{r} \sqrt{x_{1}^{2}+cx_{1}x_{2}+x_{2}^{2}}+\sqrt{x_{2}^{2}+cx_{2}x_{3}+x_{3}^{2}}+\ldots+\sqrt{x_{n}^{2}+cx_{n}x_{1}+x_{1}^{2}}=\\ =\sqrt{c+2}(x_{1}+x_{2}+\ldots+x_{n}), \end{array} $

to $c =2$ lub $x_1 = x_2 = \ldots = x_n$ .

Rozwiązanie

Wprowadźmy następujące oznaczenia:

$ a_{i}=\sqrt{c+2}(x_{i}+x_{i+1})\ \textrm{oraz}\ b_{i}=2\sqrt{x_{i}^{2}+cx_{i}x_{i+1}+x_{i+1}^{2}}\ \textrm{dla}\ i=1,2, \ldots, n, $

przyjmując $x_{n+1} = x_1$ . Liczby $a_i$ są dodatnie. Redukując wyrazy podobne otrzymujemy zależność $a_{i}^{2}-b_{i}^{2}=(c-2)(x_{i}-x_{i+1})^{2}$ . Stąd oraz z danej w treści zadania równości dostajemy

$ 0=\sum_{i=1}^{n}(a_{i}-b_{i})=\sum_{i=1}^{n}\frac{a_{i}^{2}-b_{i}^{2}}{a_{i}+b_{i}}=(c-2)\sum_{i=1}^{n}\frac{(x_{i}-x_{i+1})^{2}}{a_{i}+b_{i}}. $

Prawa strona powyższej równości jest równa 0 jedynie wtedy, gdy $c = 2$ lub $x_1 = x_2 = \ldots = x_n$ .

LVI OM - III - Zadanie 5

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

III

Niech $k$ będzie liczbą naturalną większą od 1 i niech $m = 4k^2 - 5$ .

Wykazać, że istnieją takie liczby całkowite dodatnie $a$ , $b$ , że każdy wyraz ciągu $(x_n)$ określonego wzorami

$ x_{1}=a,\ x_{2}=b,\ x_{n+2}=x_{n+1}+x_{n}\ \textrm{dla}\ n\geq 1 $

jest względnie pierwszy z liczbą $m$ .

Rozwiązanie

Wykażemy, że warunki zadania spełniają liczby $a = 1$ , $b = 2k^2 + k - 2$ . Udowodnimy indukcyjnie, że $x_n \equiv b^{n-1}(\mathrm{mod}\ m)$ dla $n = 1,2,3,...$ . Dla $n = 1$ i $n = 2$ zależność ta jest oczywiście spełniona.

Korzystając ze związku $4k^2\equiv 5(\mathrm{mod}\ m)$ uzyskujemy kolejno:

$ 2b=4k^{2}+2k-4\equiv 2k+1(\mathrm{mod}\ m), $

$ 4b^{2}\equiv 4k^{2}+4k+1\equiv 4k+6\equiv 4b+4(\mathrm{mod}\ m). $

Liczby 4 i $m$ są względnie pierwsze, więc $b^2\equiv b+1(\mathrm{mod}\ m)$ . Stąd i z założenia indukcyjnego dostajemy

$ x_{n+2}=x_{n+1}+x_{n}\equiv b^{n}+b^{n-1}\equiv b^{n+1}(\mathrm{mod}\ m). $

Dowód indukcyjny jest zakończony.

Z uzyskanej w tym dowodzie zależności $b^2 \equiv b +1 (\mathrm{mod}\ m)$ wynika, że liczby $b$ i $m$ są względnie pierwsze. Skoro zaś $x_n \equiv b^{n-1} (\mathrm{mod}\ m)$ , wnosimy stąd, że (dla każdego $n$ ) liczby $x_n$ i $m$ są względnie pierwsze.

LVI OM - III - Zadanie 6

Zawody matematyczne:

LVI OM, 2004-2005

Etap:

III

Udowodnić, że każdy wielokąt wypukły o polu 1 zawiera sześciokąt wypukły o polu nie mniejszym niż 3/4.

Rozwiązanie

Spośród wierzchołków danego wielokąta $\mathcal{W}$ wybieramy trzy $A$ , $B$ i $C$ będące wierzchołkami trójkąta o największym polu, równym $s$ . Niech $X$ będzie punktem wielokąta $\mathcal{W}$ , leżącym po przeciwnej stronie prostej $BC$ niż punkt $A$ i oddalonym najdalej od prostej $BC$ (rys. 4). Analogicznie definiujemy punkty $Y$ i $Z$ .

Wykażemy, że pole sześciokąta $AZBXCY$ jest nie mniejsze niż 3/4, co zakończy rozwiązanie zadania.

Przez punkty $A$ , $B$ i $C$ poprowadźmy proste równoległe odpowiednio do prostych $BC$ , $CA$ i $AB$ wyznaczające trójkąt o wierzchołkach $D$ , $E$ , $F$ (rys. 5). Z faktu, iż trójkąt $ABC$ ma największe pole spośród wszystkich trójkątów o wierzchołkach w wierzchołkach wielokąta $\mathcal{W}$ wynika, że wielokąt $\mathcal{W}$ jest zawarty w trójkącie $DEF$ .

Przez punkty $X$ , $Y$ , $Z$ prowadzimy proste równoległe odpowiednio do prostych $BC$ , $CA$ , $AB$ przecinające boki trójkąta $DEF$ w punktach $K$ , $L$ , $M$ , $N$ , $P$ , $Q$ , jak na rysunku 5. Z określenia punktów $X$ , $Y$ , $Z$ wynika, że wielokąt $\mathcal{W}$ jest zawarty w sześciokącie o wierzchołkach $K$ , $L$ , $M$ , $N$ , $P$ , $Q$ .

Oznaczmy przez $s$ pole trójkąta $ABC$ . Wówczas każdy z trójkątów $BCD$ , $CAE$ i $ABF$ ma pole równe $s$ . Niech ponadto $x$ , $y$ , $z$ oznaczają odpowiednio pola trójkątów $BCX$ , $CAY$ i $ABZ$ . Należy wykazać, że $x + y + z + s \geq 3/4$ .

Niech $J$ będzie takim punktem, że czworokąt $CBJL$ jest równoległobokiem. Wówczas trójkąty $CBD$ i $JKB$ są podobne. Oznaczając przez $[\mathcal{F}]$ pole figury $\mathcal{F}$ , mamy zależności