L Olimpiada Matematyczna

Szkice rozwiązań zadań z zawodów stopnia drugiego Pierwszy dzień (26 lutego 1999 r.)

1. Przypuśćmy, że istnieją funkcje g i h spełniające warunki zadania. Ponieważ funkcje te są rosnące, więc dla każdego k ∈ ℕ mamy

\begin{aligned}g( \frac{1}{2k+1} ) & = & f( \frac{1}{2k+1} )+h( \frac{1}{2k+1} ) = −1+h( \frac{1}{2k+1} ) < \\ & < & −1+h( \frac{1}{2k} ) = 1+h( \frac{1}{2k} )−2 = f ( \frac{1}{2k} )+h( \frac{1}{2k} )−2 = g( \frac{1}{2k} )−2 < g( \frac{1}{2k−1} )−2. \end{aligned}

Z monotoniczności funkcji g oraz powyższych nierówności dostajemy

g(0) < g( \frac{1}{2k+1} ) < g( \frac{1}{2k−1} )−2 < g( \frac{1}{2k−3} )−4 < ...< g( \frac{1}{3})−2(k −1) < g(1)−2k.

Zatem g(1)−g(0) > 2k dla dowolnego k ∈ ℕ, co nie jest możliwe.

*  *  *  *  *

2. Przeprowadzimy dowód indukcyjny. Dla n = 1 teza zadania jest oczywiście prawdziwa. Załóżmy więc, że teza jest prawdziwa dla pewnego n i rozważmy sześcian C o krawędzi 2^{n+1} z wyróżnionym sześcianem jednostkowym D. Sześcian C dzielimy na osiem przystających sześcianów C_{1},C_{2},...,C_{8}, każdy o krawędzi 2^{n}. W jednym z nich (przyjmijmy, że w C_{8}) znajduje się sześcian jednostkowy D. Połóżmy klocek w samym środku sześcianu C tak, aby jego część wspólna z każdym z sześcianów C_{1},C_{2},...,C_{7} była sześcianem jednostkowym. Wówczas pozostanie nam do wypełnienia klockami osiem sześcianów C_{1},C_{2},...,C_{8}, każdy z usuniętym sześcianem jednostkowym. To zaś, na mocy założenia indukcyjnego, jest wykonalne. Dowód indukcyjny jest więc zakończony.

*  *  *  *  *

3. Załóżmy najpierw, że proste AD i BC nie są równoległe i przecinają się w punkcie S. Wówczas trójkąty ASB i CSD są podobne. Ponieważ AE: EB = CF : F D, więc podobne są również trójkąty ASE i CSF. Stąd < ) DSE = < ) CSF. Ponadto

\frac{SE}{SF} = \frac{SA}{SC} = \frac{AB}{CD} = \frac{P E}{P F} ,

skąd dostajemy < ) ESP = < ) F SP. Zatem punkt P jest równoodległy od prostych AD i BC. Stosunek pól trójkątów AP D i BP C jest więc równy stosunkowi długości odcinków AD i BC, czyli nie zależy od wyboru punktów E i F.

Załóżmy teraz, że proste AD i BC są równoległe. Wtedy ABCD jest trapezem równoramiennym, gdzie AB = CD. Punkt P jest środkiem odcinka EF oraz BE = DF. Punkty E i F są więc jednakowo odległe odpowiednio od prostych BC i AD. Ponadto punkt P jest równoodległy od prostych przechodzących przez punkty E, F i równoleglych do podstaw trapezu ABCD. Zatem również w tym przypadku odległości od punktu P do prostych AD i BC są jednakowe. Powtarzając końcówkę rozumowania z poprzedniego przypadku dostajemy tezę.

(wp, jwr)

L Olimpiada Matematyczna

Szkice rozwiązań zadań z zawodów stopnia drugiego Drugi dzień (27 lutego 1999 r.)

