XXV OM

XXV Olimpiada Matematyczna

Opracowanie rozwiązań: Jerzy Browkin

XXV OM - I etap

I etap XXV Olimpiady Matematycznej

XXV - I - Zadanie 1

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

W czasie pierwszej wojny światowej toczyła się bitwa w pobliżu pewnego zamku. Jeden z pocisków rozbił stojącą u wejścia do zamku statuą rycerza z piką w ręku. Stało się to ostatniego dnia miesiąca. Iloczyn daty dnia, numeru miesiąca, wyrażonej w stopach długości piki, połowy wyrażonego w latach wieku dowódcy baterii strzelającej do zamku oraz połowy wyrażonego w latach czasu, jaki stała statua, równa sią 451 066. W którym roku postawiono statuę?

Rozwiązanie

Ostatnim dniem miesiąca może być tylko $28$ , $29$ , $30$ lub $31$ . Z tych liczb tylko $29$ jest dzielnikiem liczby $451 066 = 2 \cdot 7 \cdot 11 \cdot 29 \cdot 101$ . Zatem bitwa toczyła się $29$ lutego w roku przestępnym. W czasie pierwszej wojny światowej tylko rok $1916$ był przestępny. Z treści zadania wynika, że pewien dzielnik liczby $7 \cdot 11 \cdot 101$ jest połową wieku dowódcy baterii. Jedynie liczba $11$ spełnia ten warunek, a więc dowódca baterii miał $22$ lata. Długość piki jest dzielnikiem liczby $7 \cdot 101$ . Wynika stąd, że pika miała $7$ stóp długości. Zatem połowa czasu, jaki stała statua, jest równa $101$ lat. Postawiono ją więc $202$ lata przed rokiem $1916$ , tzn. w roku $1714$ .

XXV - I - Zadanie 2

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

Dowieść, że dla każdego $m$ naturalnego

$ \frac{(2m+1)2m(2m-1)\ldots (m+2)}{m!} < 2^{2m} $

Rozwiązanie

Mamy dowieść, że

$ (1) \qquad \binom{2m + 1}{m} < 2^{2m}. $

Ze wzoru $\displaystyle \binom{n}{k} = \binom{n}{n-k}$ , gdzie $0 \leq k \leq n$ , wynika w szczególności, że $\displaystyle \binom{2m+1}{m} = \binom{2m+1}{m+1}$ . Ze wzoru dwumianowego otrzymujemy

$ 2^{2m+1}= (1+1)^{2m+1} = \sum_{i=0}^{2m+1} \binom{2m + 1}{m} > \binom{2m+1}{m} + \binom{2m+1}{m+1} = 2 \binom{2m+1}{m}. $

Wynika stąd nierówność (1).

XXV - I - Zadanie 3

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

Udowodnić, że dwusieczne kątów utworzonych przez proste zawierające przeciwległe boki czworokąta wypukłego wpisanego w okrąg są odpowiednio równoległe do dwusiecznych kątów utworzonych przez proste zawierające przekątne tego czworokąta.

Rozwiązanie

Niech $A$ , $B$ , $C$ , $D$ będą kolejnymi wierzchołkami czworokąta wpisanego w okrąg. Niech $O$ będzie punktem przecięcia prostych $AB$ i $CD$ , a $k$ niech będzie dwusieczną kąta $\measuredangle AOD$ (rys. 12). Jeżeli $A'$ i $C'$ są obrazami punktów $A$ i $C$ odpowiednio w symetrii względem prostej $k$ , to proste $A'C'$ i $BD$ są równoległe. Mamy bowiem $\measuredangle OBD = \measuredangle ACO$ (jako kąty wpisane oparte na tym samym łuku) oraz $\measuredangle ACO = \measuredangle A'C'O$ (symetria zachowuje miary kątów). Zatem odpowiednie dwusieczne kątów wyznaczonych przez proste $AC$ i $BD$ oraz $AC$ i $A'C'$ są równoległe. Tą ostatnią dwusieczną jest prosta $k$ .

XXV - I - Zadanie 4

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

Dowieść, że jeśli $x_1, \ldots, x_n$ są takimi liczbami rzeczywistymi, że $\sum_{i=1}^n x_i = 0$ , to dla dowolnych liczb rzeczywistych $t_1, t_2, \ldots, t_n$ prawdziwa jest nierówność

$ \sum_{i=1}^n \sum_{j=1}^n (t_i-t_j)^2 x_ix_j $

Rozwiązanie

Ponieważ $\displaystyle \sum_{k=1}^n x_k = 0$ , więc

$ \begin{split} & \sum_{i=1}^n \sum_{j=1}^n (t_i - t_j)^2 x_ix_j = \sum_{i=1}^n \sum_{j=1}^n (t_i - t_j)^2 \left( t_i^2 - 2t_it_j + t_j^2 \right) x_ix_j =\\ &\quad=\sum_{i=1}^n t_i^2 x_i \sum_{j=1}^n x_j - 2 \sum_{i=1}^n t_i x_i \sum_{j=1}^n t_jx_j + \sum_{i=1}^n x_i \cdot \sum_{j=1}^n t_j^2x_j= -2 \left( \sum_{i=1}^n t_ix_i \right)^2 \leq 0. \end{split} $

XXV - I - Zadanie 5

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

Dowieść, że dla każdego $k$ , $k$ -te od końca cyfry w układzie dziesiętnym liczb $5, 5^2, 5^3, \ldots$ tworzą od pewnego miejsca ciąg okresowy.

Rozwiązanie

Niech $a_n$ będzie liczbą utworzoną z $k$ ostatnich cyfr liczby $5^n$ . Wystarczy dowieść, że ciąg $\{a_n\}$ jest okresowy. Liczba $a_n$ jest resztą z dzielenia liczby $5^n$ przez $10^k$ , tzn. $5^n = 10^k \cdot b_n + a_n$ , gdzie $b_n \geq 0$ i $0 \leq a_n < 10^k$ . Stąd $5^{n+1} = 5 \cdot 10^k \cdot bn + 5 \cdot a_n$ oraz $5^{n+1} = 10^k \cdot b_{n+1} + a_{n+1}$ . Zatem liczby $5^{n+1}$ i $5 \cdot a_n$ dają tę samą resztę $a_{n+1}$ z dzielenia przez $10^k$ . Wobec tego $a_{n+1}$ jest liczbą utworzoną z $k$ ostatnich cyfr liczby $5 \cdot a_n$ . Wynika stąd, że każdy wyraz ciągu $\{a_n\}$ jednoznacznie wyznacza wyraz następny. Ponieważ ciąg $\{a_n\}$ przybiera tylko skończoną liczbę wartości (nie więcej niż $10^k$ ), więc pewien wyraz ciągu się powtarza: $a_r = a_{r+t}$ dla pewnych naturalnych $r$ i $t$ . Wobec tego $a_{r+1} = a_{r+t+1}$ i ogólnie $a_{r+s} = a_{r+t+s}$ dla $s = 1, 2, \ldots$ . Ciąg $\{a_n\}$ jest więc od pewnego miejsca okresowy.

XXV - I - Zadanie 6

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

Udowodnić, że dla dowolnych liczb rzeczywistych $a, b, c$ pewna, wartość funkcji $f(x) = |a \sin x + b \sin 2x + c sin 4x|$ jest nie mniejsza od $\frac{1}{2}(|a| + |b| + |c|)$ .

Rozwiązanie

Ponieważ zmiana znaków liczb $a$ , $b$ , $c$ nie zmienia warunków zadania, więc bez zmniejszenia ogólności możemy przyjąć, że $a \geq 0$ . Wtedy w zależności od znaków liczb $b$ i $c$ następująca liczba $x$ spełnia warunki zadania: jeżeli $b \geq 0$ i $c \geq 0$ , to $x = \displaystyle \frac{\pi}{6}$ ; jeżeli $b \geq 0$ i $c \leq 0$ , to $x = \displaystyle \frac{\pi}{3}$ ; jeżeli $b \leq 0$ i $c \geq 0$ , to $x = \displaystyle \frac{2\pi}{3}$ ; jeżeli $b \leq 0$ i $c \leq 0$ , to $x = \displaystyle \frac{5\pi}{6}$ .

Rozpatrzymy na przykład ostatni przypadek, w pozostałych - dowód przebiega podobnie. Ponieważ $b \leq 0$ i $c \leq 0$ , więc

