XXXIX OM - II etap

II etap XXXIX Olimpiady Matematycznej

XXXIX OM - II - Zadanie 1

Zawody matematyczne:

XXXIX OM, 1987-1988

Etap:

Niech $f(x)$ będzie wielomianem, $n$ - liczbą naturalną. Udowodnić, że jeżeli $f(x^{n})$ dzieli się przez $x-1$ , to dzieli się również przez $x^{n-1} + x^{n-2} + \ldots + x + 1$ .

Rozwiązanie

Z warunku zadania wynika, że wielomian $F(x) = f(x'')$ przyjmuje w punkcie $x = 1$ wartość $0$ . Zatem i wielomian $f$ przyjmuje w punkcie $1$ wartość $0$ . Na mocy twierdzenia Bezout wielomian $f$ jest więc podzielny przez dwumian $x-1$ . Innymi słowy, istnieje wielomian $g$ taki, że $f(x) = (x-1)g(x)$ . Stąd

$ \begin{split} F(x) & =f(x^n) = (x^n-1)g(x^n) =\\ = (x-1)(x^{n-1}+x^{n-2}+ \ldots +x+1)g(x^n), \end{split} $

co dowodzi tezy zadania.

XXXIX OM - II - Zadanie 2

Zawody matematyczne:

XXXIX OM, 1987-1988

Etap:

Dane są liczby rzeczywiste $x_i$ , $y_i$ ( $i = 1, 2, \ldots, n$ ) takie, że

$ (1) \qquad x_1 \geq x_2 \geq \ldots \geq x_n \geq 0, \quad \qquad y_1 > y_2 > \ldots > y_n 0, $

oraz

$ \prod_{i=1}^k x_i \geq \prod_{i=1}^k y_i,\quad \text{ dla }\quad k=1,2,\ldots, n. $

Udowodnić, że

$ \sum_{i=1}^n x_i > \sum_{i=1}^n y_i. $

Rozwiązanie

Przepiszmy założenie (2) w postaci

$ \prod_{i=1}^k \frac{x_i}{y_i} \geq 1 \ \textrm{dla} \ k=1, \ldots,n. $

Na mocy nierówności między średnimi mamy więc

$ nr{3} \frac{1}{k} \sum_{i=1}^k \frac{x_i}{y_i} \geq \left( \frac{i=1}{k} \frac{x_i}{y_i} \right)^{1/k} \geq 1 \ \textrm{dla} \ k=1, \ldots,n. $

Wprowadźmy oznaczenie:

$ s_k= \sum_{i=1}^k \left( \frac{x_i}{y_i} -1 \right) = \left( \sum_{i=1}^k \frac{x_i}{y_i} \right) - k \ \textrm{dla} \ k=1, \ldots, n $

i przyjmijmy dodatkowo $s_0 = 0$ . Z otrzymanej przed chwilą nierówności (3) wynika, że liczby $s_k$ są nieujemne. Zauważmy, że

$ s_k - s_{k-1} = \frac{x_k}{y_k} - 1 = \frac{x_k -y_k}{y_k}, $

skąd

$ x_k-y_k = y_k(s_k-s_{k-1}) \ \textrm{dla} \ k = 1, \ldots, n. $

A zatem

$ \begin{split} (4) \qquad \sum_{k=1}^n (x_k - y_k) & = \sum_{k=1}^n y_k (s_k - s_{k-1}) = \\ & = y_1(s_1-s_0)+y_2(s_2-s_1)+\ldots+y_n(s_n-s_{n-1})=\\ & = (y_1y_2)s_1 + (y_2-y_3)s_2 + \ldots + (y_{n-1}-y_n)s_{n-1}+y_ns_n. \end{split} $

Wobec nierówności $y_1 \geq \ldots \geq y_n$ oraz $s_k \geq 0$ otrzymana suma jest nieujemna. Tak więc

$ \sum_{k=1}^n (x_k-y_k) \geq 0. $

A to właśnie mieliśmy wykazać.

