L OM - II etap

II etap L Olimpiady Matematycznej

Załącznik	Wielkość
L OM II etap - Zadania [1]	59.62 KB
L OM II etap - Rozwiązania [2]	76.06 KB

L OM - II - Zadanie 1

Zawody matematyczne:

L OM, 1998-1999

Etap:

Dana jest funkcja $f: \langle 0,1 \rangle \to \mathbb{R}$ taka, że $f(\frac{1}{n}) = (-1)^n$ dla $n = 1, 2,\ldots$ . Wykazać, że nie istnieją takie funkcje rosnące $g: \langle 0,1 \rangle \to \mathbb{R}$ , $h: \langle 0,1 \rangle \to \mathbb{R}$ , że $f = g - h$ .

Rozwiązanie

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 \in \mathbb{N}$ mamy

$ \begin{split} g\left(\frac{1}{2k+1}\right)&=f\left(\frac{1}{2k+1}\right)+h\left(\frac{1}{2k+1}\right)=\\ &=-1+h\left(\frac{1}{2k+1}\right)< - 1 +h\left(\frac{1}{2k}\right)=1+h\left(\frac{1}{2k}\right)-2=\\ &=f\left(\frac{1}{2k}\right)+h\left(\frac{1}{2k}\right)-2=g\left(\frac{1}{2k}\right)-2< g\left(\frac{1}{2k-1}\right)-2. \end{split} $

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

$ \begin{split} g(0) < g\left(\frac{1}{2k+1}\right) < & g\left(\frac{1}{2k-1}\right)-2 < g\left(\frac{1}{2k-3}\right)-4 < \ldots < \\ & < g\left(\frac{1}{3}\right)-2(k-1) < g(1)-2k. \end{split} $

Zatem $g(1)-g(0) > 2k$ dla dowolnego $k\in \mathbb{N}$ , co nie jest możliwe.

L OM - II - Zadanie 2

Zawody matematyczne:

L OM, 1998-1999

Etap:

Sześcian $S$ o krawędzi $2$ jest zbudowany z ośmiu sześcianów jednostkowych. Klockiem nazwiemy bryłę otrzymaną przez usunięcie z sześcianu $S$ jednego spośród ośmiu sześcianów jednostkowych. Sześcian $T$ o krawędzi $2^n$ jest zbudowany z $(2^n)^3$ sześcianów jednostkowych. Udowodnić, że po usunięciu z sześcianu $T$ dowolnego spośród $(2^n)^3$ sześcianów jednostkowych powstaje bryła, którą daje się szczelnie wypełnić klockami.

Rozwiązanie

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,\ldots,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,\ldots,C_7$ była sześcianem jednostkowym. Wówczas pozostanie nam do wypełnienia klockami osiem sześcianów $C_1,C_2,\ldots,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.

L OM - II - Zadanie 3

Zawody matematyczne:

L OM, 1998-1999

Etap:

Czworokąt wypukły $ABCD$ jest wpisany w okrąg. Punkty $E$ i $F$ leżą odpowiednio na bokach $AB$ i $CD$ , przy czym $AE: EB = CF: FD$ . Punkt $P$ leży na odcinku $EF$ i spełnia warunek $EP: PF = AB: CD$ . Udowodnić, że stosunek pól trójkątów $APD$ i $BPC$ nie zależy od wyboru punktów $E$ i $F$ .

Rozwiązanie

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 : FD$ , więc podobne są również trójkąty $ASE$ i $CSF$ . Stąd $\measuredangle DSE = \measuredangle CSF$ . Ponadto

$ \frac{SE}{SF}=\frac{SA}{SC}=\frac{AB}{CD}=\frac{PE}{PF}, $

skąd dostajemy $\measuredangle ESP = \measuredangle FSP$ . Zatem punkt $P$ jest równoodległy od prostych $AD$ i $BC$ . Stosunek pól trójkątów $APD$ i $BPC$ 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ównoległych 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ę.

L OM - II - Zadanie 4

Zawody matematyczne:

L OM, 1998-1999

Etap:

Punkt $P$ leży wewnątrz trójkąta $ABC$ i spełnia warunki: $\measuredangle PAB = \measuredangle PCA$ oraz $\measuredangle PAC = \measuredangle PBA$ . Punkt $O$ jest środkiem okręgu opisanego na trójkącie $ABC$ . Dowieść, że jeżeli $O \ne P$ , to kąt $APO$ jest prosty.

Rozwiązanie

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 $\measuredangle BAK = \measuredangle 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 $\measuredangle APO = 90^\circ$ .

L OM - II - Zadanie 5

Zawody matematyczne:

L OM, 1998-1999

Etap:

Niech $S = \{1, 2,3,4, 5\}$ . Wyznaczyć liczbę funkcji $f: S \to S$ spełniających równość $f^{50} (x) = x$ dla wszystkich $x \in S$ .

Uwaga: $f^{50}(x) = \underbrace{f \circ f \circ \ldots \circ f}_{50} (x)$ .

Rozwiązanie

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

Jeżeli istnieje taka liczba $a \in 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\in 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 \in 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 \in S \setminus \{a,b\}$ , to $f$ jest wyznaczona przez wybór dwuelementowego podzbioru $\{a,b\}$ zbioru $S$ , co można uczynić na ${5 \choose 2}=10$ sposobów.

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

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

Taka funkcja $f$ jest wyznaczona przez wybór liczby $e$ (można to zrobić na $5$ sposobów) oraz podział zbioru $S \setminus \{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.

L OM - II - Zadanie 6

Zawody matematyczne:

L OM, 1998-1999

Etap:

Dana jest liczba naturalna $k \geq 2$ oraz liczby całkowite $a_1, a_2,\ldots, a_n$ spełniające warunki

$ a_1 + 2^i a_2 + 3^i a_3 + \ldots + n^i a_n = 0\ \textrm{dla}\ i = 1, 2,\ldots, k-1. $

Dowieść, że liczba $a_1 + 2^k a_2 + 3^k a_3 + \ldots + n^k a_n$ jest podzielna przez $k!$ .

Rozwiązanie

Dla dowolnej liczby całkowitej $m \geq k$ liczba ${m \choose k}$ jest całkowita. Stąd dla dowolnej liczby całkowitej dodatniej $m$ liczba $m(m-1)(m-2)\ldots(m-k+1)$ jest podzielna przez $k!$ . Istnieją więc takie liczby całkowite $b_1,b_2,\ldots,b_{k-1}$ , że dla dowolnej liczby całkowitej dodatniej $m$ ,

$ m^k \equiv b_1m+b_2m^2 +\ldots+b_{k-1}m^{k-1} (\mathrm{mod}\ k!). $

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

$ \begin{split} a_1 +2^ka_2 +\ldots+n^ka_n \equiv & b_1(a_1 +2a_2 +\ldots+na_n)+b_2(a_1 +2^2a_2 +\ldots+n^2 a_n)+\ldots \\ &\qquad\ldots+b_{k-1}(a_1 +2^{k-1}a_2 +\ldots+n^{k-1}a_n)= \\ &= 0 (\mathrm{mod}\ k!). \end{split} $