$ \begin{split} f\left( \frac{5}{6} \pi \right)&= \left| \frac{1}{2}a - \frac{\sqrt{3}}{2}b - \frac{\sqrt{3}}{2}c \right|= \left| \frac{1}{2}a + \frac{\sqrt{3}}{2}(-b) + \frac{\sqrt{3}}{2}(-c) \right|=\\ &=\frac{1}{2}a + \frac{\sqrt{3}}{2}(-b) + \frac{\sqrt{3}}{2}(-c) \geq \frac{1}{2}a + \frac{1}{2}(-b) + \frac{1}{2}(-c) = \frac{1}{2} (|a|+|b|+|c|). \end{split} $

XXV - I - Zadanie 7

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

Udowodnić, że jeżeli w trójkącie ostrokątnym każdą wysokość można za pomocą ruchu sztywnego przenieść wewnątrz trójkąta tak, aby jej spodek zajął miejsce wierzchołka, a wierzchołek miejsce spodka, to trójkąt jest równoboczny.

Rozwiązanie

Jeżeli $h$ jest długością pewnej wysokości trójkąta $ABC$ , to z warunków zadania wynika, że w trójkącie $ABC$ można umieścić odcinek o długości $h$ mający dowolny zadany z góry kierunek. Jeżeli trójkąt $ABC$ nie jest równoboczny, to długości pewnych jego wysokości są różne, np. $h_A > h_B$ . Wtedy nie można w tym trójkącie umieścić odcinka o długości $h_A$ , który byłby równoległy do wysokości poprowadzonej z punktu $B$ . Najdłuższym bowiem odcinkiem o tym kierunku zawartym w trójkącie $ABC$ jest wysokość poprowadzona z punktu $B$ , która ma długość $h_B$ . Zatem trójkąt $ABC$ spełniający warunki zadania jest równoboczny.

XXV - I - Zadanie 8

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

Dany jest wielościan wypukły i punkt $A$ w jego wnętrzu. Udowodnić, że istnieje taka ściana $S$ tego wielościanu, że rzut prostokątny punktu $A$ na jej płaszczyznę należy do $S$ .

Rozwiązanie

Niech $S$ będzie taką ścianą danego wielościanu, że odległość $d$ punktu $A$ od płaszczyzny ściany $S$ jest nie większa od odległości tego punktu od płaszczyzny każdej innej ściany wielościanu. Niech $k$ będzie półprostą o początku w punkcie $A$ prostopadłą do płaszczyzny ściany $S$ . Jeżeli półprosta $k$ nie przecina ściany $S$ , to przecina pewną inną ścianę $T$ danego wielościanu w punkcie $P$ . Z wypukłości danego wielościanu wynika, że punkty $A$ i $P$ należą do jednej półprzestrzeni wyznaczonej przez płaszczyznę ściany $S$ . Zatem $AP < d$ tym bardziej odległość punktu $A$ od płaszczyzny ściany $T$ jest mniejsza od $d$ . Otrzymana sprzeczność dowodzi, że półprostą $k$ przecina ścianę $S$ .

XXV - I - Zadanie 9

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

Zbiór dokumentów rozdzielono na $n$ części dając je do przechowania $n$ osobom, z których każda posiada telefon. Dowieść, że dla $n \geq 4$ wystarczy $2n - 4$ rozmów telefonicznych, aby po ich przeprowadzeniu każda z $n$ osób znała treść wszystkich dokumentów.

Rozwiązanie

Dla czterech osób $A$ , $B$ , $C$ , $D$ wystarczą cztery rozmowy. Mianowicie, najpierw $A$ i $B$ oraz $C$ i $D$ informują się nawzajem o posiadanych przez siebie dokumentach. Następnie $A$ i $C$ oraz $B$ i $D$ wymieniają między sobą posiadane informacje.

Jeżeli liczba osób $n$ przekracza $4$ , to ustalamy pewne $4$ osoby $A$ , $B$ , $C$ , $D$ . Najpierw każda z pozostałych $n - 4$ osób informuje $A$ o treści posiadanych przez siebie dokumentów. Potem osoby $A$ , $B$ , $C$ , $D$ przeprowadzają między sobą $4$ rozmowy (jak wyżej) i wymieniają posiadane przez siebie informacje. Wreszcie każda z pozostałych $n - 4$ osób dzwoni do $A$ i dowiaduje się od niej o treści wszystkich dokumentów.

Zostały przeprowadzone $(n - 4) + 4 + (n - 4) = 2n - 4$ rozmowy i każda z osób zna treść wszystkich dokumentów.

XXV - I - Zadanie 10

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

Każda przekątna pewnego pięciokąta wypukłego odcina od niego trójkąt o polu 1. Obliczyć pole tego pięciokąta.

Rozwiązanie

Niech $ABCDE$ będzie danym pięciokątem wypukłym, a $A'B'C'D'E'$ - takim pięciokątem foremnym, że pole trójkąta $A'B'C'$ jest równe $1$ . Ponieważ trójkąty $ABC$ i $ABE$ mają równe pola, więc odległości punktów $C$ i $E$ od prostej $AB$ są równe. Zatem $CE \parallel AB$ i podobnie każda przekątna pięciokąta $ABCDE$ jest równoległa do odpowiedniego boku.

Dla dowolnej trójki punktów niewspółliniowych istnieje takie przekształcenie afiniczne, które przeprowadza ją na dowolną inną trójkę punktów niewspółliniowych. Niech $\varphi$ będzie takim przekształceniem afinicznym płaszczyzny, że $\varphi(A) = A'$ , $\varphi(B) = B'$ i $\varphi(C) = = C'$ . Każde przekształcenie afiniczne zachowuje stosunek pól. Ponieważ pola trójkątów $ABC$ i $\varphi(A) \varphi(B) \varphi(C)$ są równe, więc przekształcenie $\varphi$ zachowuje pola.

Przekształcenie afiniczne zachowuje równoległość odcinków. Zatem $\varphi(C)\varphi(E) \parallel \varphi(A)\varphi(B)$ , czyli $C' \varphi(E) \parallel A'B'$ . Wobec tego $(E) \in C'E'$ i podobnie 9 $\varphi(D) \in A'D'$ . Ponadto mamy $\varphi(D)\varphi(E) \parallel A'C'$ i stąd $\varphi(D)\varphi(E) \parallel D'E'$ (rys. 13).

Gdyby $\varphi(D) \ne D'$ , to jeden z trójkątów $C'\varphi(D)\varphi(E)$ i $C'D'E'$ byłby ściśle zawarty w drugim. Jest to niemożliwe, ponieważ mają one równe pola. Stąd $\varphi(D) = D'$ i podobnie $\varphi(E) = E'$ . Zatem obrazem pięciokąta $ABCDE$ w przekształceniu $\varphi$ jest pięciokąt foremny $A'B'C'D'E'$ . Pola pięciokątów tych są więc równe.

To ostatnie pole łatwo jest obliczyć. Pole trójkąta $A'B'C'$ jest równe

$ 1 = \frac{1}{2} A'B' \cdot B'C' \sin \measuredangle A'B'C' = \frac{1}{2} a^2 \sin \frac{3}{5} \pi, $

gdzie $a = A'B'$ (rys. 14). Stąd $\displaystyle a^2 = \frac{2}{\sin \frac{3}{5}\pi}$ . Odległość $d$ boku $A'B'$ od środka pięciokąta foremnego jest równa $\displaystyle d = \frac{a}{2} \tan \frac{3}{10} \pi$ .

Zatem pole pięciokąta $A'B'C'D'E'$ jest równe

$ 5 \cdot \frac{1}{2} ad = \frac{5}{4} a^2 \tan \frac{3}{10} \pi = \frac{5}{4 \cos^2 \frac{3}{10} \pi } \approx 3,62. $

XXV - I - Zadanie 11

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

Niech $X_n$ i $Y_n$ bądą niezależnymi zmiennymi losowymi o tym samym rozkładzie $\left{ \left(\frac{k}{2^n}, \frac{1}{2^n}\right) : k = 0, 1, \ldots, 2^n-1\right}$ . Oznaczmy przez $p_n$ prawdopodobieństwo zdarzenia, że istnieje liczba rzeczywista $t$ spełniająca równanie $t^2 + X_n \cdot t + Y_n = 0$ . Obliczyć $\lim_{n\to\infty} p_n$ .

Rozwiązanie

Zdarzenie sprzyjające polega na tym, że wyróżnik trójmianu $t^2 + X_n t + Y_n$ jest liczbą nieujemną. Niech $\displaystyle X_n = \frac{r}{2^n}$ , $\displaystyle Y_n = \frac{s}{2^n}$ , gdzie $r, s = 0, 1, \ldots, 2^n - 1$ . Nierówność $X_n^2 - 4 Y_n \geq 0$ jest równoważna nierówności $r^2 - 4 \cdot 2^n s \geq 0$ , czyli

