LI Olimpiada Matematyczna

Rozwiązania zadań konkursowych zawodów stopnia drugiego

25 lutego 2000 r. (pierwszy dzień zawodów)

Zadanie 1.

Rozstrzygnąć, czy każdą liczbę wymierną dodatnią można przedstawić w postaci

\frac{a^{2} +b^{3}}{c^{5} +d^{7}} ,

gdzie a, b, c, d są liczbami całkowitymi dodatnimi.

Rozwiązanie

Dla dowolnych liczb całkowitych dodatnich p, q zachodzą następujące równości:

\frac{p}{q} = \frac{p}{q}· \frac{p^{5}q^{4}+p^{14}q^{6}}{p^{5}q^{4}+p^{14}q^{6}} = \frac{p^{6}q^{4}+p^{15}q^{6}}{p^{5}q^{5}+p^{14}q^{7}} = \frac{(p^{3}q^{2})^{2}+(p^{5}q^{2})^{3}}{(pq)^{5}+(p^{2}q)^{7}} .

Zatem każdą liczbę wymierną dodatnią można przedstawić w żądanej postaci.

Zadanie 2.

Dwusieczna kąta BAC trójkąta ABC przecina okrąg opisany na tym trójkącie w punkcie D różnym od A. Punkty K i L są rzutami prostokątnymi odpowiednio punktów B i C na prostą AD. Dowieść, że AD BK +CL.

Rozwiązanie

Oznaczmy przez o okrąg opisany na trójkącie ABC. Z równości kątów BAD i DAC wynika, że długości łuków BD i DC okręgu o są równe (długość łuku XY jest mierzona od punktu X do punktu Y w kierunku przeciwnym do ruchu wskazówek zegara).

[figure: A; B; C; E; D; K; L; N; o; rys. 1; A; B; C; E; D; K; L; N; o; rys. 2]

Niech E będzie punktem symetrycznym do punktu D względem symetralnej boku AB, zaś niech N będzie rzutem prostokątnym punktu E na prostą AD (rys. 1 i 2). Wówczas AD = BE. Ponadto długości łuków DC i EA są równe, co oznacza, że EN = CL.

Punkty B i E leżą po dwóch różnych stronach prostej AD. Zatem długość odcinka BE jest nie mniejsza niż suma odległości punktów B i E od prostej AD. Innymi słowy BE BK +EN , czyli AD BK +CL.

Zadanie 3.

Na polach szachownicy n×n rozmieszczono n^{2} różnych liczb całkowitych, po jednej na każdym polu. W każdej kolumnie pole z największą liczbą pomalowano na czerwono. Zbiór n pól szachownicy nazwiemy dopuszczalnym, jeżeli żadne dwa z tych pól nie znajdują się w tym samym wierszu, ani w tej samej kolumnie. Spośród wszystkich zbiorów dopuszczalnych wybrano zbiór, dla którego suma liczb umieszczonych na jego polach jest największa. Wykazać, że w tak wybranym zbiorze jest czerwone pole.

Rozwiązanie Przeprowadzimy dowód nie wprost. Załóżmy, że w wybranym zbiorze dopuszczalnym (oznaczmy go przez A)

nie ma czerwonego pola.

Zdefiniujemy ciąg pól D_{1},E_{1},D_{2},E_{2},... danej szachownicy według niżej opisanej reguły. (Dla n = 8 proces wyboru pól D_{1},E_{1},D_{2},E_{2},... jest przedstawiony na rysunkach 1 i 2. Pola czerwone są zacieniowane, zaś pola ze zbioru A są oznaczone kółkiem.)

Pole D_{1} jest dowolnym polem ze zbioru A. Niech E_{1} będzie polem czerwonym leżącym w tej samej kolumnie, co D_{1}.

Następnie rozważamy to pole D_{2} ze zbioru A, które leży w tym samym wierszu, co E_{1}. Przez E_{2} oznaczamy pole czerwone leżące w tej samej kolumnie, co D_{2}. Postępowanie to kontynuujemy. (Ogólnie: pole czerwone E_{i} leży w tej samej kolumnie, co D_{i}, natomiast pole D_{i+1} jest polem ze zbioru A leżącym w tym samym wierszu, co E_{i}.)

