XXXIV OM

XXXIV Olimpiada Matematyczna

Opracowanie rozwiązań: Maciej Bryński

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.

XXXIV OM - II etap

II etap XXXIV Olimpiady Matematycznej

XXXIV OM - II - Zadanie 1

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Na płaszczyźnie z ustalonym układem współrzędnych dany jest wielokąt wypukły, którego wszystkie wierzchołki mają współrzędne całkowite. Dowieść, że podwojone pole tego wielokąta jest liczbą całkowitą.

Rozwiązanie

Obieramy dowolny wierzchołek wielokąta i prowadzimy z niego wszystkie przekątne. Podzielimy w ten sposób dany wielokąt na trójkąty, których wierzchołki mają współrzędne całkowite. Wystarczy więc udowodnić rozważane twierdzenie dla trójkąta.

Przez wierzchołki trójkąta prowadzimy proste równolegle do osi układu współrzędnych. Proste te przecinają się w punktach o współrzędnych całkowitych, wyznaczają więc prostokąt, którego pole jest liczbą całkowitą i na którego bokach leżą wierzchołki rozważanego trójkąta. Trójkąt nasz powstaje z tego prostokąta przez odcięcie jednego, dwóch albo trzech trójkątów prostokątnych o przyprostokątnych równoległych do osi układu współrzędnych i wierzchołkach w punktach o współrzędnych całkowitych. Długości przyprostokątnych tych trójkątów są liczbami całkowitymi, więc pole każdego trójkąta (równe połowie iloczynu długości przyprostokątnych) jest liczbą całkowitą albo połową liczby całkowitej. Wobec tego pole $S$ rozważanego trójkąta jest różnicą liczby całkowitej (pola prostokąta) i jednej, dwóch albo trzech liczb, z których każda jest całkowita albo jest połową liczby całkowitej. Zatem $2S$ jest liczbą całkowitą.

XXXIV OM - II - Zadanie 2

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Dane są takie trzy liczby nieujemne $a, b, c$ , że suma każdych dwóch jest nie mniejsza od pozostałej. Dowieść, że

$ \sqrt{a+b-c} + \sqrt{a-b+c} + \sqrt{-a+b+c} \leq \sqrt{a} + \sqrt{b} + \sqrt{c}. $

Rozwiązanie

Zastosujemy nierówność

$ (1) \qquad \sqrt{\frac{x+y}{2}} \geq \frac{1}{2} (\sqrt{x}+\sqrt{y}), \ \textrm{dla} \ x, y > 0, $

którą można wyprowadzić z własności funkcji pierwiastkowej, albo udowodnić bezpośrednio jak następuje. Podnosząc obustronnie do kwadratu otrzymujemy nierówność równoważną

$ \frac{x+y}{2} \geq \frac{1}{4} (x+y+2\sqrt{xy}), $

którą następnie przekształcamy do postaci

$ \begin{split} \frac{x+y}{4} \geq \frac{\sqrt{xy}}{2},\\ x+y-2\sqrt{xy} \geq 0,\\ (\sqrt{x} - \sqrt{y})^2 \geq 0 \end{split} $

Cztery powyższe nierówności są oczywiście równoważne, a ostatnia jest spełniona dla wszystkich nieujemnych $x$ , $y$ .

W nierówności (1) podstawiamy $x= a+b-c$ , $y = a-b+c$ i dostajemy

$ \sqrt{a} \geq \frac{1}{2}(\sqrt{a+b-c}+\sqrt{a-b+c}). $

Analogicznie

$ \sqrt{b} \geq \frac{1}{2}(\sqrt{a+b-c}+\sqrt{-a+b+c}) $

$ \sqrt{c} \geq \frac{1}{2}(\sqrt{a-b+c}+\sqrt{-a+b+c}). $

Po dodaniu tych nierówności otrzymujemy

$ \sqrt{a} + \sqrt{b} + \sqrt{c} \geq \sqrt{a+b-c}+\sqrt{a-b+c}+\sqrt{-a+b+c}. $

Uwaga. Jeśli liczby $a$ , $b$ , $c$ są różne, to każdą z powyższych nierówności można zastąpić przez nierówność ostrą.

XXXIV OM - II - Zadanie 3

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Punkt $P$ leży wewnątrz trójkąta $ABC$ , przy czym $\measuredangle PAC = \measuredangle PBC$ . Punkty $L$ i $M$ są odpowiednio rzutami $P$ na proste $BC$ i $CA$ , $D$ jest środkiem odcinka $AB$ . Dowieść, że $DL = DM$ .

Rozwiązanie