$ (1) \qquad 0 \leq s \leq \frac{r^2}{4 \cdot 2^n}. $

Znajdziemy więc liczbę takich par $(r, s)$ , dla których zachodzi (1). Dla dowolnego $a$ liczba rozwiązań nierówności $0 \leq x \leq a$ w liczbach całkowitych $x$ jest równa $[a] + 1$ , gdzie $[a]$ jest największą liczbą całkowitą nie przekraczającą $a$ . Zatem liczba par $(r, s)$ spełniających
(1) jest równa

$ A_n = \sum_{r=0}^{2^n-1} \left( \left[ \frac{r^2}{4 \cdot 2^n} \right] +1 \right). $

Rozważmy sumę

$ B_n = \sum_{r=0}^{2^n-1} \frac{r^2}{4 \cdot 2^n} = \frac{1}{4 \cdot 2^n} \sum_{r=0}^{2^n-1} r^2. $

Na mocy wzoru

$ 1^2 + 2^2 + \ldots + k^2 = \frac{1}{6} k(k+ 1)(2k+1) $

mamy

$ (2) \qquad B_n = \frac{1}{4 \cdot 2^n} \cdot \frac{1}{6}(2^n - 1) 2^n (2^{n+1} - 1) = \frac{1}{12} \left( 2^{2n} - 3 \cdot 2^{n-1} + \frac{1}{2} \right). $

Ponieważ dla dowolnej liczby rzeczywistej x zachodzi nierówność

$ x < [x] + 1 \leq x + 1, $

więc

$ (3) \qquad B_n < A_n \leq \sum_{r=0}^{2^n-1} \left( \frac{r^2}{4 \cdot 2^n} + 1 \right) = B_n + 2^n. $

Liczba wszystkich zdarzeń elementarnych, czyli rozważanych par $(r, s)$ , jest równa $2^{2n}$ . Wobec tego $\displaystyle p^n = \frac{A^n}{2^{2n}}$ i z (3) wynika, że

$ (4) \qquad \frac{B_n}{2^{2n}} < p_n \leq \frac{B_n}{2^{2n}} + \frac{1}{2^n}. $

Z (2) otrzymujemy, że $\displaystyle \lim_{n \to \infty} \frac{B_n}{2^{2n}} = \frac{1}{12}$ i wobec tego z (4) wnosimy, że $\displaystyle \lim_{n \to \infty} p_n = \frac{1}{12}$

XXV - I - Zadanie 12

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

Dowieść, że w dowolnym kącie trójściennym, w którym co najwyżej jeden kąt płaski jest prosty, trzy proste prostopadłe w wierzchołku kąta trójściennego do jego krawędzi i zawarte w płaszczyznach ścian przeciwległych do tych krawędzi są zawarte w jednej płaszczyźnie.

Rozwiązanie

Niech $a$ , $b$ , $c$ będą niezerowymi wektorami równoległymi do krawędzi danego kąta trójściennego. Żadne dwa z tych wektorów nie są więc równoległe. Z warunków zadania wynika, że co najmniej dwie z liczb $\lambda = bc$ , $\mu = ca$ , $\nu = ab$ są różne od zera, ponieważ co najwyżej jedna para wektorów z $a$ , $b$ , $c$ jest prostopadła. Zatem wektory

$ (1) \qquad r = \lambda a - \mu b, \quad s = \mu b - \nu c, \quad t = \nu c - \lambda a $

są niezerowe. Z (1) wynika, że $r + s = -t$ , czyli wektory $r$ , $s$ , $t$ są równoległe do jednej płaszczyzny. Mamy też $rc = \lambda ac - \mu bc = \lambda \mu - \mu \lambda = 0$ , tzn. wektory $r$ i $c$ są prostopadłe. Podobnie dowodzimy, że $s \bot a$ i $t \bot b$ .

Wobec tego prosta zawarta w płaszczyźnie równoległej do wektorów $a$ i $b$ i prostopadła do krawędzi równoległej do wektora $c$ ma kierunek wektora $r$ . Analogicznie dowodzimy, że pozostałe dwie proste, o których jest mowa w zadaniu, są równoległe odpowiednio do wektorów $s$ i $t$ .

Jak wykazaliśmy, wektory $r$ , $s$ , $t$ są równoległe do jednej płaszczyzny. Każda z prostych rozpatrywanych w zadaniu jest równoległa do jednego z tych wektorów i proste te mają punkt wspólny. Zatem te trzy proste są zawarte w jednej płaszczyźnie.

XXV OM - II etap

II etap XXV Olimpiady Matematycznej

XXV OM - II - Zadanie 1

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

Niech $Z$ będzie zbiorem $n$ -elementowym. Znaleźć liczbę takich par zbiorów $(A, B)$ , że $A$ zawiera się w $B$ i $B$ zawiera się w $Z$ . Przyjmujemy, że każdy zbiór zawiera także siebie i zbiór pusty.

Rozwiązanie

Jak wiadomo, jeżeli $0 \leq r \leq s$ , to liczba podzbiorów $r$ -elementowych zbioru $s$ -elementowego jest równa $\binom{s}{r}$ , a liczba
wszystkich podzbiorów zbioru $s$ -elementowego jest równa $2^s$ .

Podzbiór $k$ -elementowy $A$ , gdzie $0 \leq k \leq n$ , można wybrać ze zbioru $Z$ na $\binom{n}{k}$ sposobów. Po ustaleniu zbioru $A$ zbiór $B-A$ jest pewnym podzbiorem zbioru $Z-A$ , który ma $n - k$ elementów. Zbiór $B-A$ może więc być wybrany na $2^{n-k}$ sposobów. Różnym wyborom zbioru $B-A$ odpowiadają przy tym różne zbiory $B$ zawierające zbiór $A$ . Zatem liczba par zbiorów $(A,B)$ spełniających warunki zadania jest równa

$ \sum_{k=0}^n \binom{n}{k} 2^{n-k} = \sum_{k=0}^n \binom{n}{k} 1^k \cdot 2^{n-k} = (1+2)^n = 3^n $

na mocy wzoru dwumianowego.

XXV OM - II - Zadanie 2

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

Dowieść, że dla każdego $n = 2, 3, \ldots$ oraz dowolnych liczb rzeczywistych $t_1, t_2, \ldots, t_n$ , $s_1, s_2, \ldots, s_n$ , jeżeli

$ \sum_{i=1}^n t_i = 0, \text{ to } \sum_{i=1}^n\sum_{j=1}^n t_it_j |s_i-s_j| \leq 0. $

Rozwiązanie

Dokonując tej samej permutacji ciągów $t_1, t_2, \ldots,t_n$ i $s_1, s_2, \ldots, s_n$ nie zmieniamy warunków zadania. Możemy więc założyć, że ciąg $s_1, s_2, \ldots, s_n$ jest niemalejący.

Niech $a_k = s_{k+1} - s_k$ dla $k = 1, 2, \ldots, n-1$ . Wtedy dla $i <j$ mamy $s_j - s_i = (s_j - s_{j-1}) + (s_{j-1} - s_{j-2}) + \ldots + (s_{i+ 1} - s_i)$ .

Wobec tego

$ (1) \qquad |s_j - s_i | = \sum_{i \leq k < j} a_k \ \textrm{dla} \ i<j. $

W sumie

$ (2) \qquad \sum_{i=1}^n \sum_{j=1}^n t_i t_j |s_i - s_j | $

składnik odpowiadający parze wskaźników $(i,j)$ jest równy składnikowi odpowiadającemu parze $(j, i)$ . Ponadto, jeżeli $i = j$ , to składnik odpowiadający parze $(i,j)$ jest równy zeru. Wobec tego suma (2) jest równa

$ (3) \qquad 2 \sum_{1 \leq i < j \leq n} t_it_j |s_i - s_j |. $

Na mocy (1) sumę tę możemy zapisać w postaci

$ 2 \sum_{1 \leq i < j \leq n} t_it_j \sum_{i \leq k < j} a_k, $

czyli

$ (4) \qquad 2 \sum_{1 \leq i \leq k < j \leq n} t_it_j a_k. $

Suma składników w (4) odpowiadających ustalonym wartościom $i$ i $k$ jest równa

$ (5) \qquad \sum_{j=k+1}^n t_it_j a_k = t_i a_k \sum_{j=k+1}^n t_j = -t_i a_k \sum_{j=1}^k t_j, $