4. Oznaczmy przez K, L, M odpowiednio punkty przecięcia prostych AP, BP, CP z okręgiem opisanym na trójkącie ABC. Na mocy równości < ) BAK = < ) ACM długości łuków BK i AM są równe. Analogicznie, długości łuków KC i LA są równe. Odcinki LC, AK, MB są więc równoległe oraz mają wspólną symetralną, przechodzącą przez punkt O. Na tej symetralnej leży również punkt P, jako punkt przecięcia przekątnych MC i BL trapezu równoramiennego MBCL. Zatem w szczególności < ) AP O = 90^{∘}.

*  *  *  *  *

5. Niech f będzie funkcją spełniającą warunki zadania. Dla liczb x ≠ y dostajemy f^{49}(f(x)) = x ≠ y = f^{49}(f(y)), skąd f(x) ≠ f(y). Zatem f jest permutacją zbioru S. Oznaczmy przez r(x) (x ∈ S) najmniejszą liczbę całkowitą dodatnią taką, że f^{r(x)} (x) = x. Wówczas r(x) 5 oraz r(x)|50, skąd r(x) ∈ {1,2,5}.

Jeżeli istnieje taka liczba a ∈ S, że r(a) = 5, to liczby a, f(a), f^{2}(a), f^{3}(a), f^{4}(a) są różne; wyczerpują więc zbiór S. Wtedy dla dowolnej liczby x ∈ S, r(x) = 5. Funkcja f jest więc jednoznacznie wyznaczona przez permutację (f(1),f^{2}(1),f^{3}(1),f^{4}(1)) zbioru {2,3,4,5}; zatem może być określona na 4! =24 sposoby.

Jeżeli dla wszystkich x ∈ S zachodzi r(x) = 1, to f jest funkcją identycznościową. Taka funkcja jest jedna.

Pozostał do rozpatrzenia przypadek, w którym największa wartość osiągana przez funkcję r wynosi 2. Niech więc a będzie takim elementem zbioru S, że r(a) = 2. Wtedy także r(b) = 2, gdzie b = f(a).

Jeżeli r(x) = 1 dla wszystkich x ∈ S \{a,b}, to f jest wyznaczona przez wybór dwuelementowego podzbioru \{a,b\} zbioru S, co można uczynić na \binom{5}{2} =10 sposobów.

Jeżeli natomiast istnieje taka liczba c ∈ S \{a,b}, że r(c) = 2, to przyjmując d = f(c) oraz oznaczając przez e jedyny element zbioru S \{a,b,c,d}, mamy

f(a) = b, f(b) = a,  f(c) = d, f(d) = c,  f(e) = e.  (1)

Taka funkcja f jest wyznaczona przez wybór liczby e (można to zrobić na 5 sposobów) oraz podział zbioru S \{e} na dwa podzbiory dwuelementowe {a,b} i {c,d} (istnieją 3 takie podziały). Dostajemy więc 15 funkcji postaci (1).

Łącznie istnieje 50 funkcji spełniających warunki zadania.

*  *  *  *  *

6. Dla dowolnej liczby całkowitej m k liczba \binom{m}{k} jest całkowita. Stąd dla dowolnej liczby całkowitej dodatniej m liczba m(m− 1)(m− 2)...(m− k+ 1) jest podzielna przez k!. Istnieją więc takie liczby całkowite b_{1},b_{2},...,b_{k−1} , że dla dowolnej liczby całkowitej dodatniej m,

m^{k} ≡ b_{1}m+b_{2}m^{2} +...+b_{k−1} m^{k−1} (mod k!).

Mnożąc powyższą kongruencję przez a_{m}, a następnie dodając stronami od m = 1 do m = n otrzymujemy

a_{1} +2^{k}a_{2} +...+n^{k}a_{n} ≡ b_{1}(a_{1} +2a_{2} +...+na_{n})+b_{2}(a_{1} +2^{2}a_{2} +...+n^{2}a_{n})+...
...+b_{k−1} (a_{1} +2^{k−1} a_{2} +...+n^{k−1} a_{n}) =
= 0 (mod k!).

(wp, jwr)