Niech $Q$ i $R$ będą odpowiednio środkami odcinków $AP$ i $BP$ . Punkty te są środkami kół opisanych odpowiednio na trójkątach $APM$ i $BPL$ , skąd wynika, że

$ \measuredangle MQP = 2 \measuredangle PAM \ \textrm{i} \ \measuredangle LRP = 2 \measuredangle PBL $

jako kąty środkowe oparte na tych samych łukach, co odpowiednie kąty wpisane. Kąty $PAM$ i $PBL$ są równe z założenia. Zatem

$ \ (1) \qquad \measuredangle MQP= \measuredangle LRP. $

Odcinek $\overline{DQ}$ łączy środki boków $\overline{AB}$ i $\overline{AP}$ trójkąta $ABP$ . Wynika stąd, że $\overline{DQ} || \overline{BP}$ . Analogicznie $\overline{DR} || \overline{AP}$ . Wobec tego czworokąt $DRPQ$ jest równoległobokiem, skąd wynika, że

$ (2) \qquad \measuredangle PQD = \measuredangle PRD. $

Z równości (1) i (2) otrzymujemy, że $\measuredangle MQD = \measuredangle DRL$ . Ponadto $MQ= QP= DR$ oraz $LR= RP= DQ$ . Wynika stąd, że trójkąty $MQD$ i $DRL$ są przystające, a zatem $DM$ = $DL$ .

XXXIV OM - II - Zadanie 4

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Niech $a(k)$ będzie największą liczbą nieparzystą, przez którą dzieli się $k$ . Udowodnić, że

$ \sum_{k=1}^{2^n} a(k) = \frac{1}{3}(4^n+2). $

Rozwiązanie

Największy dzielnik nieparzysty $a(k)$ liczby $k$ możemy otrzymać w następujący sposób. Jeśli $k$ jest liczbą nieparzystą, to $a(k)= k$ , w przeciwnym razie rozważamy liczbę $k/2$ . Jeśli $k/2$ jest liczbą nieparzystą, to $a(k) = k/2$ , w przeciwnym razie rozważamy liczbę $k/4$ itd.

Wobec tego szukaną sumę otrzymamy odejmując od sumy kolejnych liczb naturalnych od $1$ do $2^n$ połówki co drugiego składnika, następnie czwarte części co czwartego składnika, dalej ósme części co ósmego składnika itd. Zatem

$ \begin{split} \sum_{k=1}^{2^n} a(k) &= \sum_{k=1}^{2^n} k - \sum_{k=1}^{2^{n-1}} k - \sum_{k=1}^{2^{n-2}}k - \ldots - \sum_{k=1}^{2} k -1 = \\&= \frac{2^n(2^n+1)}{2} - \frac{2^{n-1}(2^{n-1}+1)}{2} - \frac{2^{n-2}(2^{n-2}+1)}{2} - \ldots - \frac{2(2+1)}{2} -1=\\ &=\frac{1}{2} \cdot 2^n(2^n+1) - \sum_{m=0}^{n-1} \frac{1}{2} \cdot 2^m(2^m+1) =\\ &= \frac{1}{2} (4^n + 2^n) - \frac{1}{2} \sum_{m=0}^{n-1} 4^m - \frac{1}{2} \sum_{m=0}^{n-1} 2^m = \frac{1}{2} (4^n+2^n) - \frac{4^n-1}{4-1} - \frac{2^n-1}{2-1}=\\ &= \frac{1}{2} \left( 4^n+ 2^n - \frac{1}{3} \cdot 4^n + \frac{1}{3} - 2^n + 1 \right) = \frac{1}{3} (4^n+2). \end{split} $

XXXIV OM - II - Zadanie 5

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Dwusieczne kątów $CAB, ABC, BCA$ trójkąta $ABC$ przecinają okrąg opisany na tym trójkącie odpowiednio w punktach $K, L, M$ . Dowieść, że

$ AK+BL+CM > AB+BC+CA. $

Rozwiązanie

Oznaczmy krótko przez $A$ , $B$ , $C$ odpowiednie kąty trójkąta $ABC$ . Kąt $AKB$ jest oparty na tym samym łuku, co kąt $C$ , więc $\measuredangle AKB = C$ . W trójkącie $AKB$ suma miar kątów wynosi $180^\circ$ , więc $\measuredangle ABK = 180^\circ -\measuredangle AKB- \measuredangle BAK = 180^\circ - C- A/2$ . Stąd i z twierdzenia sinusów zastosowanego do trójkąta $ABK$ otrzymujemy $AK= 2R\sin \measuredangle ABK = 2R \sin (180^\circ -C-A/2) = 2R\sin \left( C+ \frac{A}{2} \right)$ . Analogicznie mamy

$ BL= 2R \sin \left(A+ \frac{B}{2} \right). $

