LII Olimpiada Matematyczna

Rozwiązania zadań konkursowych zawodów stopnia trzeciego

2 kwietnia 2001 r. (pierwszy dzień zawodów)

Zadanie 1.

Dowieść, że dla każdej liczby naturalnej n 2 i dowolnych liczb rzeczywistych nieujemnych x_{1},x_{2},...,x_{n} zachodzi nierówność

∑_{i=1}^{n} ix_{i} ( \begin{matrix}n \\ 2 \end{matrix}) +∑_{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} = ...= y_{i} = 1 (2 i n)

otrzymujemy

x_{i} = ^{i} \sqrt{y_{1}y_{2}y_{3}...y_{i}} \frac{y_{1}+y_{2}+y_{3}+...+y_{i}}{i} = \frac{x_{i}^{i} +(i−1)}{i} .

Zatem

∑_{i=1}^{n} ix_{i} ∑_{i=1}^{n} (i−1)+∑_{i=1}^{n} x_{i}^{i}, czyli ∑_{i=1}^{n} ix_{i} ( \begin{matrix}n \\ 2 \end{matrix}) +∑_{i=1}^{n} x_{i}^{i} .

Uwaga

W nierówności (1) równość zachodzi wtedy i tylko wtedy, gdy wszystkie liczby y_{1},y_{2},...,y_{i} są równe. Zatem w danej w zadaniu nierówności równość zachodzi tylko przy x_{2} = x_{3} = ...= x_{n} = 1.

Zadanie 2.

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 C_{i} będzie czworościanem, którego jedną ścianą jest ta ściana czworościanu A_{1}A_{2}A_{3}A_{4}, która zawiera punkt B_{i}, zaś przeciwległym wierzchołkiem punkt P. Wtedy

∑_{i=1}^{4} \frac{P B_{i}}{A_{i}B_{i}} = ∑_{i=1}^{4} \frac{V (C_{i})}{V (A_{1}A_{2}A_{3}A_{4})}= 1,  skąd  ∑_{i=1}^{4} \frac{A_{i}P}{A_{i}B_{i}} = 3.

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

Zadanie 3.

Rozważamy ciąg (x_{n}) określony rekurencyjnie wzorami

x_{1} = a, x_{2} = b oraz x_{n+2} = x_{n+1} +x_{n} dla n = 1,2,3,... , 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} dla n = 1,2,3,... .

Niech dodatkowo F_{0} = 0 oraz F_{−n} = (−1)^{n+1} F_{n} dla n = 1,2,3,.... 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,...,4001 uzyskujemy x_{n} = F_{n−4002} = F_{4002−n} = x_{8004−n} . Stąd wynika, że liczby F_{1},F_{3},F_{5},...,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} dla n = 1,2,3,...

istnieją takie liczby rzeczywiste A i B, że

x_{n} = Aα^{n} +Bβ^{n} dla n = 1,2,3,...,

gdzie α = \frac{1}{2}(1+ \sqrt{5}), β = \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 ≠ 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 ≠ 0, to

lim_{n→∞} x_{n} = \{ \begin{matrix}+∞ & gdy A > 0 , \\ −∞ & gdy A < 0 . \end{matrix}

Zatem istnieje taka liczba naturalna N, że dla wszystkich n N, x_{n} ≠ 0. Ponadto

\frac{x_{n+1}}{x_{n}} = \frac{Aα^{n+1} +Bβ^{n+1}}{Aα^{n} +Bβ^{n}} = \frac{Aα+Bβ( \frac{β}{α} ) ^{n}}{A+B( \frac{β}{α} ) ^{n}} (n N),

a zatem lim_{n→∞} \frac{x_{n+1}}{x_{n}} = α > 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 Olimpiada Matematyczna

Rozwiązania zadań konkursowych zawodów stopnia trzeciego

3 kwietnia 2001 r. (drugi dzień zawodów)

Zadanie 4.

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

Rozwiązanie

Jeżeli b = 0, to a = 0, gdyż dla a ≠ 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 0 oraz b ≠ 0.

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

2^{2k}a+b 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} oraz 2^{2k}a+4b = y_{k}^{2} .

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

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

Zatem ciąg (x_{k}) jest ograniczony, co jest możliwe tylko wtedy, gdy a = 0.

Zadanie 5.

Punkty K i L leżą odpowiednio na bokach BC i CD równoległoboku ABCD, przy czym BK ·AD = DL·AB. Odcinki DK i BL przecinają się w punkcie P. Wykazać, że < ) DAP = < ) 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} .

A  B  C D  X Y L  K Prys. 1  A  B  C D  X  Y L K P rys. 2

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.

Zadanie 6.

Dane są liczby całkowite dodatnie n_{1} < n_{2} < ...< n_{2000} < 10^{100}. Dowieść, że ze zbioru {n_{1},n_{2},...,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 ⊆ {n_{1},n_{2},...,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},...,n_{2000}}, dla których s_{i}(C) = s_{i}(D) dla i = 0,1,2. Wówczas zbiory A = C \D oraz B = D \C są niepuste i spełniają warunki zadania.

Dla dowolnego podzbioru X zbioru {n_{1},n_{2},...,n_{2000}} mamy

(1) s_{0}(X) < 10^{4}, s_{1}(X) < 2000·10^{100} < 10^{104}, s_{2}(X) < 2000·10^{200} < 10^{204}.

Oznaczając S(X) = s_{0}(X)+10^{4}s_{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},...,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.

(wp, jwr)

∗  ∗  ∗

Zadania z poprzednich Olimpiad Matematycznych oraz bieżące informacje można znaleźć w internecie pod adresem:

www.impan.gov.pl/˜ olimp/