LX OM - II etap

II etap LX Olimpiady Matematycznej

Załącznik	Wielkość
LX OM II etap - Zadania [1]	70.92 KB
LX OM II etap - Zadania z rozwiązaniami [2]	138.95 KB

LX OM - II - Zadanie 1

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Liczby rzeczywiste $a_1, a_2, \cdots , a_n$ $(n \geqslant 2)$ spełniają warunek
$a_1 \geqslant a_2 \geqslant \cdots \geqslant a_n > 0$ . Udowodnić nierówność

$ a_1a_2 \cdots a_{n-1} +(2a_2 -a_1)(2a_3 -a_2) \cdots (2a_n -a_{n-1}) \geqslant 2a_2a_3 \cdots a_n. $

Rozwiązanie

Zastosujemy indukcję matematyczną ze względu na wartość liczby $n$ .

Dla $n = 2$ teza zadania jest prawdziwa, gdyż obie strony dowodzonej zależności są równe $2a_2$ .

Przechodząc do kroku indukcyjnego rozpatrzmy liczby rzeczywiste
$a_1, a_2, \cdots , a_{n+1}$ , dla których $a_1 \geqslant a_2 \geqslant \cdots \geqslant a_{n+1} >0$ .
Należy udowodnić nierówność

$ (1) \qquad a_1a_2 \cdots a_n +(2a_2 -a_1)(2a_3 -a_2) \cdots (2a_{n+1} -a_n) \geqslant 2a_2a_3 \cdots a_na_{n+1}. $

Wprowadźmy oznaczenia

$ t = a_1 -a_2, \quad K = a_2a_3 \cdots a_n, \quad L = (2a_3 -a_2) \cdots (2a_{n+1} -a_n); $

wówczas lewą stronę zależności (1) możemy zapisać w postaci

$ (2) a_1K +(2a_2 -a_1)L =(a_2 +t)K +(a_2 -t)L = a_2(K +L)+t(K -L). $

Stosując założenie indukcyjne do $n$ liczb $a_2 \geqslant a_3 \geqslant \cdots \geqslant a_{n+1} \geqslant 0$
uzyskujemy

$ \begin{split} K+L &= a_2a_3 \cdots a_n +(2a_3 -a_2)(2a_4 -a_3) \cdots (2a_{n+1} -a_n) \geqslant \geqslant 2a_3 \cdots a_na_{n+1}. \end{split} $

Ponadto dla dowolnych liczb rzeczywistych $x\geqslant y>0$ prawdziwa jest podwójna nierówność
$-x \leqslant -x+2(x-y)= x-2y<x$ , skąd $|x-2y|\leqslant x$ i w konsekwencji

$ |L| = |2a_3 -a_2|\cdot |2a_4 -a_3|\cdot \cdots \cdot|2a_{n+1} -a_n|\leqslant a_2 \cdot a_3 \cdot \cdots \cdot a_n = K. $

Oznacza to, że liczba $K - L$ jest nieujemna. Liczba $t = a_1 - a_2$ jest również nieujemna, zatem
kontynuując zależność (2) i wykorzystując (3) dostajemy

$ a_2(K +L)+t(K -L) \geqslant a_2 \cdot 2a_3 \cdots a_na_{n+1}. $

Otrzymaliśmy prawą stronę nierówności (1), co kończy dowód indukcyjny.

LX OM - II - Zadanie 2

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Dane są takie liczby całkowite $a$ i $b$ , że $a>b> 1$ oraz liczba $ab +1$ jest podzielna przez $a+b$ ,
zaś liczba $ab-1$ jest podzielna przez $a-b$ .

Wykazać, że $a<b\sqrt{3}$ .

Rozwiązanie

Zauważmy najpierw, że

$ (a+b)b-(ab+1) = b^2 -1\quad \text{oraz} \quad (ab-1)-b(a-b)= b^2 -1. $

Zatem z danych w treści zadania podzielności wynika, że liczba $b^2 - 1$ jest podzielna przez
$a+b$ i przez $a-b$ .

