XXXIV OM - I etap

I etap XXXIV Olimpiady Matematycznej

XXXIV OM - I - Zadanie 1

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

$A$ rzuca monetą $n$ razy, $B$ rzuca $n+1$ razy. Jakie jest prawdopodobieństwo tego, ze $B$ wyrzuci więcej orłów niż $A$ ?

Rozwiązanie

Rozważmy następujące zdarzenia. $Z_0$ - zdarzenie polegające na tym, że gracz $B$ wyrzucił orła więcej razy niż gracz $A$ , $Z_r$ - zdarzenie polegające na tym, że $B$ wyrzucił reszkę więcej razy niż gracz $A$ . Zdarzenia te są jednakowo prawdopodobne: gdy moneta jest symetryczna, to obojętne jest, którą stronę nazwiemy orłem, a którą reszką. Zatem $P(Z_0) = P(Z_r)$ . Niech teraz $a_0$ , $a_r$ $b_0$ , $b_r$ będą kolejno liczbą orłów i liczbą reszek wyrzuconych przez $A$ oraz liczbą orłów i liczbą reszek wyrzuconych przez $B$ . Zgodnie z warunkami zadania $a_0+ a_r = n$ , $b_0+b_r=n+1$ . Stąd, przez odjęcie stronami, $(b_0-a_0)+ (b_r-a_r) = 1$ . Z równości tej wynika, że jedna i tylko jedna z liczb $b_0-a_0$ i $b_r-a_r$ jest dodatnia, czyli, że zajść może i musi dokładnie jedno ze zdarzeń $Z_0$ i $Z_r$ . Innymi słowy zdarzenia te są rozłączne i wyczerpują wszystkie możliwości. Wobec tego $P(Z_0)=P(Z_r)= 1/2$ .

XXXIV OM - I - Zadanie 2

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Dowieść, że jeżeli $A, B, C$ są kątami trójkąta, to

$ \sin A + \sin B + \sin C < \sin\left(A + \frac{B}{2}\right) + \sin\left(B + \frac{C}{2}\right) + \sin\left(C + \frac{A}{2}\right). $

Rozwiązanie

Ponieważ $A+B+C = 180^\circ$ , więc $A+ \frac{B}{2} = 90^\circ + \frac{A-C}{2}$ i na podstawie wzorów redukcyjnych otrzymujemy $\sin \left( A + \frac{B}{2} \right) = cos \frac{A-C}{2}$ . Analogicznie stwierdzamy, że $\sin \left( B+ \frac{C}{2} \right) = \cos \frac{B-A}{2}$ , $\sin \left( C +\frac{A}{2} \right) = \cos \frac{C-B}{2}$ .

Z drugiej strony

$ \begin{split} \sin A + \sin B+\sin C &= \frac{1}{2} (\sin A + \sin B)+ \frac{1}{2}(\sin B+\sin C) + \frac{1}{2}(\sin C+ \sin A) = \\ &=\sin \frac{A+B}{2} \cos \frac{A-B}{2} + \sin \frac{B+C}{2} \cos \frac{B-C}{2} +\\ &\quad +\sin \frac{C+A}{2} \cos \frac{C-A}{2}=\\ &= \sin \left( 90^\circ - \frac{C}{2} \right) \cos \frac{A-B}{2}+ \\&\quad + \sin \left( 90^\circ - \frac{A}{2} \right) \cos \frac{B-C}{2} + \sin \left( 90^\circ - \frac{B}{2} \right) \cos \frac{C-A}{2}=\\ &=\cos \frac{C}{2} \cos \frac{A-B}{2} + \cos \frac{A}{2} \cos \frac{B-C}{2} + \cos \frac{B}{2} \cos \frac{C-A}{2} \end{split} $

Dana w zadaniu nierówność jest więc równoważna nierówności

$ \begin{split} \cos \frac{C}{2} \cos\frac{A-B}{2}+ \cos \frac{A}{2} \cos\frac{B-C}{2}+ \cos \frac{B}{2} \cos\frac{C-A}{2}<\qquad &\\ <\cos \frac{B-A}{2} + \cos \frac{C-B}{2} + \cos \frac{A-C}{2}.& \end{split} $

