XXII OM - II etap

II etap XXII Olimpiady Matematycznej

XXII OM - II - Zadanie 1

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

Na ile sposobów można tak wybrać $k$ pól szachownicy $n \times n$ ( $k \leq n$ ), aby żadne dwa z wybranych pól nie leżały ani w jednym wierszu, ani w jednej kolumnie?

Rozwiązanie

Można najpierw wybrać $k$ wierszy, w których mają leżeć wybrane pola. Uczynić to można na $\displaystyle \binom{n}{k}$ sposobów. Następnie w każdym z tych wierszy należy kolejno wybrać jedno z $n$ pól, jedno z $n - 1$ pól leżących w pozostałych kolumnach, itd. - jedno z $n - k + 1$ pól. Zatem łączna liczba sposobów równa jest $\displaystyle \binom{n}{k} n(n - 1) \ldots (n - k + 1)$ .

XXII OM - II - Zadanie 2

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

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

$ 1 < \cos A + \cos B + \cos C \leq \frac{3}{2}. $

Rozwiązanie

Ponieważ $C = \pi - (A + B)$ , więc

$ \begin{split} \cos A + \cos B + \cos C &= 2 \cos \frac{A+B}{2} \cos \frac{A-B}{2} - \cos (A + B) =\\ &=2 \cos \frac{A+B}{2} \cos \frac{A-B}{2} - 2\cos^2 \frac{A + B}{2} +1. \end{split} $

Stąd

$ \begin{split} \cos A+\cos B+ \cos C &=1 + 2\cos \frac{A + B}{2} \left( \cos \frac{A-B}{2}- \cos \frac{A+B}{2} \right) =\\ &= 1 + 4 \cos \frac{A+B}{2} \sin \frac{A}{2}\sin \frac{B}{2}> 1. \end{split} $

Ponadto, biorąc pod uwagę, że $\left| \frac{A-B}{2} \right| \leq \frac{\pi}{2}$ , otrzymujemy

$ \begin{split} \cos A + \cos B + \cos C &= 2 \cos \frac{A+B}{2} \cos \frac{A-B}{2} - 2\cos^2 \frac{A + B}{2} +1 \leq\\ &\leq2 \cos \frac{A+B}{2} - 2\cos^2 \frac{A+B}{2} + 1 =\\ &= -2 \left( \cos \frac{A + B}{2} - \frac{1}{2} \right)^2 + \frac{3}{2} \leq \frac{3}{2}. \end{split} $

XXII OM - II - Zadanie 3

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

Danych jest 6 prostych w przestrzeni, z których żadne 3 nie są równoległe, żadne 3 nie przechodzą przez ten sam punkt i żadne 3 nie są zawarte w jednej płaszczyźnie. Udowodnić, że wśród tych 6 prostych istnieją 3 proste wzajemnie skośne.

Rozwiązanie

Z warunków zadania wynika, że w każdej trójce rozważanych prostych istnieje para prostych skośnych. Przyporządkujmy danym prostym w sposób wzajemnie jednoznaczny wierzchołki sześciokąta wypukłego oznaczone cyframi $1, 2, \ldots, 6$ (rys. 11). Jeżeli pewne dwie proste są skośne, to połączmy odpowiadające im wierzchołki sześciokąta linią ciągłą, a jeżeli nie są skośne - linią przerywaną.

Zadanie sprowadziliśmy więc do następującego: Danych jest sześć punktów. Każde dwa z nich połączone są linią ciągłą lub przerywaną. Przy tym każdy trójkąt o wierzchołkach należących do danego zbioru punktów ma co najmniej jeden bok będący linią ciągłą. Dowieść, że istnieje trójkąt, którego wszystkie boki są liniami ciągłymi.

Przypuśćmy, że nie ma trójkąta, którego wszystkie boki są. liniami ciągłymi. Istnieje więc para punktów połączona linią przerywaną. Niech to będzie na przykład para $1, 2$ . Ponieważ w każdym z trójkątów $1, 2, 3$ ; $1, 2, 4$ ; $1, 2, 5$ ; $1, 2, 6$ istnieje bok narysowany linią ciągłą i bokiem tym nie jest $1, 2$ , więc każdy z punktów $3, 4, 5, 6$ jest połączony linią ciągłą z co najmniej jednym z punktów $1, 2$ .

Gdyby pewien z punktów $1, 2$ był połączony linią ciągłą z co najmniej trzema z punktów $3, 4, 5, 6$ , na przykład punkt $1$ z punktami $3, 4, 5$ , to rozważając trójkąty $1, 3, 4$ ; $1,4, 5$ ; $1, 3, 5$ , w których dwa boki narysowane są linią ciągłą, stwierdzamy, że boki $3, 4$ ; $4, 5$ oraz $3, 5$ są narysowane linią przerywaną (rys. 11). W trójkącie $3, 4, 5$ żaden z boków nie byłby więc narysowany linią ciągłą. Jest to sprzeczne z warunkami zadania.

