LII OM - III etap

III etap LII Olimpiady Matematycznej

Załącznik	Wielkość
LII OM III etap - Zadania [1]	78.81 KB
LII OM III etap - Zadania z rozwiązaniami [2]	175.32 KB

LII OM - III - Zadanie 1

Zawody matematyczne:

LII OM, 2000-2001

Etap:

III

Dowieść, że dla każdej liczby naturalnej $n \geq 2$ i dowolnych liczb rzeczywistych nieujemnych $x_1,x_2,\ldots,x_n$ zachodzi nierówność

$ \sum_{i=1}^{n}ix_{i}\leq{n \choose 2}+\sum_{i=1}^{n}x_{i}^{i}. $

Rozwiązanie

Z nierówności między średnią geometryczną i średnią arytmetyczną zastosowanej do liczb

$ y_{1}=x_{i}^{i},\ y_{2}=y_{3}=\ldots=y_{i}=1\ (2\leq i\leq n) $

otrzymujemy

$ x_{i}=\sqrt[i]{y_{1}y_{2}y_{3}\ldots y_{i}}\leq\frac{y_{1}+y_{2}+y_{3}+\ldots+y_{i}}{i}=\frac{x_{i}^{i}+(i-1)}{i}. $

Zatem

$ \sum_{i=1}^{n}ix_{i}\leq\sum_{i=1}^{n}(i-1)+\sum_{i=1}^{n}x_{i}^{i},\ \textrm{czyli}\ \sum_{i=1}^{n}ix_{i}\leq{n \choose 2}+\sum_{i=1}^{n}x_{i}^{i}. $

LII OM - III - Zadanie 2

Zawody matematyczne:

LII OM, 2000-2001

Etap:

III

Dowieść, że suma odległości dowolnego punktu leżącego wewnątrz czworościanu foremnego o krawędzi $1$ od jego wierzchołków jest nie większa niż $3$ .

Rozwiązanie

Niech $A_1 A_2 A_3 A_4$ będzie danym czworościanem, a $P$ dowolnym punktem w jego wnętrzu. Załóżmy, że prosta $A_i P$ przecina przeciwległą ścianę czworościanu $A_1 A_2 A_3 A_4$ w punkcie $B_i$ . Niech $\mathcal{C}_i$ będzie czworościanem, którego jedną ścianą jest ta ściana czworościanu $A_1 A_2A_3A_4$ , która zawiera punkt $B_i$ , zaś przeciwległym wierzchołkiem punkt $P$ . Wtedy

$ \sum_{i=1}^{4}\frac{PB_{i}}{A_{i}B_{i}}=\sum_{i=1}^{4}\frac{V(\mathcal{C}_{i})}{V(A_{1}A_{2}A_{3}A_{4})}=1, \quad \textrm{stąd} \quad \sum_{i=1}^{4}\frac{A_{i}P}{A_{i}B_{i}}=3. $

( $V(\mathcal{T})$ oznacza objętość czworościanu $\mathcal{T}$ .) Z nierówności $A_iB_i < 1$ oraz z powyższej zależności wynika teza.

LII OM - III - Zadanie 3

Zawody matematyczne:

LII OM, 2000-2001

Etap:

III

Rozważamy ciąg $(x_n)$ określony rekurencyjnie wzorami

$ x_{1}=a,\ x_{2}=b\ \textrm{oraz}\ x_{n+2}=x_{n+1}+x_{n}\ \textrm{dla}\ n=1,2,3,\ldots, $

gdzie $a$ i $b$ są liczbami rzeczywistymi.

Liczbę $c$ będziemy nazywać wartością wielokrotną ciągu $(x_n)$ , jeżeli istnieją co najmniej dwie różne liczby całkowite dodatnie $k$ i $l$ takie, że $x_k = x_l = c$ . Wykazać, że można tak dobrać liczby $a$ i $b$ , aby ciąg $(x_n)$ miał więcej niż $2000$ wartości wielokrotnych, ale nie można tak dobrać $a$ i $b$ , aby miał on nieskończenie wiele wartości wielokrotnych.

