LII OLIMPIADA MATEMATYCZNA

Do Pani/Pana Dyrektora Szkoły Do Pani/Pana Profesora Matematyki

Komitet Główny Olimpiady Matematycznej uprzejmie prosi o zapoznanie uczniów i nauczycieli zainteresowanych zadaniami Olimpiady z podanymi tu rozwiązaniami zadań konkursowych stopnia pierwszego LII Olimpiady Matematycznej.

W dalszej części niniejszego druku podajemy teksty zadań z zawodów międzynarodowych: XLI Międzynarodowej Olimpiady Matematycznej i XXIII Austriacko–Polskich Zawodów Matematycznych, a także z XI Zawodów Matematycznych Państw Bałtyckich (Baltic Way 2000).

Zawody pierwszego stopnia LII Olimpiady Matematycznej są zakończone. Zawody stopnia drugiego odbędą się w dniach 23 i 24 lutego 2001 r. Zawody stopnia trzeciego odbędą się w dniach 2 i 3 kwietnia 2001 r.

Zawiadomienia o dokładnym terminie i miejscu zawodów stopnia drugiego wyślą komitety okręgowe zakwalifikowanym zawodnikom w terminie do dnia 10 lutego 2001 r.

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

www.impan.gov.pl/˜ olimp/

Komitet Główny Olimpiady Matematycznej

Rozwiązania zadań konkursowych

zawodów stopnia pierwszego LII Olimpiady Matematycznej^{1}

Zadanie 1.

Rozwiązać w liczbach całkowitych równanie

x^{2000} +2000^{1999} = x^{1999} +2000^{2000} .

Rozwiązanie

Dane równanie sprowadzamy do postaci f(x) = f(2000), gdzie

f(x) = x^{2000} −x^{1999} = (x−1)x^{1999}.

