LVII OM - II etap

II etap LVII Olimpiady Matematycznej

Załącznik	Wielkość
LVII OM II etap - Zadania [1]	67.82 KB
LVII OM II etap - Zadania z rozwiązaniami [2]	131.16 KB

LVII OM - II - Zadanie 1

Zawody matematyczne:

LVII OM, 2005-2006

Etap:

Liczby całkowite dodatnie $a, b, c, x, y, z$ spełniają równości

$ a^2 + b^2 = c^2, \quad x^2+y^2 = z^2 $

oraz nierówności $|x-a|\leq 1$ , $|y-b|\leq 1$ .

Wykazać, że zbiory $\{a,b\}$ oraz $\{x,y\}$ są równe.

Rozwiązanie

Wobec symetrii ról trójek $(a,b,c)$ oraz $(x,y,z)$ można przyjąć, że $z \geq c$ . Patrząc na punkty
$A=(a,b)$ , $X =(x,y)$ na płaszczyźnie z początkiem układu współrzędnych $O = (0,0)$ widzimy, że

$ z-c = OX -OA \leq AX = \sqrt{(x-a)^2 +(y-b)^2} \leq \sqrt{2}. $

Mamy więc dwie możliwości: $z=c+1$ lub $z=c$ .

Jeśli $z=c+1$ , to wtedy $x^2+y^2>a^2+b^2$ . Wobec tego $x>a$ lub $y>b$ . Bez straty ogólności możemy przyjąć,
że $x>a$ , czyli $x=a+1$ . Wówczas

$ y = z^2 -x^2 =(c+1)^2 -(a+1)^2 = b^2 +2c-2a. $

Zatem liczby $b$ i $y$ są jednakowej parzystości. Ponadto $c>a$ , więc powyższa równość implikuje również, że $y>b$ . Uzyskaliśmy sprzeczność z warunkiem $|y -b|\leq 1$ .
Jeśli $z = c$ , to mamy równość $x^2 +y^2= a^2 +b^2$ , czyli

$ (x-a)(x+a)=(b-y)(b+y). $

Albo obie strony tego równania są równe zeru i wtedy mamy tezę ( $x = a$ , $y = b$ ), albo są różne od zera i wtedy

$ \frac{x+a}{b+y}=\frac{b-y}{x-a}=\pm\frac{b-y}{x-a}=\pm 1 $

Wartość $-1$ wykluczamy, bo liczby $a, b, x, y$ są dodatnie. Z ostatniej równości uzyskujemy zatem $a+x = b+y$ oraz $b-y = x-a$ .
Stąd dostajemy $x = b$ oraz $y = a$ , czyli tezę zadania.

LVII OM - II - Zadanie 2

Zawody matematyczne:

LVII OM, 2005-2006

Etap:

Dany jest trójkąt $ABC$ , w którym $AC+BC =3AB$ . Okrąg o środku $I$ wpisany w trójkąt $ABC$ jest styczny do boków
$BC$ i $CA$ odpowiednio w punktach $D$ i $E$ . Niech $K$ i $L$ będą punktami symetrycznymi odpowiednio do punktów
$D$ i $E$ względem punktu $I$ . Udowodnić, że punkty $A, B, K, L$ leżą na jednym okręgu.

Rozwiązanie

Oznaczmy przez P punkt przecięcia dwusiecznej kąta ACB z okręgiem opisanym na trójkącie ABC (rys. 1). Wówczas AP = BP . Ponadto

$ \begin{split} \measuredangle PAI &= \measuredangle PAB +\measuredangle BAI = \measuredangle PCB + \measuredangle CAI = \\ &= \measuredangle ACI +\measuredangle CAI = \measuredangle PIA, \end{split} $

skąd wynika, że $AP = IP$ .

Punkty $A, B$ oraz $I$ leżą więc na okręgu o środku $P$ . Wykażemy, że na tym okręgu leżą również punkty $K$ i $L$ .

Punkty $D$ i $E$ są punktami styczności okręgu wpisanego w trójkąt $ABC$ z bokami $BC$ i $AC$ , a więc $CD = CE = \frac{1}{2}(AC+BC-AB)$ . Ponadto dana w treści zadania równość jest równoważna zależności $AB=\frac{1}{2}(AC+BC-AB)$ . Stąd wynika, że CD = AB.