ponieważ $\displaystyle \sum_{j=1}^k t_j + \sum_{j=k+1}^n t_j = \sum_{j=1}^n t_j =0$ z założenia.

Wobec tego na mocy (5) suma (4) jest równa

$ \begin{split} 2 \sum_{1 \leq i \leq k < n} \sum_{j=k+1}^n t_i t_j a_k &= - 2 \sum_{1 \leq i \leq k < n} t_i a_k \sum_{j=1}^k t_j =- 2 \sum_{k=1}^{n-1} \sum_{i=1}^k \sum_{j=1}^k a_k t_i t_j =\\ &= - 2 \sum_{k=1}^{n-1} a_k \sum_{i=1}^k t_i \sum_{j=1}^k t_j =- 2 \sum_{k=1}^{n-1} a_k \left( \sum_{i=1}^k t_i \right)^2. \end{split} $

Ta ostatnia liczba jest niedodatnia, ponieważ każda z liczb $a_k$ jest nieujemna.

XXV OM - II - Zadanie 3

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

Udowodnić, że rzuty prostokątne wierzchołka $D$ czworościanu $ABCD$ na płaszczyzny dwusieczne kątów dwuściennych wewnętrznych i zewnętrznych przy krawędziach $\overline{AB}$ , $\overline{BC}$ i $\overline{CA}$ należą do jednej płaszczyzny.

Rozwiązanie

Płaszczyzna dwusieczna jest płaszczyzną symetrii kąta dwuściennego. Wobec tego obraz $D'$ wierzchołka $D$ w symetrii względem dowolnej z rozważanych płaszczyzn dwusiecznych należy do płaszczyzny $ABC$ . Wynika stąd, że jeżeli $P$ jest rzutem prostokątnym punktu $D$ na płaszczyznę dwusieczną, to $P$ jest środkiem odcinka $\overline{DD'}$ . Zatem punkt $P$ jest obrazem punktu $D'$ w jednokładności $\varphi$ o środku w punkcie $D$ i stosunku $\displaystyle \frac{1}{2}$ . Wobec tego rzuty punktu $P$ na wszystkie rozważane płaszczyzny dwusieczne należą do płaszczyzny będącej obrazem płaszczyzny $ABC$ w jednokładności $\varphi$ .

XXV OM - II - Zadanie 4

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

W czworokącie wypukłym $ABCD$ o polu $S$ każdy z boków podzielono na 3 równe części i poprowadzono odcinki łączące odpowiednie punkty podziału przeciwległych boków w ten sposób, że czworokąt został podzielony na 9 czworokątów. Dowieść, że suma pól następujących trzech czworokątów powstałych z podziału: zawierającego wierzchołek $A$ , środkowego i zawierającego wierzchołek $C$ równa jest $\frac{S}{3}$ .

Rozwiązanie

Udowodnimy najpierw
Lemat. Odcinek łączący odpowiednie punkty podziału przeciwległych boków czworokąta danego w zadaniu przecina się z analogicznymi odcinkami łączącymi odpowiednie punkty podziału pozostałych boków czworokąta w punktach, które dzielą ten odcinek na trzy równe części.

Dowód. Niech punkty $S$ , $Z$ , $W$ , $R$ odpowiednio dzielą boki $\overline{AB}$ , $\overline{BC}$ , $\overline{DC}$ , $\overline{AD}$ danego czworokąta $ABCD$ w stosunku $1 \colon 2$ (rys. 16). Niech $E$ będzie punktem przecięcia odcinków $\overline{RZ}$ i $\overline{SW}$ . Wystarczy dowieść, że punkt $E$ dzieli każdy z tych odcinków w stosunku $1 \colon 2$ .

Ponieważ

$ \frac{AR}{AD} = \frac{AS}{AB} = \frac{1}{3}, $

więc na mocy twierdzenia odwrotnego do twierdzenia Talesa mamy $RS \parallel DB$ . Wynika stąd, że trójkąty $ARS$ i $ADB$ są podobne w stosunku $1 \colon 3$ . Stąd

$ (1) \qquad \frac{RS}{DB} = \frac{1}{3}. $

Analogicznie z równości $\displaystyle \frac{CW}{CD} = \frac{CZ}{CB} = \frac{2}{3}$ wynika, że $WZ \parallel DB$ . Zatem trójkąty $CWZ$ i $CDB$ są podobne w stosunku $2 \colon 3$ . Stąd

$ (2) \qquad \frac{WZ}{DB} = \frac{2}{3}. $

Z (1) i (2) wynika, że $\displaystyle \frac{RS}{WZ} = \frac{1}{2}$ . Ponadto mamy $RS \parallel WZ$ . Zatem trójkąty $RSE$ i $ZWE$ są podobne w stosunku $1 \colon 2$ . W szczególności wynika stąd, że $\displaystyle \frac{RE}{EZ} = \frac{SE}{EW} = \frac{1}{2}$ .

Przystępujemy teraz do rozwiązania zadania. Niech punkty $R,G \in \overline{AD}$ , $W,P \in \overline{DC}$ , $Q,Z \in \overline{BC}$ , $S, H \in \overline{AB}$ dzielą odpowiednio każdy z odcinków $\overline{AD}$ , $\overline{DC}$ , $\overline{BC}$ , $\overline{AB}$ na trzy równe części (rys. 17). Wtedy z lematu wynika, że punkty $E, U \in \overline{RZ}$ , $T, F \in \overline{GQ}$ , $E, T \in \overline{WS}$ , $F,U \in \overline{HP}$ dzielą odpowiednio każdy z odcinków $\overline{RZ}$ , $\overline{GQ}$ , $\overline{WS}$ , $\overline{HP}$ na trzy równe części.

\spos{1} Ponieważ $RE = EU$ , $TE = ES$ , więc z twierdzenia odwrotnego do twierdzenia Talesa wynika, że $RS \parallel TU$ . Zatem trójkąty $ERS$ i $ETU$ są przystające. Stąd $RS = TU$ .

Dowodząc lematu wykazaliśmy, że $RS \parallel DB$ i $RS = \displaystyle \frac{1}{3} DB$ . Podobnie $PQ \parallel DB$ i $PQ = \displaystyle \frac{1}{3} DB$ . Mamy więc $TU \parallel RS \parallel DB \parallel PQ$ oraz

$ (3) \qquad PQ = RS = TU = \frac{1}{3} DB. $

Prowadząc wysokości w trójkątach

$ (4) \qquad ARS,\ ERS,\ ETU,\ FTU,\ FPQ,\ CPQ $

na podstawy odpowiednio $\overline{RS}$ , $\overline{TU}$ , $\overline{PQ}$ widzimy, że suma długości tych wysokości jest równa sumie długości $h'$ i $h''$ wysokości trójkątów $ABD$ i $CBD$ poprowadzonych na podstawę $\overline{DB}$ . Ponieważ długości podstaw trójkątów (4) są równe (na mocy (3) są one równe $\displaystyle \frac{1}{3} DB$ ), więc suma ich pól, czyli suma pól czworokątów $ARSE$ , $ETFU$ , $FPCQ$ jest równa połowie iloczynu liczby $\displaystyle \frac{1}{3} DB$ przez sumę ich wysokości, czyli liczbie

$ \frac{1}{2} (h' + h'') \frac{1}{3} DB = \frac{1}{3} \left( \frac{1}{2} h' \cdot DB + \frac{1}{2} h'' \cdot DB \right) = \frac{1}{3} (S_{ABD} + S_{CBD}) = \frac{1}{3} S_{ABCD}. $

Uwaga. Analogiczne twierdzenie jest prawdziwe w przypadku podziału boków czworokąta $ABCD$ na $n$ równych części, gdzie $n > 3$ . Wtedy suma pól czworokątów położonych na przekątnej jest równa $\displaystyle \frac{1}{n} S_{ABCD}$ .

XXV OM - II - Zadanie 5

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