Ponieważ f jest funkcją rosnącą na przedziale ⟨1,∞), więc dane równanie ma w tym przedziale tylko jedno rozwiązanie, którym jest x = 2000. Na zbiorze (−∞,0⟩ funkcja f jest malejąca, więc istnieje co najwyżej jedna liczba całkowita ujemna a, dla której f(a) = f(2000). Jednakże

f(−1999) = 2000·1999^{1999} < 1999·2000^{1999} = f(2000) = f(a) oraz

f(−2000) = 2001·2000^{1999} > 1999·2000^{1999} = f(2000) = f(a) .

Zatem a ∈ (−2000,−1999), co przeczy temu, że a jest liczbą całkowitą. Odpowiedź: Dane równanie ma jedno rozwiązanie w liczbach całkowitych: x = 2000.

Zadanie 2.

Punkty D i E leżą odpowiednio na bokach BC i AC trójkąta ABC. Odcinki AD i BE przecinają się w punkcie P. Punkty K i L leżą odpowiednio na bokach BC i AC, przy czym czworokąt CLP K jest równoległobokiem. Dowieść, że

\frac{AE}{EL} = \frac{BD}{DK} .

Rozwiązanie

Ponieważ KD ∥ LP, DP ∥ P A oraz P K ∥ AL, więc trójkąty KDP i LP A są podobne (rys. 1). Zatem

\frac{DK}{P L} = \frac{P K}{AL} ,  czyli  AL·DK = P K ·P L.

Analogicznie, korzystając z podobieństwa trójkątów LEP i KP B dowodzimy, że BK ·EL = P L·P K. Na mocy dwóch ostatnich równości otrzymujemy

AL·DK = BK ·EL,  czyli  \frac{AL}{EL} = \frac{BK}{DK} . A  B C P K L  D E  rys. 1

Stąd

\frac{AE +EL}{EL} = \frac{BD +DK}{DK} ,  a więc  \frac{AE}{EL} = \frac{BD}{DK} .

1Opracowali Waldemar Pompe i Jarosław Wróblewski.

Zadanie 3.

Znaleźć wszystkie takie liczby naturalne n 2, że nierówność

(1)  x_{1}x_{2} +x_{2}x_{3} +...+x_{n−1} x_{n} \frac{n−1}{n} (x_{1}^{2} +x_{2}^{2} +...+x_{n}^{2})

zachodzi dla dowolnych liczb rzeczywistych dodatnich x_{1},x_{2},...,x_{n}.

Rozwiązanie Odpowiedź: Jedyną liczbą spełniającą warunki zadania jest n = 2. Dla n = 2 dana nierówność przyjmuje postać

x_{1}x_{2} \frac{1}{2}(x_{1}^{2}+x_{2}^{2}), co sprowadza się do 0 \frac{1}{2}(x_{1}−x_{2})^{2} . Zatem liczba n = 2 spełnia warunki zadania.

Jeśli n 3, to nierówność (1) nie jest prawdziwa dla dowolnych liczb rzeczywistych dodatnich. Liczby

(2)  x_{1} = 3, x_{2} = x_{3} = ...= x_{n−1} = 4, x_{n} = 3

stanowią kontrprzykład. Istotnie: wstawiając powyższe wartości do nierówności (1) uzyskujemy

12+\underbrace{16+16+...+16}_{n−3}+12 \frac{n−1}{n} (9+\underbrace{16+16+...+16}_{n−2}+9).

Przekształcając równoważnie powyższą nierówność otrzymujemy 3n 7, co nie jest prawdą, gdy n 3.

Zadanie 4.

Rozstrzygnąć, czy w sześciennym pudełku o krawędzi 4 można umieścić 65 kul o średnicy 1.

Rozwiązanie Odpowiedź: Można. Sposób umieszczenia kul jest następujący. Na dnie pudełka umieszczamy warstwę złożoną z 16 kul. Następnie kła-

dziemy warstwę złożoną z 9 kul, z których każda jest styczna do czterech kul pierwszej warstwy (rys. 1 i 2). Trzecia warstwa składa się z 16 kul stycznych do kul drugiej warstwy (rys. 4 i 5). Podobnie umieszczamy dwie następne warstwy (rys. 6).

rys. 1 (widok z góry)  rys. 2 (widok z boku)  1 1 rys. 3  1

Łącznie umieściliśmy więc 16+9+16+9+16 = 66 kul. Pozostaje obliczyć, jak wysoko sięga piąta warstwa.

rys. 4 (widok z góry)  rys. 5 (widok z boku)  rys. 6 (widok z boku)

Wybierzmy dowolną kulę drugiej warstwy; kula ta jest styczna do czterech kul pierwszej warstwy. Środki tych pięciu kul są wierzchołkami ostrosłupa prawidłowego czworokątnego, którego każda krawędź ma długość 1 (rys. 3). Na mocy twierdzenia Pitagorasa wysokość tego ostrosłupa wynosi \frac{\sqrt{2}}{2}. Stąd wynika, że najwyższy punkt, do którego sięga piąta warstwa, jest odległy od płaszczyzny podstawy o \frac{1}{2} +4·\frac{\sqrt{2}}{2} + \frac{1}{2} = 1+2\sqrt{2}< 4. Umieszczone w ten sposób 66 kul mieści się w sześciennym pudełku o krawędzi 4.

Zadanie 5.

Dowieść, że dla dowolnej liczby naturalnej n 2 i dowolnej liczby pierwszej p liczba n^{p^{p}} +p^{p} jest złożona.

Rozwiązanie Jeżeli p jest liczbą pierwszą nieparzystą, to na mocy tożsamości

(1)  x^{p}+y^{p}= (x+y)(x^{p−1} −x^{p−2} y +x^{p−3} y^{2}−...−xy^{p−2} +y^{p−1} ) ,

w której kładziemy x = n^{p^{p−1}} i y = p, liczba n^{p^{p}} +p^{p} jest złożona. (Dla powyższych wartości x, y zachodzą nierówności x^{p}+y^{p}> x+y > 1, więc każdy z czynników stojących po prawej stronie wzoru (1) jest większy od 1).

Natomiast dla p = 2 otrzymujemy n^{4}+4 = (n^{2}+2n+2)(n^{2}−2n+2). Ponieważ n 2, więc oba czynniki są większe od 1. Stąd wynika, że dla n 2 liczba n^{4}+4 jest złożona.

Zadanie 6.

Liczby całkowite a, b, x, y spełniają równanie

a+b\sqrt{2001}= ( x+y\sqrt{2001}) ^{2000} .

Udowodnić, że a 44b.

Rozwiązanie Wykażemy najpierw, że zachodzi następująca równość:

(1)  a−b\sqrt{2001}= (x−y\sqrt{2001}) ^{2000} .

Istotnie: ze wzoru dwumianowego Newtona otrzymujemy

(x+y\sqrt{2001}) ^{2000} = ∑_{k=0}^{2000}( \begin{matrix}2000 \\ k \end{matrix}) y^{k}2001^{k/2}x^{2000−k} = c+d\sqrt{2001},

gdzie liczby całkowite c, d są dane przez:

(2) c = ∑_{ℓ=0}^{1000}( \begin{matrix}2000 \\ 2ℓ \end{matrix}) y^{2ℓ}2001^{ℓ}x^{2000−2ℓ} , d = ∑_{ℓ=0}^{999} ( \begin{matrix}2000 \\ 2ℓ+1 \end{matrix} ) y^{2ℓ+1} 2001^{ℓ}x^{1999−2ℓ} .

Korzystając z danej w treści zadania równości uzyskujemy

(a−c)+(b−d)\sqrt{2001}= 0.

Z niewymierności liczby \sqrt{2001} wynika, że b = d, co z kolei pociąga za sobą a = c. Zatem na mocy związków (2) otrzymujemy

a−b\sqrt{2001} = c−d\sqrt{2001}=
= ∑_{k=0}^{2000}( \begin{matrix}2000 \\ k \end{matrix}) (−y)^{k}2001^{k/2}x^{2000−k} = (x−y\sqrt{2001}) ^{2000} ,

co dowodzi równości (1).

Z zależności (1) wynika, że a b\sqrt{2001}. Ponadto

2a = (x+y\sqrt{2001}) ^{2000} +(x−y\sqrt{2001}) ^{2000} 0.

Jeżeli b < 0, to nierówność podana w tezie zadania jest spełniona, gdyż a 0. Jeśli zaś b 0, to

a b\sqrt{2001} 44b.

Zadanie 7.

Dany jest trójkąt równoramienny ABC o kącie prostym przy wierzchołku A. Punkty D i E leżą na przeciwprostokątnej BC, przy czym < ) DAE = 45^{∘}. Okrąg opisany na trójkącie ADE przecina boki AB i AC odpowiednio w punktach P i Q. Dowieść, że BP +CQ = P Q .

Rozwiązanie

Punkty A, P, E, D leżą na jednym okręgu, więc < ) ADE = < ) BP E (rys. 1). Ponadto < ) DAE = 45^{∘} = < ) P BE. Z powyższych równości wynika, że trójkąty ADE i BP E są podobne, skąd w szczególności