Dla dowodu tej ostatniej nierówności pokażemy, że każdy składnik występujący po lewej stronie jest mniejszy od odpowiedniego składnika po prawej stronie. Istotnie
$\cos \frac{A-B}{2} = \cos \frac{B-A}{2} > 0$ oraz $0 < \cos \frac{C}{2} < 1$ , bo każdy z kątów $A$ , $B$ , $C$ jest większy od $0^\circ$ i mniejszy od $180^\circ$ . Zatem $\cos \frac{C}{2} \cos \frac{A-B}{2} < \cos \frac{B-A}{2}$ . Analogicznie dostajemy $\cos \frac{A}{2} \cos \frac{B-C}{2} < \cos \frac{C-B}{2}$ , $\cos \frac{B}{2} \cos \frac{C-A}{2} < \cos \frac{A-C}{2}$ , co kończy dowód.

XXXIV OM - I - Zadanie 3

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Liczby $x_1, x_2$ są pierwiastkami równania $x^2+ax+b = 0$ , o współczynnikach całkowitych, przy czym $|x_1| < 1$ . Dowieść, że $\lim_{n\to \infty} \{x_2^n\} = 0$ , gdzie $\{t\}$ jest taką liczbą z przedziału $\langle -\frac{1}{2}, \frac{1}{2}\rangle$ , że $t+ \{t\}$ jest liczbą całkowitą.

Rozwiązanie

Dowód. Obwód sumy mnogościowej kół stycznych zewnętrznie o promieniach $r_1$ i $r_2$ równy jest sumie obwodów tych kół, wynosi więc $2\pi r_1 + 2 \pi r_2$ . Koło opisane na sumie mnogościowej rozważanych kół stycznych ma średnicę będącą sumą średnic tamtych kół. Wobec tego jego obwód wynosi $2\pi(r_1+r_2)$ .

Dowód. Obwód sumy mnogościowej $K_1 \cup K_2$ równy jest liczbie $2\pi(r_1+ r_2)$ zmniejszonej o obwód ,,soczewki'' będącej częścią wspólną tych kół ( $r_1$ , $r_2$ są odpowiednio promieniami kół $K_1$ i $K_2$ ). Obwód tej części wspólnej jest większy od obwodu koła wpisanego w nią, to jest największego koła w niej zawartego, bo spośród obszarów o danym polu najkrótszy obwód ma koło, a pole ,,soczewki'' jest większe od pola koła w nią wpisanego. Wobec tego obwód sumy $K_1 \cup K_2$ jest mniejszy od liczby $2\pi (r_1 + r_2-r_3)$ , gdzie $r_3$ jest promieniem koła wpisanego w soczewkę. Jeśli jednak $r_0$ jest promieniem koła $K_0$ , to $r_0 = r_2-r_3$ , więc obwód $K_1 \cup K_2$ jest mniejszy od liczby $2 \pi (r_1 + r_0)$ . (Liczba ta jest mniejsza od sumy obwodów $K_1$ i $K_2$ .)

Dowód tezy sformułowanej w zadaniu przeprowadzimy przez indukcję względem liczby kół umieszczonych we wnętrzu koła $K$ .

Obwód jednego koła leżącego wewnątrz koła $K$ oczywiście nie przekracza obwodu $K$ . Załóżmy, że dla pewnej liczby $n$ obwód sumy mnogościowej co najwyżej $n$ kół umieszczonych wewnątrz danego koła i mających środki na jego średnicy, nie przekracza obwodu tego koła. Rozważmy $n+1$ kół znajdujących się wewnątrz koła $K$ i mających środki na średnicy $K$ . Jeżeli wśród tych kół znajdują się takie, które zawierają się w innych, to obwód sumy mnogościowej tych kół jest w istocie równy obwodowi sumy mnogościowej co najwyżej $n$ kół. Stosuje się w tym przypadku założenie indukcyjne. Załóżmy teraz, że tak nie jest. Oznaczmy koła przez $K_1, K_2, \ldots, K_{n + 1}$ według kolejności leżenia ich środków na średnicy koła $K$ . Na mocy założenia indukcyjnego obwód sumy mnogościowej $K_1 \cup K_2 \cup \ldots \cup K_n$ nie przekracza obwodu koła opisanego na tej sumie. Jeżeli koło $K_{n +1}$ nie ma wspólnych punktów wewnętrznych z kołem $K_n$ , to wynika stąd, że obwód sumy $K_1 \cup K_2 \cup \ldots \cup K_{n + 1}$ nie przekracza obwodu $K$ .

