XL OM - I etap

I etap XL Olimpiady Matematycznej

XL OM - I - Zadanie 1

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Udowodnić, że jeśli liczby $k$ , $n$ ( $k < n$ ) są względnie pierwsze, to liczba $\binom{n-1}{k-1}$ jest podzielna przez $k$ .

Rozwiązanie

Oznaczmy:

$ N= \binom{n}{k}=\frac{n!}{k!(n-k)!}, \quad M=\binom{n-1}{k-1}=\frac{(n-1)!}{(k-1)!(n-k)!}. $

Są to liczby całkowite. Zachodzi równość

$ \frac{N}{M}=\frac{n!}{k!(n-k)!}\cdot \frac{(k-1)!(n-k)!}{(n-1)!}=\frac{n}{k} $

czyli $M \cdot n = N \cdot k$ . Zatem liczba $k$ jako względnie pierwsza z $n$ , musi być
dzielnikiem $M$ ; a to właśnie mieliśmy wykazać.

XL OM - I - Zadanie 2

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Dla ustalonej liczby naturalnej $n$ znaleźć liczbę rozwiązań równania

$ x^2 - [x^2] = (x - [x])^2 $

spełniających warunek $1 \leq x \leq n$ .
Uwaga. $[t]$ jest największą liczbą całkowitą nie większą od $t$ .

Rozwiązanie

Oznaczmy lewą i prawą stronę podanego równania przez $L(x)$ i $P(x)$ . Przedstawiając liczbę rzeczywistą $x$ w postaci $x = k + r$ , gdzie $k = [x]$ , $r = x - [x] \in\langle 0; 1)$ , możemy napisać:

$ \begin{split} L(x) &= k^2 + 2kr + r^2 - [k^2 + 2kr + r^2] =\\ &= 2kr + r^2 - [2kr + r^2] ,\\ P(x) &= r^2. \end{split} $

Zatem $L(x) = P(x)$ wtedy i tylko wtedy, gdy $[2kr + r^2] = 2kr$ . Ta zaś równość jest równoważna stwierdzeniu, że $2kr$ jest liczbą całkowitą. Stąd wniosek, że liczba $x = k + r$ ( $k$ całkowite, $r \in \langle 0; 1)$ ) spełnia warunki zadania wtedy i tylko wtedy, gdy

$ (1) \qquad k \in \{1,\ldots , n - 1\} , \quad 2kr\ \textrm{całkowite} $

lub

$ (2) \qquad k = n, \quad r = 0. $

Dla ustalonej wartości $k \in \{1,\ldots, n-1\}$ istnieje $2k$ wartości $r \in \rangle 0; 1)$ , dla których $2kr$ jest całkowite (mianowicie ułamki $j/(2k)$ , $j = 0,1,\ldots, 2k-1$ ). Wobec tego liczba par $(k, r)$ spełniających warunki (1) wynosi $2 + 4 + \ldots + +2(n -1) = n^2 - n$ . Warunki (2) spełnia tylko jedna taka para. Wszystkich liczb $x$ spełniających warunki zadania jest więc $n^2 - n + 1$ .

XL OM - I - Zadanie 3

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Trójkąty $ABC$ i $ABC'$ mają równo obwody, a dwusieczne kątów zewnętrznych przy wierzchołkach $C$ i $C'$ przecinają się w punkcie $O$ . Dowieść, że kąty $AOC$ i $BOC'$ są równe.

Rozwiązanie

Sumy $|AC| + |BC|$ i $|AC'| + |BC'|$ są równe; oznaczmy ich wspólną wartość przez $s$ . Na przedłużeniach odcinków $AC$ i $BC$ odkładamy odcinki $CD$ i $CE$ tak, by

$ (1) \qquad |AD| = |BE| = s. $

Trójkąty $BCD$ i $AC'E$ są równoramienne, a punkt $O$ leży na osi symetrii każdego z nich (rysunek 1). Zatem

$ (2) \qquad |OB| = |OD|, \quad |OA| = |OE| $

oraz

$ (4) \qquad |\measuredangle AOC| + |\measuredangle BOC| = |\measuredangle BOC'| + |\measuredangle AOC'|. $

Wykażemy teraz, że