(1)  < ) AED = < ) BEP .

Analogicznie dowodzimy, że

(2)  < ) ADE = < ) CDQ.

Niech A′, P′, Q′będą odpowiednio punktami symetrycznymi do A, P, Q względem prostej BC. Na mocy równości (1) punkty A, E, P′są współliniowe; z równości (2) wynika, że punkty A, D, Q′ są współliniowe.

A  B C  D  E P Q  A′ P′ Q′ rys. 1

Pozostaje wykazać, że BP′+CQ′= P′Q′, przy założeniu, że punkty P′ i Q′leżą odpowiednio na bokach BA′i CA′kwadratu ABA′C oraz spełniony jest warunek < ) P′AQ′= 45^{∘} (rys. 2).

Niech K będzie punktem symetrycznym do punktu B względem prostej AP′. Wówczas

(3) AC = AK  oraz  < ) AKP′= 90^{∘}.

Ponadto

< ) CAQ′= 45^{∘}−< ) P′AB =
= 45^{∘}−< ) P′AK = < ) KAQ′.

Z ostatniej zależności oraz z pierwszej równości (3) wynika, że trójkąty CAQ′ i KAQ′ są przystające (cecha bok-kąt-bok).

A  B C  A′ P′ Q′  K rys. 2

Zatem < ) AKQ′= 90^{∘}, co w połączeniu z drugą równością (3) dowodzi, że punkty P′, K, Q′ leżą na jednej prostej. Stąd BP′+CQ′= KP′+KQ′= = P′Q′, co należało wykazać.

Zadanie 8.

Rozstrzygnąć, dla jakich par liczb naturalnych m i n prostokąt o bokach długości m i n można pociąć na części przystające do figury na rysunku. Każdy z czterech kwadratów na rysunku ma bok długości 1.

Rozwiązanie

Odpowiedź: Żądany podział jest możliwy wtedy i tylko wtedy, gdy m,n > 1 oraz iloczyn mn jest podzielny przez 8.

Załóżmy najpierw, że udało nam się pociąć prostokąt m×n na części przystające do danej figury (które w dalszej części rozwiązania będziemy nazywać klockami). Oczywiście m,n > 1. Wykażemy, że 8|mn.

Każdy klocek składa się z czterech kwadratów jednostkowych, zatem iloczyn mn (pole prostokąta) musi być liczbą podzielną przez 4. Stąd w szczególności wynika, że długość jednego z boków prostokąta m×n jest liczbą parzystą. Przyjmijmy więc, bez straty ogólności, że szerokość prostokąta, np. wielkość m, jest parzysta.

Podzielmy dany prostokąt na mn kwadratów jednostkowych (które będziemy dalej nazywać kratkami). Wówczas prostokąt składa się z m (a więc parzystej liczby) kolumn, z których każda zawiera n kratek (rys. 1).

rys. 1  [figure: rys. 2]

Pomalujmy kolumny prostokąta na przemian na czarno i biało (rys. 2). Każdy klocek wycięty z tak pomalowanego prostokąta zawiera trzy kratki jednego koloru i jedną kratkę drugiego koloru. Ponieważ liczba kratek białych danego prostokąta jest równa liczbie kratek czarnych, więc klocków zawierających trzy kratki białe musi być tyle samo, co klocków zawierających trzy kratki czarne. Liczba klocków, na które składa się cały prostokąt, jest więc parzysta, co oznacza, że iloczyn mn jest podzielny przez 8.

Załóżmy teraz, że m,n > 1 oraz 8|mn. Wykażemy, że prostokąt m×n da się pociąć na klocki.

Zauważmy, że prostokąty 4×2 oraz 8×3 da się pociąć na klocki (rys. 3, 4). Zatem wystarczy wykazać, że prostokąt m×n da się pociąć na prostokąty 4×2 oraz 8×3.

rys. 3  rys. 4

Jeśli jedna z liczb m, n jest podzielna przez 4, a druga parzysta, to prostokąt m×n da się pociąć na prostokąty 4×2 (rys. 5), bez konieczności używania prostokątów 8×3.

rys. 5  rys. 6

Pozostał do rozpatrzenia przypadek, w którym jedna z liczb m, n jest podzielna przez 8 (bez straty ogólności przyjmijmy, że jest nią m), zaś druga (czyli n) jest nieparzysta i nie mniejsza niż 3. Prostokąt m×n dzielimy wówczas na dwa prostokąty m×(n− 3) i m×3, z których pierwszy dzielimy na prostokąty 4×2, a drugi na prostokąty 8×3 (rys. 6). Zatem również i w tym przypadku żądany podział jest możliwy.

Zadanie 9.

Dowieść, że wśród dowolnych 12 kolejnych liczb całkowitych dodatnich istnieje liczba nie będąca sumą 10 czwartych potęg liczb całkowitych.

Rozwiązanie

Liczba będąca czwartą potęgą liczby całkowitej daje z dzielenia przez 16 resztę 0 lub 1. Istotnie: dla liczb parzystych postaci 2k mamy (2k)^{4} = 16k^{4}, natomiast dla liczb nieparzystych 2k +1 uzyskujemy

(2k +1)^{4} = 16(k^{4}+2k^{3}+ \frac{1}{2}k(3k+ 1)) +1.

(Liczba \frac{1}{2}k(3k+ 1) jest całkowita dla dowolnej liczby całkowitej k).