Dane są liczby rzeczywiste $q,t \in \langle \frac{1}{2}; 1)$ , $t \in (0; 1 \rangle$ . Udowodnić, że istnieje taki rosnący ciąg liczb naturalnych ${n_k}$ ( $k = 1,2, \ldots$ ), że

$ t = \lim_{N\to \infty} \sum_{j=1}^N q^{n_j}. $

Rozwiązanie

Ciąg $\{n_k\}$ $(k = 1,2, \ldots)$ określamy indukcyjnie, jak następuje. Ponieważ $0 < q < 1$ , więc $q^0= 1$ oraz $\displaystyle \lim_{n \to \infty} q^n = 0$ . Dla każdej liczby $t$ należącej do przedziału $(0;\ 1 \rangle$ istnieje więc taka liczba naturalna $n_1$ , że

$ g^{n_1} < t \leq q^{n_1-1}. $

Wtedy

$ 0 < t - q^{n_1} \leq q^{n_1-1} - q^{n_1} = q^{n_1-1} (1 - q) \leq = q^{n_1}, $

ponieważ $1 - q \leq q$ dla $\displaystyle q \in \langle \frac{1}{2};\ 1)$ .

Załóżmy z kolei, że dla pewnej liczby naturalnej $k$ został już określony taki rosnący ciąg liczb naturalnych $n_1, n_2, \ldots, n_k$ , że

$ (1) \qquad 0 < t - \sum_{j=1}^k q^{n_j} \leq q^{n_k}. $

Jako $n_{k+1}$ przyjmujemy taką liczbę naturalną $m$ , że

$ (2) \qquad q^m < t - \sum_{j=1}^k q^{n_j} \leq q^{m-1}. $

Z (1) i (2) wynika, że $q^m < q^{n_k}$ , a więc $m > n_k$ , czyli $n_{k+1} > n_k$ . Ponadto z (2) otrzymujemy

$ 0 < t - \sum_{j=1}^{k+1} q^{n_j} = t - \sum_{j=1}^k q^{n_j} - q^{n_{k+1}} \leq q^{m-1} - q^m = q^{m-1} (1-q) \leq q^m = q^{n_{k+1}}, $

ponieważ $1 - q \leq q$ dla $q \in \langle \frac{1}{2};\ 1)$ .

Wobec tego na mocy zasady indukcji istnieje taki nieskończony rosnący ciąg liczb naturalnych $n_1, n_2,\ldots$ , że spełniony jest warunek (1) dla $k = 1, 2, \ldots$ .

Ponieważ $\displaystyle \lim_{n \to\infty} q^{n_k} = 0$ , więc z (1) wynika, że

$ \lim_{k \to \infty} (t - \sum_{j=1}^k q^{n_j}) = 0,\ \textrm{czyli}\ t = \lim_{k \to \infty} \sum_{j=1}^k q^{n_j} = \sum_{j=1}^\infty q^{n_j}. $

Uwaga. Ciąg $\{n_k \}$ spełniający warunki zadania na ogół nie jest wyznaczony jednoznacznie. Rozpatrzmy wielomian $f(x) = x^3 + x^2 - 1$ . Ma on pierwiastek w przedziale $\displaystyle \left( \frac{1}{2};\ 1 \right)$ , ponieważ na końcach tego przedziału $f(x)$ przybiera wartości przeciwnych znaków. Oznaczmy taki pierwiastek przez $q$ . Wtedy obliczając sumy szeregów geometrycznych otrzymujemy

$ \sum_{n=1}^\infty q^{2n} = \frac{q^2}{1-q^2} \ \textrm{oraz} \ \sum_{n=1}^\infty q^{3n-2} = \frac{q}{1-q^3}. $

Przy tym z równości $q^3 + q^2 - 1 = 0$ wynika, że

$ \frac{q^2}{1-q^2} = \frac{q^2}{q^3} = \frac{1}{q} \ \textrm{oraz} \ \frac{q}{1-q^3} = \frac{q}{q^2} = \frac{1}{q}. $

Zatem

$ \sum_{n=1}^\infty q^{2n} = \sum_{n=1}^\infty q^{3n-2}. $

XXV OM - II - Zadanie 6

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

Dany jest ciąg liczb całkowitych $a_1, a_2, \ldots, a_{2n+1}$ o następującej własności: po odrzuceniu dowolnego wyrazu pozostałe można podzielić na takie dwie grupy po $n$ wyrazów, że suma wyrazów w pierwszej grupie równa jest sumie wyrazów w drugiej. Dowieść, że wszystkie wyrazy ciągu są równe.

Rozwiązanie

\spos{1} Zauważmy najpierw, że jeżeli pewien ciąg liczb rzeczywistych

$ (1) \qquad a_1, a_2, \ldots, a_{2n + 1} $

spełnia warunki zadania, to również spełnia je każdy z ciągów

$ a_1 + k, a_2 + k, \ldots, a_{2n+1} + k, $

$ ka_1, ka_2, \ldots, ka_{2n+1}, $

gdzie $k$ jest dowolną liczbą rzeczywistą.

Przypuśćmy, że pewien ciąg (1) liczb całkowitych spełnia warunki zadania oraz $a_1 \ne a_2$ . Bez zmniejszenia ogólności możemy przyjąć, że $a_1 = 0$ . W przeciwnym bowiem razie do każdego wyrazu ciągu dodalibyśmy $-a_1$ . Wśród ciągów (1) o wyrazach całkowitych spełniających warunki zadania, $a_1 \ne a_2$ $a_1 = 0$ wybierzmy taki, w którym liczba $|a_2|$ ma minimalną wartość.

Po odrzuceniu wyrazu $a_1 = 0$ suma pozostałych wyrazów jest parzysta na mocy warunków zadania. Wobec tego suma wszystkich wyrazów ciągu (1) jest parzysta. Analogicznie, po odrzuceniu dowolnego wyrazu $a_j$ suma pozostałych wyrazów jest parzysta. Zatem dowolny wyraz $a_j$ ciągu (1) jest parzysty.

Wynika stąd, że wyrazy ciągu $b_1, b_2, \ldots, b_{2n+1}$ , gdzie $b_i = \displaystyle \frac{1}{2} a_i$ dla $i= 1,2,\ldots, 2n+1$ , są liczbami całkowitymi. Mamy $|b_2| = \displaystyle \frac{1}{2} |a_2| < |a_2|$ , ponieważ $a_2 \ne 0$ . Przeczy to minimalności liczby $|a_2|$ .

Uzyskana sprzeczność dowodzi, że w każdym ciągu liczb całkowitych (1) spełniającym warunki zadania wszystkie wyrazy są równe.

XXV OM - III etap

III etap XXV Olimpiady Matematycznej

XXV OM - III - Zadanie 1

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

III

W czworościanie $ABCD$ krawędź $\overline{AB}$ jest prostopadła do krawędzi $\overline{CD}$ i $\measuredangle ACB = \measuredangle ADB$ . Udowodnić, że płaszczyzna wyznaczona przez krawędź $\overline{AB}$ i środek krawędzi $\overline{CD}$ jest prostopadła do krawędzi $\overline{CD}$ .

Rozwiązanie

Udowodnimy najpierw
Lemat. Jeżeli proste $AB$ i $PQ$ przecinają się pod kątem prostym w punkcie $P$ , to liczba punktów półprostej $PQ^\to$ , z których widać odcinek $\overline{AB}$ pod kątem $\alpha$ , jest równa $0$ , $1$ lub $2$ .

Dowód. Jak wiadomo, zbiór punktów zawartych w półpłaszczyźnie o krawędzi $AB$ i zawierającej punkt $Q$ , z których widać odcinek $AB$ pod kątem $\alpha$ , jest łukiem pewnego okręgu. Ten łuk ma z półprostą $PQ^\to$ $0$ , $1$ lub $2$ punkty wspólne w zależności od położenia odcinka $AB$ względem punktu $P$ i od wielkości kąta $\alpha$ (rys. 19).

Wniosek. Niech prosta $AB$ będzie prostopadła do płaszczyzny $\pi$ . Zbiór punktów płaszczyzny $\pi$ , z których widać odcinek $\overline{AB}$ pod kątem
$\alpha(0 < \alpha < \pi)$ , jest pusty, jest okręgiem lub sumą dwóch okręgów współśrodkowych.

Dowód. Niech $P$ będzie punktem przecięcia prostej $AB$ z płaszczyzną $\pi$ , a $Q$ - dowolnym punktem płaszczyzny $\pi$ różnym od $P$ . Na mocy lematu półprosta $PQ^\to$ zawiera co najwyżej dwa punkty, z których widać odcinek $\overline{AB}$ pod kątem $\alpha$ . Przy obrocie dokoła prostej $AB$ punkty te utworzą co najwyżej dwa okręgi współśrodkowe i z każdego punktu tych okręgów widać odcinek $\overline{AB}$ pod kątem $\alpha$ . Na mocy lematu z każdego punktu płaszczyzny $\pi$ nie należącego do tych okręgów widać odcinek $\overline{AB}$ pod kątem różnym od $\alpha$ .

