LVI OM - I etap

I etap LVI Olimpiady Matematycznej

Załącznik	Wielkość
LVI OM I etap - Zadania [1]	99.49 KB
LVI OM I etap - Zadania z rozwiązaniami [2]	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ą.