Liczby $a$ i $b$ są względnie pierwsze. Jeżeli bowiem $d$ jest ich wspólnym dzielnikiem dodatnim,
to liczby $a + b$ i $ab$ są podzielne przez $d$ ; z drugiej strony, liczba $ab+1$ jest podzielna przez liczbę
$a+b$ podzielną przez $d$ . Zatem liczby $ab$ i $ab+1$ są podzielne przez $d$ , skąd wynika, że $d = 1$ .

Niech $e$ oznacza największy wspólny dzielnik liczb $a+b$ i $a-b$ . Wówczas $e$ jest dzielnikiem sumy
i różnicy tych dwóch liczb, równych odpowiednio $2a$ i $2b$ . Skoro liczby $a$ i $b$ są względnie pierwsze,
otrzymujemy $e = 1$ lub $e = 2$ . Stąd wniosek, że jeśli liczba całkowita jest podzielna przez
$a + b$ i $a - b$ , to dwukrotność tej liczby jest podzielna przez $(a+b)(a-b)= a^2 - b^2$ .

Jak zauważyliśmy wcześniej, liczba $b^2-1$ jest podzielna przez $a+b$ i przez $a-b$ . Oznacza to,
że liczba $2(b^2-1)$ jest podzielna przez $a^2-b^2$ . Ponadto $b>1$ , a więc liczba $2(b^2 -1)$ jest
dodatnia i wobec tego jest nie mniejsza niż $a^2 -b^2$ . Zapisując nierówność
$2(b^2 - 1) \geqslant a^2 -b^2$ w równoważnej postaci $a^2 \leqslant 3b^2 - 2$
widzimy, że $a<3b^2$ , co jest równoznaczne z tezą zadania.

LX OM - II - Zadanie 3

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Rozłączne okręgi $o_1$ i $o_2$ o środkach odpowiednio $I_1$ i $I_2$ są styczne do prostej
$k$ odpowiednio w punktach $A_1$ i $A_2$ oraz leżą po tej samej jej stronie. Punkt $C$ leży na odcinku
$I_1I_2$ , przy czym $\meqsuredangle A_1CA_2 =90^{\circ}$ . Dla $i=1,2$ niech $B_i$ będzie punktem różnym od
$A_i$ , w którym prosta $A_iC$ przecina okrąg $o_i$ . Dowieść, że prosta $B_1B_2$ jest styczna do okręgów
$o_1$ i $o_2$ .

Rozwiązanie

Niech prosta styczna do okręgu $o_1$ w punkcie $B_1$ przecina prostą $A_1A_2$ w punkcie $D$ .
(Punkt przecięcia istnieje, gdyż punkt $C$ nie leży na prostej $A_1I_1$ , a więc odcinek $A_1B_1$
nie jest średnicą okręgu $o_1$ .) Trójkąt $A_1B_1D$ jest wówczas równoramienny, gdyż dwa jego boki
są odcinkami stycznych do okręgu $o_1$ poprowadzonymi z punktu $D$ . Wobec tego prosta
$DI_1$ jako dwusieczna kąta $\measuredangle A_1DB_1$ jest prostopadła do cięciwy $A_1B_1$ ,
a więc równoległa do prostej $CA_2$ .

Udowodnimy, że proste $A_1B_1$ i $DI_2$ są równoległe.

Jeżeli $A_1A_2 || I_1I_2$ , to $A_1A_2 = I_1I_2$ i czworokąt $I_1CA_2D$ jest równoległobokiem.
W takim razie $CI_2 = A_1D$ i czworokąt $CI_2DA_1$ także jest równoległobokiem. W szczególności
więc $A_1B_1 || DI_2$ .

Jeżeli natomiast proste $A_1A_2$ i $I_1I_2$ przecinają się w punkcie $E$ , to stosując dwukrotnie
twierdzenie Talesa do kąta $\measuredangle A_1EI_1$ przeciętego prostymi równoległymi $I_1D$ , $CA_2$
oraz $I_1A_1$ , $I_2A_2$ otrzymujemy