$ CM = 2R \sin \left(B+ \frac{C}{2} \right), $

skąd wynika, że

$ AK+BL+CM = 2R \left( \sin \left(A + \frac{B}{2} \right) + \sin \left(B+\frac{C}{2} \right) +\sin \left(C+\frac{A}{2}\right) \right), $

natomiast

$ AB+BC+CA=2R(\sin A+\sin B+\sin C). $

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

$ \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), $

a ta ostatnia była treścią zadania 2 z zawodów stopnia pierwszego.

XXXIV OM - II - Zadanie 6

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Dla danej liczby $n$ oznaczmy przez $p_n$ prawdopodobieństwo tego, że przy losowym wyborze pary liczb całkowitych $k, m$ spełniających warunki $0 \leq k \leq m \leq 2^n$ (wybór każdej pary jest jednakowo prawdopodobny) liczba $\binom{m}{k}$ będzie parzysta. Obliczyć $\lim_{n\to \infty} p_n$ .

Rozwiązanie

Diagram na rysunku 10 przedstawia trójkąt Pascala napisany modulo $2$ , to znaczy mający zera i jedynki odpowiednio w tych miejscach, gdzie w zwykłym trójkącie Pascala występują liczby parzyste i nieparzyste. Jak w zwykłym trójkącie Pascala, tak i tu każdy element jest sumą elementów stojących bezpośrednio nad nim zgodnie z tabliczką dodawania modulo 2: $0+0=0$ , $0+1=1$ , $1+0=1$ , $1+1 = 0$ . Narysowane linie poziome dzielą ten trójkąt na warstwy:

warstwa $W_0$ złożona z wiersza nr $0$ ,
warstwa $W_1$ złożona z wiersza nr $1$ ,
warstwa $W_2$ złożona z wierszy nr $2$ i $3$ ,
warstwa $W_3$ złożona z wierszy nr $4$ , $5$ , $6$ , $7$ ,
$\ldots$
warstwa $W_j$ złożona z wierszy o numerach od $2^{j-1}$ do $2^j- 1$
$\ldots$

Udowodnimy indukcyjnie, że w dowolnej warstwie $W_j$ znajdują się dwa rozłączne trójkąty, z których każdy jest identyczny z trójkątem utworzonym przez warstwy $W_0, W_1, \ldots, W_{j-1}$ , oraz, że te dwa trójkąty są rozdzielone odwróconym trójkątem złożonym z samych zer; górny wiersz warstwy składa się ze skrajnych jedynek i samych zer, dolny zaś wiersz warstwy składa się z samych jedynek.

Dla $j= 1, 2, 3$ jest to widoczne z rysunków (linie ukośne wyznaczają podział na trójkąty, o których mowa). Załóżmy prawdziwość powyższych zależności dla pewnego $j$ i weźmy pod uwagę warstwę $W_{j + 1}$ .Z założenia indukcyjnego, ostatni wiersz warstwy $W_j$ ma postać $111\ldots 111$ , a zatem zgodnie z podaną wyżej regułą dodawania, pierwszy wiersz warstwy $W_{j + 1}$ ma postać $100\ldots 001$ . Skrajne jedynki tego wiersza dają początek dwóm nowym kopiom trójkąta Pascala, a pomiędzy nimi znajdują się zera. Warstwa $W_{j + 1}$ ma tyle samo wierszy, co warstwy $W_0, W_1, \ldots, W_j$ razem wzięte, więc w podstawie każdego z tych dwóch trójkątów na dole warstwy $W_{j + 1}$ znajdzie się ten sam układ cyfr, co i w ostatnim wierszu warstwy $W_j$ , czyli rząd jedynek. Wypełnią one ostatni rząd warstwy $W_{j + 1}$ . Kończy to dowód tezy indukcyjnej.

Liczba $p_n$ określona w zadaniu równa się stosunkowi liczby zer w wierszach o numerach od $0$ do $2^n$ do liczby wszystkich elementów tych wierszy. Wiersze te obejmują warstwy $W_0, W_1, \ldots, W_n$ oraz pierwszy wiersz warstwy $W_{n+1}$ . Z wyżej udowodnionego związku wynika, że w sumie warstw $W_0, \ldots, W_j$ jest trzykrotnie więcej jedynek, niż w sumie warstw $W_0, \ldots, W_{j-1}\ (j = 1, 2, 3,\ldots)$ , a ponieważ w warstwie $W_0$ jest jedna jedynka, więc w sumie warstw $W_0, \ldots, W_n$ jest $3^n$ jedynek. Doliczając do tego dwie skrajne jedynki następnego wiersza widzimy, że w rozważanym fragmencie trójkąta Pascala jest $a_n = 3^n+ 2$ jedynek. Wszystkich elementów jest w tym fragmencie $b_n= 1 + 2 + 3 + \ldots+ (2^n+ 1) = (2^n+ 1) (2^n+ 2) /2$ , a więc jest tam $b_n- a_n$ zer. Badane prawdopodobieństwo równa się

