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.