Uwaga 1: Zastosowane w końcowej fazie rozumowania przekształcenie (4) polegające na takim przegrupowaniu składników, by zamiast sumy wyrażeń postaci $y_k \cdot \Delta s_k$ (gdzie $\Delta s_k = s_k-s{k-1}$ ) rozważać sumę wyrażeń $s_k \cdot \Delta y_k$ , nosi nazwę przekształcenia Abela. Jest ono często stosowane w różnych zagadnieniach związanych z badaniem ciągów i szeregów liczbowych. Warto zwrócić uwagę na podobieństwo tego przekształcenia do reguły ,,całkowania przez części''.

Uwaga 2: Nie korzystaliśmy nigdzie z założenia monotoniczności ciągu $(x_i)$ . Również w następnych sposobach nie będzie ono nam niepotrzebne.

To znaczy, przyjmujemy warunki (2) oraz (1'):

$ (1') \qquad y_1 \geq \ldots \geq y_n > 0;\ x_i > 0 \ \textrm{dla} \ i = 1, \ldots, n. $

Uwaga 3: Zadanie jest szczególnym przypadkiem następującego ogólnego twierdzenia:

Jeżeli liczby rzeczywiste $a_1, \ldots, a_n, b_1, \ldots, b_n$ spełniają warunki : $b_1 \geq \ldots \geq b_n$ oraz

$ (10) \qquad \sum_{i=1}^k a_i >\sum_{i=1}^k b_i \textrm{dla} \ k= 1,\ldots,n, $

to dla dowolnej niemalejącej funkcji wypukłej $f \colon \mathbb{R} \to \mathbb{R}$ zachodzi nierówność

$ (11) \qquad \sum_{i=1}^n f(a_i) \geq \sum_{i=1}^n f(b_i). $

(Aby otrzymać nasze zadanie, wystarczy przyjąć $x_i = e^{a_i}$ , $y_i = e^{b_i}$ , $f(x) = e^x$ .)

Jest to twierdzenie Hardy'ego—Littlewooda—Pólya'i (w skrócie H—L—P), a ściślej, jeden z jego wariantów. W oryginalnym (i najczęściej stosowanym) sformułowaniu twierdzenia H—L—P zakłada się dodatkowo, źe także $a_1 \geq \ldots \geq a_n$ i że nierówność (10) staje się równością dla $k = n$ ; za to teza (11) zachodzi wtedy dla dowolnej funkcji wypukłej $f$ , niekoniecznie monotonicznej. W przytoczonym przez nas brzmieniu nosi ono czasem nazwę twierdzenia Tomića lub twierdzenia Weyla; częściej jednak jest uważane za wariant starszego odeń twierdzenia H—L—P (którego dowody dadzą się łatwo przetwarzać na dowody twierdzenia Tomića—Weyla).

Omawiane twierdzenie, w obu tych wersjach, znajdzie Czytelnik wraz z dowodami i komentarzem na przykład w książce: D.S. Mitrinović, Analytic Inequalities; Berlin-Heidelberg-New York 1970 (Ch.2.24, Thms 1, 2). Stosowana tam metoda wykorzystuje przekształcenie Abela (a więc w pewnej mierze koresponduje z rozwiązaniem naszego zadania przedstawionym w sposobie I). Można jednakże, i to bez nadmiernych trudności, uzyskać dowód twierdzenia H—L—P (w którejkolwiek z rozważanych wersji) wzorując się na rozwiązaniu podanym w sposobie II; może to być interesującym zadaniem dla ambitniejszych Czytelników.

XXXIX OM - II - Zadanie 3

Zawody matematyczne:

XXXIX OM, 1987-1988

Etap:

Wewnątrz trójkąta ostrokątnego $ABC$ rozważamy punkt $P$ i jego rzuty $L, M, N$ odpowiednio na boki $BC, CA, AB$ . Wyznaczyć taki punkt $P$ , dla którego suma $|BL|^2 + |CM|^2 + |AN|^2$ jest najmniejsza.

Rozwiązanie

Niech $P$ będzie dowolnym punktem wewnątrz trójkąta $ABC$ . Rozważając trójkąty prostokątne $ANP$ , $BLP$ , $CMP$ (rysunek 7) stwierdzamy, że

$ |AP|^2+|BP|^2+|CP|^2 = |AN|^2+|PN|^2+|BL|^2 + |PL|^2+|CM|^2+|PM|^2. $

Analogicznie, z trójkątów AMP, BNP, CLP dostajemy

$ |AP|^2+|BP|^2 + |CP|^2 = |AM|^2 + |PM|^2+|BN|^2+|PN|^2 + |CL|^2 + |PL|^2. $

Stąd przez przyrównanie prawych stron otrzymanych równości:

$ (1) \qquad |AN|^2+|BL|^2+ |CM|^2 = |AM|^2+|BN|^2+|CL|^2. $

Lewa strona równości (1) - to właśnie rozważana w zadaniu wielkość; oznaczmy ją przez $f(P)$ . Mamy znaleźć punkt $P$ , dla którego $f(P)$ osiąga minimum.

Suma lewej i prawej strony równości (1) wynosi $2f(P)$ . Tak więc

$ (2) \qquad 2f(P) = (|BL|^2 + |CL|^2)+(|CM|^2 + |AM|^2)+ (|AN|^2+|BN|^2). $

Zauważmy teraz, że

$ \begin{split} |BL|^2+|CL|^2 & = \frac{1}{2}((|BL| + |CL|)^2+ (|BL|-|CL|)^2) =\\ & = \frac{1}{2}(|BC|^2+(|BL|-|CL|)^2). \end{split} $

Wartość tego wyrażenia jest najmniejsza, gdy różnica $|BL| - |CL|$ jest zerem (bo $|BC|$ jest stałe) - czyli gdy $L$ jest środkiem odcinka $BC$ . Tak samo pozostałe dwie sumy w nawiasach po prawej stronie (2) mają wartość najmniejszą, gdy punkty $M$ i $N$ są środkami boków $CA$ i $AB$ .

Te zaś warunki dają się zrealizować jednocześnie: rzuty punktu $P$ na boki trójkąta pokrywają się ze środkami tych boków wtedy i tylko wtedy, gdy $P$ leży na przecięciu symetralnych boków. Stąd odpowiedź: wielkość $f(P)$ osiąga minimum, gdy $P$ jest środkiem okręgu opisanego na trójkącie $ABC$ (należy on do wnętrza trójkąta $ABC$ , skoro trójkąt ten jest ostrokątny).

XXXIX OM - II - Zadanie 4

Zawody matematyczne:

XXXIX OM, 1987-1988

Etap:

Udowodnić, że dla każdej liczby naturalnej $n$ liczba $n^{2n} - n^{n+2} + n^n - 1$ jest podzielna przez $(n - 1 )^3$ .

Rozwiązanie

Oznaczmy:

$ N = n^{2n}-n^{n+2}+n^n-1, \ m = n-1. $

Przyjmijmy, że $n \geq 2$ , czyli $m \geq 1$ . Zgodnie z wzorem dwumianowym,

$ \begin{split} N & = (m + 1)^{2m+2}-(m+l)^{m+3}+ (m+1)^{m+1}-1 =\\ & = \left[ 1 +\binom{2m+2}{1} m +\binom{2m+2}{2}m^2+Am^3 \right]-\\ & - \left[ 1 +\binom{m+3}{1} m +\binom{m+3}{2}m^2+Bm^3 \right]+\\ & + \left[ 1 +\binom{m+1}{1} m +\binom{m+1}{2}m^2+Cm^3 \right]-1 \end{split} $

gdzie $A$ , $B$ , $C$ są liczbami całkowitymi. Przekształcamy dalej:

$ \begin{split} N & = (2m+2)m+(m+1) (2m + 1)m^2+Am^3-\\ & - (m+3)m- \frac{1}{2} (m+3) (m+2)m^2-Bm^3 +\\ + (m+1)m+ \frac{1}{2}(m+1)m \cdot m^2 + Cm^3 =\\ & = 2m^4 + m^3 + (A-B+C)m^3. \end{split} $

Zatem $N = Dm^3= D(n - 1)^3$ , gdzie $D$ jest liczbą całkowitą (oczywiście dla $n = 1$ jest to też prawda).

Wykazaliśmy więc, że $N$ dzieli się przez $(n - 1)^3$ .

XXXIX OM - II - Zadanie 5

Zawody matematyczne:

XXXIX OM, 1987-1988

Etap:

Rozstrzygnąć, czy każdy prostokąt, który można pokryć 25 kołami o promieniu 2 można też pokryć 100 kołami o promieniu 1.

Rozwiązanie

Odpowiedź jest twierdząca. Niech $R$ będzie prostokątem dającym się pokryć 25 kołami o promieniu 2. Osie symetrii prostokąta $R$ dzieją go na cztery prostokąty podobne do niego w skali $1 /2$ . Każdy z nich możemy pokryć rodziną 25 kół o promieniu 1; wystarczy przekształcić dane 25 kół o promieniu 2 przez jednokładność o skali $1/2$ względem odpowiedniego wierzchołka. Dostajemy w ten sposób 100 kół o promieniu 1 łącznie pokrywających cały prostokąt $R$ .

XXXIX OM - II - Zadanie 6

Zawody matematyczne:

XXXIX OM, 1987-1988

Etap:

Dany jest wielościan wypukły o $k$ ścianach $S_1, \ldots, S_k$ . Oznaczmy wektor długości 1 prostopadły do ściany $S_i$ ( $i = 1, \ldots, k$ ) zwrócony na zewnątrz danego wielościanu przez $\overrrightarrow{n_i}$ , natomiast pole powierzchni tej ściany przez $P_i$ . Dowieść, że

$ \sum_{i=1}^k P_i \cdot \overrightarrow{n_i} = \overrightarrow{0}. $

Rozwiązanie

Rozpoczniemy od uwagi, że jeśli w przestrzeni dany jest dowolny wielokąt płaski wypukły $S$ oraz płaszczyzna $\pi$ i jeśli $\overrightarrow{n}$ jest wektorem długości $1$ prostopadłym do płaszczyzny wielokąta $S$ , a w jest wektorem długości $1$ prostopadłym do płaszczyzny $\pi$ , to oznaczając przez $W$ rzut prostokątny wielokąta $S$ na płaszczyznę $\pi$ mamy następującą zależność między polami wielokątów $S$ i $W$ :

$ (1) \qquad \textrm{pole}\ W = (\textrm{pole}\ S) \cdot |\overrightarrow{n} \cdot \overrightarrow{w}| $

(kropka między wektorami oznacza iloczyn skalarny).

Wzór (I) jest oczywisty w przypadku, gdy rozważane płaszczyzny są równolegle lub prostopadłe (bo wówczas, odpowiednio, $|\overrightarrow{n} \cdot \overrightarrow{w}|$ równa się $1$ lub $0$ ). W pozostałym przypadku, gdy płaszczyzny te przecinają się wzdłuż prostej $l$ tworząc kąt $\varphi (0 < \varphi < \pi/2$ ), wzór (1) wynika z następujących spostrzeżeń:

Gdy $S$ jest prostokątem o jednym boku równoległym, a drugim prostopadłym do prostej $l$ , jego rzut $W$ na płaszczyznę $\pi$ też jest takim prostokątem. Długość boku równoległego do $l$ nie zmienia się przy rzutowaniu, natomiast długość boku prostopadłego do $l$ ulega skróceniu w stosunku $|\cos \varphi|$ . W tym samym stosunku zmienia się więc i pole prostokąta; otrzymujemy zatem
dla prostokąta $S$ wzór (1), bo $|\overrightarrow{n} \cdot \overrightarrow{w} | = |\cos \measuredangle (\overrightarrow{n}, \overrightarrow{w})| = |cos \varphi|$ .

Stąd natychmiast wynika prawdziwość (1) dla dowolnego trójkąta prostokątnego o jednej przyprostokątnej równoległej, a drugiej prostopadłej do $l$ , bowiem trójkąt taki można uzupełnić do prostokąta (którego dwoma bokami są przyprostokątne danego trójkąta). Pole prostokąta zmienia się przy rzutowaniu w stosunku $|cos \varphi| = |\overrightarrow{n} \cdot \overrightarrow{w}|$ , więc to samo dzieje się z dwukrotnie mniejszym polem trójkąta (rysunek 8).

Wystarczy teraz zauważyć, że dowolny wielokąt wypukły $S$ jest sumą skończonej liczby trójkątów prostokątnych o przyprostokątnych równoległych i prostopadłych do prostej $l$ , o rozłącznych wnętrzach. Pole $S$ jest sumą pól tych trójkątów, a pole $W$ (rzutu $S$ na $\pi$ ) jest sumą pól rzutów poszczególnych trójkątów (rysunek 8). Pole rzutu każdego z tych trójkątów równa się polu trójkąta pomnożonemu przez ten sam współczynnik równy $|\overrightarrow{n} \cdot\overrightarrow{w}|$ i przez zsumowanie otrzymujemy dowodzony wzór (1).

Przystępujemy do dowodu tezy zadania. Niech

$ \overrightarrow{v} = P_1 \overrightarrow{n_1} + \ldots +P_k \overrightarrow{n_k}. $

Mamy dowieść, że $\overrightarrow{v}$ jest wektorem zerowym.

Wybierzmy w przestrzeni dowolny wektor $\overrightarrow{w}$ długości $1$ . Niech $\pi$ będzie dowolną płaszczyzną prostopadłą do wektora $\overrightarrow{w}$ . Rzut prostokątny rozważanego wielościanu na płaszczyznę $\pi$ jest wielokątem wypukłym $W$ . Rzut dowolnej ściany $S_i$ jest wielokątem wypukłym $W_i$ (zdegenerowanym do odcinka, jeśli $\overrightarrow{n_i} \bot \overrightarrow{w}$ ).

Rozbijamy zbiór wskaźników $\{1, \ldots, k\}$ na trzy podzbiory:

$ I_+ = \{i : \overrightarrow{n_i} \cdot \overrightarrow{w} > 0\},\quad I_- = \{i : \overrightarrow{n_i} \cdot \overrightarrow{w} < 0\}, $

$ I_0 = \{i : \overrightarrow{n_i} \cdot \overrightarrow{w} = 0\}. $

(Patrząc na wielościan z zewnątrz, w kierunku wektora $\overrightarrow{w}$ , widzimy ściany $S_i$ o numerach $i \in I_-$ , a nie widzimy ścian o numerach $i \in I_+$ ) (rysunek 9). Rzuty ścian o numerach $i \in I_+ \cup I_0$ nie mają wspólnych punktów wewnętrznych i wypełniają cały wielokąt $W$ . To samo można powiedzieć o rzutach ścian o numerach $i \in I_- \cup I_0$ . Zatem

$ \textrm{pole} \ W= \sum_{i \in I_+ \cup I_0} \textrm{pole} W_i = \sum_{i \in I_+} \textrm{pole} \ W_i $

i jednocześnie

$ \textrm{pole} \ W= \sum_{i \in I_- \cup I_0} \textrm{pole} W_i = \sum_{i \in I_-} \textrm{pole} \ W_i $

Zauważmy teraz, że w myśl wzoru (1),

$ \textrm{pole}\ W_i = P_i \cdot |\overrightarrow{n_i} \cdot \overrightarrow{w} | = \left\{\begin{array}{ccl} P_i \cdot (\overrightarrow{n_i} \cdot \overrightarrow{w}) & \textrm{dla} & i \in I_+\\ 0 & \textrm{dla} & i \in I_0\\ -P_i \cdot (\overrightarrow{n_i} \cdot \overrightarrow{w}) & \textrm{dla} & i \in I_- \end{array}\right. $

Wobec tego

$ \begin{split} \overrightarrow{v} \cdot \overrightarrow{w} & = \left( \sum_{i=1}^k P_i \overrightarrow{n_i} \right) \cdot \overrightarrow{w} = \sum_{i=1}^k P_i \cdot (\overrightarrow{n_i} \cdot \overrightarrow{w}) = \\ & = \sum_{i \in I_+} P_i \cdot (\overrightarrow{n_i} \cdot \overrightarrow{w})+ \sum_{i \in I_-} P_i \cdot (\overrightarrow{n_i} \cdot \overrightarrow{w}) +\sum_{i \in I_0} P_i \cdot (\overrightarrow{n_i} \cdot \overrightarrow{w}) =\\ & = \sum_{i \in I_+} \textrm{pole} W_i - \sum_{i \in I_-} \textrm{pole} W_i +0 =\textrm{pole} W-\textrm{pole} W = 0. \end{split} $

Wektor $\overrightarrow{w}$ był wybrany dowolnie. Wykazaliśmy w ten sposób, że wektor $\overrightarrow{v}$ jest prostopadły do dowolnego wektora o długości $1$ . Jest więc wektorem zerowym.