Przechodzimy do rozwiązania zadania. Niech $\pi$ będzie płaszczyzną prostopadłą do $AB$ i zawierającą odcinek $\overline{CD}$ i niech $P$ będzie punktem przecięcia prostej $AB$ z płaszczyzn $\pi$ . Na mocy warunków zadania z punktów $C$ i $D$ widać odcinek $\overline{AB}$ pod tym samym kątem. Z wniosku z lematu wynika więc, że albo

1) punkty $C$ i $D$ należą do jednego okręgu o środku w punkcie $P$ , albo,

2) punkty $C$ i $D$ należą do różnych okręgów o środku w punkcie $P$ .

W pierwszym przypadku symetralna odcinka $\overline{CD}$ zawiera punkt $P$
i wobec tego płaszczyzna wyznaczona przez krawędź $\overline{AB}$ i środek krawędzi $\overline{CD}$ jest prostopadła do krawędzi $\overline{CD}$ . W drugim przypadku symetralna odcinka $\overline{CD}$ nie zawiera punktu $P$ . Gdyby bowiem go zawierała, to punkt $P$ byłby równo odległy od punktów $C$ i $D$ . Punkty te należałyby więc do jednego okręgu o środku w punkcie $P$ , co nie ma miejsca. Wobec tego płaszczyzna wyznaczona przez krawędź $\overline{AB}$ i środek krawędzi $\overline{CD}$ nie zawiera symetralnej odcinka $\overline{CD}$ , a więc nie jest do niego prostopadła.

Teza zadania w drugim przypadku nie jest więc prawdziwa. Przypadek pierwszy ma miejsce na przykład wtedy, gdy punkt $P$ należy do odcinka $\overline{AB}$ , a więc na przykład, gdy kąt $\measuredangle ACB$ jest rozwarty.

XXV OM - III - Zadanie 2

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

III

Łososie płynąc w górę rzeki muszą pokonać dwa wodospady. Prawdopodobieństwo, że łosoś pokona pierwszy wodospad w danej próbie, wynosi $p > 0$ , a prawdopodobieństwo pokonania drugiego wodospadu w danej próbie wynosi $q > 0$ . Zakładamy, że kolejne próby forsowania wodospadów są niezależne. Obliczyć prawdopodobieństwo zdarzenia, ze łosoś nie przebędzie pierwszego wodospadu w $n$ próbach pod warunkiem, że w $n$ próbach nie pokona obu wodospadów.

Rozwiązanie

Niech $A_n$ będzie zdarzeniem polegającym na tym, że łosoś nie pokona pierwszego wodospadu w $n$ próbach, a $B_n$ - zdarzeniem, że łosoś nie pokona obu wodospadów w $n$ próbach. Ponieważ prawdopodobieństwo tego, że łosoś nie pokona pierwszego wodospadu w jednej próbie równe jest $1 - p$ , a próby są niezależne, więc

$ (1) \qquad p(A_n) = (1-p)^n. $

Zdarzenie $B_n$ zajdzie wtedy, gdy albo łosoś nie pokona w $n$ próbach pierwszego wodospadu, albo pokona w $k$ -tej próbie $(1 \leq k \leq n)$ pierwszy wodospad i nie pokona w pozostałych $n-k$ próbach drugiego wodospadu. Zatem

$ (2) \qquad p(B_n) = (1 -p)^n + \sum_{k=1}^n (1 -p)^{k-1} p(1 - q)^{n-k}. $

Jeżeli $p = q$ , to wzór (2) przybiera postać

$ (3) \qquad p(B_n) = (1 -p)^n + \sum_{k=1}^n (1 -p)^{n-1} p = (1-p)^n + np(l -p)^{n-1}. $

Jeżeli $q= 1$ , to

$ (4) \qquad p(B_n) = (1 - p)^n + (1 - p)^{n-1}p = (1 - p)^{n-1}. $

W tym przypadku bowiem łosoś pokonałby drugi wodospad już w pierwszej próbie. Zatem zdarzenie $B_n$ zajdzie wtedy, gdy łosoś nie pokona pierwszego wodospadu w $n$ próbach lub pokona go dopiero w $n$ -tej próbie.

Wzór (4) wynika zresztą ze wzoru (2), jeżeli przyjmiemy, że $0^0 = 1$ .

Wreszcie, jeżeli $p \ne q$ i $q < 1$ , to korzystając ze wzoru na sumę wyrazów ciągu geometrycznego przekształcamy (2) jak następuje:

$ \begin{split} p(B_n) & = (1-p)^n + p(1-q)^{n-1} \frac{1- \left( \frac{1-p}{1-q} \right)^n}{1-\frac{1-p}{1-q}} = (1-p)^n + \\ & + (1-q)^{n} \frac{p}{p-q} \left[ 1- \left( \frac{1-p}{1-q} \right)^n \right] = (1-p)^n + \frac{p}{p-q} ((1-q)^n - (1-p)^n)=\\ & = \frac{p(1-q)^n q(1-p)^n}{p-q}. \end{split} $

Mamy więc w tym przypadku

$ (5) \qquad p (B_n) = \frac{p(1-q)^n - q(1-p)^n}{p-q}. $

Jeżeli zajdzie zdarzenie $A_n$ , to tym bardziej zajdzie zdarzenie $B_n$ . Wobec tego $A_n \cap B_n = A_n$ . Ze wzoru na prawdopodobieństwo warunkowe otrzymujemy więc

$ (6) \qquad P(A_n \mid B_n) = \frac{A_n \cap B_n)}{p(B_n)} = \frac{P(A_n)}{P(B_n)}. $

Jeżeli $n = 1$ , to z warunków zadania wynika, że $p(A_n) = 1 - p$ oraz $p(B_n) = 1$ . Zatem z (6) otrzymujemy, że $p(A_n \mid B_n)= 1 -p$ . W dalszym ciągu będziemy więc zakładali, że $n \geq 2$ .

Zauważmy, że jeżeli $p \ne q$ , to $p(B_n) \ne 0$ . Istotnie, gdyby $p(B_n) = 0$ , to ze wzoru (5) otrzymalibyśmy $p(1 - q)^n = q(1 -p)^n$ . Stąd

$ (7) \qquad \frac{p}{q} = \left( \frac{1-p}{1-q} \right)^n. $

Jeżeli na przykład $p < q$ , to $1 - p > 1 - q$ i równość (7) nie może mieć miejsca. Podobnie dowodzimy, że (7) nie zachodzi, gdy $p> q$ .

Jeżeli $p = q$ i p $(B_n) = 0$ , to ze wzoru (3) wynika, ze $p = 1$ . Zatem w przypadku, gdy $p = q = 1$ (i tylko w tym przypadku) prawdopodobieństwo warunkowe $p(A_n \mid B_n)$ nie istnieje. Obliczamy je w pozostałych przypadkach.

Jeżeli $p = q < 1$ , to z (1), (3) i (6) otrzymujemy

$ (8) \qquad p(A_n \mid B_n) = \frac{1 - p}{1-p+np} = \frac{1-p}{1+(n-1)p}. $

Jeżeli $p < q = 1$ , to z (1), (4-) i (6) otrzymujemy

$ (9) \qquad p(A_n \mid B_n) = 1-p. $

Jeżeli $p \ne q < 1$ , to z (1), (5) i (6) otrzymujemy

$ (10) \qquad p(A_n \mid B_n) =\frac{(1-p)^n(p-q)}{p(1-q)^n - q(1-p)^n}= \frac{(p-q) \left( \frac{1-p}{1-q} \right)^n}{p-g} \left( \frac{1-p}{1-q} \right)^n. $

Uwaga.

Zbadamy w każdym z przypadków liczbę $g= \lim_{n \to \infty} p(A_n \mid B_n)$ .

Jeżeli $p = q < 1$ , to ze wzoru (8) wynika, że $g = 0$ .

Jeżeli $p < q = 1$ , to ze wzoru (9) wynika, że $g = 1 - p = 1 -\displaystyle \frac{p}{1}$ .

Jeżeli $p < q < 1$ , to $1 - p > 1 - q$ i $\displaystyle \lim_{n \to \infty} \left( \frac{1-p}{1-q} \right)^n = \infty$ . Zatem z (10) wynika, że $\displaystyle g = \frac{p-q}{-q} = 1- \frac{p}{q}$ .

Jeżeli $q < p \leq 1$ , to $1 - p < l - q$ i $\displaystyle \lim_{n \to \infty} \left( \frac{1-p}{1-q} \right)^n = 0$ . Wobec tego z (10) otrzymujemy, że $g = 0$ .