Załóżmy, że koła $K_n$ i $K_{n+1}$ przecinają się i rozpatrzmy koło $K_0$ styczne wewnętrznie do $K_{n +1}$ oraz zewnętrznie do $K_n$ o środku leżącym na tej samej średnicy koła $K$ . Na mocy lematu 2 obwód sumy mnogościowej $K_n \cup K_{n+1}$ jest mniejszy od sumy obwodu koła $K_0$ i $K_{n + 1}$ . Niech $A$ , $B$ będą punktami wspólnymi okręgów kół $K_{n-1}$ , $K_n$ . Z powyższego wynika, że ograniczona punktami $A$ i $B$ część obwodu sumy $K_n \cup K_{n+1}$ jest mniejsza od sumy obwodu koła $K_0$ i stycznego do niego łuku okręgu koła $K_n$ o końcach w tych punktach. Wobec tego obwód sumy $K_1 \cup K_2 \cup \ldots \cup K_{n + 1}$ jest mniejszy od sumy obwodu $K_1 \cup K_2 \cup \ldots \cup K_n$ i obwodu koła $K_0$ . Oczywiście $K_0$ nie ma wspólnych punktów wewnętrznych z $K_n$ . Na podstawie rozważanego poprzednio przypadku ostatnia suma nie przekracza obwodu koła $K$ . Kończy to dowód kroku indukcyjnego.

Na mocy zasady indukcji twierdzenie jest prawdziwe dla dowolnej liczby okręgów.

XXXIV OM - I - Zadanie 4

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

We wnętrzu koła $K$ znajduje się $n$ kół, których środki leżą na średnicy $K$ . Wykazać, że obwód sumy mnogościowej tych kół nie przekracza obwodu $K$ .

Rozwiązanie

Udowodnimy najpierw dwa lematy
Lemat 1. Obwód sumy mnogościowej dwóch kół stycznych zewnętrznie równy jest obwodowi koła opisanego na tej sumie, to jest takiego koła, do którego oba dane koła są styczne wewnętrznie i o środku współliniowym z ich środkami.

Dowód. Obwód sumy mnogościowej kół stycznych zewnętrznie o promieniach $r_1$ i $r_2$ równy jest sumie obwodów tych kół, wynosi więc $2\pi r_1 + 2 \pi r_2$ . Koło opisane na sumie mnogościowej rozważanych kół stycznych ma średnicę będącą sumą średnic tamtych kół. Wobec tego jego obwód wynosi $2\pi(r_1+r_2)$ .

Lemat 2. Obwód sumy mnogościowej dwóch kół $K_1$ i $K_2$ , których okręgi przecinają się, jest mniejszy od sumy obwodu koła $K_1$ i obwodu koła $K_0$ stycznego zewnętrznie do $K_1$ oraz stycznego wewnętrznie do $K_2$ i mającego środek wspólliniowy ze środkami kół $K_1$ i $K_2$ .

Dowód. Obwód sumy mnogościowej $K_1 \cup K_2$ równy jest liczbie $2\pi(r_1+ r_2)$ zmniejszonej o obwód ,,soczewki'' będącej częścią wspólną tych kół ( $r_1$ , $r_2$ są odpowiednio promieniami kół $K_1$ i $K_2$ ). Obwód tej części wspólnej jest większy od obwodu koła wpisanego w nią, to jest największego koła w niej zawartego, bo spośród obszarów o danym polu najkrótszy obwód ma koło, a pole ,,soczewki'' jest większe od pola koła w nią wpisanego. Wobec tego obwód sumy $K_1 \cup K_2$ jest mniejszy od liczby $2\pi (r_1 + r_2-r_3)$ , gdzie $r_3$ jest promieniem koła wpisanego w soczewkę. Jeśli jednak $r_0$ jest promieniem koła $K_0$ , to $r_0 = r_2-r_3$ , więc obwód $K_1 \cup K_2$ jest mniejszy od liczby $2 \pi (r_1 + r_0)$ . (Liczba ta jest mniejsza od sumy obwodów $K_1$ i $K_2$ .)

Dowód tezy sformułowanej w zadaniu przeprowadzimy przez indukcję względem liczby kół umieszczonych we wnętrzu koła $K$ .

XXXIV OM - I - Zadanie 5

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Udowodnić istnienie liczby $C_0$ o tej własności, że dla każdego ciągu $x_1, x_2, \ldots, x_N$ liczb dodatnich i dla dowolnej liczby dodatniej $K$ , jeżeli liczba wyrazów $x_j$ nie mniejszych od $K$ jest nie większa od $\frac{N}{K}$ , to

$ \frac{1}{N} \sum_{j=1}^N \log x_j \leq C_0. $

Rozwiązanie