Oznaczmy przez $M$ środek odcinka $AB$ , a przez $N$ rzut prostokątny punktu $P$ na prostą $DI$ (rys. 2). Wówczas proste
$PN$ i $BC$ są równoległe, wobec czego $\measuredangle PAM = \measuredangle PCB = \measuredangle IPN$ . To w połączeniu z równością
$AP = IP$ dowodzi, że trójkąty prostokątne $APM$ i $PIN$ są przystające. Stąd otrzymujemy $PN = AM$ .

Proste $CD$ i $PN$ są równoległe, więc

$ \frac{ID}{IN}=\frac{CD}{PN}=\frac{AB}{AM}=2 $

skąd dostajemy $ID =2\cdot IN$ . Zależność ta w połączeniu z równością $ID = IK$ implikuje, że $IN =KN$ . Zatem punkt
$K$ jest symetryczny do punktu $I$ względem prostej $PN$ . Wobec tego $IP = KP$ .

Analogicznie dowodzimy, że $IP = LP$ . Z uzyskanych zależności wynika, że punkty $A, B, K, L$ oraz $I$ leżą na okręgu o środku $P$ , co kończy rozwiązanie zadania.

LVII OM - II - Zadanie 3

Zawody matematyczne:

LVII OM, 2005-2006

Etap:

Liczby dodatnie $a, b, c$ spełniają warunek $ab+bc+ca = abc$ . Dowieść, że

$ \frac{a^4+b^4}{ab(a^3+b^3)}+\frac{b^4+c^4}{bc(b^3+c^3)}+\frac{c^4+a^4}{ca(c^3+a^3)}\geq 1 $

Rozwiązanie

Dzieląc równość $ab+bc+ca = abc$ stronami przez $abc$ otrzymujemy

$ \frac{1}{a} + \frac{1}{b} + \frac{1}{c} = 1. $

Podstawmy zatem: $x=1/a,\ y =1/b,\ z =1/c$ . Wtedy liczby $x, y, z$ są dodatnie, a ich suma wynosi 1. Ponadto

$ \frac{a^4+b^4}{ab(a^3+b^3)} = \frac{\frac{1}{x^4}+\frac{1}{y^4}}{\frac{1}{xy}\left(\frac{1}{x^3} + \frac{1}{y^3}\right)} = \frac{x^4+y^4}{x^3+y^3} $

Zatem dowodzona nierówność przybiera postać

$ (1) \qquad \frac{x^4+y^4}{x^3+y^3} + \frac{y^4+z^4}{y^3+z^3} + \frac{z^4+x^4}{z^3+x^3} \geq 1 $

Wykażemy, że dla dowolnych liczb dodatnich $x, y$ spełniona jest zależność

$ (2) \qquad \frac{x^4+y^4}{x^3+y^3} \geq \frac{x+y}{2}. $

Przekształcając równoważnie powyższą nierówność dostajemy kolejno

$ \begin{split} 2x^4 + 2y^4 &\geq x^4 + x^3y + xy^3 + y^4, \\ x^4 - xy + y^4 - xy^3 &\geq 0, \\ (x^3 - y^3)(x-y) &\geq 0. \end{split} $

Uzyskaliśmy zależność prawdziwą dla dowolnych liczb dodatnich $x$ i $y$ , a zatem nierówność (2) jest spełniona. Analogicznie dowodzimy, że

$ (3) \qquad \frac{y^4+z^4}{y^3+z^3} \geq \frac{y+z}{2} \quad\text{ oraz }\quad \frac{z^4+x^4}{z^3+x^3} \geq \frac{z+x}{2}. $

Dodając stronami związki (2), (3) oraz wykorzystując warunek $x + y + z = 1$ otrzymujemy dowodzoną nierówność (1).

LVII OM - II - Zadanie 4

Zawody matematyczne:

LVII OM, 2005-2006

Etap:

Niech $c$ będzie ustaloną liczbą całkowitą dodatnią. Ciąg $(a_n)$ jest określony przez warunki

$ a_1 =1,\;a_{n+1} = d(a_n)+c \text{ dla } n =1,2,\dots, $

gdzie $d(m)$ oznacza liczbę dodatnich dzielników liczby $m$ . Wykazać, że istnieje taka liczba całkowita dodatnia $k$ ,
że ciąg $a_k,a_{k+1},a_{k+2},\ldots$ jest okresowy.

Rozwiązanie