Stąd wynika, że liczba, która jest sumą 10 czwartych potęg liczb całkowitych, daje z dzielenia przez 16 jedną z jedenastu reszt: 0,1,2,3,...,10. Wśród 12 kolejnych liczb całkowitych żadne dwie nie dają tej samej reszty z dzielenia przez 16. Zatem któraś z tych 12 liczb nie daje z dzielenia przez 16 reszty ze zbioru {0,1,2,3,...,10}. Ta liczba nie może być więc sumą 10 czwartych potęg liczb całkowitych.

Zadanie 10.

Dowieść, że wewnątrz dowolnego trójkąta ABC istnieje punkt P o następującej własności: Każda prosta przechodząca przez punkt P dzieli obwód trójkąta ABC w takim samym stosunku, w jakim dzieli ona jego pole.

Rozwiązanie

Wykażemy, że własność opisaną w treści zadania ma środek okręgu wpisanego.

Niech ℓ będzie dowolną prostą przechodzącą przez punkt P będący środkiem okręgu wpisanego w trójkąt ABC (rys. 1). Bez straty ogólności przyjmijmy, że prosta ℓ przecina boki AC i BC odpowiednio w punktach D i E. Należy wykazać, że

(1) \frac{[ABED]}{[DEC]} = \frac{DA+AB +BE}{EC +CD} ,
A  B C P D  E r r r  ℓ rys. 1

gdzie [F] jest polem figury F. Oznaczając przez r promień okręgu wpisanego w trójkąt ABC otrzymujemy

(2) [ABED]= [DAP]+[ABP]+[BEP] = \frac{1}{2}DA·r+ \frac{1}{2}AB ·r+ \frac{1}{2}BE ·r=
= \frac{1}{2}(DA+AB +BE)·r

oraz

(3) [DEC] = [ECP]+[CDP] = \frac{1}{2}EC ·r+ \frac{1}{2}CD ·r= \frac{1}{2}(EC +CD)·r.

Dzieląc stronami równości (2) i (3) uzyskujemy równość (1).

Zadanie 11.

Układ liczb całkowitych dodatnich c_{1},c_{2},...,c_{n} nazwiemy dopuszczalnym, gdy za pomocą wagi szalkowej i dwóch kompletów odważników o ciężarach c_{1},c_{2},...,c_{n} można zważyć dowolny przedmiot o ciężarze będącym liczbą naturalną nie przekraczającą 2(c_{1} +c_{2} +...+c_{n}). Dla każdej liczby n wyznaczyć maksymalną sumę n liczb tworzących układ dopuszczalny. Uwaga: Odważniki można kłaść na obie szalki wagi.

Rozwiązanie

Niech p_{1},p_{2},...,p_{n} oraz q_{1},q_{2},...,q_{n} będą dwoma zestawami odważników o ciężarach odpowiednio c_{1},c_{2},...,c_{n}. Wykażemy najpierw, że za pomocą tych dwóch zestawów możemy zważyć co najwyżej \frac{1}{2}(5^{n}− 1) przedmiotów, niezależnie od tego, czy liczby c_{1},c_{2},...,c_{n} tworzą układ dopuszczalny, czy nie.

Ustawienie odważników na szalkach wagi nazwiemy optymalnym, jeśli dla każdego k ∈ {1,2,...,n} ciężarki p_{k} i q_{k} nie znajdują się na dwóch różnych szalkach wagi.

Aby otrzymać ustawienie optymalne, dwa odważniki p_{k} i q_{k} możemy ustawić na szalkach wagi na 5 sposobów (zob. tabela obok). Zatem liczba wszystkich optymalnych ustawień odważników jest równa 5^{n}. W tej liczbie mieści się jedno ustawienie �puste”, w którym na żadną szalkę nie kładziemy odważników. Pozostałe ustawienia można połączyć w pary symetryczne, w których jedno ustawienie powstaje z drugiego przez zamianę zawartości obydwu szalek wagi.

lewa prawa
szalka szalka
0  0
1  0
2  0
0  1
0  2

Tak więc liczba niepustych, istotnie różnych optymalnych ustawień odważników wynosi \frac{1}{2}(5^{n}− 1), co oznacza, że możemy zważyć co najwyżej \frac{1}{2}(5^{n}− 1) przedmiotów o różnych ciężarach.

Załóżmy, że liczby c_{1},c_{2},...,c_{n} tworzą układ dopuszczalny. Wówczas masa najcięższego przedmiotu, jaki można zważyć, wynosi 2(c_{1}+c_{2}+...+c_{n}). Ponieważ nie da się zważyć więcej niż \frac{1}{2}(5^{n}− 1) przedmiotów,

(1)  2(c_{1}+c_{2}+...+c_{n}) \frac{1}{2}(5^{n}− 1).

Wykażemy teraz, że liczby c_{1} = 1, c_{2} = 5, c_{3} = 5^{2}, ..., c_{n} = 5^{n−1} tworzą układ dopuszczalny. Dla tych wartości c_{i} zachodzi równość

(2)  2(c_{1}+c_{2}+...+c_{n}) = \frac{1}{2}(5^{n}− 1).

Należy więc udowodnić, że za pomocą dwóch kompletów odważników o ciężarach 1, 5, 5^{2}, ..., 5^{n−1} można zważyć każdy przedmiot o ciężarze będącym liczbą naturalną nie przekraczającą \frac{1}{2}(5^{n}− 1). Dowód tego faktu przeprowadzimy na dwa sposoby.