$ \frac{EC}{EI_2}= \frac{EC}{EI_1}\cdot \frac{EI_1}{EI_2} = \frac{EA_2}{ED} \cdot \frac{EA_1}{EA_2} = \frac{EA_1}{ED} $

co w połączeniu z twierdzeniem odwrotnym do twierdzenia Talesa znowu daje zależność $A_1B_1 || DI_2$ .

Wykazana właśnie równoległość wraz z danym w treści zadania warunkiem $\measuredangle A_1CA_2 = 90^{\circ}$
pozwala wnioskować, że proste $DI_2$ i $B_2A_2$ są prostopadłe. Zauważmy teraz, że prosta $DI_2$ przechodzi
przez środek okręgu $o_2$ . W efekcie punkty $B_2$ i $A_2$ są symetryczne względem prostej $DI_2$
(gdyż są końcami cięciwy prostopadłej do tej prostej) oraz proste $DB_2$ i $DA_2$ są symetryczne
względem tej prostej. Skoro zaś prosta $DA_2$ jest styczna do okręgu $o_2$ , to również prosta $DB_2$
jest doń styczna, co kończy rozwiązanie zadania.

LX OM - II - Zadanie 4

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Odcinek $AB$ jest średnicą okręgu o opisanego na czworokącie wypukłym $ABCD$ , którego przekątne
przecinają się w punkcie $E$ . Proste styczne do okręgu o w punktach $C$ i $D$ przecinają się w punkcie
$P$ .

Udowodnić, że $PC = PE$ .

Rozwiązanie

Niech $Q$ będzie punktem przecięcia prostych $AD$ i $BC$ .

Zauważmy najpierw, że na mocy warunków zadania proste $AC$ i $BD$ są wysokościami trójkąta $ABQ$ .
Zatem prosta $QE$ jest jego trzecią wysokością i wobec tego przecina prostą $AB$ w pewnym punkcie $F$
pod kątem prostym.

W trójkącie $ECQ$ kąt przy wierzchołku $C$ jest prosty, a środek $P'$ odcinka $QE$ jest środkiem
przeciwprostokątnej. Stąd uzyskujemy zależności $\measuredangle P'CQ=\measuredangle P'QC =\measuredangle FQB$ .
Ponadto trójkąty prostokątne $ACB$ i $QFB$ mają wspólny kąt ostry przy wierzchołku $B$ ,
zatem ich pozostałe kąty ostre są równe: $\measuredangle FQB = \measuredangle CAB$ .
Udowodniliśmy tym samym, że

$ \measuredangle P'CQ = \measuredangle CAB. $

To oznacza, że prosta $P'C$ jest styczna do okręgu o w punkcie $C$ .

Podobnie dowodzimy, że prosta $P'D$ jest styczna do okręgu o w punkcie $D$ .
Stąd i z określenia punktu $P$ wynika, że $P'=P$ . Innymi słowy, punkt $P$ jest środkiem przeciwprostokątnej
w trójkącie prostokątnym $ECQ$ , skąd natychmiast wynika żądana równość $PC = PE$ .

LX OM - II - Zadanie 5

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Wyznaczyć wszystkie liczby całkowite $n\geqslant 4$ o następującej własności: Spośród dowolnych $n$
różnych 3-elementowych podzbiorów zbioru $n$ -elementowego można wybrać dwa podzbiory, które mają dokładnie
jeden element wspólny.

Rozwiązanie

Niech $A_1, A_2, \cdots , A_k$ będą różnymi 3-elementowymi podzbiorami ustalonego zbioru $n$ -elementowego.
Przypuśćmy ponadto, że dowolne dwa z tych zbiorów albo są rozłączne, albo mają dokładnie dwa wspólne elementy.

Oznaczmy $\mathcal{A} = \{A_1,A_2, \cdots ,Ak\}$ i wprowadźmy następujące oznaczenie:
$X\sim Y$ wtedy i tylko wtedy, gdy przekrój $X\cap Y$ jest zbiorem niepustym (a więc mającym co najmniej
2 elementy),