Wykażemy, że dla $n =1,2,3,\ldots$ zachodzą nierówności $1 \leq a_n \leq 2c+2$ . Pierwsza z nich jest oczywiście spełniona.
Drugą wykażemy indukcyjnie. Dla $n = 1$ mamy $a_1 = 1 \leq 2c + 2$ , co jest prawdą. Ustalmy więc $n>1$ i przyjmijmy, że
$a_n \leq 2c+2$ .

Jeśli $k \geq 3$ jest liczbą całkowitą, to żadna liczba całkowita z przedziału $(\frac{1}{2}k,k)$ nie jest dzielnikiem
liczby $k$ . Wobec tego liczba $k$ nie może mieć więcej niż $\frac{1}{2}k + 1$ dzielników dodatnich. Zatem

$ d(k) \leq \frac{k}{2} + 1 \quad \text{ dla }k =3,4,\ldots. $

Bezpośrednio sprawdzamy, że powyższa nierówność jest również spełniona dla $k = 1$ oraz dla $k = 2$ . Stąd oraz z założenia
indukcyjnego uzyskujemy

$ a_{n+1} = d(a_n)+c \leq \frac{a_n}{2}+1+c \leq \frac{2c+2}{2}+1+c =2c+2, $

co kończy dowód indukcyjny postulowanej nierówności. Ciąg $(an)$ jest więc ograniczony, a zatem istnieją takie liczby całkowite dodatnie $k<l$ , że $a_k = a_l$ .

Każdy wyraz $a_n$ danego ciągu wyznacza wyraz następny $a_{n+1}$ , a więc ciąg $a_k,a_{k+1},a_{k+2},\ldots$ jest okresowy o okresie równym $l-k$ .

LVII OM - II - Zadanie 5

Zawody matematyczne:

LVII OM, 2005-2006

Etap:

Punkt $C$ jest środkiem odcinka $AB$ . Okrąg $o_1$ przechodzący przez punkty $A$ i $C$ przecina okrąg $o_2$ przechodzący
przez punkty $B$ i $C$ w różnych punktach $C$ i $D$ . Punkt $P$ jest środkiem tego łuku $AD$ okręgu $o_1$ , który nie zawiera
punktu $C$ . Punkt $Q$ jest środkiem tego łuku $BD$ okręgu $o_2$ , który nie zawiera punktu $C$ . Dowieść, że proste $PQ$ i $CD$
są prostopadłe.

Rozwiązanie

Jeśli $AC = CD$ , to również $BC = CD$ . Wtedy odcinki $PC$ i $QC$ są odpowiednio średnicami okręgów $o_1$ i $o_2$ . Zatem $\measuredangle CDP = \measuredangle CDQ = 90^{\circ}$ , skąd wynika, że punkt $D$ leży na odcinku $PQ$ , a proste $PQ$ i $CD$ są prostopadłe.

Przyjmijmy więc w dalszej części rozwiązania, że $AC \neq CD$ .

Niech $E$ będzie takim punktem leżącym na półprostej $CD$ , że $CE = AC$ (rys. 3). Wtedy również $CE = BC$ .
Z zależności $CE = AC$ oraz $\measuredangle ACP = \measuredangle ECP$ wynika, że trójkąty $ACP$ oraz $ECP$ są przystające
(cecha bok-kąt-bok). Wobec tego $EP = AP = DP$ .

Analogicznie dowodzimy, że $EQ = DQ$ .

Z uzyskanych równości wynika, że punkty $D$ i $E$ są symetryczne względem prostej $PQ$ . Prosta $DE$ jest więc prostopadła
do prostej $PQ$ , co kończy rozwiązanie zadania.

LVII OM - II - Zadanie 6

Zawody matematyczne:

LVII OM, 2005-2006

Etap:

Dana jest liczba pierwsza $p$ oraz liczba całkowita $n$ , przy czym $p \geq n \geq 3$ . Zbiór $A$ składa się z $n$ -wyrazowych ciągów o wyrazach ze zbioru $\{0,1,2,\dots ,p-1\}$ i ma następującą własność:

Dla dowolnych dwóch ciągów $(x_1,x_2,\dots ,x_n)$ oraz $(y_1,y_2,\dots ,y_n)$ ze zbioru $A$ istnieją takie różne liczby
$k, l, m$ , że

$ x_k\neq y_k,\quad x_l\neq y_l,\quad x_m\neq y_m. $

Wyznaczyć największą możliwą liczbę elementów zbioru $A$ .