Zatem każdy z punktów $1$ i $2$ jest połączony linią ciągłą z dokładnie dwoma z punktów $3, 4, 5, 6$ . Bez zmniejszenia ogólności rozważań możemy założyć, że punkt $1$ jest połączony linią ciągłą z punktami $3$ i $4$ , a punkt $2$ - z punktami $5$ i $6$ . Natomiast punkt $1$ jest połączony linią przerywaną z punktami $5$ i $6$ , a punkt $2$ - z punktami $3$ i $4$ (rys. 12). Rozważając trójkąt $2, 5, 6$ stwierdzamy, że punkty $5$ i $6$ są połączone linią przerywaną. Wtedy jednak trójkąt $1, 5, 6$ ma wszystkie boki narysowane linią przerywaną. Jest to sprzeczne z warunkami zadania. Uzyskana sprzeczność dowodzi, że istnieje trójkąt, którego wszystkie boki są narysowane liniami ciągłymi.

XXII OM - II - Zadanie 4

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

Na płaszczyźnie dany jest skończony zbiór punktów $Z$ o tej własności, że żadne dwie odległości punktów zbioru $Z$ nie są równe. Punkty $A, B$ należące do $Z$ łączymy wtedy i tylko wtedy, gdy $A$ jest punktem najbliższym $B$ lub $B$ jest punktem najbliższym $A$ . Udowodnić, że żaden punkt zbioru $Z$ nie będzie połączony z więcej niż pięcioma innymi.

Rozwiązanie

Przypuśćmy, że punkt $A \in Z$ jest połączony z pewnymi punktami $B$ i $C$ zbioru $Z$ i niech na przykład $AB < AC$ . Wtedy punkt $C$ nie jest najbliższy $A$ , a więc z warunków zadania wynika, że punkt $A$ jest najbliższy $C$ . W szczególności więc $AC < BC$ . Zatem w trójkącie $ABC$ bok $\overline{BC}$ jest najdłuższy, a więc kąt $\measuredangle BAC$ jest największy. Wynika stąd, że $\measuredangle BAC > \frac{\pi}{3}$ .

Udowodniliśmy w ten sposób, że jeżeli punkt $A \in Z$ jest połączony z pewnymi punktami $B$ i $C$ zbioru $Z$ , to $\measuredangle BAC > \frac{\pi}{3}$ .

Jeżeli więc punkt $A \in Z$ jest połączony (rys. 13) z punktami $B_1, B_2, \ldots, B_n$ zbioru $Z$ , to

$ \measuredangle B_1AB_2 > \frac{\pi}{3},\ \measuredangle B_2AB_3 > \frac{\pi}{3},\ \ldots, \measuredangle B_nAB_1 > \frac{\pi}{3}. $

Dodając te nierówności stronami otrzymujemy, że $2\pi > n \frac{\pi}{3}$ czyli $n < 6$ . Zatem liczba $n$ punktów zbioru $Z$ , z którymi jest połączony punkt $A$ jest nie większa od $5$ .

XXII OM - II - Zadanie 5

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

Dany jest zbiór liczb $\{1, 2, 3, \ldots, 100\}$ . Ze zbioru tego utworzyć 10 podzbiorów parami rozłącznych $N_i = \{a_{i,1}, a_{i,2}, \ldots a_{i,10}}$ ( $i = 1, 2, \ldots, 10$ ) tak, aby suma iloczynów

$ \sum_{i=10}^{10}\prod_{j=1}^{10} a_{i,j} $

była największa.

Rozwiązanie

Udowodnimy najpierw następujący

Lemat. Jeżeli $\{a_1, \ldots, a_r, b_1, \ldots, b_r \}$ jest zbiorem $2r$ różnych liczb dodatnich oraz $a_i < b_j$ dla $i,j = 1,2, \ldots,r$ , to dla każdego $k$ $(1 \leq k < r)$

$ (1) \qquad a_1 \ldots a_kb_{k+1} \ldots b_r + b_1 \ldots b_k a_{k+1} \ldots a_r < a_1 \ldots a_r + b_1 \ldots b_r. $

Inaczej mówiąc lemat stwierdza, że jeżeli dany zbiór jest rozbity na dwa podzbiory $r$ -elementowe, to suma iloczynów elementów należących do każdego z podzbiorów będzie największa, gdy każda liczba należąca do jednego z podzbiorów będzie mniejsza od każdej liczby należącej do drugiego.

Dowód. Przekształcamy nierówność (1) w sposób równoważny

$ a_1 \ldots a_k (b_{k+1} \ldots b_r - a_{k+1} \ldots a_r) < b_1 \ldots b_k - a_{k+1} \ldots a_r. $

$ (2) \qquad (b_1 \ldots b_k - a_1 \ldots a_k) (b_{k+1} \ldots b_r - a_{k+1} \ldots a_r) > 0. $

Z założenia mamy $a_1 \ldots a_k < b_1 \ldots b_k$ oraz $a_{k+1} \ldots a-r <b_{k+1} \ldots b_r$ . Wynika stąd nierówność (2).