Przypuśćmy, że ciąg $x_1, x_2, \ldots, x_N$ spełnia podany warunek. Zmieniając w razie potrzeby porządek wyrazów, możemy założyć, że $x_1 \geq x_2 \geq \ldots \geq x_N$ . Pokażemy, że $x_j \leq N/j$ dla $j = 1,\ldots, N$ . Przypuśćmy, że tak nie jest, czyli, że dla pewnego numeru $m$ zachodzi nierówność $x_m > N/m$ . Weźmy dowolną liczbę $K$ taką, że $N/m < K < x_m$ . Zgodnie z założeniem liczba wyrazów $x_j$ większych od $K$ jest nie większa od $N/K$ , a więc jest mniejsza od $m$ . Otrzymujemy sprzeczność, bo $x_1,\ldots, x_m > K$ . Zatem mamy $x_j \leq N/j$ dla $j= 1,\ldots, N$ . Możemy teraz oszacować lewą stronę podanej w zadaniu nierówności:

$ L(N)= \frac{1}{N} \sum_{j=1}^N \log x_j \leq \frac{1}{N} \sum_{j=2}^N \log \frac{N}{j} = \frac{1}{N} \log \prod_{j=1}^N \frac{N}{j} = \frac{1}{N} \log \frac{N^N}{N!}. $

Udowodnimy przez indukcję, że dla dowolnej liczby naturalnej $N$ spełniona jest
nierówność $N^N/N! < e^N$ , gdzie $e$ jest granicą rosnącego ciągu $\left( \left(1+\frac{1}{n} \right) \right)$ . Dla $N = 1$ ostatnia nierówność jest spełniona. Załóżmy prawdziwość tej nierówności dla pewnego $N$ . Wówczas

$ \frac{(N+1)^{N+1}}{(N+1)!} = \frac{(N+1)^N(N+1)}{N!(N+1)} = \frac{N^N}{N!} \left( 1 + \frac{1}{N} \right)^N < \frac{N^N}{N!} \cdot e < e^N \cdot e = e^{N+1}, $

co kończy dowód indukcyjny. Kontynuując oszacowanie wielkości $L(N)$ dostajemy

$ L(N) \leq \frac{1}{N} \log \frac{N^N}{N!}< \frac{1}{N} \log e^N =\log e. $

Jako stałą $C_0$ możemy więc przyjąć liczbę $\log e$ .

Uwaga. W sformułowaniu zadania nie sprecyzowano, czy symbol $\log$ oznacza logarytm dziesiętny, czy logarytm naturalny (tj. logarytm o podstawie $e$ ). Nie ma to znaczenia. Teza jest słuszna dla logarytmów o dowolnej podstawie większej od $1$ .

XXXIV OM - I - Zadanie 6

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Wykazać, że dla dowolnego wielomianu $P$ wielomian $P\circ P \circ P \circ \ldots \circ P(x)-x$ dzieli się przez $P(x)-x$ .

Rozwiązanie

Kładąc $P(x)= a_nx^n + a_{n-1}x^{n-1} + \ldots +a_1x+a_0$ otrzymamy

$ \begin{split} P \circ P(x)-P(x) &= a_n (P(x)^n+- x^n)+ a_{n-1}P(x)^{n-1} + \ldots +a_1P(x)+a_0-\\ &\quad-a_nx^n-a_{n-1}x^{n-1}-\ldots-a_1x-a_0 =\\ &= a_n(P (x)^n-x^n)+ a_{n-1} (P(x)^{n-1} -x^{n-1}) + \ldots + a_1(P(x)- x). \end{split} $

Ponieważ każdy składnik ostatniej sumy można rozłożyć:

$ a_k(P(x)^k-x^k) = a_k(P(x)-x)(P(x)^{k-1} + P(x)^{k-2}x+\ldots+ P(x) \cdot x^{k-2}+ x^{k-1}), $

więc

$ P(x)-x|P \circ P(x)-P(x). $

Podstawiając w ostatniej relacji $P(x)$ w miejsce $x$ otrzymamy $P \circ P(x)-P(x) | P \circ P \circ P(x) - P \circ P(x)$ , skąd na mocy przechodniości relacji podzielności wynika, że $P(x)-x|P \circ P \circ P(x)-P \circ P(x)$ . Stąd dla $k= 1, 2, \ldots$ dostajemy

$ P(x)-x|\underbrace{P \circ P \circ \ldots \circ P}_k (x)- \underbrace{P \circ P \circ \ldots \circ P}_{k-1} (x) $

Wielomian $\underbrace{P \circ P \circ \ldots \circ P}_n (x) - x$ można przedstawić w postaci sumy