Rozwiązanie

Odpowiedź: $p^{n-2}$ .

Każde dwa różne ciągi zbioru $A$ muszą różnić się na co najmniej jednej z początkowych $n - 2$ pozycji. Wobec tego liczba
ciągów w tym zbiorze nie przekracza liczby wszystkich ciągów $(n-2)$ -wyrazowych o wyrazach ze zbioru $p$ -elementowego, czyli
liczby $p^{n-2}$ .

Skonstruujemy $p^{n-2}$ ciągów o wyrazach ze zbioru $S = \{0,1,2,\dots ,p-1\}$ mających postulowaną własność.
W tym celu rozpatrzmy wszystkie ciągi $(x_1,x_2,\dots ,x_n)$ o wyrazach ze zbioru $S$ spełniające warunki

$ (1) \qquad x_{n-1} \equiv \sum_{i=1}^{n-2} x_i (\mod p) \text{ oraz } x_n \equiv \sum_{i=1}^{n-2} i x_i (\mod p). $

Ciągów takich jest $p^{n-2}$ , ponieważ każdy ciąg ( $(x_1,x_2,\dots ,x_{n-2})$ o wyrazach ze zbioru $p$ -elementowego $S$
wyznacza jednoznacznie wartości $x_{n-1}$ i $x_n$ .

Każde dwa różne ciągi spełniające zależności (1) różnią się na co najmniej jednej z początkowych $n - 2$ pozycji.
Chcemy zaś dowieść, że każde dwa takie ciągi $(x_1,x_2,\dots ,x_n)$ oraz $(y_1,y_2,\dots ,y_n)$ różnią się na co najmniej
trzech pozycjach.

Jeśli ciągi te różnią się na co najmniej trzech miejscach o numerach $1,2,\dots ,n-2$ , to nie ma czego dowodzić. Pozostaje zatem rozpatrzeć następujące dwa przypadki.

Odcinki początkowe $(x_1,x_2,\dots ,x_{n-2})$ oraz $(y_1,y_2,\dots ,y_{n-2})$ różnią się na dokładnie dwóch pozycjach
o numerach $i$ , $j$ ( $1 \leq i < j \leq n-2$ ).

Wtedy $x_i \neq y_i$ oraz $x_j = y_j$ . Z zależności (1) otrzymujemy

$ \begin{cases} x_{n-1} - y_{n-1} &\equiv (x_i - y_i)+(x_j - y_j) (\mod p) \\ x_n - y_n &\equiv i(x_i -y_i)+j(x_j -y_j) (\mod p). \end{cases} $

Stąd $(x_n - y_n)-i(x_{n-1} - y_{n-1}) \equiv (j -i)(x_j -y_j) (\mod p)$ .

Liczba $p$ jest pierwsza, a liczby $x_j$ i $y_j$ są różne i należą do zbioru $S$ . Ponadto $1 \leq j -i <n \leq p$ .
Stąd wynika, że liczba $(x_n - y_n)-i(x_{n-1} - y_{n-1})$ nie jest podzielna przez $p$ . Zatem któraś z liczb
$x_{n-1} - y_{n-1}$ lub $x_n - y_n$ nie jest podzielna przez $p$ . Wobec tego $x_{n-1}\neq y_{n-1}$ lub $x_n \neq y_n$ .
Rozpatrywane ciągi różnią się więc na pozycji o numerze $n-1$ lub $n$ , czyli łącznie na co najmniej trzech pozycjach.
Odcinki początkowe $(x_1,x_2,\dots ,x_{n-2})$ oraz $(y_1,y_2,\dots,y_{n-2})$ różnią się na dokładnie jednej pozycji
o numerze $i$ ( $1 \leq i \leq n-2$ ).

Wtedy $x_i \neq y_i$ i podobnie korzystając z zależności (1) mamy

$ \begin{cases} x_{n-1} - y_{n-1} &\equiv x_i - y_i (\mod p) \\ x_n - y_n \equiv i(x_i - y_i) (\mod p) \end{cases} $

Stąd wynika, że liczby $x_{n-1} - y_{n-1}$ oraz $x_n - y_n$ nie są podzielne przez $p$ . Zatem $x_{n-1} \neq y_{n-1}$
oraz $x_n =y_n$ , czyli i w tym przypadku rozpatrywane ciągi różnią się na co najmniej trzech pozycjach.