$ p_n = \frac{b_n-a_n}{b_n} = 1 - \frac{a_n}{b_n} = 1 - \frac{2(3^n+2)}{4^n+3 \cdot 2^n + 2} = 1 - \frac{2 \left( \left( \frac{3}{4}\right)^n + 2\left( \frac{1}{4} \right)^n \right)}{1 + 3 \left( \frac{2}{4}\right)^n + 2 \left( \frac{1}{4}^n \right)}. $

Stąd $\displaystyle \lim_{n \to \infty} p_n = 1$ .

XXXIV OM - III etap

III etap XXXIV Olimpiady Matematycznej

XXXIV - III - Zadanie 3

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

III

Rozważamy grę jednoosobową na nieskończonej szachownicy opartą na następującej regule. Jeżeli na dwóch polach mających wspólny bok stoją plony i następne pole jest puste (trzy omawiane pola leżą na jednej linii poziomej lub pionowej), to możemy te piony usunąć i postawić jeden pion na trzecim z tych pól (które było puste).
Udowodnić, że jeżeli w pozycji początkowej piony wypełniają prostokąt o liczbie pól podzielnej przez 3, to nie możemy otrzymać pozycji, w której na szachownicy jest tylko jeden pion.

Rozwiązanie

Wprowadzając na płaszczyźnie odpowiedni układ współrzędnych możemy każdemu polu szachownicy przyporządkować parę liczb całkowitych, przy czym dwóm polom sąsiednim leżącym w jednym wierszu pionowym odpowiadają liczby $(m, n)$ i $(m,n+1)$ , a dwóm sąsiednim polom leżącym w jednym wierszu poziomym - liczby $(m, n)$ i $(m+1, n)$ . Każdemu polu szachownicy możemy przyporządkować sumę $m+n$ jego współrzędnych, a następnie resztę z podzielenia $m+n$ przez $3$ . W ten sposób podzielimy wszystkie pola na trzy zbiory:

$ \begin{split} & A_0 = \{(m, n) \colon m+n \equiv 0 \pmod 3\},\\ & A_1 = \{(m, n) \colon m+n \equiv 0 \pmod 3\},\\ & A_2 = \{(m, n) \colon m+n \equiv 0 \pmod 3\}, \end{split} $

Piony ustawione w pozycji początkowej zajmują prostokąt o wymiarach $3k \times l$ lub $l \times 3k$ . W każdym wierszu równoległym do boku długości $3k$ co trzeci pion stoi na polu należącym do $A_0$ , co trzeci - na polu należącym do $A_1$ i co trzeci na polu należącym do $A_2$ (sumy współrzędnych kolejnych pól są kolejnymi liczbami całkowitymi). Wobec tego w pozycji początkowej liczby pionów zajmujących pola należące do $A_0$ , do $A_1$ i do $A_2$ są równe. Jeśli w pewnej pozycji dokładnie $a_0$ pionów zajmuje pola ze zbioru $A_0$ , $a_1$ pionów - pola ze zbioru $A_1$ , $a_2$ pionów - ze zbioru $A_2$ , że dokonując ruchu dozwolonego w grze zabieramy dwa piony, a dostawiamy trzeci, przy czym zmian tych dokonujemy na trzech polach występujących obok siebie w jednym rzędzie, więc każde z tych pól należy do innego ze zbiorów $A_0$ , $A_1$ , $A_2$ . Zatem dwie z liczb $a_0$ , $a_1$ , $a_2$ zmniejszają się o $1$ , pozostała liczba wzrasta o $1$ . Ponieważ w pozycji początkowej liczby pionów zajmujących pola ze zbiorów $A_0$ , $A_1$ , $A_2$ były równe, więc po każdej serii dozwolonych ruchów liczby pionów zajmujących pola ze zbiorów $A_0$ , $A_1$ , $A_2$ są liczbami tej samej parzystości. Jeśli na szachownicy jest tylko jeden pion, to należy on do jednego ze zbiorów $A_1$ np. do $A_0$ i wówczas sytuacji tej odpowiadają liczby $a_0 = 1$ , $a_1 = 0$ , $a_2 = 0$ , które nie są tej samej parzystości. Wynika stąd, że nie można doprowadzić do pozycji, w której na szachownicy pozostałby tylko jeden pion.

XXXIV OM - III - Zadanie 1

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

