LIV OM - II etap

II etap LIV Olimpiady Matematycznej

Załącznik	Wielkość
LIV OM II etap - Zadania [1]	53.91 KB
LIV OM II etap - Zadania z rozwiązaniami [2]	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$ .