Sposób I

Indukcja. Dla n = 1 mamy dwa odważniki o ciężarze 1 każdy i za ich pomocą można zważyć przedmiot o ciężarze 1 lub 2 = \frac{1}{2}(5^{1}− 1).

Załóżmy, że dysponujemy dwoma zestawami odważników o ciężarach 1, 5, 5^{2}, ..., 5^{n−1} i za ich pomocą umiemy zważyć każdy przedmiot o ciężarze nie przekraczającym \frac{1}{2}(5^{n}− 1). Oto jak zważyć przedmiot p o ciężarze c, gdy:

(a) c ∈ ⟨\frac{1}{2}(5^{n}− 1)+1 ,5^{n}− 1⟩.

Korzystając z założenia indukcyjnego ważymy najpierw przedmiot q o ciężarze 5^{n} −c kładąc go na prawą szalkę wagi. Następnie kładziemy dodatkowy ciężarek o masie 5^{n} na prawą szalkę wagi, zdejmujemy przedmiot q i kładziemy przedmiot p na lewą szalkę.

(b) c ∈ ⟨5^{n}+ 1, \frac{1}{2}(3·5^{n}− 1)⟩.

Podobnie jak w przypadku (a), ważymy najpierw przedmiot q o ciężarze c−5^{n} kładąc go na prawą szalkę wagi. Następnie kładziemy dodatkowy ciężarek o masie 5^{n} na lewą szalkę wagi, zdejmujemy przedmiot q i kładziemy przedmiot p na prawą szalkę.

(c) c ∈ ⟨\frac{1}{2}(3·5^{n}− 1)+ 1,2·5^{n}− 1⟩.

Ważymy najpierw przedmiot q o ciężarze 2·5^{n} −c kładąc go na prawą szalkę wagi. Następnie kładziemy dwa ciężarki o masie 5^{n} na prawą szalkę wagi, zdejmujemy przedmiot q, po czym kładziemy przedmiot p na lewą szalkę.

(d) c ∈ ⟨2·5^{n}+ 1, \frac{1}{2}(5^{n+1} − 1)⟩.

Ważymy najpierw przedmiot q o ciężarze c−2·5^{n} kładąc go na prawą szalkę wagi. Następnie kładziemy dwa ciężarki o masie 5^{n} na lewą szalkę wagi, zdejmujemy przedmiot q, po czym kładziemy przedmiot p na prawą szalkę.

Przedmioty o masach 5^{n} i 2·5^{n} można zważyć używając jedynie dwóch odważników o masie 5^{n}. Dowód indukcyjny został więc zakończony.

Sposób II

Niech c będzie dowolną liczbą naturalną nie przekraczającą \frac{1}{2}(5^{n}− 1). Wówczas liczba c+ \frac{1}{2}(5^{n}− 1) jest mniejsza od 5^{n}. Liczbę tę można zatem zapisać w systemie piątkowym przy użyciu co najwyżej n cyfr. Innymi słowy

c+ \frac{1}{2}(5^{n}− 1) = ∑_{i=0}^{n−1} a_{i}5^{i}, gdzie a_{i} ∈ \{0,1,2,3,4\}.

Ponieważ \frac{1}{2}(5^{n}− 1) = 2(1+5+5^{2}+...+5^{n−1} ), więc

c = ∑_{i=0}^{n−1} ε_{i}5^{i}, gdzie ε_{i} ∈ {−2,−1,0,1,2}.

Powyższa równość oznacza, że przedmiot o ciężarze c można zważyć za pomocą dwóch kompletów odważników o ciężarach 1, 5, 5^{2}, ..., 5^{n−1} , co kończy dowód.

Z równości (1) i (2) wynika, że maksymalna suma zbioru n liczb dopuszczalnych wynosi \frac{1}{4}(5^{n}− 1).

Zadanie 12.

Rozpatrujemy ciągi liczb całkowitych x_{0},x_{1},...,x_{2000} spełniające warunki

x_{0} = 0 oraz |x_{n}| = |x_{n−1} +1| dla n = 1,2,...,2000 .

Znaleźć najmniejszą wartość wyrażenia |x_{1} +x_{2} +...+x_{2000} | .

Rozwiązanie Odpowiedź: Najmniejsza wartość danego wyrażenia wynosi 12. Wykażemy indukcyjnie, że dla dowolnego ciągu (x_{n}) spełniającego warun-

ki zadania zachodzi równość

(1) x_{0}+x_{1}+x_{2}+...+x_{n} = \frac{1}{2}(x_{n}^{2} +2x_{n} −n)  (n = 0,1,2,3,...,2000).

Dla n = 0 obie strony powyższej równości są równe 0. Załóżmy więc, że zależność (1) jest prawdziwa dla pewnego n. Wówczas

x_{0}+x_{1}+x_{2}+...+x_{n} +x_{n+1} = \frac{1}{2}(x_{n}^{2} +2x_{n} −n)+x_{n+1} =
= \frac{1}{2}((x_{n} +1)^{2}−(n+1))+x_{n+1} = \frac{1}{2}(x_{n+1}^{2} −(n+1))+x_{n+1} =
= \frac{1}{2}(x_{n+1}^{2} +2x_{n+1} −(n+1)),

co kończy dowód indukcyjny wzoru (1).

Zatem

|x_{1}+x_{2}+...+x_{2000}| = \frac{1}{2}|x_{2000}^{2} +2x_{2000} −2000| = \frac{1}{2}|(x_{2000} +1)^{2}−2001|.