III

Na płaszczyźnie dany jest $n$ -kąt wypukły $P_1, \ldots, P_n$ oraz punkt $Q$ w jego wnętrzu nie należący do żadnej przekątnej. Dowieść, że jeśli $n$ jest liczbą parzystą, to liczba trójkątów $P_iP_jP_k$ ( $i,j,k= 1,2,\ldots,n$ ), które zawierają punkt $Q$ jest parzysta.

Rozwiązanie

Rozważmy najpierw czworokąt wypukły $ABCD$ i punkt $K$ w jego wnętrzu nie należący do żadnej przekątnej. Punkt $K$ należy do jednej z dwóch półpłaszczyzn o krawędzi $AC$ . Wynika stąd, że punkt $K$ należy do dokładnie dwóch spośród trójkątów $ABC$ , $ABD$ , $ACD$ , $BCD$ (na rys. 11 punkt $K$ należy do trójkątów $ACD$ i $BCD$ ). Udowodniliśmy w ten sposób tezę twierdzenia dla $n = 4$ . Przypuśćmy, że $n$ jest liczbą parzystą większą od $4$ . Wybierając dowolne cztery wierzchołki $P_i$ , $P_j$ , $P_k$ , $P_l$ danego wielokąta otrzymamy czworokąt wypukły. Jeśli punkt $Q$ należy do tego czworokąta, to należy on do dwóch spośród trójkątów $P_iP_jP_k$ , $P_iP_jP_l$ , $P_iP_kP_l$ , $P_jP_kP_l$ ; jeśli punkt $Q$ nie należy do czworokąta, to nie należy również do żadnego z tych trójkątów. W każdym przypadku liczba trójkątów wyznaczonych przez wierzchołki $P_i$ , $P_j$ , $P_k$ , $P_l$ i zawierających punkt $Q$ jest parzysta. Dowolnie ustalony trójkąt $P_iP_jP_k$ jest zawarty w $n-3$ czworokątach o wierzchołkach będących wierzchołkami danego wielokąta. Wobec tego rozważając wszystkie czworokąty $P_iP_jP_kP_l$ i zawarte w nich trójkąty zawierające punkt $Q$ policzymy każdy trójkąt $(n-3)$ -krotnie. Dodając liczby trójkątów zawartych w czworokątach $P_iP_jP_kP_l$ i zawierających punkt $Q$ otrzymamy więc pewną liczbę parzystą równą $(n-3)t$ , gdzie $t$ jest liczbą trójkątów $P_iP_jP_k$ zawierających punkt $Q$ . Ponieważ $n-3$ jest liczbą nieparzystą (bo $n$ jest liczbą parzystą), więc liczba rozważanych trójkątów jest parzysta.

XXXIV OM - III - Zadanie 2

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

III

Dana jest liczba niewymierna $a$ należąca do przedziału $(0,1)$ i liczba naturalna $N$ . Udowodnić, że istnieją takie liczby naturalne $p, q, r, s$ , że

$ \frac{p}{q} < a < \frac{r}{s}, \; \frac{r}{s} - \frac{p}{q} < \frac{1}{N} \quad \text{oraz} \quad rq-ps=1. $

Rozwiązanie

Niech $k$ będzie największą liczbą naturalną spełniającą nierówność $\frac{1}{k} > a$ . Wobec tego

$ (1) \qquad \frac{1}{1+k} < a < \frac{1}{k}, $

a zatem przyjmując $p_0 = 1$ , $q_0= k+1$ , $r_0 = 1$ , $s_0=k$ mamy spełnioną nierówność

$ \frac{p_0}{q_0} < a < \frac{r_0}{s_0} $

oraz warunek $r_0q_0-p_0s_0 = 1$ , gdyż $1 \cdot (k+1)-1 \cdot k = 1$ . Jeżeli ponadto $\frac{1}{k} - \frac{1}{k+1} < \frac{1}{N}$ , to liczby $p_0$ , $q_0$ , $r_0$ , $s_0$ stanowią rozwiązanie zadania. Jeśli ostatnia nierówność nie jest spełniona to następujący lemat wskaże drogę do rozwiązania.

Lemat. Jeśli liczby naturalne $b$ , $c$ , $d$ , $e$ spełniają warunki

$ \frac{b}{c} < \frac{d}{e} \ \textrm{oraz} \ dc-be=1, $

$ \begin{split} & \frac{b}{c} < \frac{b+d}{c+e},\ (b+d)c - b(c+e) = 1,\ \frac{b+d}{c+e} - \frac{b}{c} = \frac{1}{(c+e)c}, \\ & \frac{b+d}{c+e} < \frac{d}{e},\ d(e+c)-(b+d)e=1,\ \frac{d}{e} - \frac{b+d}{c+e} = \frac{1}{e(c+e)}. \end{split} $