dla (niekoniecznie różnych) zbiorów $X,Y \in \mathcal{A}$ .

Dla dowolnych zbiorów $X,Y,Z \in \mathcal{A}$ zachodzą następujące własności:

$X \sim X$ ;
jeżeli $X \sim Y$ , to $Y \sim X$ ;
jeżeli $X \sim Y$ oraz $Y \sim Z$ , to $X \sim Z$ .

Istotnie, własności 1) i 2) są oczywiste, a by uzasadnić własność 3), wystarczy spostrzec, że z faktu,
iż zbiory $X, Y , Z$ mają 3 elementy, a przekroje $X \cap Y$ i $Y \cap Z$ mają przynajmniej 2 elementy, wynika,
iż przekrój $X \cap Z$ jest zbiorem niepustym. Na mocy przyjętego na początku rozwiązania założenia przekrój ten
zawiera zatem przynajmniej 2 elementy, co oznacza, że $X \sim Z$ .

Własności 1)—3) dowodzą, że zbiory $A_1, A_2, \cdots , A_k$ można podzielić na parami rozłączne
klasy równoważności w taki sposób, by dowolne dwa zbiory $X, Y$ należące do tej samej klasy spełniały
relację $X \sim Y$ , natomiast dowolne dwa zbiory należące do różnych klas tej relacji nie spełniały.

Niech $\mathcal{B}_1, \mathcal{B}_2, \cdots , \mathcal{B}_m$ będą tak zadanymi klasami równoważności oraz niech
$C_i$ $(i =1,2, \cdots ,m)$ będzie sumą wszystkich zbiorów należących do klasy \mathcal{B}_i. Wówczas zbiory
$C_1, C_2, \cdots , C_m$ są parami rozłączne, bowiem zbiory należące do różnych klas są rozłączne.
Ponadto każdy z tych zbiorów zawiera przynajmniej 3 elementy, gdyż jest sumą zbiorów 3-elementowych.

Dla każdego zbioru $C_i$ rozpatrzmy następujące trzy możliwości:

Zbiór $C_i$ ma dokładnie 3 elementy.
Zbiór $C_i$ ma dokładnie 4 elementy.
Zbiór $C_i$ ma przynajmniej 5 elementów.

W przypadku 1. rodzina $\mathcal{B}_i$ składa się z jednego zbioru, mianowicie z tego zbioru
$A_j$ $(j =1,2, \cdots ,k)$ , który jest równy zbiorowi $C_i$ .

W przypadku 2. każdy zbiór należący do rodziny $\mathcal{B}_i$ jest 3-elementowym podzbiorem 4-elementowego
zbioru $C_i$ . Zatem w rodzinie tej znajdują się najwyżej 4 zbiory.

Rozpatrzmy z kolei przypadek 3.. Wybierzmy różne zbiory $X,Y \in \mathcal{B}_i$ . Są to zbiory 3-elementowe,
których przekrój $X\cap Y$ ma 2-elementy, a więc suma $X \cap Y$ jest zbiorem 4-elementowym. To oznacza, że w
rodzinie $\mathcal{B}_i$ istnieje zbiór $Z$ zawierający element, który nie należy do sumy $X \cap Y$ .
Stąd wniosek, że 2-elementowe przekroje $X \cap Y$ , $X \cap Z$ , $Y \cap Z$ muszą się pokrywać, a więc
można napisać

$ X = \{p,q,x\},\quad Y = \{p,q,y\}, \quad Z = \{p,q,z\}, $