Liczbą kwadratową leżącą najbliżej liczby 2001 jest 2025 = 45^{2}. Stąd oraz z powyższej równości wnioskujemy, że wyrażenie |x_{1}+x_{2}+...+x_{2000}| nie może przyjąć wartości mniejszej niż \frac{1}{2}|2025−2001| = 12.

Pozostaje zauważyć, że wartość 12 można zrealizować przyjmując

x_{n} = \{ \begin{matrix}n & dla & n 44; \\ −45 & dla & n > 44, n nieparzyste; \\ 44 & dla & n > 44, n parzyste. \end{matrix}

Powyższy ciąg spełnia warunki zadania. Ponadto x_{2000} = 44, co na mocy równości (1) daje |x_{1}+x_{2}+...+x_{2000}| = 12.

Zadania z XLI Międzynarodowej Olimpiady Matematycznej Taejon (Korea Południowa), 19 i 20 lipca 2000 r.

1. Dwa okręgi Γ_{1} i Γ_{2} przecinają się w punktach M i N. Niech l będzie taką wspólną prostą styczną do Γ_{1} i Γ_{2}, że punkt M znajduje się bliżej prostej l niż punkt N. Prosta l jest styczna do Γ_{1} w punkcie A oraz do Γ_{2} w punkcie B. Prosta równoległa do l przechodząca przez M przecina Γ_{1} ponownie w punkcie C oraz Γ_{2} ponownie w punkcie D. Proste CA i DB przecinają się w punkcie E; proste AN i CD przecinają się w punkcie P; proste BN i CD przecinają się w punkcie Q. Wykazać, że EP = EQ.

2. Niech a, b, c będą takimi liczbami rzeczywistymi dodatnimi, że abc = 1. Udowodnić, że

( a−1+ \frac{1}{b}) ( b−1+ \frac{1}{c}) ( c−1+ \frac{1}{a}) 1 .

3. Niech n 2 będzie liczbą naturalną. Na danej poziomej prostej znajduje się n pcheł, nie wszystkie w tym samym punkcie. Dla liczby rzeczywistej dodatniej λ definiujemy ruch następująco:

(i) wybieramy dwie pchły, w punktach A i B, przy czym A znajduje się na lewo od B;

(ii) pchła z punktu A skacze na punkt C, znajdujący się na danej prostej na prawo od B i taki, że BC/AB = λ.

Wyznaczyć wszystkie takie wartości λ, że dla dowolnego punktu M na prostej i dowolnego początkowego położenia n pcheł istnieje skończony ciąg ruchów, który przeprowadza wszystkie pchły na prawo od M.

4. Iluzjonista ma sto kart ponumerowanych od 1 do 100. Wkłada je do trzech pudełek, czerwonego, białego i niebieskiego tak, że każde z nich zawiera przynajmniej jedną kartę. Ktoś z widzów wybiera dwa z tych trzech pudełek, wyciąga po jednej karcie z każdego z wybranych pudełek i podaje sumę liczb na wyciągniętych kartach. Mając daną tę sumę, iluzjonista wskazuje to pudełko, z którego nie została wyciągnięta żadna karta.

Na ile sposobów można włożyć wszystkie karty do pudełek tak, by ta sztuka zawsze się udała? (Dwa sposoby uważa się za różne, gdy przynajmniej jedna karta znajdzie się za każdym razem w innym pudełku).

5. Rozstrzygnąć, czy istnieje taka liczba całkowita dodatnia n, że

(i) n jest podzielna przez dokładnie 2000 różnych liczb pierwszych oraz (ii) liczba 2^{n} +1 jest podzielna przez n.

6. Niech AH_{1}, BH_{2}, CH_{3} będą wysokościami trójkąta ostrokątnego ABC. Okrąg wpisany w trójkąt ABC jest styczny do BC, CA, AB odpowiednio w punktach T_{1}, T_{2}, T_{3}. Niech proste l_{1}, l_{2}, l_{3} będą symetrycznymi obrazami prostych H_{2}H_{3}, H_{3}H_{1}, H_{1}H_{2} odpowiednio względem prostych T_{2}T_{3}, T_{3}T_{1}, T_{1}T_{2}. Udowodnić, że proste l_{1}, l_{2}, l_{3} wyznaczają trójkąt, którego wierzchołki leżą na okręgu wpisanym w trójkąt ABC.

Zadania z XXIII Austriacko-Polskich Zawodów Matematycznych Baranów Sandomierski, 28–30 czerwca 2000 r.

1. Wyznaczyć wszystkie wielomiany P (x) o współczynnikach rzeczywistych, dla których istnieje taka dodatnia liczba całkowita n, że dla nieskończenie wielu wartości x zachodzi równość:

∑_{k=1}^{2n+1} (−1)^{k}[ \frac{k}{2}]P (x+k) = 0 .

2. W sześcianie o krawędzi długości 1, ABCD jest pewną ścianą, a CG krawędzią do niej prostopadłą. Okrąg o_{1} jest wpisany w kwadrat ABCD, a okrąg o_{2} jest opisany na trójkącie BDG. Wyznaczyć najmniejszą wartość odległości XY dla X ∈ o_{1} i Y ∈ o_{2}.

3. Dla każdej liczby naturalnej n 3 rozwiązać w liczbach rzeczywistych następujący układ równań:

\{ \begin{matrix}x_{1}^{3} & = & x_{2}+x_{3}+1 \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ x_{k}^{3} & = & x_{k+1} +x_{k+2} +1 \\ . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . & . \\ x_{n−1}^{3} & = & x_{n} +x_{1}+1 \\ x_{n}^{3} & = & x_{1}+x_{2}+1 \end{matrix}

4. Wyznaczyć wszystkie liczby całkowite dodatnie N, nie mające dzielników pierwszych różnych od 2 i 5, takie, że N +25 jest kwadratem liczby całkowitej.

5. Dla jakich liczb naturalnych n 5 możliwe jest pokolorowanie wierzchołków n-kąta foremnego nie więcej niż sześcioma kolorami, w ten sposób, aby w każdej grupie pięciu kolejnych wierzchołków wystąpiło pięć różnych kolorów?

6. Rozważmy bryłę Q postaci Q = Q_{0}∪Q_{1}∪Q_{2}∪Q_{3}∪Q_{4}∪Q_{5}∪Q_{6}, gdzie Q_{i} (i = 0,1,2,...,6) są siedmioma różnymi sześcianami o krawędziach długości 1, przy czym sześcian Q_{0} ma wspólną ścianę z każdym z sześciu pozostałych. Rostrzygnąć, czy można wypełnić przestrzeń nieskończoną ilością brył, z których każda powstaje przez przesunięcie równoległe bryły Q, a żadne dwie nie mają wspólnych punktów wewnętrznych.

7. Na płaszczyźnie dany jest trójkąt A_{0}B_{0}C_{0}. Rozważamy trójkąty ABC spełniające następujące warunki:

(i) proste AB, BC, CA przechodzą, odpowiednio, przez punkty C_{0}, A_{0}, B_{0}; (ii) trójkąty ABC i A_{0}B_{0}C_{0} są podobne (tzn. istnieje podobieństwo prze- kształcające A na A_{0}, B na B_{0} i C na C_{0}).

Wyznaczyć miejsce geometryczne środków okręgów opisanych na wszystkich takich trójkątach ABC.

8. Na płaszczyźnie danych jest 27 punktów, z których żadne trzy nie są współliniowe. Cztery spośród tych punktów są wierzchołkami kwadratu o boku długości 1, a pozostałe 23 leżą wewnątrz tego kwadratu. Udowodnić, że pewne trzy spośród danych punktów są wierzchołkami trójkąta o polu nie większym niż \frac{1}{48}.

9. Udowodnić, że jeśli a, b, c są nieujemnymi liczbami rzeczywistymi, przy czym a+b+c = 1, to mają miejsce nierówności:

2 (1−a^{2}) ^{2}+(1−b^{2}) ^{2}+(1−c^{2}) ^{2} (1+a)(1+b)(1+c) .

Dla każdej z tych nierówności rozstrzygnąć, kiedy zachodzi równość.

10. Plan zamku w Baranowie Sandomierskim można w przybliżeniu przedstawić jako graf o 16 węzłach, narysowany poniżej:

Nocny strażnik planuje zamkniętą trasę obchodu wzdłuż krawędzi tego grafu.

(a) Ile istnieje takich tras (bez uwzględniania kierunku), które przechodzą przez każdy węzeł dokładnie raz?

(b) Ile istnieje takich tras (z uwzględnieniem kierunku), które przechodzą przez każdą krawędź dokładnie raz i nie krzyżują się same ze sobą?

Zadania z XI Zawodów Matematycznych Państw Bałtyckich Oslo (Norwegia), 4 listopada 2000 r.

1. Niech K będzie punktem leżącym wewnątrz trójkąta ABC. Niech M i N będą takimi punktami, że M i K leżą po przeciwnych stronach prostej AB, oraz N i K leżą po przeciwnych stronach prostej BC. Załóżmy, że < ) MAB = < ) MBA = < ) NBC = < ) NCB = < ) KAC = < ) KCA. Udowodnić, że MBNK jest równoległobokiem.