Dowód. $(b+d)c-b(c+e)= bc+dc-bc-be= dc-be = 1$ . Obliczamy różnicę

$ \frac{b+d}{c+e}- \frac{b}{c} = \frac{(b+d)c-b(c+e)}{(c+e)c} = \frac{1}{(c+e)c}, $

skąd oczywiście wynika, że $\displaystyle \frac{b}{c} < \frac{b+d}{c+e}$ . Pozostałe warunki otrzymujemy analogicznie.

Rozważamy cztery ciągi liczb naturalnych $(p_n)$ , $(q_n)$ , $(r_n)$ , $(s_n)$ określone, jak następuje:

$ \begin{split} p_0 = 1,\ q_0 = k+1,\ r_0=1, s_0 = k,\\ p_{n+1} = p_n,\ q_{n + 1} = q_n, r_{n+1} = p_n+r_n,\ s_{n + 1} = q_n+s_n, \end{split} $

gdy

$ \frac{p_n}{q_n} < a < \frac{p_n+r_n}{q_n+s_n} $

oraz

$ p_{n+1} = p_n+r_n,\ q_{n + 1}= q_n+s_n,\ r_{n + 1}= r_n, s_{n + 1} = s_n, $

gdy

$ \frac{p_n+r_n}{q_n+s_n} < a < \frac{r_n}{s_n} $

Z powyższego określenia wynika, na podstawie nierówności (1) i lematu, że liczby $p_n$ , $q_n$ , $r_n$ , $s_n$ spełniają warunki

$ \frac{p_n}{q_n} < a < \frac{r_n}{s_n},\ r_nq_n - p_ns_n=1 \ \textrm{oraz} \ \frac{r_n}{s_n}-\frac{p_n}{q_n}=\frac{1}{s_nq_n}. $

Iloczyny $q_ns_n$ tworzą ciąg ściśle rosnący, bowiem przy przejściu od $n$ do $n+ 1$ jeden z czynników zwiększa się, drugi zaś pozostaje nie zmieniony. Wobec tego wystarczy przyjąć tak duże $n$ , żeby zachodziła nierówność $s_nq_n > N$ . Liczby $p_n$ , $q_n$ , $r_n$ , $s_n$ spełniają wówczas warunki zadania.

XXXIV OM - III - Zadanie 4

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

III

Udowodnić, że jeżeli liczby naturalne $a, b, c, d$ spełniają równość $ab = cd$ , to

$ \frac{\mathrm{NWD}(a, c)\cdot \mathrm{NWD}(a, d)}{\mathrm{NWD}(a, b, c, d)} = a. $

Rozwiązanie

Udowodnimy najpierw, że dla dowolnych liczb naturalnych $k$ , $j$ , $m$ , $n$

$ (1) \qquad \mathrm{NWD}(k,l) \cdot \mathrm{NWD} (m, n) = \mathrm{NWD} (km, kn, lm, ln). $

Jeśli liczba pierwsza $p$ spełnia relacje $p^\alpha | \mathrm{NWD} (k, l)$ oraz $p^\beta | \mathrm{NWD} (m,n)$ , to $p^\alpha | k$ , $p^\alpha | l$ , $p^\beta | m$ , $p^\beta | n$ , więc $p^{\alpha+\beta}$ dzieli każdą z liczb $km$ , $kn$ , $lm$ , $ln$ . Stąd $p^{\alpha+\beta} | \mathrm{NWD} (km, kn, lm, ln)$ . Wobec tego $\mathrm{NWD} (k, l) \cdot \mathrm{NWD} (m, n) | \mathrm{NWD} (km, kn, lm, ln)$ .

Jeśli $p^\gamma | \mathrm{NWD} (km, kn, lm, ln)$ oraz $p^\alpha | \mathrm{NWD} (k, l)$ , ale $p^{\alpha + 1} not \mid \mathrm{NWD} (k, l)$ , to jedna z liczb $k$ , $l$ nie dzieli się przez $p^{\alpha+1}$ , np. $k= p^\alpha \cdot k_1$ , $p \not \mid k_1$ . Ponieważ $p^\gamma | km$ , $p^\gamma | kn$ , więc $p^{\gamma \cdot \alpha} | \mathrm{NWD}(m, n)$ .

Wynika stąd, że $p^\gamma | \mathrm{NWD} (k, l) \cdot \mathrm{NWD} (m, n)$ , więc $\mathrm{NWD} (km, kn, lm, ln) | \mathrm{NWD} (k, l) \cdot \mathrm{NWD} (m, n)$ .