gdzie elementy $p, q, x, y, z$ są różne. Weźmy teraz pod uwagę dowolny zbiór $S$ należący do rodziny
$\mathcal{B}_i$ i różny od zbiorów $X, Y , Z$ . Wówczas $S$ nie jest zbiorem $\{x,y,z\}$ , gdyż ten ostatni
ma dokładnie jeden element wspólny ze zbiorem $X$ . Wobec tego przynajmniej jeden z elementów $x, y, z$
nie należy do zbioru $S$ . Przyjmijmy, nie zmniejszając ogólności dalszego rozumowania, iż jest to element $x$ .
Skoro przekrój $X\cap S$ jest zbiorem 2-elementowym oraz $x \notin S$ , musimy mieć $X \cap S = \{p,q\}$ .
Ale to, wobec dowolności wyboru $S$ , oznacza, że każdy zbiór należący do rodziny $\mathcal{B}_i$
zawiera elementy $p$ i $q$ . Stąd wniosek, że liczba elementów tej rodziny nie przekracza liczby elementów zbioru
$C_i$ pomniejszonej o 2.

Udowodniliśmy w ten sposób, że każda z rodzin $\mathcal{B}_i$ zawiera najwyżej tyle zbiorów, ile jest
elementów w zbiorze $C_i$ , przy czym równość może mieć miejsce tylko wtedy, gdy zbiór $C_i$ ma 4 elementy.

Ponadto zbiory $C_1, C_2, \cdots , C_m$ są parami rozłączne, a ich suma zawiera się w ustalonym na
początku rozwiązania zbiorze $n$ -elementowym, więc suma liczb elementów tych zbiorów nie przekracza $n$ .
Tym bardziej suma liczb elementów rodzin $\mathcal{B}_1, \mathcal{B}_2, \cdots , \mathcal{B}_m$ nie przekracza
$n$ , przy czym równość jest możliwa tylko w przypadku, gdy każdy ze zbiorów $C_i$ oraz każda z rodzin
$\mathcal{B}_i$ $(i =1,2, \cdots ,m)$ ma dokładnie 4 elementy,

Jednakże każdy ze zbiorów $A_1, A_2, \cdots , A_k$ należy do dokładnie jednej z tych rodzin. Stąd wniosek,
że $k \leqslant n$ , przy czym równość może mieć miejsce tylko wtedy, gdy każda z rodzin $\mathcal{B}_i$
$(i =1, 2, \cdots ,m)$ ma dokładnie 4 elementy oraz suma ilości elementów tych rodzin jest równa $n$ .
Jest to możliwe tylko wtedy, gdy zachodzi równość $n=4m$ . Jeśli zatem istnieje układ $n$ trójelementowych
podzbiorów zbioru $n$ -elementowego, z których żadne dwa nie mają dokładnie jednego elementu wspólnego,
to liczba $n$ jest podzielna przez $4$ .

Implikacja odwrotna również jest prawdziwa: jeżeli $n =4s$ dla pewnej liczby całkowitej $s \geqslant 1$ ,
to definiujemy zbiory $A_1, A_2, \cdots , A_{4s}$ warunkami

$ \begin{split} A_{4j-3} = \{4j -2,4j -1,4j\},&\quad A_{4j-1} = \{4j -3,4j -2,4j\},\\ A_{4j-2} = \{4j -3,4j -1,4j\},&\quad A_{4j} = \{4j -3,4j -2,4j -1\} \end{split} $

dla $j =1,2, \cdots ,s$ . Wówczas dowolne dwa z określonych wyżej zbiorów albo są rozłączne, albo mają
dokładnie dwa wspólne elementy.

Odpowiedź: Liczba $n \geqslant 4$ spełnia warunki zadania wtedy i tylko wtedy, gdy nie jest
podzielna przez 4.

LX OM - II - Zadanie 6

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Dla każdej liczby całkowitej $n \geqslant 3$ wyznaczyć wszystkie ciągi liczb rzeczywistych
$(x_1,x_2, \cdots ,x_n)$ , dla których

$ \sum_{i=1}^n x_i = n \quad \text{ oraz } \sum_{i=1}^n (x_{i-1} -x_i + x_{i+1})^2 = n, $

gdzie przyjmujemy $x_0 = x_n$ i $x_{n+1} = x_1$ .

Rozwiązanie

Przypuśćmy, że ciąg $(x_1,x_2, \cdots ,x_n)$ ma żądaną własność. Przyjmijmy

$ (1) \qquad y_i = x_{i-1} -x_i + x_{i+1} -1 \quad \text{ dla } \quad i =1,2, \cdots ,n. $