Zawsze więc $g = \max \left(0, 1 - \frac{p}{q} \right)$ .

XXV OM - III - Zadanie 3

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

III

Niech $r$ będzie liczbą naturalną. Dowieść, że trójmian $x^2 - rx - 1$ nie jest dzielnikiem żadnego wielomianu $p(x) \neq 0$ o współczynnikach całkowitych, mniejszych co do wartości bezwzględnej od $r$ .

Rozwiązanie

\spos{1} Przypuśćmy, że wielomian

$ p(x) = a_0 + a_1x + \ldots + a_nx^n $

gdzie $a_n \ne 0$ , ma współczynniki całkowite, co do wartości bezwzględnej mniejsze od $r$ i jest podzielny przez trójmian $f(x) = x^2 - rx - 1$ . Mamy więc

$ (1) \qquad p = f \cdot h, $

gdzie wielomian $h(x) = b_0 + b_1x + \ldots + b_{n-2}x^{n-2}$ ma współczynniki całkowite, co wynika z algorytmu dzielenia wielomianów.

Porównując odpowiednie współczynniki wielomianów po obu stronach równości (1) otrzymujemy

$(2.0) \qquad a_0 = -b_0,$

$(2.1) \qquad a_1 = -b_1-rb_0,$

$(2.2) \qquad a_2 = -b_2 - rb_1 + b_0,$

$\vdots$

$(2.k) \qquad a_k = -b_k - rb_{k-1} + b_{k-2} \ \textrm{dla} \ k = 2, 3, \ldots,n- 2,$

$\vdots$

$(2.n-2) \qquad a_{n-2} = - b_{n-2} - rb_{n-3} + b_{n-4},$

$(2.n-1) \qquad a_{n-1} = - rb_{n-2} + b_{n-3},$

$(2.n) \qquad a_n = b_{n-2}$

Z równości (2.n) wynika, że $b_{n-2} \ne 0$ . Następnie z (2.n - 1) wynika, że $b_{n-3} \ne 0$ i liczby $b_{n-2}$ i $b_{n-3}$ mają ten sam znak. W przeciwnym razie bowiem mielibyśmy $|a_{n-1}| = |-rb_{n-2} + b_{n-3}| = |-rb_{n-2}| + |b_{n-3}| \geq r |b_{n-2}| \geq r$ , co przeczy założeniu, że $|a_{n-1} < r$ . Analogicznie z (2.n - 2) otrzymujemy, że $b_{n-4} \ne 0$ i liczby $b_{n-3}$ i $b_{n-4}$ mają ten sam znak. W przeciwnym razie bowiem mielibyśmy $|a_{n-2}| = |-b_{n-2} - rb_{n-3} + b_{n-4}| = |-b_{n-2}| + |-rb_{n-3}| + |b_{n-4}| \geq r |b_{n-3}| \geq r|$ , co przeczy założeniu, że $|a_{n-2}| < r$ .

Ogólnie, jeżeli dla pewnej liczby $k \in \{2, 3, \ldots, n - 2\}$ liczby $b_k$ i $b_{k-1}$ mają ten sam znak, to $b_{k-2} \ne 0$ i liczby $b_{k-1}$ i $b_{k-2}$ mają ten sam znak. W przeciwnym razie bowiem z równości (2.k) otrzymalibyśmy, że $|a_k| = |-b_k| + |-rb_{k-1}|+ |b_{k-2}| \geq r$ , co przeczy założeniu.

Na mocy zasady indukcji wynika stąd, że liczby $b_{n-2}, b_{n-3}, \ldots, b_1, b_0$ są różne od zera i mają jednakowe znaki. Wobec tego z równości (2.1) otrzymujemy $|a_1| = |-b_1 -rb_0| = |b_1| + |rb_0| \geq r$ , co przeczy założeniu.

Uzyskana sprzeczność dowodzi, że taki wielomian $p$ nie istnieje.

Uwaga 1. W powyższym rozwiązaniu nie korzystaliśmy w sposób istotny z założenia, że wielomian $p$ ma współczynniki całkowite. Wystarczyłoby zakładać, że $|p_n| \geq 1$ oraz $|p_i| \leq r - 1$ dla $r = 0, 1,\ldots, n-1$ .

Uwaga 2. Niech $H(f)$ będzie największą wartością bezwzględną współczynników wielomianu $f$ . Dla wielomianów o współczynnikach całkowitych na ogół nie jest prawdą, że jeżeli $f \mid g$ , to $H(f) \leq H(g)$ . Na przykład

$ (1 - x + x^2)(1 + 2x + x^2) = 1 + x + x^3 + x^4. $

XXV OM - III - Zadanie 4

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

III

Dowieść, że dla każdej liczby naturalnej $n$ i ciągu liczb rzeczywistych $a_1, a_2, \ldots, a_n$ istnieje liczba naturalna $k \leq n$ taka, że

$ \left| \sum_{i=1}^k a_i - \sum_{i=k+1}^n a_i \right| \leq \max_{1\leq i \leq n} |a_i| $

Rozwiązanie

Udowodnimy najpierw
Lemat. Jeżeli $\varepsilon \geq 0$ i liczby rzeczywiste $s_1, s_2, \ldots, s_n$ spełniają warunki

$ (1) \qquad |s_1| \leq \varepsilon, | s_{i+1} - s_i | \leq \varepsilon \ \textrm{dla}\ i = 1, 2, \ldots, n - 1,\ \textrm{to istnieje taka liczba naturalna}\ k \leq n,\ \textrm{że} $

$ (2) \qquad \left| s_k - \frac{1}{2}s_n \right| \leq \frac{1}{2}\varepsilon. $

Dowód. Jeżeli $\varepsilon = 0$ , to z (1) wynika, że $s_1 = s_2 = \ldots = s_n = 0$ , i teza lematu oczywiście zachodzi. Załóżmy więc, że $\varepsilon > 0$ .

Niech $a$ będzie najmniejszą, a $b$ - największą z liczb $s_1, s_2, \ldots, s_n$ . Liczby $s_1, s_2, \ldots, s_n$ dzielą więc przedział $\langle a;\ b \rangle$ na odcinki o długości nie przekraczającej $\varepsilon$ . Każda liczba tego przedziału jest więc odległa od jednej z liczb $s_1, s_2, \ldots, s_n$ nie więcej niż o $\displaystyle \frac{1}{2} \varepsilon$ . W szczególności, jeżeli $\displaystyle \frac{1}{2} s_n \in \langle a;\ b \rangle$ , to spełniony jest warunek (2). Załóżmy więc, że $\displaystyle \frac{1}{2} s_n \ne \langle a;\ b \rangle$ .

Z określenia liczb $a$ i $b$ wynika, że $s_n \in \langle a ;\ b \rangle$ . Jeżeli $0 \in \langle a ;\ b \rangle$ , to otrzymujemy, że $\displaystyle \frac{1}{2} s_n \in \langle a ;\ b \rangle$ , co przeczy przyjętemu założeniu.

Niech więc $0 \not \in \langle a ;\ b \rangle$ . Wtedy liczby $s_1, s_2, \ldots, s_n$ mają jednakowy znak. Ponieważ zmiana znaku wszystkich tych liczb nie zmienia warunków lematu, więc możemy założyć, że liczby $s_1, s_2, \ldots, s_n$ są dodatnie. Mamy więc

$ (3) \qquad 0 < a \leq s_n \leq b $

oraz

$ (4) \qquad 0 < a \leq s_1 \leq \varepsilon. $

Ponieważ $\displaystyle \frac{1}{2} s_n \not \in \langle a ;\ b \rangle$ , więc z (3) wynika, że $\displaystyle 0 < \frac{1}{2}a \leq \frac{1}{2} s_n < a$ . Zatem na mocy (4) mamy $\displaystyle | a - \frac{1}{2} s_n | < \frac{1}{2} a \leq \frac{1}{2} \varepsilon$ . Liczba $a$ jest jedną z liczb $s_1, s_2, \ldots, s_n$ . Otrzymaliśmy więc warunek (2).

Z lematu wynika natychmiast teza zadania. Wystarczy mianowicie przyjąć $\varepsilon = \max_{1 \leq i \leq n} | a_i |$ , $s_i = a_1 + a_2 + \ldots + a_i$ dla $i = 1, 2, \ldots, n$ . Wtedy $|s_1| = |a_1| \leq \varepsilon$ i $|s_{i+1} - s_i| = | a_{i+1} | \leq \varepsilon$ dla $i = 1, 2, \ldots, n - 1$ . Spełnione są więc założenia lematu. Z lematu wynika, że dla pewnej liczby naturalnej $k \leq n$ zachodzi $|2s_k -s_n | \leq \varepsilon$ , czyli