Tym samym równość (1) została udowodniona. Podstawiając w tej równości $k = a$ , $l = c$ , $m = a$ , $n= d$ otrzymamy

$ \mathrm{NWD}(a, c) \cdot \mathrm{NWD}(a,d)= \mathrm{NWD} (a^2, ad, ac, cd). $

Wobec założenia $cd = ab$ dostajemy stąd

$ \mathrm{NWD} (a, c) \cdot \mathrm{NWD} (a, d) = \mathrm{NWD} (a^2, ad, ac, ab) = a \cdot \mathrm{NWD} (a, d, c, b) = a \cdot \mathrm{NWD} (a, b, c, d). $

XXXIV OM - III - Zadanie 5

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

III

Na płaszczyźnie dane są wektory $\overrightarrow{a_1}, \overrightarrow{a_2}, \overrightarrow{a_3}$ o długości 1. Dowieść, że można tak wybrać liczby $\varepsilon_1, \varepsilon_2, \varepsilon_3$ równe 1 lub 2, że długość wektora $\varepsilon_1\overrightarrow{a_1} + \varepsilon_2\overrightarrow{a_2} + \varepsilon_3\overrightarrow{a_3}$ jest nie mniejsza od 2.

Rozwiązanie

Zaczepmy w dowolnym punkcie $0$ wektory $\overrightarrow{a_1}$ , $\overrightarrow{a_2}$ , $\overrightarrow{a_3}$ . Wyznaczają one trzy proste przecinające się w punkcie $0$ . Wśród kątów wyznaczonych przez pary tych prostych istnieje kąt o mierze $\alpha$ nie większej od $\frac{\pi}{3}$ . Przypuśćmy, że jest to kąt między prostymi wyznaczonymi przez wektory $\overrightarrow{a_1}$ i $\overrightarrow{a_2}$ (w innym przypadku wystarczy zmienić numerację wektorów). Wobec tego jeden z kątów $\measuredangle (\overrightarrow{a_1}, \overrightarrow{a_2})$ , $\measuredangle (\overrightarrow{a_1}, -\overrightarrow{a_2})$ ma miarę $\alpha \in \left[0, \frac{\pi}{3} \right]$ .

Przyjmujemy $\varepsilon_2$ tak, by kąt $\measuredangle (\overrightarrow{a_1}\varepsilon_2 \overrightarrow{a_2})$ miał miarę $\alpha$ . Obliczmy iloczyn skalarny wektora $\overrightarrow{b}=\overrightarrow{a_1}+\varepsilon_2 \overrightarrow{a_2}$ przez siebie:

$ \begin{split} \overrightarrow{b_2}^2 = (\overrightarrow{a_1}+\varepsilon_2 \overrightarrow{a_2})^2 = |\overrightarrow{a_1}|^2 + |\overrightarrow{a_2}|^2 + 2 \overrightarrow{a_1} |\varepsilon_2 \overrightarrow{a_2} |=\\ 2 + 2 |\overrightarrow{a_1}| \cdot |\varepsilon_2 \overrightarrow{a_2}| \cdot \cos \alpha \geq 2 + 2 \cdot \frac{1}{2} = 3. \end{split} $

Wobec tego $|\overrightarrow{b}| \geq \sqrt{3}$ .

Zauważmy następnie, że

$ (\overrightarrow{b}+\overrightarrow{a_3})^2+ (b-\overrightarrow{a_3})^2 = \overrightarrow{b}^2 + 2\overrightarrow{b} \cdot \overrightarrow{a_3} + \overrightarrow{a_3}^2 +\overrightarrow{b}^2-2\overrightarrow{b} \cdot \overrightarrow{a_3} +\overrightarrow{a_3}^2 = 2|b|^2+2 \geq 2 \cdot 3+2= 8. $

Wobec tego jedna z liczb $(\overrightarrow{a_1}+ \varepsilon_2 \overrightarrow{a_2} +\overrightarrow{a_3})^2$ , $(\overrightarrow{a_1}+ \varepsilon_2 \overrightarrow{a_2} -\overrightarrow{a_3})^2$ nie jest mniejsza od $4$ . Przyjmujemy $\varepsilon_3$ tak, by $(a_1+ \varepsilon_2 a_2 +\varepsilon_3 a_3)^2 \geq 4$ . Wówczas $|a_1 + \varepsilon_2 a_2+\varepsilon_3a_3| \geq 2$ .

XXXIV OM - III - Zadanie 6

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

III

Wykazać, że jeśli wszystkie kąty dwuścienne czworościanu są ostre, to wszystkie jego ściany są trójkątami ostrokątnymi.

Rozwiązanie