$ \begin{split} & \underbrace{P \circ P \circ \ldots \circ P}_n (x)- x = (\underbrace{P \circ P \circ \ldots \circ P}_n(x) - \underbrace{P \circ P \circ \ldots \circ P}_{n-1}(x))+ \\ & + \underbrace{(P \circ P \circ \ldots P}_{n-1}(x)-\underbrace{P \circ P \circ \ldots \circ P}_{n-2}(x))+ \ldots + (P \circ P(x)-P(x))+(P(x)-x) \end{split} $

Na mocy poprzednich rozważań każdy składnik tej sumy dzieli się przez $P(x) - x$ , skąd wynika, że $P(x) - x|\underbrace{P \circ P \circ \ldots \circ P}_n(x) - x$ .

XXXIV OM - I - Zadanie 7

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Niech $S_n$ będzie zbiorem ciągów długości $n$ o wyrazach $-1$ , $+1$ . Określamy funkcję $f: S_n - \{(-1, 1, 1,\ldots, 1)} \to S_n$ jak następuje: jeśli $(a_1, \ldots, a_n) \in S_n - \{(-1, 1, 1,\ldots, 1)\}$ i $k = \max_{1\leq j \leq n} \{j \;:\; a_1\cdot a_2\cdot \ldots \cdot a_j = 1\}$ , to $f(a_1,\ldots, a_n) = (a_1, \ldots, a_{k-1}, -a_k, a_{k+1}, \ldots, a_n)$ . Udowodnić, że

$ \underbrace{f\circ f\circ \ldots \circ f}_{2^n-1}(1, 1, \ldots, 1)= (-1,1,1, \ldots, 1). $

Rozwiązanie

Dla uproszczenia zapisu wprowadzimy symbol $f^{(k)}$ na oznaczenie $k$ -krotnej iteracji funkcji $f$ :

$ f^{(k)} = \underbrace{f \circ f \circ \ldots \circ f}_k $

Tezę zadania udowodnimy indukcyjnie. Określenie funkcji $f$ zależy oczywiście od liczby naturalnej $n$ . Tam, gdzie pomoże to uniknąć nieporozumień będziemy pisali $f_n$ zamiast $f$ aby wyeksponować wartość liczby naturalnej $n$ .

Udowodnimy najpierw dwa lematy.

Lemat 1. Jeśli $m$ , $n$ są liczbami naturalnymi i $f_n^{(2m)}(1, 1, \ldots, 1)= (a_1, a_2, \ldots, a_n)$ , to $a_1a_2 \ldots a_n=1$ .

Dowód. Z określenia funkcji $f$ wynika, że jeśli $f(b_1, b_2, \ldots, b_n)= (c_1, c_2, \ldots, c_n)$ , to $c_1c_2\ldots c_n = -b_1 b_2 \ldots b_n$ . Zatem parzystokrotne złożenie funkcji $f$ przyporządkowuje ciągowi $(1, 1,\ldots, 1)$ ciąg, którego wyrazy dają w iloczynie $1$ .

Lemat 2. Jeżeli $f_n^{(m)} (1,1,\ldots,1) = (a_1, a_2, \ldots, a_n)$ , to $f_{n+1}^{(2m)}(1, 1, \ldots,1)= (a_1, a_2, \ldots, a_n, a)$ , gdzie $a = 1$ lub $a = - 1$ .

Dowód. Zastosujemy indukcję względem $m$ .

Jeśli $m= 1$ , to $f_n(1, 1,\ldots, 1)= (1, 1,\ldots, 1, - 1)$ , natomiast $f_{n+1}^{(2)} (1,1,\ldots,1) = f_{n+1}(1,1,\ldots, 1,-1)= (1,1,\ldots,-1,-1)$ .