Rozwiązanie

Ciąg $(x_n)$ spełnia taką samą rekurencję, jak ciąg Fibonacciego

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

Niech dodatkowo $F_0 = 0$ oraz $F_{-n} = (-1)^{n+1}F_n$ dla $n = 1,2,3,\ldots$ . Wówczas równość $F_{n+2} = F_{n+1} + F_n$ zachodzi dla dowolnej liczby całkowitej $n$ .

Przyjmijmy $a = F_{-4001}$ oraz $b = F_{-4000}$ . Wtedy $x_n = F_{n-4002}$ . Ponadto dla $n = 1,3,5,7,\ldots,4001$ uzyskujemy $x_n = F_{n-4002} = F_{4002-n} = x_{8004-n}$ . Stąd wynika, że liczby $F_1,F_3,F_5,\ldots,F_{4001}$ są wartościami wielokrotnymi ciągu $(x_n)$ ; są one różne i jest ich więcej niż $2000$ .

Dla dowolnego ciągu $(x_n)$ spełniającego warunek

$ x_{n+2} = x_{n+1} + x_n \ \textrm{dla}\ n = 1,2,3,\ldots $

istnieją takie liczby rzeczywiste $A$ i $B$ , że

$ x_{n}=A\alpha^{n}+B\beta^{n}\text{ }dla\text{ }n=1,2,3,\ldots, $

gdzie $\alpha=\frac{1}{2}(1+\sqrt{5})$ , $\beta=\frac{1}{2}(1-\sqrt{5})$ są pierwiastkami wielomianu $x^2-x - 1$ .

Jeżeli $A = B = 0$ , to wszystkie wyrazy ciągu $(x_n)$ są zerami i liczba $0$ jest jedyną wartością wielokrotną ciągu $(x_n)$ .

Jeżeli $A = 0$ oraz $B \neq 0$ , to wszystkie wyrazy ciągu $(x_n)$ są różne i ciąg $(x_n)$ nie ma wartości wielokrotnych.

Jeżeli natomiast $A \ne 0$ , to