$ (5) \qquad \textrm{punkty $A$ i $B$ leżą w obszarze kąta wypukłego $COC'$}. $

Weźmy pod uwagę zbiór $\mathcal{E}$ złożony z wszystkich punktów, których suma odległości od $A$ i $B$ równa się $s$ . Jest to elipsa. Warunek, który ją określa, jest spełniony w szczególności przez punkty $C$ i $C'$ . Zatem $C,C' \in \mathcal{E}$ .

Zauważmy, że proste $OC$ i $OC'$ są styczne do elipsy $\mathcal{E}$ . Gdyby na przykład prosta $OC$ nie była do niej Styczna, wówczas moglibyśmy znaleźć na tej prostej punkt $Y$ taki, że $|AY| + |BY| <s$ . Ale $|BY| = |DY|$ (bo $OC$ jest symetralną odcinka $BD$ ). Otrzymalibyśmy więc nierówność $|AY| + |DY| < s = |AD|$ , która jest niemożliwa.

Podobnie dowodzimy styczności prostej $OC'$ do elipsy $\mathcal{E}$ .

Ogniskami $\mathcal{E}$ są punkty $A$ i $B$ . Z uzyskanych relacji styczności wynika, że cała elipsa $\mathcal{E}$ leży w sektorze wyznaczonym przez półproste $OC^\to$ i $OC'^\to$ . Znajdują się tam więc i punkty $A$ i $B$ . Stąd słuszność stwierdzenia (5).

Konkluzją tego stwierdzenia jest równość

$ (6) \qquad |\measuredangle AOC| + |\measuredangle AOC'| = |\measuredangle BOC| + |\measuredangle BOC'|. $

Wszystkie przeprowadzone rozważania są słuszne przy każdej konfiguracji danych punktów. (Na przykład: punkty $C$ i $C'$ mogą leżeć po tej samej stronie lub po różnych stronach prostej $AB$ . Gdy leżą po tej samej stronie, odcinki $AC$ i $BC$ mogą się przecinać, mogą być równoległe, bądź też przecinają się ich przedłużenia, przy czym punkt przecięcia tych prostych może leżeć ,,nad'' lub ,,pod'' prostą $AB$ . Gdy punkty $C$ i $C'$ leżą po różnych stronach prostej $AB$ , powstaje czworokąt $ACBC'$ , który może być wypukły, wklęsły, a może też się redukować do trójkąta. Rysunek 1 przedstawia tylko jedno z możliwych usytuowań tych punktów. Proponujemy Czytelnikowi wykonanie rysunków w innych przypadkach i przekonanie się, że istotnie rozumowanie prowadzące do równości (4) oraz (6) nie jest od rysunku zależne.)

Dodając stronami równości (4) i (6) otrzymujemy (po redukcji) dowodzoną równość $|\measuredangle AOC| = |\measuredangle BOC'|$ .

XL OM - I - Zadanie 4

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Dowieść, że nie można tak pociąć kwadratu wzdłuż skończonej liczby odcinków i łuków okręgów, by z otrzymanych części można było złożyć koło (części można odwracać).

Rozwiązanie

Przypuśćmy, że podział, o jakim mowa w zadaniu, jest wykonalny. Otrzymane w jego wyniku części kwadratu oznaczmy przez $K_1,\ldots, K_n$ . Brzeg każdej figury $K_i$ składa się ze skończonej liczby odcinków oraz łuków okręgów. Spośród łuków okręgów będących fragmentami brzegu $K_i$ niektóre są zwrócone wypukłością na zewnątrz $K_i$ , inne są zwrócone wypukłością do wewnątrz $K_i$ . Sumę długości tych pierwszych łuków oznaczmy przez $a_i$ , a tych drugich - przez $b_i$ . Przyjmijmy $d_i = a_i - b_i$ .

Weźmy pod uwagę sumę $s = d_1 + \ldots + d_n$ .

Figury $K_i$ powstały z podziału kwadratu. Brzeg kwadratu składa się z odcinków linii prostych. Zatem każdy fragment okręgu będący linią podziału kwadratu jest jednocześnie podzbiorem brzegu dwóch figur $K_i$ , przy czym w jednej z tych figur jego długość wchodzi do sumy $s$ ze znakiem plus, a w drugiej --- ze znakiem minus. Tak więc $s = 0$ .

Założyliśmy, że z figur $K_i$ można złożyć koło. Niektóre z rozważanych łuków muszą być wtedy zużyte na utworzenie brzegu tego koła. Przy obliczaniu sumy $s$ długości tych łuków będą liczone jednokrotnie, stale ze znakiem plus. Natomiast długości pozostałych łuków okręgów, tworzących linie podziału koła, ulegną redukcji, jak w przypadku kwadratu. Suma $s$ będzie więc równa obwodowi koła.

Otrzymana sprzeczność ( $s = 0$ i jednocześnie $s > 0$ ) kończy dowód.

XL OM - I - Zadanie 5

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Dla danej liczby naturalnej $n$ wyznaczyć liczbę ciągów $(a_1, a_2, \ldots , a_n)$ , których wyrazy $a_i$ należą do zbioru $\{0,1,2,3,4\}$ oraz spełniają warunek $|a_i - a_{i+i}| = 1$ dla $i = 1,2,\ldots,n-1$ .

Rozwiązanie

Wszystkie ciągi spełniające podane w zadaniu warunki podzielimy na trzy rodzaje:

ciągi I rodzaju — kończące się symbolem $0$ lub $4$ ;\\
ciągi II rodzaju — kończące się symbolem $1$ lub $3$ ;\\
ciągi III rodzaju — kończące się symbolem $2$ .

Oznaczmy przez $x_n$ , $y_n$ , $z_n$ odpowiednio liczbę $n$ --wyrazowych ciągów I, II, III rodzaju. Każdy ciąg I rodzaju (długości $n$ ) można przedłużyć w jeden tylko sposób do ciągu długości $n + 1$ ; będzie to ciąg II rodzaju (bowiem po zerze może być tylko jedynka, a po czwórce może być tylko trójka). Z każdego ciągu II rodzaju (długości $n$ ) można utworzyć dwa ciągi długości $n+1$ , jeden I rodzaju i jeden III rodzaju (po jedynce zero, po trójce czwórka, bądź też, po jedynce lub trójce - dwójka). Wreszcie ciąg III rodzaju (długości $n$ ) da życie dwóm ciągom długości $n+1$ , obu II rodzaju (po dwójce - trójka lub jedynka).

Otrzymujemy więc zależność

$ (1) \qquad \left\{ \begin{split} x_{n+1} &= y_n\\ y_{n+1} &=x_n + 2z_n\\ z_{n+1} &= y_n, \end{split}\right. $

a z niej:

$ (2) \qquad \left\{ \begin{split} x_{n+2} &= y_{n+1}=x_n+2z_n\\ y_{n+2} &=x_{n+1} + 2z_{n+1}=3y_n\\ z_{n+2} &= y_{n+1}=x_n+2-z_n, \end{split} \right. $

Z wzorów (1) widać, że

$ (3) \qquad x_n = z_n \quad \textrm{dla } n \geq 2. $

Oznaczmy sumę $x_n + y_n + z_n$ (czyli liczbę wszystkich dopuszczalnych ciągów długości $n$ ) przez $s_n$ . Dodając stronami wzory (2) i uwzględniając równość (3) otrzymujemy związek:

$ (4) \qquad s_{n+2} = 3s_n \quad \textrm{dla } n \geq 2. $

Musimy jeszcze znać wartości $s_1$ $s_2$ i $s_3$ . Ciąg długości $1$ to pojedynczy symbol. Mamy do dyspozycji pięć symboli, więc $s_1 = 5$ . Wypiszmy teraz wszystkie dopuszczalne ciągi długości 2 oraz 3:

$ (01),\ (10),\ (12),\ (21),\ (23),\ (32),\ (34),\ (43) $

oraz

$ (010),\ (012),\ (101),\ (121),\ (123),\ (210),\ (212), $

$ (232),\ (234),\ (321),\ (323),\ (343),\ (432),\ (434). $

Wobec tego

$ s_1 = 5,\quad s_2 = 8, \quad s_3 = 14. $

Stąd i z wzoru rekurencyjnego (4) otrzymujemy przez oczywistą indukcję odpowiedź:

$ s_{2k} = 8 \cdot 3^{k-1} ,\quad s_{2k+1} = 14 \cdot 3^{k-1} \textrm{dla } k \geq 1. $

XL OM - I - Zadanie 6

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Obliczyć sumę szeregu $\sum_{n\in A}\frac{1}{2^n}$ , w którym sumowanie przebiega zbiór $A$ wszystkich liczb naturalnych niepodzielnych przez 2, 3, 5.

Rozwiązanie

Liczba naturalna $n$ jest niepodzielna przez $2$ , $3$ i $5$ wtedy i tylko wtedy, gdy przy dzieleniu przez 30 daje jedną z następujących ośmiu reszt:

$ r_1 = 1,\ r_2 = 7 , r_3 = 11, r_4 = 13 , r_5 = 17 , r_6 = 19 , r_7 = 23 , r_8 = 29 . $

Wobec tego suma, którą mamy obliczyć, równa się

$ (1) \qquad s = s_1 + s_2 + s_3 + s_4 + s_5 + s_6 + s_7 + s_8 , $

gdzie $s_i$ oznacza sumę analogicznego szeregu utworzonego ze składników odpowiadających tym wartościom $n$ , które mają postać

$ n = 30k + r_i,\quad k = 0, 1, 2, 3, \ldots . $

Tak więc

$ (2) \qquad s_i=\sum_{k=0}^\infty 2^{-(30k+r_i)}\quad \textrm{dla } i=1,\ldots,8. $

(Poprawność zastosowanego przekształcenia oraz słuszność równości (1) wynika z tego, że wyrazami rozważanego szeregu są liczby dodatnie; można je więc w dowolny sposób grupować i przestawiać, bez wpływu na zbieżność i wartość sumy szeregu.)

Prawa strona wzoru (2) przedstawia szereg geometryczny o ilorazie $2^{-30}$ . Jego suma równa się

$ s_i= \frac{2^{-r_i}}{1-2^{-30}}= \frac{2^{30-r_i}}{2^{30}-1}\quad \textrm{dla } i=1,\ldots, 8. $

Podstawiamy te liczby do równości (1) i otrzymujemy

$ \frac{2^{29}+2^{23}+2^{17}+2^{11}+2^7+2^1}{2^{30}-1}=\frac{545925250}{1073741823} $

Jest to poszukiwana wartość.

XL OM - I - Zadanie 7

Zawody matematyczne:

XL OM, 1988-1989

Etap:

W przestrzeni dany jest skończony zbiór punktów, z których każde cztery są wierzchołkami czworościanu o objętości mniejszej lub równej 1. Udowodnić, że istnieje czworościan o objętości nie większej niż 27, zawierający wszystkie te punkty.

Rozwiązanie

Niech $ABCD$ będzie czworościanem o maksymalnej objętości wśród wszystkich czworościanów, których wierzchołkami są punkty rozważanego zbioru. Oznaczmy przez $O$ jego środek ciężkości, to znaczy punkt przecięcia czterech odcinków, z których każdy łączy wierzchołek czworościanu ze środkiem ciężkości przeciwległej ściany. Wiadomo, że środek ciężkości czworościanu dzieli każdy z tych czterech odcinków w stosunku $3:1$ .

Niech $A'B'C'D'$ będzie obrazem czworościanu $ABCD$ w jednokładności o środku $O$ i skali $-3$ ( $A'$ - obraz punktu $A$ itd.). Zgodnie z uczynioną przed chwilą uwagą, środek ciężkości każdej ściany czworościanu przechodzi w tej jednokładności na przeciwległy wierzchołek.

W myśl założenia zadania, objętość czworościanu $ABCD$ nie przekracza $1$ . Zatem objętość czworościanu $A'B'C'D'$ nie przekracza $27$ (stosunek objętości brył podobnych równa się sześcianowi skali podobieństwa). Wykażemy, że czworościan $A'B'C'D'$ zawiera wszystkie rozważane punkty - jest więc poszukiwanym czworościanem.

Przypuśćmy, że pewien z tych punktów - nazwijmy go $P$ - leży poza czworościanem $A'B'C'D'$ . Każdy czworościan jest częścią wspólną czterech półprzestrzeni otrzymanych z podziału całej przestrzeni płaszczyznami ścian. Jeżeli więc punkt $P$ nie należy do $A'B'C'D'$ , to znaczy, że $P$ nie należy do jednej z tych półprzestrzeni; powiedzmy, do półprzestrzeni wyznaczonej przez płaszczyznę $A'B'C'$ . Innymi słowy, $P$ leży po przeciwnej stronie płaszczyzny $A'B'C'$ niż punkt $O$ . Ale płaszczyzna $A'B'C'$ , równoległa do ściany $ABC$ czworościanu $ABCD$ , przechodzi przez jego wierzchołek $D$ (bowiem, jak zauważyliśmy wyżej, wierzchołek $D$ jest obrazem środka ciężkości ściany $ABC$ w określonej na początku jednokładności).

Stąd wniosek, że odległość punktu $P$ od płaszczyzny $ABC$ jest większa niż odległość punktu $D$ od tej płaszczyzny. Co za tym idzie, objętość czworościanu $ABCP$ jest większa od objętości czworościanu $ABCD$ . A przecież czworościan $ABCD$ określiliśmy jako ten spośród wszystkich czworościanów o wierzchołkach w zadanych punktach, którego objętość jest maksymalna.

Otrzymana sprzeczność dowodzi, że wszystkie punkty danego zbioru leżą w czworościanie $A'B'C'D'$ . Dowód jest zakończony.

XL OM - I - Zadanie 8

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Dana jest liczba naturalna $n$ oraz skończony ciąg liczb rzeczywistych $A^{(1)}= (a_1^{(1)}, a_2^{(1)}, \ldots, a_n^{(1)})$ . Dla każdej liczby naturalnej $m$ wybieramy dwie liczby naturalne $i$ , $j$ spełniające warunek $1 \leq i < j \leq n$ i określamy ciąg $A^{(m+1)}= (a_1^{(m+1)}, a_2^{(m+1)}, \ldots, a_n^{(m+1)})$ , jak następuje:

$ \begin{split} a_i^{(m+1)} &= a_j^{(m+1)} = \frac{1}{2}(a_i^{(m)} + a_j^{(m)}),\\ a_k^{(m+1)} = a_k^{(m)} \quad\text{dla}\quad k\neq i, j. \end{split} $

Udowodnić, że jeżeli każda para liczb naturalnych $(i,j)$ należących do przedziału $\langle 1;n\rangle$ będzie wybrana nieskończenie wiele razy, to

$ \lim_{n\to \infty} a_k^{(m)} = \frac{1}{n}(a_1^{(1)} + \ldots + a_n^{(1)}) $

dla $k = 1,2,\ldots, n$ .

Rozwiązanie

Przyjmijmy oznaczenia:

$ u^{(m)}=\min_{1\leq k \leq n} a_k^{(m)}, \quad v^{(m)}=\max_{1\leq k \leq n} a_k^{(m)}, $

$ s^{(m)}=\sum_{k=1}^n a_k^{(m)},\quad q^{(m)}=\sum_{k=1}^n\left(a_k^{(m)}\right)^2. $

Sumę $s^{(1)}$ oznaczmy krótko przez $s$ . Teza zadania orzeka, że ciąg $\left(a_1^{(m)}\right)^\infty_{m=1}$ jest zbieżny do liczby $s/n$ , także ciąg $\left(a_2^{(m)}\right)^\infty_{m=1}$ Jest zbieżny do tej samej liczby, to samo można powiedzieć o ciągu $\left(a_3^{(m)}\right)^\infty_{m=1}$ , i tak dalej: dla każdego numeru $k \in \{1,\ldots, n\}$ ciąg $\left(a_k^{(m)}\right)^\infty_{m=1}$ jest zbieżny, a liczba $s/n$ jest wspólną granicą tych n ciągów. Sprowadza się to do wykazania, że

$ (1) \qquad \lim_{m \to \infty} u^{(m)} = \lim_{m \to \infty} v^{(m)} = \frac{s}{n} . $

Dla każdego $m$ zachodzą nierówności

$ u^{(m)} \leq \frac{s^{(m)}}{n} \leq v^{(m)} $

(średnia arytmetyczna układu liczb zawiera się między najmniejszą a największą z tych liczb). Zauważmy dalej, że opisana w zadaniu operacja nie zmienia sumy liczb: $s^{(m)} = s^{(m+1)}$ dla każdego $m$ ; a wobec tego $s^{(m)} = s$ dla wszystkich $m$ . Tak więc

$ (2) \qquad u^{(m)} \leq \frac{s^{(m)}}{n} \leq v^{(m)} $

Oczywiście $\rangle u^{(m)}, v^{(m)} \langle$ jest najmniejszym przedziałem zawierającym wszystkie liczby układu $A^{(m)}$ . Rozważana operacja nie wyprowadza poza ten przedział; układ $A^{(m+1)}$ także jest w nim zawarty. To znaczy, że

$ u^{(m)} \leq u^{(m+1)}, \quad v^{(m)} \geq v^{(m+1)}; $

ciąg $\left(u^{(m)}\right)$ jest niemalejący, a ciąg $\left(u^{(m)}\right)$ jest nierosnący. Nierówności (2) pokazują, że pierwszy z tych ciągów jest. ograniczony z góry przez liczbę $s/n$ , a drugi jest ograniczony z dołu przez tę samą liczbę. Istnieją zatem granice

$ u = \lim u^{(m)}\leq \frac{s}{n} , \quad v = \lim v^{(m)}\leq \frac{s}{n}. $

Jeśli wykażemy, że granice te są równe, to liczba $s/n$ będzie musiała być ich wspólną wartością i otrzymamy dowodzoną równość (1).

Przypuśćmy wobec tego, że $u < v$ . Mamy równość

$ \begin{split} q^{(m)}-q^{(m+1)}&= \sum_{k=1}^n \left(a_k^{(m)}\right)^2 - \sum_{k=1}^n \left(a_k^{(m+1)}\right)^2=\\ &= \left(a_i^{(m)}\right)^2 + \left(a_j^{(m)}\right)^2 - \left(a_i^{(m+1)}\right)^2 - \left(a_j^{(m+1)}\right)^2=\\ &=\left(a_i^{(m)}\right)^2+\left(a_j^{(m)}\right)^2 - 2\left(\frac{1}{2} \left(a_i^{(m)}+a_j^{(m)}\right)\right)^2=\\ &=\left(a_i^{(m)}+a_j^{(m)}\right)^2 \end{split} $

gdzie $(i,\ j)$ jest parą wskaźników wybraną w $m$ -tym kroku opisanej w zadaniu procedury (tj. przy określaniu układu liczb $A^{(m+1)}$ ). Ponieważ para ta zależy od bieżącej wartości wskaźnika $m$ , bardziej poprawnie będzie oznaczyć ją przez $(i_m,\ j_m)$ . Przepiszmy więc otrzymaną równość:

$ (3) \qquad q^{(m)}-q^{(m+1)} = \left(a_{i_m}^{(m)}+a_{j_m}^{(m)}\right)^2. $

Widać stąd, że $\left(q^{(m)}\right)$ jest nierosnącym ciągiem liczb nieujemnych, więc zbieżnym do granicy skończonej. Możemy wobec tego przejść do granicy z wyrażeniem znajdującym się po lewej stronie równości (3): ta różnica dąży do zera. Wobec tego także różnica w nawiasie po prawej stronie równości (3) musi dążyć do zera.

Założyliśmy, że $u < v$ . Oznaczmy liczbę $(v - u)/(n - 1)$ przez $d$ jest to ustalona liczba dodatnia:

$ d=\frac{v-u}{n-1}>0. $

Wyrazy ciągu zbieżnego do zera stają się od pewnego miejsca mniejsze od d. Istnieje więc taki numer $M$ , że

$ (4) \qquad \left| a_{i_m}^{(m)} - a_{j_m}^{(m)}) \right| < d \quad \textrm{dla } m\geq M. $

Weźmy pod uwagę przedział $\langle u^{(M)};\ v^{(M)} \rangle$ . Zawiera on przedział $\langle u;\ v \rangle$ , a więc ma długość nie mniejszą niż $v - u = (n - 1)d$ . Liczby $a_1^{(M)},\ldots, a_n^{(M)}$ dzielą ten przedział $n-1$ podprzedziałów (lub mniej, gdy niektóre z nich są równe). W każdym razie co najmniej jeden z tych podprzedziałów musi mieć długość nie mniejszą od $d$ . Ustalmy ten podprzedział i nazwijmy go $\langle \alpha;\ \beta \rangle$ .

Cały zbiór $\{a_1^{(M)},\ldots, a_n^{(M)}\}$ zawiera się w sumie przedziałów

$ P' = \langle u^{(M)};\ \alpha \rangle\quad \textrm{oraz} \quad P" = \langle \beta;\ v^{(M)} \rangle, $

odległych od siebie co najmniej o $d$ , przy czym w obu tych przedziałach są jakieś elementy tego zbioru. Przyjmijmy:

$ K' = \{k: a_k^{(M)} \in P'\} , $

$ K'' = \{k : a_k^{(M)} \in P''\}; $

są to niepuste zbiory wskaźników, dające w sumie zbiór $\{1,\ldots, n\}$ . Na mocy nierówności (4) (która musi zachodzić w szczególności dla $m = M$ ) wskaźniki $i_M$ , $j_M$ muszą oba należeć albo do $K'$ , albo do $K''$ . „Uśredniane" w $M$ -tym kroku liczby $a_{i_M}^{(M)}$ , $a_{j_M}^{(M)}$ obie leżą albo w przedziale $P'$ , albo w $P''$ . Ich średnia arytmetyczna także leży w tym przedziale. Tak więc

$ a_k^{(M+1)} \in P' \quad \textrm{dla } k \in K' $

$ a_k^{(M+1)} \in P'' \quad \textrm{dla } k \in K'' $

I znów, na mocy (4), wskaźniki $i_{M+1}$ i $j_{M+1}$ muszą oba należeć albo do $K'$ , albo do $K''$ . Kontynuując to rozumowanie dowodzimy indukcyjnie, że

$ \{i_m,j_m\} \subset K' \quad \textrm{lub} \quad \{i_m,j_m\} \subset K'' \quad \textrm{dla}\quad m\geq M. $

(Intuicyjny sens rozumowania jest taki: podprzedział $\langle \alpha;\ \beta \rangle$ stanowi ,,cezurę'' rozdzielającą całe ,,pole operacyjne'' na część lewą i prawą, których odległość wynosi nie mniej niż $d$ ; tymczasem nierówność (4) orzeka, że - począwszy od chwili $M$ - do ,,uśredniania'' wybiera się już tylko pary liczb odległych od siebie o mniej niż $d$ , a więc pary, których oba elementy leżą bądź w lewej, bądź w prawej części.)

Jeśli więc $(i,j)$ jest taką parą wskaźników, że $i\in K'$ , $j\in K''$ (lub odwrotnie), to $(i,j)\neq (i_m,j_m)$ dla wszystkich $m \geq M$ - wbrew warunkowi zadania mówiącemu, że każda para wskaźników pojawia się w ciągu wybranych par $(i_m,j_m)$ nieskończenie wiele razy.

Uzyskana sprzeczność pokazuje niesłuszność przypuszczenia, że $u < v$ , i tym samym kończy cały dowód.

Uwaga. Przypuśćmy, że $(i,j)$ jest parą wskaźników, która w ciągu wybranych par $(i_m,j_m)$ pojawia się nieskończenie wiele razy. Będziemy wówczas mówili, że wskaźniki $i$ oraz $j$ są stowarzyszone. Założenie zadania można wyrazić następująco: każde dwa wskaźniki $i,j \in \{1,\ldots,n\}$ są stowarzyszone. Zauważmy wszelako, że tak silne założenie nie jest nam potrzebne w dowodzie; wystarczy zakładać, że zbioru $\{1,\ldots ,n\}$ nie da się podzielić na dwa niepuste rozłączne podzbiory $K'$ i $K''$ tak, by żaden element zbioru $K'$ nie był stowarzyszony z żadnym elementem zbioru $K''$ ; udowodniona teza pozostaje w mocy, a dowód przenosi się bez żadnych zmian.

XL OM - I - Zadanie 9

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Wyznaczyć wszystkie liczby naturalne $x$ , $y$ , $z$ spełniające równanie

$ 1 = \frac{2}{x^2} + \frac{3}{y^2} + \frac{4}{z^2} $

Rozwiązanie

Z podanego równania wynika, że jeśli $x$ , $y$ , $z$ jest rozwiązaniem, to $x, y \geq 2$ , $z \geq 3$ . Rozpatrzymy trzy przypadki:

{\em Przypadek} l. $x = 2$ . Równanie przybiera postać $3y^{-2} + 4z^{-2} =\frac{1}{2}$ , czyli równoważnie: $4y^2 + 3z^2 = \frac{1}{2} y^2z^2$ , czyli jeszcze inaczej:

$ (y^2 - 6)(z^2 - 8) = 48 \quad (y \geq 2,\ z \geq 3). $

Rozważając wszystkie możliwe rozkłady liczby $48$ na czynniki całkowite (dodatnie i ujemne) stwierdzamy, że nie ma rozwiązania w tym przypadku.
{\em Przypadek} II. $y = 2$ . Równanie przybiera postać $2x^{-2} + 4z^{-2} = \frac{1}{4}$ , czyli - analogicznie jak poprzednio -

$ (x^2 - 8)(z^2 - 16) = 128 \quad (x \geq 2,y \geq 3). $

Znów rozważamy wszystkie rozkłady liczby $128$ na czynniki i znajdujemy jedyne (w tym przypadku) rozwiązanie: $x = 3$ , $z = 12$ .

{\em Przypadek} III. $x, y \geq 3$ ; także $z \geq 3$ . Tym razem musimy zauważyć, że zachodzi nierówność

$ 2x^{-2} + 3y^{-2} + 4z^{-2} \leq \frac{2}{9} + \frac{3}{9} + \frac{4}{9} = 1, $

przy czym staje się ona równością tylko dla $x = y = z = 3$ .

Rozważyliśmy wszystkie możliwości i znaleźliśmy dwie trójki $(x,y,z)$ liczb całkowitych będące rozwiązaniami danego równania: $(3,2,12)$ oraz $(3,3,3)$ .

XL OM - I - Zadanie 10

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Liczby dodatnie $\alpha$ , $\beta$ , $\gamma$ spełniają nierówności

$ \alpha+\beta+\gamma < \pi, \alpha < \beta + \gamma, \beta < \gamma + \alpha, \gamma < \alpha + \beta. $

Udowodnić, że z odcinków o długościach $\sin \alpha$ , $\sin \beta$ , $\sin \gamma$ można zbudować trójkąt i że pole tego trójkąta jest nie większe od

$ \frac{1}{8} (\sin 2\alpha + \sin 2\beta + \sin 2\gamma). $

Rozwiązanie

Wykażemy, że istnieje w przestrzeni kąt trójścienny $OABC$ taki, że

Możemy przyjąć, że $\gamma \geq \alpha$ , $\gamma\geq \alpha$ . Oczywiście $\gamma < \pi/2$ (gdyby bowiem było $\gamma \geq \pi/2$ , to mielibyśmy $\alpha+\beta< \pi - \gamma \leq \pi/2 \leq \gamma$ , wbrew założeniu). Zatem $2\gamma < \pi$ .

Weźmy pod uwagę kąt wypukły $AOB$ o rozwartości $2\gamma$ . W obszarze tego kąta (w jego płaszczyźnie) umieśćmy półproste $OA'^\rightarrow$ i $OB'^\rightarrow$ tak, by $|\measuredangle AOA' =2\beta$ , $|\measuredangle BOB'| = 2\alpha$ . Kąty wypukłe $AOA'$ i $BOB'$ mają niepustą część wspólną (bo $\alpha + \beta > \gamma$ ).

Niech $AOA''$ będzie obrazem kąta $AOA'$ w symetrii osiowej względem prostej $OA$ . Analogicznie określamy kąt $BOB''$ . Rozważamy kąty $A'O A''$ i $B'OB''$ , zawierające (odpowiednio) półproste $OA^\rightarrow$ i $OB^\rightarrow$ . Ich rozwartości wynoszą $4\beta$ i $4\alpha$ - a więc kąty te mogą nie być wypukłe. Mają one w każdym razie niepustą część wspólną, bo zawierają kąty $AOA'$ i $BOB'$ (rysunek 2).

Wychodzimy teraz z rozważaniami w przestrzeń. Obracając półprostą $OA'^\rightarrow$ wokół prostej $OA$ otrzymujemy powierzchnię obrotową, rozdzielającą przestrzeń na dwie części. Jedna z nich jest nieograniczonym stożkiem kołowym (wypukłym); drugą będziemy nazywać stożkiem wklęsłym. W szczególnym przypadku, gdy $\beta = \pi/4$ , obie te części są półprzestrzeniami (które też będziemy uważać za graniczną, ,,zdegenerowaną'' postać stożka); oczywiście rozdzielająca je powierzchnia jest w tym przypadku po prostu płaszczyzną.

Bierzemy pod uwagę ten stożek (wypukły lub wklęsły), który zawiera półprostą $OA^\rightarrow$ . Oznaczmy go przez $K_A$ . Rozwartość kąta przy wierzchołku stożka $K_A$ wynosi $4\beta$ ; płaski kąt $A'OA"$ jest jego przekrojem osiowym. Analogicznie określamy stożek $K_B$ (wypukły lub wklęsły), którego przekrojem osiowym jest kąt $B'OB"$ . Z poprzednich konkluzji wynika, że stożki $K_A$ i $K_B$ mają wspólne punkty wewnętrzne. Ich powierzchnie boczne przecinają się wzdłuż dwóch wspólnych tworzących, położonych symetrycznie względem płaszczyzny $OAB$ . Jedną z nich (dowolnie wybraną) oznaczymy przez $OC^\rightarrow$ . Tworzy ona z osią obrotu stożka $K_A$ , czyli z półprostą $OA^\rightarrow$ , kąt o mierze $2\beta$ , a z osią obrotu stożka $K_B$ , czyli z półprostą $OB^\rightarrow$ - kąt o mierze $2\alpha$ . Tak więc półproste $OA^\rightarrow$ , $OB^\rightarrow$ , $OC^\rightarrow$ tworzą poszukiwany kąt trójścienny (rysunek 2).

Możemy przyjąć, że punkty $A$ , $B$ , $C$ leżą na tych półprostych w odległości $1/2$ od punktu $O$ .

Niech M będzie środkiem odcinka AB. Wówczas

$ |\measuredangle AOM|=\gamma, \quad |AB| = 2|AM| = \sin \gamma, \quad |OM| = \frac{1}{2} \cos \gamma, $

$ \mathrm{pole}(AOB) = \frac{1}{2} |AB| \cdot |OM| = \frac{1}{8} \sin 2\gamma. $

Analogicznie

$ |BC| = \sin \alpha,\quad |CA|=\sin \beta, $

$ \mathrm{pole}(BOC) = \frac{1}{8} \sin 2\alpha , \mathrm{pole}(COA) = \frac{1}{8} \sin 2\beta . $

Zatem trójkąt $ABC$ ma boki długości $\sin \alpha$ , $\sin \beta$ , $\sin \gamma$ ; jest więc poszukiwanym trójkątem.

Rzuty dowolnych trzech ścian czworościanu na płaszczyznę czwartej ściany pokrywają tę ścianę, a pola rzutów nic są większe niż pola samych ścian. Wobec tego pole trójkąta $ABC$ nic jest większe od sumy pól trzech pozostałych ścian czworościanu $OABC$ , czyli nie przekracza wartości

$ \frac{1}{8} (\sin 2\alpha + \sin 2\beta + \sin 2\gamma) . $

To właśnie mieliśmy wykazać.

XL OM - I - Zadanie 11

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Punkty $A_1$ , $A_2$ , $A_3$ , $A_4$ leżą na powierzchni sfery, przy czym odległość każdych dwóch z nich jest mniejsza od długości krawędzi czworościanu foremnego wpisanego w tę sferę. Dowieść, że wszystkie te punkty można oświetlić jednym punktowym źródłem światła umieszczonym na zewnątrz sfery.

Rozwiązanie

Niech $C_1C_2C_3C_4$ będzie dowolnym czworościanem foremnym wpisanym w daną sferę; punkt $O$ niech będzie jej środkiem, a $r$ - długością promienia. Weźmy pod uwagę wektory

$ \mathbf{u} _k = \overrightarrow{OA_k},\quad \mathbf{u} _k = \overrightarrow{OC_k} \quad (k = 1,2,3,4) $

oraz sumę

$ (1) \qquad \mathbf{u}_1+\mathbf{u}_2+\mathbf{u}_3+\mathbf{u}_4=\mathbf{w}. $

Analogiczna suma utworzona dla wektorów $\mathbf{v}_k$ (wyznaczonych przez wierzchołki czworościanu foremnego i jego środek ciężkości) jest, rzecz jasna, wektorem zerowym:

$ (2) \qquad \mathbf{v}_1+\mathbf{v}_2+\mathbf{v}_3+\mathbf{v}_4= 0. $

Mnożymy skalarnie równość (1) stronami przez wektor $\mathbf{u}_1$ , a równość (2) przez $\mathbf{v}_1$ :

$ r^2 + \mathbf{u}_1 (\mathbf{u}_2+\mathbf{u}_3+\mathbf{u}_4) = \mathbf{u}_1 \cdot w , $

$ r^2 + \mathbf{v}_1 (\mathbf{v}_2+\mathbf{v}_3+\mathbf{v}_4) = 0 . $

Odejmując otrzymane równości stronami dostajemy

$ \mathbf{u}_1\cdot \mathbf{w} = \sum_{j=2}^4 (\mathbf{u}_1\cdot \mathbf{u}_j - \mathbf{v}_1\cdot \mathbf{v}_j). $

Zgodnie, z warunkiem zadania odległość $|A_i A_j|$ jest mniejsza od $|C_iC_j|$ dla dowolnej pary różnych wskaźników $i$ , $j$ . Wobec tego kąt między wektorami $\mathbf{u}_i$ , $\mathbf{u}_j$ jest mniejszy od kąta między wektorami $\mathbf{v}_i$ , $\mathbf{v}_j$ . To z kolei oznacza, że iloczyn skalarny $\mathbf{u}_i \cdot \mathbf{u}_j$ jest większy niż $\mathbf{v}_i \cdot \mathbf{v}_j$ dla $i \neq j$ Zatem wszystkie trzy różnice będące składnikami sumy po prawej stronie równości (3) są liczbami dodatnimi i w konsekwencji

$ \mathbf{u}_1 \cdot \mathbf{w} > 0. $

Możemy teraz powtórzyć to samo rozumowanie zastępując wektor $\mathbf{u}_1$ dowolnym spośród wektorów $\mathbf{u}_2$ , $\mathbf{u}_3$ , $\mathbf{u}_4$ . Wobec tego $\mathbf{u}_k \cdot \mathbf{w} >0$ dla $k = 1,2,3,4$ . Znaczy to, że wektory $\mathbf{u}_k$ tworzą z wektorem $\mathbf{w}$ kąty ostre. Stąd wniosek, że punkty $A_k$ leżą, wszystkie po jednej stronie płaszczyzny przechodzącej przez punkt $O$ i prostopadłej do wektora $\mathbf{w}$ - czyli leżą na jednej połówce rozważanej sfery. Można je więc oświetlić z punktu położonego poza tą sferą.

XL OM - I - Zadanie 12

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Udowodnić, że dla każdej liczby całkowitej $k\geq l$ istnieje taka liczba rzeczywista $x$ , że przy każdym całkowitym $m \geq 1$ liczba $[x^m] + 1$ dzieli się przez $k$ .

Użyjemy tożsamości

$ (3) \qquad (k + t)^m + (k-t)^m = 2 \sum_{j=0}^{[m/2]} k^{m-2}t^{2j} , $

zachodzącej dla dowolnych liczb $k$ , $t$ , a wynikającej natychmiast z wzoru dwumianowego. Zakładamy, że $k \geq 2$ jest daną w zadaniu liczbą całkowitą i przyjmujemy $t = \sqrt{k^2 - k}$ . Wówczas $t^2 = k^2 - k > (k -1)^2$ , więc

$ (4) \qquad 0 < k - t < 1. $

Po prawej stronie wzoru (3) liczba $t$ występuje tylko w parzystych potęgach. Wobec tego prawa strona (3) przedstawia liczbę całkowitą, i to będącą wielokrotnością $k$ . Lewa strona (3) ma postać sumy, której drugi składnik jest (w myśl (4)) liczbą z przedziału $(0; 1)$ . Wynika stąd, że jej pierwszy składnik ma część całkowitą o $1$ mniejszą od liczby napisanej po prawej stronie (3):

$ [(k + t)^m] + 1 = (\textrm{prawa strona} (3)) = (\textrm{wielokrotność} k). $

Wystarczy zatem przyjąć $x = k + t = k \sqrt{k^2-k}$ , by uczynić zadość postulatowi zadania.