Załóżmy, że dla pewnego $m$ jeśli $f_n^{(m)}(1,1,\ldots, 1) =(a_1,a_2,\ldots,a_n)$ , to $f_{n+1}^{(2m)}(1,1,\ldots, 1) =(a_1, a_2,\ldots,a_n, a)$ . Z określenia funkcji $f$ wynika, że $f_n^{(m+1)}(1,1,\ldots, 1 =f_n(a_1, a_2, \ldots, a_n)= (a_1, a_2, \ldots, -a_k, \ldots, a_n)$ . Na podstawie lematu 1 $a_1a_2\ldots a_na= 1$ , zatem $f_{n+1}(a_1, a_2, \ldots, a_n, a)= (a_1, a_2, \ldots, a_n, -a)$ , więc przyjmując $a_{n + 1} = -a$ mamy $f_{n+1}(a_1,a_2,\ldots, a_n,a)= (a_1, a_2, \ldots, a_n, a_{n+1})$ . Ponieważ $a_1a_2\ldots a_{n + 1} = - 1$ , więc

$ \max_{1 \leq j \leq n+1} \{j \colon a_1a_2\ldots a_j = 1\}= \max_{1 \leq j \leq n} \{ j \colon a_1a_2\ldots a_j=1 \}, $

a stąd wynika, że $f_{n+1}(a_1, a_2, \ldots, a_{n+1})= (a_1,a_2,\ldots,-a_k, \ldots, a_{n+1})$ . Wobec tego $f_{n+1}^{(2(k+1))}(1, 1, \ldots, 1)= f_{n+1}^{(2)} (a_1, a_2, \ldots, a_n, -a_{n+1}) = (a_1, a_2, \ldots, -a_k, \ldots, a_n, a_{n+1})$ . Kończy to dowód kroku indukcyjnego. Na mocy zasady indukcji teza lematu jest spełniona dla każdego naturalnego $k$ .

Przystąpimy obecnie do dowodu twierdzenia sformułowanego w treści zadania.

Dla $n =2$ twierdzenie jest oczywiście spełnione.

Załóżmy dla pewnego $n$ , że

$ f_{n}^{(2^n-1)} (1,1,\ldots,1)=(-1, 1,1,\ldots, 1) $

Na podstawie lematu 2

$ f^{(2(2^n-1))}(1,1,\ldots,1) = (-1, 1, \ldots,1, a), $

gdzie $a = 1$ lub $a = -1$ .

Z lematu 1 wynika jednak, że $-1 \cdot 1 \cdot \ldots \cdot 1 \cdot a = 1$ , więc $a = - 1$ . Wobec tego

$ f_{n+1}^{(2^{n+1}-1)}(1,1,\ldots,1) = f_{n+1} f_{n+1}^{(2(2^{n-1}))}(1, 1, \ldots,1) = $

$ \quad = f_{n+1}(-1, 1, \ldots,1, -1) = (-1, 1, \ldots, 1). $

Na mocy zasady indukcji dla każdego $n$ jest $f^{2^{n-1}} (1,1,\ldots, 1)= (-1,1,\ldots, 1)$ .

XXXIV OM - I - Zadanie 8

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Rozstrzygnąć, czy w kuli o promieniu 1 zmieści się 20 czworościanów foremnych o krawędzi 1 mających wnętrza parami rozłączne.

Rozwiązanie

Rozważmy dwudziestościan foremny wpisany w kulę. Każda ściana tego dwudziestościanu jest trójkątem równobocznym o boku dłuższym od 1 (porównaj zadanie przygotowawcze E z XXXI Olimpiady Matematycznej). Wobec tego w trójkącie sferycznym ograniczonym łukami trzech kół wielkich poprowadzonych przez pary wierzchołków dowolnej ściany dwudziestościanu, istnieją trzy punkty będące wierzchołkami trójkąta równobocznego o boku długości 1. Ten trójkąt równoboczny przyjmujemy za podstawę czworościanu, którego wierzchołkiem jest środek kuli. Długość każdej krawędzi tego czworościanu wynosi $1$ . Zbudowane w ten sposób czworościany, mające podstawy w trójkątach sferycznych wyznaczonych przez różne ściany dwudziestościanu, nie mają wspólnych punktów wewnętrznych. Podaliśmy więc sposób umieszczenia w kuli o promieniu 1 dwudziestu czworościanów foremnych o krawędzi 1 mających wnętrza parami rozłączne.

XXXIV OM - I - Zadanie 9

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Liczby naturalne $m, n$ spełniają warunek $\sqrt{7} - \frac{m}{n}$ . Wykazać, że $\sqrt{7} - \frac{m}{n} > \frac{1}{mn}$ .

Rozwiązanie

Przypuśćmy, że liczby naturalne $m$ , $n$ spełniają warunki

$ \sqrt{7} - \frac{m}{n} > 0, \ \sqrt{7} - \frac{m}{n} \leq \frac{1}{mn}. $

Z tych warunków

$ \frac{m}{n} < \sqrt{7} \leq \frac{m}{n} + \frac{1}{mn}. $

mamy więc następujące nierówności

$ \frac{m^2}{n^2} < 7 \leq \frac{m^2}{n^2} + 2\cdot \frac{1}{n^2} + \frac{1}{m^2n^2}, \ m^2 < 7n^2 < m^2 + 2 + \frac{1}{m^2}. $

Ponieważ nic może zachodzić równość $m = 1$ , więc jest spełniona nierówność podwójna $m^2 < 7n^2 < m^2+3$ .

Wobec tego albo (1) $7n^2 = m^2+1$ albo $7n^2 = m^2+2$ . Pokażemy, że jest to niemożliwe. Liczba $m$ ma jedną z następujących postaci $m= 7k$ , $m= 7k \pm 1$ , $m= 7k \pm 2$ , $m= 7k \pm 3$ . Badając, jaką resztę daje $m^2$ przy dzieleniu przez $7$ stwierdzamy, że

$ \begin{split} & (7k)^2= 49k^2+0\\ & (7k \pm 1)^2 = 49k^2 \pm 14k+1 = 7a+1\\ & (7k \pm 2)^2 = 49k^2 \pm 28k+4 = 7b+4\\ & (7k \pm 3)^2 = 49k^2 \pm 42k+9 = 7c+2 \end{split} $

Zatem ani $m^2+1$ ani $m^2+2$ nie może być liczbą podzięlną przez $7$ wbrew warunkowi (I). Tak więc przypuszczenie, że $7 - \frac{m}{n} \leq\frac{1}{mn}$ doprowadziło do sprzeczności.

XXXIV OM - I - Zadanie 10

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Czy istnieją trzy punkty płaszczyzny o współrzędnych postaci $a+b\sqrt[3]{2}$ , gdzie $a, b$ są liczbami wymiernymi, o tej własności, że co najmniej jedna z odległości dowolnego punktu płaszczyzny od każdego z tych punktów jest liczbą niewymierną?

Rozwiązanie

Punkty takie istnieją. Pokażemy, że np. trójka punktów $A = (\sqrt[3]{2},0)$ , $B=(-\sqrt[3]{2},0)$ , $C = (0,0)$ ma żądaną własność. Przypuśćmy bowiem, że odległość pewnego punktu $P=(x,y)$ od każdego z punktów $A$ , $B$ , $C$ jest liczbą wymierną. Wobec tego wymierne są też liczby $PA^2 = (x-\sqrt[3]{2})^2+y^2$ , $PB^2 = (x+\sqrt[3]{2})^2+y^2$ , $PC^2 = x^2+y^2$ , a więc liczba $PA^2+PB^2-2PC^2 = (x^2-2\sqrt[3]{2}x+\sqrt[3]{4}+y^2) + (x^2+2\sqrt[3]{2}x+\sqrt[3]{4}+y^2)-2(x^2+y^2) = 2\sqrt[3]{4}$ musiałaby być wymierna - co nie jest prawdą. Otrzymana sprzeczność dowodzi, że co najmniej jedna z odległości $PA$ , $PB$ , $PC$ jest liczbą niewymierną.

XXXIV OM - I - Zadanie 11

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Wyznaczyć liczbę takich podzbiorów zbioru $\{1, 2, \ldots, n\}$ które nie zawierają dwóch kolejnych liczb.

Rozwiązanie

Dla $n= 1$ są dwa takie podzbiory $\emptyset$ , $\{1\}$ , dla $n = 2$ jest ich trzy: $\emptyset$ , $\{1\}$ , $\{2\}$ . Przypuśćmy, że $n > 2$ . Każdy podzbiór zbioru $\{1, 2,\ldots, n+1\}$ nie zawierający dwóch kolejnych liczb, do którego nie należy liczba $n+1$ jest podzbiorem żądanej postaci zbioru $\{1,2,\ldots, n\}$ . Każdy podzbiór zbioru $\{1, 2,\ldots, n+1\}$ nie zawierający dwóch kolejnych liczb, do którego należy liczba $n+1$ jest podzbiorem postaci $\{k_1, k_2,\ldots, k_m, n+1\}$ , przy czym liczby $k_1, k_2, \ldots, k_m$ są mniejsze od $n$ i nie ma wśród nich dwóch liczb kolejnych. Jeśli więc $a_n$ jest liczbą omawianych podzbiorów zbioru $\{1, 2,\ldots, n\}$ , to dla $n > 1$ jest

$ a_{n+1} = a_n + a_{n-1}. $

Ciąg $(a_n)$ spełnia poniższe warunki:

$ a_1 = 2,\ a_2 = 3,\ a_n = a_{n-1}+a_{n-2} \ \textrm{dla} \ n>2. $

Jest to ciąg Fibonacciego. Jak wiadomo (łatwo to zresztą sprawdzić przez indukcję), wyrazy tego ciągu można zadać jawnym wzorem

$ a_n = \frac{(1+\sqrt{5})^{n+2} - (1-\sqrt{5})^{n+1}}{2^{n+2} \sqrt{5}}. $

XXXIV OM - I - Zadanie 12

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Na czworościanie $ABCD$ opisujemy sferę. $\alpha, \beta, \gamma, \delta$ są płaszczyznami stycznymi do tej sfery odpowiednio w wierzchołkach $A, B, C, D$ , przy czym $\alpha \cap \beta = p$ , $\gamma \cap \delta = q$ i $p \cap CD \neq \emptyset$ . Udowodnić, że proste $q$ i $AB$ leżą w jednej płaszczyźnie.

Rozwiązanie

Niech $S$ i $E$ będą odpowiednio sferą opisaną na czworościanie $ABCD$ i punktem wspólnym prostych $p$ i $CD$ . Punkt $E$ leży poza odcinkiem $CD$ , można założyć, że należy on do półprostej $CD^\to$ , jak na rys. 4. Ponieważ $E \subset \alpha$ , więc prosta $AE$ jest styczna do $S$ , jest więc też styczna do okręgu opisanego na trójkącie $ACD$ . Jeśli $O$ jest środkiem okręgu, to ponieważ $2 \measuredangle DAO+ \measuredangle AOD = 180^\circ$ , więc $\measuredangle DAE = 90^\circ- \measuredangle DAO = 90^\circ-(90^\circ- (90^\circ - \frac{1}{2} \measuredangle AOD) = \frac{1}{2}\measuredangle AOD$ . Kąt $AOD$ jest kątem środkowym opartym na łuku $\overline{AD}$ , kąt $ACD$ jest kątem wpisanym opartym na tym samym łuku, więc $\measuredangle ACD = \frac{1}{2} \measuredangle AOD$ . Wobec tego

$ \measuredangle DAE= \measuredangle ACD. $

Trójkąty $EAD$ i $ECA$ mają wspólny kąt przy wierzchołku $E$ , są więc na mocy powyższej równości trójkątami podobnymi. Wynika stąd, że

$ \frac{EC}{EA} = \frac{AC}{AD} $

Ponieważ jednocześnie $E \in \beta$ , więc prosta $BE$ jest styczna do $S$ i do okręgu opisanego na trójkącie $BCD$ . Rozumując analogicznie otrzymamy proporcję

$ \frac{EC}{EB} = \frac{BC}{BD}. $

Z dwóch ostatnich równości wynika

$ (1) \qquad \frac{AC}{BC} = \frac{AD}{BD}, $

gdyż $EA = EB$ jako długości odcinków stycznych do sfery $S$ poprowadzonych z punktu $E$ .

Przypuśćmy, że jedna z płaszczyzn $\gamma$ i $\delta$ jest równoległa do prostej $AB$ . Załóżmy, że zachodzi relacja $\gamma || AB$ . Wówczas $AC = BC$ i z (1) wynika, że $AD = BD$ , a zatem $\sigma || AB$ . Otrzymujemy stąd, że $q =\gamma \cap \delta$ jest prostą równoległą do $AB$ . Wobec tego proste $q$ i $AB$ leżą w jednej płaszczyźnie.

Załóżmy, że prosta $AB$ nie jest równoległa do żadnej z płaszczyzn $\gamma$ i $\delta$ i $F$ , $G$ są odpowiednimi punktami przecięcia. Rozumując analogicznie jak na początku rozwiązania, otrzymujemy proporcje

$ \frac{FA}{FC} = \frac{AC}{BC} \ \textrm{i} \ \frac{GA}{GD} = \frac{AD}{BD} $

Zachodzą równości $FC = FB$ , $GD = GB$ , gdyż odcinki $\overline{FC}$ , $\overline{FB}$ , $\overline{GD}$ i $\overline{GB}$ poprowadzone odpowiednio z $F$ oraz $G$ są styczne do $S$ . Otrzymujemy więc na mocy (1) następującą równość

$ \frac{FA}{FB} = \frac{GA}{GB} $

Punkty $F$ i $G$ leżą na zewnątrz sfery $S$ , więc nie należą do odcinka $AB$ , a skoro należą do prostej $AB$ , to z powyższej równości wynika, że $F = G$ . Wobec tego $F \in \gamma \cap \delta = q$ . Zatem $F$ jest punktem wspólnym prostych $q$ i $AB$ , skąd wynika, że proste te leżą w jednej płaszczyźnie.