2. Dany jest trójkąt równoramienny ABC o kącie < ) A = 90^{∘}. Niech M będzie środkiem boku AB. Prosta przechodząca przez punkt A i prostopadła do prostej CM przecina bok BC w punkcie P. Dowieść, że

< ) AMC = < ) BMP.

3. Dany jest trójkąt ABC, w którym < ) A = 90^{∘} oraz AB ≠ AC. Punkty D, E, F leżą odpowiednio na bokach BC, CA, AB, w taki sposób, że AF DE jest kwadratem. Wykazać, że prosta BC, prosta F E oraz styczna w punkcie A do okręgu opisanego na trójkącie ABC przecinają się w jednym punkcie.

4. Dany jest trójkąt ABC, w którym < ) A = 120^{∘}. Punkty K i L leżą odpowiednio na bokach AB i AC. Niech BKP i CLQ będą trójkątami równobocznymi zbudowanymi na zewnątrz trójkąta ABC. Udowodnić, że P Q \frac{\sqrt{3}}{2}(AB +AC).

5. Niech ABC będzie takim trójkątem, że

\frac{BC}{AB −BC} = \frac{AB +BC}{AC} .

Wyznaczyć iloraz < ) A: < ) C.

6. Fredek prowadzi pensjonat. Twierdzi on, że za każdym razem, gdy jego pensjonat odwiedza n 3 gości, potrafi wskazać takich dwóch, którzy wśród pozostałych gości mają taką samą liczbę znajomych oraz wspólnego znajomego lub wspólnego nieznajomego. Dla jakich wartości n Fredek ma rację?