$ \left| \sum_{i=1}^k a_i - \sum_{i=k+1}^n a_i \right| \leq \max_{1 \leq i \leq n} |a_i|. $

XXV OM - III - Zadanie 5

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

III

Udowodnić, że jeżeli liczby naturalne $n$ , $r$ spełniają nierówność $r + 3 \leq n$ ,to liczby $\binom{n}{r}$ , $\binom{n}{r+1}$ , $\binom{n}{r+2}$ , $\binom{n}{r+3}$ nie są kolejnymi wyrazami żadnego ciągu arytmetycznego.

Rozwiązanie

Udowodnimy najpierw dwa lematy.

Lemat 1. Dla ustalonej liczby naturalnej $n$ istnieją co najwyżej dwie takie liczby naturalne $k \leq n - 2$ , że liczby $\binom{n}{k}$ , $\binom{n}{k+1}$ , $\binom{n}{k+2}$ są kolejnymi wyrazami ciągu arytmetycznego.

Dowód. Jeżeli liczby $\displaystyle \binom{n}{k}, \binom{n}{k+1}, \binom{n}{k+2}$ są kolejnymi wyrazami ciągu arytmetycznego, to

$ \binom{n}{k} + \binom{n}{k+2} = 2\binom{n}{k+1}. $

Mnożąc tę równość stronami przez $\displaystyle \frac{(k+2)!(n-k)!}{n!}$ otrzymamy

$ (k + 2) (k +1) + (n - k) (n - k - 1) = 2 (k + 2) (n - k). $

Jest to równanie kwadratowe ze względu na $k$ . Ma więc ono co najwyżej dwa rozwiązania.

Lemat 2. Dla ustalonej liczby naturalnej $n$ istnieje co najwyżej jedna taka liczba naturalna $k \leq n - 1$ , że $\displaystyle \binom{n}{k} = \binom{n}{k+1}$ .

Dowód. Mnożąc powyższą równość obustronnie przez $\displaystyle \frac{(k+1)!(n-k)!}{n!}$ otrzymujemy $k + 1 = n - k$ . Jest to równanie stopnia pierwszego ze względu na $k$ . Ma więc ono co najwyżej jedno rozwiązanie w zbiorze liczb naturalnych mniejszych od $n$ .

Przystępujemy teraz do rozwiązania zadania. Dla uproszczenia zapisu przyjmijmy, że $a_j = \displaystyle \binom{n}{j}$ dla $j = 1, 2, \ldots, n$ . Przypuśćmy, ze
liczby

$ (1) \qquad a_r, a_{r+1}, a_{r+2}, a_{r+3} $

są kolejnymi wyrazami ciągu arytmetycznego. Na mocy wzoru $\displaystyle \binom{n}{k} = \binom{n}{n-k}$ , czyli $a_k = a_{n-k}$ , również liczby $a_{n-r-3}, a_{n-r-2}, a_{n-r-1}, a_{n-r}$ są kolejnymi wyrazami ciągu arytmetycznego. Mamy więc następujące ciągi arytmetyczne trójwyrazowe

$ a_{r}, a_{r+1}, a_{r + 2}, $

$ a_{r+1}, a_{r+2}, a_{r + 3}, $

$ a_{n-r-3}, a_{n-r-2}, a_{n-r-1} $

$ a_{n-r-2}, a_{n-r-1}, a_{n-r}, $

Z lematu 1 wynika, że zbiór $\{r, r + 1, n - r - 3, n - r - 2\}$ zawiera co najwyżej dwie różne liczby. Ponieważ $r$ i $r + 1$ oraz $n - r - 3$ i $n - r - 2$ są kolejnymi liczbami naturalnymi, więc $r =n - r - 3$ i $r + 1 = n - r - 2$ .

Zatem $a_{r+1} = a_{n-r-2} = a_{r+2}$ czyli ciąg arytmetyczny (1) jest stały. Z lematu 2 wynika, że jest to niemożliwe.

Uzyskana sprzeczność dowodzi, że liczby (1) nie są kolejnymi wyrazami ciągu arytmetycznego.

Uwaga. Można dowieść, że jeżeli dla pewnych liczb naturalnych $n$ i $r$ , gdzie $r \leq n - 2$ , liczby $\displaystyle \binom{n}{r}, \binom{n}{r+1}, \binom{n}{r+2}$ są kolejnymi wyrazami ciągu arytmetycznego, to istnieje taka liczba naturalna $m \geq 3$ , że $n = m^2 - 2$ i $r = \displaystyle \frac{1}{2} (m^2 - m) - 2$ lub $r = \displaystyle \frac{1}{2} (m^2 + m) - 2$ .

Na odwrót, jeżeli liczby $n$ i $r$ są określone powyższymi wzorami, to liczby $\displaystyle \binom{n}{k}, \binom{n}{k+1}, \binom{n}{k+2}$ są kolejnymi wyrazami ciągu arytmetycznego.

Na przykład biorąc $m = 3$ otrzymujemy, że liczby $\displaystyle \binom{7}{1}, \binom{7}{2}, \binom{7}{3}$ tworzą ciąg arytmetyczny.

XXV OM - III - Zadanie 6

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

III

Podzielono $n$ -kąt wypukły przekątnymi na trójkąty w ten sposób, że
1° z każdego wierzchołka wychodzi parzysta liczba przekątnych,
2° żadne dwie przekątne nie mają wspólnych punktów wewnętrznych.
Udowodnić, że $n$ jest podzielne przez 3.

Rozwiązanie

Udowodnimy najpierw

Lemat. Jeżeli $F$ jest figurą na płaszczyźnie i za pomocą $r$ prostych podzielono ją na części, to można te części tak pomalować dwoma kolorami, by każde dwie części mające odcinek wspólny miały różne kolory.

Dowód. Zastosujemy indukcję ze względu na $r$ . W przypadku $r = 1$ teza jest oczywista, ponieważ prosta dzieli płaszczyznę na dwie półpłaszczyzny. Części figury $F$ zawarte w jednej półpłaszczyźnie malujemy jednym kolorem, a części zawarte w drugiej - drugim.

Niech $r$ będzie liczbą naturalną. Zakładamy, że w przypadku $r$ prostych można otrzymane części figury $F$ tak pomalować dwoma kolorami, by był spełniony warunek lematu. Prowadząc $(r + 1)$ -szą prostą dzielimy płaszczyznę na dwie półpłaszczyzny. Części figury $F$ zawarte w jednej z tych półpłaszczyzn zostawiamy tak pomalowane, jak dotychczas, a części zawarte w drugiej - malujemy odwrotnie niż dotychczas (zmieniamy kolor każdej części). Wtedy oczywiście będzie spełniony warunek lematu.

Przystępujemy do rozwiązania zadania. Ponieważ dany $n$ -kąt został podzielony za pomocą pewnej liczby prostych (przekątnych), więc części otrzymane z podziału (trójkąty) można na mocy lematu tak pomalować dwoma kolorami, by trójkąty mające wspólny bok różniły się kolorem.

Ponieważ liczba rozpatrywanych przekątnych wychodzących z dowolnego wierzchołka $A$ danego $n$ -kąta jest parzysta, więc liczba trójkątów, dla których punkt $A$ jest wierzchołkiem, jest nieparzysta. Wobec tego, że trójkąty te mają kolejno różne kolory, więc skrajne trójkąty mają ten sam kolor. Wynika stąd, że trójkąty, których jednym z boków jest bok danego wielokąta, są wszystkie pomalowane na ten sam kolor.

Zatem suma liczby boków $n$ -kąta i liczby wszystkich rozważanych przekątnych jest równa liczbie boków trójkątów pomalowanych tym kolorem. Liczba ta jest więc podzielna przez $3$ . Z drugiej strony liczba rozważanych przekątnych jest równa liczbie boków trójkątów pomalowanych drugim kolorem. Liczba ta jest więc też podzielna przez $3$ . Zatem różnica tych liczb, czyli liczba $n$ , tez jest podzielna przez $3$ .

Uwaga. Jeżeli w treści zadania trójkąty zastąpić przez $k$ -kąty, gdzie $k > 3$ , to zastępując w powyższym rozwiązaniu trójkąty przez $k$ -kąty otrzymamy, że liczba $n$ jest podzielna przez $k$ .