$ \lim_{n\to \infty} x_n=\left\{\begin{array}{ll} +\infty&\textrm{gdy}\ A>0,\\ -\infty&\textrm{gdy}\ A<0. \end{array}\right. $

Zatem istnieje taka liczba naturalna $N$ , że dla wszystkich $n \geq N$ , $x_n \ne 0$ . Ponadto

$ \frac{x_{n+1}}{x_{n}}=\frac{A\alpha^{n+1}+B\beta^{n+1}}{A\alpha^{n}+B\beta^{n}}=\frac{A\alpha+B\beta(\frac{\beta}{\alpha})^{n}}{A+B(\frac{\beta}{\alpha})^{n}}\ (n\geq N), $

a zatem $\lim_{n\to \infty} \frac{x_{n+1}}{x_n} =\alpha>1$ .

Stąd wynika, że ciąg $(x_n)$ od pewnego miejsca jest rosnący i w związku z tym nie może mieć nieskończenie wielu wartości wielokrotnych.

LII OM - III - Zadanie 4

Zawody matematyczne:

LII OM, 2000-2001

Etap:

III

Dane są takie liczby całkowite $a$ i $b$ , że dla każdej liczby całkowitej nieujemnej $n$ liczba $2^na + b$ jest kwadratem liczby całkowitej. Dowieść, że $a = 0$ .

Rozwiązanie

Jeżeli $b = 0$ , to $a = 0$ , gdyż dla $a \ne 0$ liczby $a$ i $2a$ nie mogą być jednocześnie kwadratami liczb całkowitych.

Gdyby liczba $a$ była ujemna, to dla pewnej, dużej liczby naturalnej $n$ , liczba $2^n a + b$ też byłaby ujemna, nie mogłaby więc być kwadratem liczby całkowitej.

Pozostaje do rozpatrzenia przypadek, gdy $a \geq 0$ oraz $b \neq 0$ .

Dla każdej liczby całkowitej dodatniej $k$ , liczby

$ 2^{2k} a + b \ \textrm{oraz}\ 4(2^{2k-2} a + b) = 2^{2k} a + 4b $

są kwadratami różnych liczb całkowitych nieujemnych, powiedzmy

$ 2^{2k}a+b=x_{k}^{2}\ \textrm{oraz}\ 2^{2k}a+4b=y_{k}^{2}. $

Wówczas $x_{k}+y_{k}\leq(x_{k}+y_{k})|x_{k}-y_{k}|=|x_{k}^{2}-y_{k}^{2}|=|3b|$ , skąd

$ 2^{2k}a+b=x_{k}^{2}\leq(x_{k}+y_{k})^{2}\leq 9b^{2}\ \textrm{dla każdego $k$.} $

Zatem ciąg $(x_k)$ jest ograniczony, co jest możliwe tylko wtedy, gdy $a = 0$ .

LII OM - III - Zadanie 5

Zawody matematyczne:

LII OM, 2000-2001

Etap:

III

Punkty $K$ i $L$ leżą odpowiednio na bokach $BC$ i $CD$ równoległoboku $ABCD$ , przy czym $BK \cdot AD = DL \cdot AB$ . Odcinki $DK$ i $BL$ przecinają się w punkcie P. Wykazać, że $\measuredangle DAP = \measuredangle BAC$ .

Rozwiązanie

Niech $Y$ będzie punktem przecięcia prostych $AP$ i $CD$ oraz niech $X$ będzie punktem przecięcia prostych $DK$ i $AB$ (rys. $1$ i $2$ ). Wówczas

$ \frac{DL}{DY}=\frac{BX}{AX}=\frac{BK}{AD}. $

Stąd oraz z równości danej w treści zadania otrzymujemy:

$ \frac{DY}{AD}=\frac{DL}{BK}=\frac{AD}{AB}=\frac{BC}{AB}. $

To dowodzi, że trójkąty $ABC$ i $ADY$ są podobne, skąd wynika teza.

LII OM - III - Zadanie 6

Zawody matematyczne:

LII OM, 2000-2001

Etap:

III

Dane są liczby całkowite dodatnie $n_1 <n_2 < \ldots <n_{2000} < 10^{100}$ . Dowieść, że ze zbioru $\{n_1,n_2,\ldots,n_{2000}\}$ można wybrać niepuste rozłączne podzbiory $A$ i $B$ mające tyle samo elementów, taką samą sumę elementów i taką samą sumę kwadratów elementów.

Rozwiązanie

Dla zbioru $X \subseteq \{n_1,n_2,\ldots,n_{2000}\}$ niech $s_0(X)$ , $s_1(X)$ i $s_2(X)$ oznaczają odpowiednio liczbę elementów, sumę elementów i sumę kwadratów elementów zbioru $X$ .

Wystarczy udowodnić, że istnieją takie dwa różne podzbiory $C$ i $D$ zbioru $\{n_1,n_2,\ldots,n_{2000}\}$ , dla których $s_i(C) = s_i(D)$ dla $i = 0,1,2$ . Wówczas zbiory $A = C \setminus D$ oraz $B = D\setminus C$ są niepuste i spełniają warunki zadania.

Dla dowolnego podzbioru $X$ zbioru $\{n_1 , n_2, \ldots ,n_{2000}\}$ mamy

$ (1) \qquad s_0(X) < 10^4,\ s_1(X) < 2000 \cdot 10^{100} < 10^{104}, s_2(X) < 2000\cdot 10^{200} < 10^{204}. $

Oznaczając $S(X) = s_0(X) + 10^4s_1(X) + 10^{108}s_2(X)$ uzyskujemy

$ S(X) < 10^{313} < (10^3)^{105} < 2^{1050} < 2^{2000} . $

Stąd istnieją takie dwa różne podzbiory $C$ , $D$ zbioru $\{n_1 , n_2, \ldots ,n_{2000}\}$ , że $S(C) = S(D)$ . Z nierówności (1) wynika, że $s_i(C) = s_i(D)$ dla $i = 0, 1, 2$ , co kończy rozwiązanie zadania.