Każdej ścianie przyporządkowujemy wektor jednostkowy prostopadły do niej i skierowany na zewnątrz czworościanu. Rozważmy dwie ściany tworzące kąt $\alpha$ . Wektory przyporządkowane tym ścianom tworzą kąt $\pi - \alpha$ (rys. 12). Wobec tego na to, by wszystkie kąty dwuścienne czworościanu były ostre, potrzeba i wystarcza, by kąty między każdą parą spośród wektorów $\overrightarrow{a}$ , $\overrightarrow{b}$ , $\overrightarrow{c}$ , $\overrightarrow{d}$ przyporządkowanych poszczególnym ścianom były rozwarte, a więc by

$ \overrightarrow{a} \cdot \overrightarrow{b} < 0, \overrightarrow{a} \cdot \overrightarrow{c} < 0, \overrightarrow{a} \cdot \overrightarrow{d} < 0, \overrightarrow{b} \cdot \overrightarrow{c} < 0, \overrightarrow{b} \cdot \overrightarrow{d} < 0, \overrightarrow{c} \cdot \overrightarrow{d} < 0. $

Załóżmy, że spełnione są powyższe nierówności. Udowodnimy, że każdy kąt płaski czworościanu jest ostry. Rozważmy kąt $ABC$ . Wektor $\overrightarrow{a}$ przyporządkowany ścianie $BCD$ jest prostopadły do prostej $BC$ . Wobec tego rzut $\overrightarrow{a}_{ABC}$ wektora $\overrightarrow{a}$ na płaszczyznę $ABC$ też jest prostopadły do prostej $BC$ . Podobnie wektor $\overrightarrow{c}$ przyporządkowany ścianie $ABD$ jest prostopadły do prostej $AB$ , więc jego rzut $\overrightarrow{c}_{ABC}$ na płaszczyznę $ABC$ jest prostopadły do $AB$ . Wynika stąd, że

$ \measuredangle (\overrightarrow{a}_{ABC} \cdot \overrightarrow{c}_{ABC} )= \pi - \measuredangle ABC. $

Wobec tego kąt $ABC$ jest ostry wtedy i tylko wtedy, gdy $\overrightarrow{a}_{ABC} \cdot \overrightarrow{c}_{ABC} < 0$ .

Wektory $\overrightarrow{a}$ , $\overrightarrow{b}$ , $\overrightarrow{c}$ , $\overrightarrow{d}$ mają długość $1$ , wobec tego (rys. 14)

$ \overrightarrow{a}_{ABC} = \overrightarrow{a} - (\overrightarrow{a} \cdot \overrightarrow{d} ) \cdot \overrightarrow{d},\ \overrightarrow{c}_{ABC} = \overrightarrow{c} - (\overrightarrow{c} \cdot \overrightarrow{d} ) \cdot \overrightarrow{d}. $

Stąd

$ \begin{split} &\overrightarrow{a}_{ABC} \cdot \overrightarrow{c}_{ABC} = (\overrightarrow{a} - (\overrightarrow{a} \cdot \overrightarrow{d} ) \cdot \overrightarrow{d}) \cdot (\overrightarrow{c} - (\overrightarrow{c} \cdot \overrightarrow{d} ) \cdot \overrightarrow{d}) =\\ &\qquad =\overrightarrow{a} \cdot \overrightarrow{c} - (\overrightarrow{c} \cdot \overrightarrow{d})(\overrightarrow{a} \cdot \overrightarrow{d}) - (\overrightarrow{a} \cdot \overrightarrow{d})(\overrightarrow{c} \cdot \overrightarrow{d}) - +(\overrightarrow{a} \cdot \overrightarrow{d})(\overrightarrow{c} \cdot \overrightarrow{d})(\overrightarrow{d} \cdot \overrightarrow{d})=\\ &\qquad =\overrightarrow{a} \cdot \overrightarrow{c} - (\overrightarrow{c} \cdot \overrightarrow{d})(\overrightarrow{a} \cdot \overrightarrow{d}) - (\overrightarrow{a} \cdot \overrightarrow{d})(\overrightarrow{c} \cdot \overrightarrow{d}) +(\overrightarrow{a} \cdot \overrightarrow{d})(\overrightarrow{c} \cdot \overrightarrow{d}) \cdot 1=\\ &\qquad =\overrightarrow{a} \cdot \overrightarrow{c} - (\overrightarrow{c} \cdot \overrightarrow{d})(\overrightarrow{a} \cdot \overrightarrow{d}) < 0, \end{split} $

bo każdy z występujących tu iloczynów skalarnych jest ujemny. Wykazaliśmy więc, że kąt $ABC$ jest ostry. Dla pozostałych kątów płaskich dowód jest analogiczny.