[figure: rys. 1; D_{1}; E_{1}; D_{2}; E_{2}; D_{3}; E_{3}; D_{4}; E_{4}; rys. 2; rys. 3]

W ten sposób otrzymujemy ciąg pól D_{1},E_{1},D_{2},E_{2},D_{3},..., w którym każde pole jednoznacznie wyznacza pole następne. Ponieważ pól czerwonych jest skończenie wiele, więc znajdziemy takie liczby całkowite dodatnie i, t, dla których E_{i} = E_{i+t} oraz E_{i} ≠ E_{i+s} dla s = 1,2,...,t− 1. (W naszym przykładzie przedstawionym na rysunkach 1 i 2, E_{2} = E_{5}, a więc i = 2, t = 3.)

Usuwamy ze zbioru A pola D_{i+1} ,D_{i+2} ,...,D_{i+t} zastępując je odpowiednio polami E_{i+1} ,E_{i+2} ,...,E_{i+t} (rys. 3). Otrzymany w ten sposób zbiór oznaczmy przez B.

Z określenia ciągu D_{1},E_{1},D_{2},E_{2},D_{3},... wynika, że pola

D_{i+1} , D_{i+2} , ..., D_{i+t}

znajdują się odpowiednio w tych samych kolumnach, co pola

E_{i+1} , E_{i+2} , ..., E_{i+t}

oraz odpowiednio w tych samych wierszach, co pola

E_{i} = E_{i+t} , E_{i+1} , E_{i+2} , ..., E_{i+t−1} .

Zatem zbiór B jest dopuszczalny. Ponadto liczby, które zostały napisane na polach E_{i+1} ,E_{i+2} ,...,E_{i+t} są większe odpowiednio od liczb napisanych na polach D_{i+1} ,D_{i+2} ,...,D_{i+t} . Wynika stąd, że suma liczb napisanych na polach zbioru B jest większa od sumy liczb napisanych na polach zbioru A. To jednak przeczy założeniu, że A ma największą sumę liczb spośród wszystkich zbiorów dopuszczalnych.

(wp, jwr)

∗  ∗  ∗

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

www.impan.gov.pl/˜ olimp/

LI Olimpiada Matematyczna

Rozwiązania zadań konkursowych zawodów stopnia drugiego

26 lutego 2000 r. (drugi dzień zawodów)

Zadanie 4.

Punkt I jest środkiem okręgu wpisanego w trójkąt ABC, w którym AB ≠ AC. Proste BI i CI przecinają boki AC i AB odpowiednio w punktach D i E. Wyznaczyć wszystkie miary kąta BAC, dla których może zachodzić równość DI = EI.

Rozwiązanie Wykażemy, że jedyną wartością przyjmowaną przez kąt BAC jest 60^{∘}. Na mocy twierdzenia sinusów zastosowanego do trójkątów ADI i AEI

otrzymujemy sin< ) AEI = sin< ) ADI. Stąd

< ) AEI = < ) ADI lub < ) AEI +< ) ADI = 180^{∘}. Przypuśćmy najpierw, że zachodzi równość < ) AEI = < ) ADI (rys. 1). Wte-

dy również < ) AIE = < ) AID, co oznacza, że trójkąty AEI oraz ADI są przystające (cecha kąt-bok-kąt). Zatem AD = AE. To dowodzi, że przystające są także trójkąty ADB i AEC (cecha kąt-bok-kąt). Stąd uzyskujemy równość AB = AC, co przeczy założeniom poczynionym w treści zadania.

A B  C D E  I rys. 1  B E A I rys. 2 D  C

Pozostał do rozpatrzenia przypadek, w którym < ) AEI +< ) ADI = 180^{∘} (rys. 2). Wtedy punkty A, E, I, D leżą na jednym okręgu. Zatem