Wówczas zachodzi równość $y_1 + y_2 + \cdots +y_n = x_1 + x_2 + \cdots + x_n -n$ , a zatem
z danych w treści zadania dwóch równości wynika, że

$ y_1 +y_2 + \cdots +y_n =0 \text{ oraz }(1+ y_1)^2 +(1+y_2)^2 + \cdots +(1+y_n)^2 = n, $

skąd uzyskujemy

$ \sum_{i=1}^n y_i^2 = \sum_{i=1}^n [(1+y_i)^2 -2y_i -1]= \sum_{i=1}^n (1+y_i)^2 -2\sum_{i=1}^n y_i - \sum_{i=1}^n 1= n-0-n =0. $

Zatem $y_1 = y_2 = \cdots = y_n = 0$ , co z uwagi na wzór (1) daje

$ (2) \qquad x_i-1 -x_i + x_i+1 = 1 \text{ dla } i =1,2, \cdots ,n. $

Na odwrót, każdy ciąg $(x_1,x_2, \cdots ,x_n)$ spełniający warunek (2) spełnia także równości dane w zadaniu.
Pozostaje więc wyznaczyć wszystkie ciągi, dla których zachodzi warunek (2).

Oznaczmy $x_0 = a$ oraz $x_1 = b$ . Wówczas stosując zależność (2) w postaci
$x_{i+1} =1 -x_i-1 + x_i$ dla $i =1,2, 3,4,5,6$ otrzymujemy

$ x_2 =1 -a+b,\; x_3 =2-a,\; x_4 =2-b,\; x_5 =1+a-b,\; x_6 = a,\; x_7 = b. $

Kontynuując to postępowanie stwierdzamy, że ciąg $x_0, x_1, x_2, \cdots$ jest okresowy:
$x_{k+6} =x_k$ dla $k =0,1,2, \cdots$ . Ponieważ $x_0 = x_n$ oraz $x_1 =x_{n+1}$ , więc para
$(x_0,x_1)$ pokrywa się z parą $(x_r,x_{r+1})$ , gdzie $r$ jest resztą z dzielenia liczby $n$ przez 6.

Korzystając z wyliczonych wyżej wartości $x_0, x_1, x_2, x_3, x_4, x_5, x_6$ sprawdzamy bezpośrednio,
że dla dowolnej wartości $r =1,2,3,4,5$ jedynym rozwiązaniem układu równań
$x_0 = x_r, x_1 = x_{r+1}$ , czyli odpowiednio układów

$ \begin{cases} a=b\\ b=1-a+b \end{cases}, \begin{cases} a=1-a+b\\ b=2-a \end{cases}, \begin{cases} a=2-a\\ b=2-b \end{cases}, \begin{cases} a=2-b\\ b=1+a-b \end{cases}, \begin{cases} a=1+a-b\\ b=a \end{cases}, $

są liczby $a = b = 1$ . W tej sytuacji oczywiście $x_1 = x_2 = \cdots = x_n = 1$ i liczby te mają
żądane w treści zadania własności.

Jeżeli natomiast $r = 0$ , a więc gdy liczba $n$ jest podzielna przez 6, to możemy wybrać dowolne
wartości rzeczywiste $x_0 = x_n$ i $x_1$ i korzystając ze wzoru (2) wyznaczyć jednoznacznie wartości
$x_2, x3, \cdots , x_{n+1}$ . Nietrudno spostrzec, że warunek (2) będzie wówczas spełniony.

Odpowiedź: Dla każdej liczby całkowitej $n \geqslant 3$ rozwiązaniem zadania jest ciąg
$(x_1,x_2, \cdots ,x_n) = (1,1, \cdots ,1)$ ; ponadto dla liczb $n$ podzielnych przez 6 istnieją rozwiązania
o okresie długości 6 następującej postaci:

$ (x_1,x_2, \cdots ,x_n)=(b,1 -a +b,2-a,2-b,1+ a-b,a,b,1-a+b, \cdots ,a). $