7. Tablica kontrolna o wymiarach 40×50 składa się 2000 guzików, z których każdy jest w pozycji: włączony lub wyłączony. Naciśnięcie guzika powoduje zmianę jego pozycji oraz pozycji wszystkich guzików w tej samej kolumnie i w tym samym wierszu. Wykazać, że przyciskając guziki można tablicę z początkowo wyłączonymi guzikami doprowadzić do tablicy, w której wszystkie guziki są włączone. Wyznaczyć najmniejszą potrzebną do tego liczbę naciśnięć.

8. Na przyjęciu spotkało się czternastu kolegów. Jeden z nich, Fredek, chciał wcześniej położyć się spać. Pożegnał się więc z 10 kolegami, zapominając o trzech pozostałych i poszedł spać. Po chwili wrócił na przyjęcie, pożegnał się z 10 kolegami (niekoniecznie tymi samymi co poprzednio) i poszedł spać. Fredek powracał jeszcze wielokrotnie i za każdym razem żegnał się z 10 kolegami, po czym szedł spać. Kiedy tylko pożegnał się z każdym ze swoich kolegów co najmniej raz, to już nie wrócił. Rano Fredek uświadomił sobie, że z każdym z trzynastu kolegów pożegnał się inną liczbę razy. Ile co najmniej razy powracał Fredek?

9. Po szachownicy 2k ×2k złożonej z jednostkowych kwadratów skacze żaba. Skoki żaby są długości \sqrt{1+k^{2}} i przenoszą ją ze środka jednego kwadratu do środka innego kwadratu. Pewnych m kwadratów szachownicy zaznaczono krzyżykiem. Wszystkie kwadraty, do których może skoczyć żaba z pól oznaczonych krzyżykiem, oznaczono kółkiem (nawet, jeśli na którymś z tych pól jest już krzyżyk). Kółkiem oznaczono n kwadratów. Dowieść, że n m.

10. Na tablicy napisano dwie liczby całkowite dodatnie. Początkowo, jedna z nich jest równa 2000, a druga jest mniejsza niż 2000. Jeśli średnia arytmetyczna m dwóch liczb napisanych na tablicy jest liczbą całkowitą, możemy wykonać następującą procedurę: ścieramy jedną z liczb zastępując ją przez m. Dowieść, że ta procedura nie może być wykonana więcej niż dziesięć razy. Podać przykład, w którym powyższa procedura jest wykonywana dziesięć razy.

11. Dany jest taki ciąg liczb całkowitych dodatnich a_{1},a_{2},..., że dla dowolnych m i n zachodzi: jeśli m jest dzielnikiem liczby n oraz m < n, to a_{m} jest dzielnikiem liczby a_{n} oraz a_{m} < a_{n}. Znaleźć najmniejszą możliwą wartość liczby a_{2000}.

12. Niech x_{1},x_{2},...,x_{n} będą takimi liczbami całkowitymi dodatnimi, że żadna z nich nie jest początkowym fragmentem żadnej innej (na przykład 12 jest początkowym fragmentem liczb \underline{12}, \underline{12}5 oraz \underline{12}405). Dowieść, że

\frac{1}{x_{1}} + \frac{1}{x_{2}} +...+ \frac{1}{x_{n}} < 3.

13. Niech a_{1},a_{2},...,a_{n} będzie takim ciągiem arytmetycznym liczb całkowitych, że i | a_{i} dla i = 1,2,...,n− 1 oraz n |̸ a_{n}. Udowodnić, że n jest potęgą liczby pierwszej.

14. Znaleźć wszystkie takie dodatnie liczby całkowite n, że n równa się liczbie dodatnich dzielników liczby n pomnożonej przez 100.

15. Niech n będzie dodatnią liczbą całkowitą niepodzielną ani przez 2, ani przez 3. Wykazać, że dla wszystkich liczb całkowitych k liczba

(k +1)^{n} −k^{n} −1

jest podzielna przez k^{2}+k +1.

16. Udowodnić, że dla wszystkich dodatnich liczb rzeczywistych a, b, c zachodzi nierówność

\sqrt{a^{2}−ab+b^{2}} +\sqrt{b^{2}−bc+c^{2}} \sqrt{a^{2}+ac+c^{2}} .

17. Znaleźć wszystkie rozwiązania w liczbach rzeczywistych następującego układu równań:

\{ \begin{matrix}x & + & y & + & z & + & t & = & 5 \\ xy & + & yz & + & zt & + & tx & = & 4 \\ xyz & + & yzt & + & ztx & + & txy & = & 3 \\ xyzt & & & & & & & = & −1. \end{matrix}

18. Wyznaczyć wszystkie dodatnie liczby rzeczywiste x i y spełniające równanie

x+y + \frac{1}{x} + \frac{1}{y} +4 = 2·(\sqrt{2x+1} +\sqrt{2y +1} ).

19. Niech t \frac{1}{2} będzie liczbą rzeczywistą, a n dodatnią liczbą całkowitą. Dowieść, że t^{2n} (t−1)^{2n} +(2t−1)^{n}.

20. Dla dowolnej liczby całkowitej dodatniej n, niech

x_{n} = \frac{(2n+1)(2n+3)·...·(4n−1)(4n+1)}{(2n)(2n+2)·...·(4n−2)(4n)} .

Dowieść, że

\frac{1}{4n} < x_{n} −\sqrt{2}< \frac{2}{n} .