< ) BAC = < ) DIC = < ) IBC +< ) ICB = \frac{1}{2}< ) ABC + \frac{1}{2}< ) BCA.

Stąd otrzymujemy

180^{∘} = < ) BAC +< ) ABC +< ) BCA = < ) BAC +2< ) BAC = 3< ) BAC, czyli < ) BAC = 60^{∘}.

Do zakończenia rozwiązania pozostało wykazać, że istnieje trójkąt ABC, w którym AB ≠ AC, < ) BAC = 60^{∘} oraz DI = EI. Wykażemy więcej: w każdym trójkącie ABC o kącie BAC równym 60^{∘} zachodzi równość DI = EI.

Jeżeli < ) BAC = 60^{∘}, to

< ) DIC = \frac{1}{2}< ) ABC + \frac{1}{2}< ) BCA = 90^{∘}− \frac{1}{2}< ) BAC = 60^{∘} = < ) BAC. Na czworokącie AEID można więc opisać okrąg. Ponieważ AI jest dwusieczną kąta EAD, więc DI = EI.

Zadanie 5.

Niech ℕ oznacza zbiór liczb całkowitych dodatnich. Rozstrzygnąć, czy istnieje taka funkcja f: ℕ → ℕ, że dla każdego n ∈ ℕ zachodzi równość f(f(n)) = 2n.

Rozwiązanie Taka funkcja istnieje. Oto przykład. Niech A będzie zbiorem tych liczb całkowitych dodatnich, w których

rozkładzie na czynniki pierwsze �trójka” występuje nieparzystą liczbę razy. Funkcję f definiujemy wzorem:

f(n) = \{ \begin{matrix}\frac{1}{3}n & dla & n ∈ A, \\ 6n & dla & n ∈ ℕ\A. \end{matrix}

Wówczas, jeśli n ∈ A, to f(n) ∈ ℕ\A, skąd

f(f(n)) = f(\frac{1}{3}n) = 2n dla n ∈ A.

Podobnie, jeżeli n ∈ ℕ\A, to f(n) ∈ A, co daje f(f(n)) = f (6n)= 2n dla n ∈ ℕ\A.

Zadanie 6.

Wielomian w(x) stopnia drugiego o współczynnikach całkowitych przyjmuje dla całkowitych x wartości będące kwadratami liczb całkowitych. Dowieść, że wielomian w(x) jest kwadratem pewnego wielomianu.

Rozwiązanie

Niech w(x) = ax^{2}+bx+c. Wprowadźmy oznacznie: k_{n} = \sqrt{w(n)} dla dowolnej liczby całkowitej dodatniej n. Wówczas k_{n} może być zerem dla co najwyzej dwóch wartości n. Dla pozostałych n mamy

k_{n+1} −k_{n} = \frac{k_{n+1}^{2} −k_{n}^{2}}{k_{n+1} +k_{n}} = \frac{(2n+1)a+b}{\sqrt{a(n+ 1)^{2}+b(n+ 1)+c} + \sqrt{an^{2}+bn+c}} .

Dzieląc licznik i mianownik otrzymanego ułamka przez n i przechodząc z n do nieskończoności widzimy, że ciąg (k_{n+1} −k_{n}) jest zbieżny i jego granica wynosi \sqrt{a}. Ponieważ wyrazy ciągu (k_{n+1} −k_{n}) są całkowite, więc granica tego ciągu, liczba \sqrt{a}, jest też całkowita. Ponadto istnieje taka liczba naturalna m, że

(1) k_{n+1} −k_{n} = \sqrt{a} dla n m.

Niech d = k_{m} −m\sqrt{a}. Ze związku (1) wynika, że

(2) k_{n} = n\sqrt{a}+d dla n m.

Przyjmijmy: p(x) = (x\sqrt{a}+d)^{2}. Na mocy definicji liczb k_{n} oraz równości (2) uzyskujemy równość p(n) = w(n) dla n m. To oznacza, że p(x) = w(x), skąd

w(x) = (x\sqrt{a}+d) ^{2} . (wp, jwr)