Przystępujemy teraz do rozwiązania zadania. Przypuśćmy, że podzbiory $N_i$ ( $i =1,2, \ldots, 10$ ) zbioru $\{ 1, 2, 3, \ldots, 100\}$ spełniają warunki zadania. Wynika stąd w szczególności, że dla $i \ne j$ zbiór $N_i \cup N_j$ ma następującą własność: Jeżeli rozbić w dowolny sposób zbiór $N_i \cup N_j$ na dwa podzbiory $10$ -elementowe, to suma iloczynów elementów należących do każdego z podzbiorów będzie największa wtedy, gdy tymi podzbiorami będą $N_i$ i $N_j$ .

Z lematu wynika więc, że każda liczba należąca do zbioru $N_i$ jest mniejsza od każdej liczby należącej do zbioru $N_j$ lub odwrotnie. Zatem (zamieniając ewentualnie kolejność zbiorów $N_i$ ) zbiory $N_i$ spełniające warunki zadania mają następującą własność: Każda liczba należąca do zbioru $N_i$ jest mniejsza od każdej liczby należącej do zbioru $N_{i+1}$ dla $i = 1,2, \ldots, 9$ . Wobec tego do $N_1$ należy $10$ najmniejszych liczb zbioru $\{1, 2, 3, \ldots, 100\}$ , do $N_2$ - $10$ następnych liczb naturalnych itd. Ogólnie $N_i = \{10(i - 1) + j \colon j = 1, 2, \ldots, 10\}$ dla $i = 1,2, \ldots, 10$ .

XXII OM - II - Zadanie 6

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

Dany jest ciąg nieskończony $\{a_n\}$ . Dowieść, że jeżeli

$ a_n + a_{n+2} > 2a_{n+1} \quad \tex{ dla } \quad n = 1, 2, \ldots, $

$ \frac{a_1+a_3+\ldots a_{2n+1}}{n+1} \geq \frac{a_2+a_4+\ldots a_{2n}}{n} $

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

Rozwiązanie

Nierówność $a_n + a_{n+2} \geq 2a_{n+1}$ daną w założeniu przekształcamy do postaci równoważnej

$ (1) \qquad a_{n+2} - a_{n+1} \geq a_{n + 1} - a_n/ $

Oznaczając $b_{n+1} = a_{n+1} - a_n$ dla $n = 1, 2, \ldots$ nierówność (1) można zapisać w postaci $b_{n+2} > b_{n+1}$ . Zatem ciąg $\{b_n\}$ jest niemalejący.

Nierówność daną w tezie przekształcamy do postaci równoważnej

$ (2) \qquad n(a_1 + a_3+ \ldots + a_{2n+1}) \geq (n + 1)(a_2 + a_4 + \ldots + a_{2n}). $

Nierówność (2) udowodnimy przez indukcję ze względu na $n$ . Dla $n = 1$ przybiera ona postać $a_1 + a_3 \geq 2a_2$ . Jest to szczególny przypadek nierówności danej w założeniu.

Załóżmy z kolei, że nierówność (2) zachodzi dla pewnej liczby naturalnej $n$ , udowodnimy, że zachodzi ona dla liczby $n + 1$ , tzn. że

$ (3) \qquad (n +1)(a_1 + a_3+ \ldots + a_{2n+1} + a_{2n+3}) \geq (n + 2) (a_2 + a_4 + \ldots + a_{2n} + a_{2n+2}). $

Porównując (2) i (3) stwierdzamy, iż wystarczy dowieść, że

$ (4) \qquad (a_1 + a_3+ \ldots + a_{2n+1}) + (n + 1)a_{2n+3} \geq (a_2 + a_4 + \ldots + a_{2n}) + (n + 2)a_{2n+2}. $

Wtedy dodając stronami (2) i (4) otrzymamy (3).

Przekształcamy nierówność (4) w sposób równoważny

$ \begin{split} (n + 1)(a_{2n+3} - a_{2n+2}) \geq (a_2 - a_1) + (a_4 - a_3) + \ldots + \\ +(a_{2n} - a_{2n} - 1) + (a_{2n+2} - a_{2n+1}), \end{split} $

$ (5) \qquad (n + 1) b_{2n+3} \geq b_2 + b_4+ \ldots +b_{2n} + b_{2n+2}. $

Ponieważ, jak stwierdziliśmy na początku, ciąg $\{b_n\}$ jest niemalejący, więc w szczególności

$b_{2n + 3} \geq b_2,$

$b_{2n + 3} \geq b_4,$

$\ldots$

$b_{2n + 3} \geq b_{2n},$

$b_{2n + 3} \geq b_{2n+2}.$

Dodając te nierówności stronami otrzymujemy (5). Zatem prawdziwe są nierówności (4) i (3). Wobec tego na mocy zasady indukcji nierówność (2) zachodzi dla każdej liczby naturalnej $n$ .