XXIII OM - III etap

III etap XXIII Olimpiady Matematycznej

XXIII OM - III - Zadanie 1

Zawody matematyczne:

XXIII OM, 1971-1972

Etap:

III

Wielomiany $u_1(x) = a_ix + b_i$ ( $a_i, b_i$ - liczby rzeczywiste; $i = 1, 2, 3$ ) spełniają dla pewnego naturalnego $n > 2$ równanie

$ (1) \qquad [u_1(x)]^n + [u_2(x)]^n = [u_3(x)]^n. $

Udowodnić, że istnieją takie liczby rzeczywiste $A, B, c_1, c_2, c_3$ , że $u_i(x)=c_i(Ax+B)$ dla $i = 1, 2, 3$ .

Rozwiązanie

Jeżeli $a_1 = a_2 = 0$ , to wielomiany $u_1$ i $u_2$ są stałe. Wobec tego wielomian $u_3$ też jest stały, tzn. $a_3 = 0$ . W tym przypadku wystarczy przyjąć $c_i = b_i$ dla $i = 1, 2, 3$ oraz $A = 0$ i $B = 1$ .

Niech więc co najmniej jedna z liczb $a_1, a_2$ będzie różna od zera, np. $a_1 \ne 0$ . Oznaczając $y = a_1x + b_1$ otrzymamy $u_j(x) = \displaystyle \frac{a_j}{a_1} y + \frac{b_ja_1 - a_jb_1}{a_1}$ dla $j = 2, 3$ , czyli $u_j(x) = A_jy + B_j$ , gdzie $A_j = \displaystyle \frac{a_j}{a_1}$ , $\displaystyle \frac{b_ja_1 - a_jb_1}{a_1}$ , $j = 2, 3$ . Równość (1) przybiera więc postać

$ (2) \qquad y^n + (A_2y + B_2)^n = (A_3y + B_3)^n,\ \textrm{gdzie} y \in \mathbb{R}. $

Porównując wyrazy wolne i współczynniki przy $y$ i $y^n$ (korzystamy tu z założenia n > 2) po obu stronach równości (2) otrzymamy

$ (3) \qquad B^n_2 = B^n_3, $

$ (4) \qquad n \cdot A_2 B^{n-1}_2 = n \cdot A_3 B_3^{n-1}, $

$ (5) \qquad 1 + A_2^n = A_3^n. $

Jeżeli $B_2 = 0$ , to z (3) wynika, że $B_3 = 0$ i wobec tego $b_ja_1 - a_jb_1 = 0$ dla $j = 2, 3$ , czyli $b_j = \displaystyle \frac{a_j}{a_1} b_1$ . Wystarczy więc w tym przypadku przyjąć $c_1 = 1$ , $c_j = \displaystyle \frac{a_j}{a_1}$ dla $j = 2, 3$ , $A = a_1$ , $B = b_1$ .

Jeżeli $B_2 \ne 0$ , to z (3) wynika, że $B_3 = 0$ i dzieląc stronami (4) przez (3) otrzymamy $\displaystyle \frac{A_2}{B_2} = \frac{A_3}{B_3}$ . Podnosząc obie strony ostatniej nierówności do $n$ -tej potęgi i wykorzystując (3) otrzymujemy $A^n_2 = A^n_3$ . Przeczy to równości (5). Zatem ten przypadek nie może mieć miejsca.

XXIII OM - III - Zadanie 2

Zawody matematyczne:

XXIII OM, 1971-1972

Etap:

III

Na płaszczyźnie danych jest $n > 2$ punktów, z których żadne trzy nie ją współliniowe. Udowodnić, że najkrótsza spośród łamanych zamkniętych przechodzących przez te punkty jest łamaną zwyczajną.

Rozwiązanie

Przypomnijmy określenie łamanej zwyczajnej: Łamaną zamkniętą o kolejnych wierzchołkach $W_1, W_2, \ldots, W_n, W_{n+1}$ , gdzie $W_{n+1} = W_1$ , nazywamy łamaną zwyczajną, jeżeli odcinki domknięte $\overline{W_iW_{i+1}}$ i $\overline{W_jW_{j+1}}$ są rozłączne dla $1 \leq i,j \leq n$ , $1 <j - i < n - 1$ .

Niech żadne trzy z punktów $A_1, A_2, \ldots, A_n$ na płaszczyźnie nie będą współliniowe i niech $A_{n+1} = A_1$ . Przypuśćmy, że łamana zamknięta $L$ przechodząca kolejno przez punkty $A_1, A_2, \ldots, A_n, A_{n+1}$ jest najkrótsza i nie jest łamaną zwyczajną. Jeżeli $i \ne j$ , $1 \leq i, j \leq n$ , to niech $L (A_i, A_j)$ będzie częścią łamanej $L$ o początku w punkcie $A_i$ i zawierającą kolejno punkty $A_{i+1}, A_{i+2}, \ldots, A_j$ .

Dla $i = 1, 2, \ldots, n$ mamy $L(A_i, A_{i+1}) = \overline{A_i A_{i+1}}$ , ponieważ najkrótszą łamaną łączącą dwa punkty jest odcinek.

Z przypuszczenia, że $L$ nie jest łamaną zwyczajną wynika, że istnieją takie liczby $i$ , $j$ , że

$ (1) \qquad 1 \leq i, j \leq n \ \textrm{oraz}\ 1 < j - i < n - 1 $

oraz łamana $L(A_i, A_{i+1})$ i $L(A_j, A_{j+1})$ mają punkt wspólny $P$ (rys. 15). Z warunków (1) wynika, że punkty $A_i, A_{i+1}, A_j, A_{j+1}$ są różne. Wobec tego punkt $P$ należy do wnętrza każdego z odcinków $\overline{A_iA_{i+1}}$ , $\overline{A_jA_{j+1}}$ ; z założenia bowiem żadne trzy z punktów $A_1, A_2, \ldots, A_n$ nie leżą na jednej prostej.

Ponieważ w trójkącie długość dowolnego boku jest mniejsza niż suma długości boków pozostałych, więc

$ A_iA_j < A_iP + PA_j \ \textrm{oraz}\ A_{i+1}A_{j+1} < A_{i+1}P + PA_{j+1}. $

Stąd

$ A_1A_j + A_{i+1}A_{j+1} < A_iA_{i+1} + A_jA_{j+1}. $

Wobec tego łamana zamknięta $L'$ złożona kolejno z łamanych $L(A_{j+1}, A_i)$ , $\overline{A_iA_j}$ , $L(A_{i+1}, A_j)$ , $\overline{A_{i+1}A_{j+1}}$ przechodzi przez punkty $A_1, A_2, \ldots, A_n$ i jest krótsza od łamanej zamkniętej $L$ , która składa się kolejno z łamanych $L(A_{j+1}, A_i)$ , $\overline{A_iA_{i+1}}$ , $L(A_{i+1}, A_j)$ , $\overline{A_jA_{j+1}}$ . Uzyskana sprzeczność dowodzi, że najkrótsza łamana zamknięta przechodząca przez punkty $A_1, A_2, \ldots, A_n$ jest łamaną zwyczajną.

Uwaga. Łatwo dowieść, że istnieje łamana zamknięta najkrótsza przechodząca przez dane punkty $A_1, A_2, \ldots, A_n$ . Mianowicie, jeżeli łamana przechodzi kolejno przez punkty $A_i$ i $A_j$ , to część łamanej zawarta między tymi punktami jest niekrótsza od odcinka $\overline{A_iA_j}$ (odcinek bowiem jest najkrótszą łamaną łączącą dwa punkty). Zatem, by znaleźć łamaną najkrótszą przechodzącą przez punkty $A_1, A_2, \ldots, A_n$ , wystarczy rozważać łamane złożone z odcinków $\overline{A_iA_j}$ . Odcinków takich jest liczba skończona. Zatem i łamanych zamkniętych wyznaczonych przez takie odcinki jest tylko liczba skończona. Istnieje więc wśród tych łamanych najkrótsza.

XXIII OM - III - Zadanie 3

Zawody matematyczne:

XXIII OM, 1971-1972

Etap:

III

Dowieść, że istnieje taki wielomian $P(x)$ o współczynnikach całkowitych, że dla wszystkich $x$ z przedziału $\langle \frac{1}{10}, \frac{9}{10}\rangle$ zachodzi nierówność

$ \left| P(x) - \frac{1}{2}\right| < \frac{1}{1000} $

Rozwiązanie

Rozpatrzmy wielomian $f_n(x) = \displaystyle \frac{1}{2} [(2x - 1)^n + 1]$ . Ma on oczywiście współczynniki całkowite. Ponadto dla $x \in \left< \displaystyle \frac{1}{10};\ \displaystyle \frac{9}{10} \right>$ mamy
$\displaystyle -\frac{4}{5} \leq 2x-1 \leq \frac{4}{5}$ i wobec tego $\left| f_n(x) - \displaystyle \frac{1}{2} \right| = \frac{1}{2} \left| 2x - 1 \right|^n \leq \frac{1}{2} \left( \frac{4}{5} \right)^n$ .

Zbadamy, dla jakich liczb naturalnych $n$ zachodzi nierówność $\displaystyle \frac{1}{2} \left( \frac{4}{5} \right)^n \leq \frac{1}{1000}$ . Przekształcamy ją w sposób równoważny

$ \displaystyle \left( \frac{4}{5} \right)^n < \frac{1}{500}, $

$ n \cdot \log 0,8 < \log 0,002, $

$ n > \frac{\log 0,002}{\log 0,8} = 27,8. $

Zatem warunki zadania spełnia każdy wielomian $f_n(x)$ , gdzie $n \geq 28$ .

XXIII OM - III - Zadanie 4

Zawody matematyczne:

XXIII OM, 1971-1972

Etap:

III

Na prostej nie mającej punktów wspólnych z kulą $K$ dane są punkty $A$ i $B$ . Rzut prostokątny $P$ środka kuli $K$ na prostą $AB$ lezy między punktami $A$ i $B$ , przy czym $AP$ i $BP$ są większe od promienia kuli. Rozpatrujemy zbiór $Z$ trójkątów $ABC$ , których boki $\overline{AC}$ i $\overline{BC}$ są styczne do kuli $K$ . Udowodnić, że $T$ jest trójkątem o największym obwodzie spośród trójkątów zbioru $Z$ wtedy i tylko wtedy, gdy $T$ jest trójkątem o największym polu spośród trójkątów zbioru $Z$ .

Rozwiązanie

Udowodnimy najpierw

Lemat. Jeżeli $S$ jest wierzchołkiem, $O$ - środkiem podstawy stożka obrotowego prostego, a punkt $T$ należy do płaszczyzny podstawy, to prosta $ST$ tworzy największy kąt z taką tworzącą $SR$ stożka, że $O \in \overline{TR}$ (rys 16).

Dowód. Dla dowolnego punktu $R$ należącego do obwodu podstawy stożka mamy na mocy twierdzenia cosinusow

$ TR^2 = SR^2 + TS^2 - 2SR \cdot TS \cos \measuredangle TSR. $

Ponieważ wielkości $SR$ i $TS$ są stałe (nie zależą od położenia punktu $R$ ), więc $\measuredangle TSR$ będzie największy, gdy jego cosinus będzie najmniejszy, tzn. gdy $TR$ będzie możliwie duże. To ma miejsce, gdy $O \in \overline{TR}$ .

Przystępujemy teraz do rozwiązania zadania. Niech $ABC_O$ będzie tym trójkątem rodziny $Z$ , który zawiera środek $O$ kuli $K$ (trójkąt ten oczywiście należy do rodziny $Z$ ).

Niech $\alpha_0 = \measuredangle BAC_0$ , $\beta_0 = \measuredangle ABC_0$ i analogicznie dla dowolnego trójkąta $ABC$ rodziny $Z$ niech $\alpha = \measuredangle BAC$ , $\beta = \measuredangle ABC$ . Ponieważ prosta $AC$ jest styczna do kuli $K$ , więc jest ona tworzącą stożka obrotowego o osi $AO$ . Na mocy lematu mamy więc $\alpha_0 \geq \alpha$ i podobnie $\beta_0 \geq \beta$ . Rysując trójkąty $ABC_0$ i $ABC$ w jednej płaszczyźnie (rys. 17) stwierdzamy, że $\triangle ABC \subset \triangle ABC_0$ i trójkąty te mają wspólną podstawę. Wobec tego pole i obwód tróikata $ABC_0$ są nie mniejsze odpowiednio od pola i obwodu trójkąta $ABC$ .

XXIII OM - III - Zadanie 5

Zawody matematyczne:

XXIII OM, 1971-1972

Etap:

III

Udowodnić, że wszystkie podzbiory zbioru skończonego można ustawić w ciąg, którego kolejne wyrazy różnią się jednym elementem.

Rozwiązanie

Załóżmy, że dany zbiór skończony $A$ ma $n$ elementów. Stosując indukcję względem $n$ udowodnimy, że istnieje taki ciąg

$ (1) \qquad A_1, A_2, \ldots, A_{2^n} $

wszystkich podzbiorów zbioru $A$ , że

$ \begin{split} (2) \qquad \textrm{ dla } & i = 1, 2, \ldots, 2^n \textrm{ jeden ze zbiorów } A_{i+1} - A_i \\ \textrm{ oraz } & A_i - A_{i+1} \textrm{ jest pusty, a drugi - jednoelementowy}. \end{split} $

Dla $n = 1$ ciąg $\emptyset$ , $A$ spełnia oczywiście (2). Załóżmy że dla pewnej liczby naturalnej $n$ istnieje taki ciąg (1) wszystkich podzbiorów zbioru $n$ -elementowego $A$ , który spełnia (2). Udowodnimy, że istnieje ciąg wszystkich podzbiorów zbioru $(n+1)$ -elementowego $A \cup \{b\}$ , który spełnia (2).

Stosujemy indukcję względem $n$ . Jeżeli ciąg (1) wszystkich podzbiorów zbioru $n$ -elementowego $A$ spełnia warunek (2), to następujący ciąg wszystkich podzbiorów zbioru $(n + 1)$ -elementowego $A \cup \{b\}$ spełnia też ten warunek:

$ (5) \qquad A_1, A_2, \ldots, A_{2n}, A_{2n} \cup \{b\}, A_{2n-1} \cup \{b\}, \ldots, A_2 \cup \{b\}, A_1 \cup \{b\}, $

zawiera on bowiem wszystkie zbiory $A_i$ oraz wszystkie zbiory $A \cup \{b\}$ dla $i = 1, 2, \ldots, 2^n$ , tzn. wszystkie podzbiory zbioru $A \cup \{b\}$ . Rozpatrzmy kolejne wyrazy ciągu (5). Z założenia indukcyjnego wiemy, że jeden ze zbiorów $A_{i+1} - A_i$ oraz $A_i - A_{i+1}$ jest pusty, a drugi - jednoelementowy; wynika stąd też, że jeden ze zbiorów ( $A_{i+1} \cup \{b\} - (A_i \cup \{b\}) = A_{i+1} - A_i$ oraz $(A_i \cup \{b\}) - (A_{i+1} \cup \{b\}) = A_i - A_{i+1}$ jest pusty, a drugi - jednoelementowy.

Wreszcie $(A_{2^n} \cup \{b\}) - A_{2^n} = \{b\}$ i $A_{2^n} - (A_{2^n} \cup \{b\}) = \emptyset$ . Zatem ciąg (5) spełnia warunek (2).

Uwaga. Zadanie to ma interesującą interpretację geometryczną. Rozpatrzmy przypadek $n = 3$ . Jeżeli $A = \{a_1, a_2, a_3\}$ , to każdy podzbiór $A'$ zbioru $A$ można utożsamiać z punktem $(e_1, e_2, e_3)$ , którego współrzędne są równe $0$ lub $1$ . Mianowicie określamy

$ e_j = \left\{ \begin{array}{cll} 0, & \textrm{gdy} & a_j \not \in A', \\ 1, & \textrm{gdy} & a_j \in A'. \\ \end{array} \right. $

Punkty takie są wierzchołkami sześcianu wyznaczonego przez wektory jednostkowe osi układu współrzędnych.

Niech $A'$ i $A''$ będą podzbiorami zbioru $A$ . Jeden ze zbiorów $A' - A''$ oraz $A'' - A'$ jest pusty, a drugi - jednoelementowy wtedy i tylko wtedy, gdy punkty odpowiadające zbiorom $A'$ i $A''$ różnią się jedną współrzędną. Punkty takie należą do pewnej krawędzi sześcianu. Zadanie nasze można więc sformułować tak: Istnieje taka łamana utworzona przez pewne krawędzie sześcianu, która przechodzi dokładnie jeden raz przez każdy jego wierzchołek.

W przypadku $n \ne 3$ można podać analogiczną interpretację zadania. Należy tylko zamiast sześcianu rozpatrywać kostkę $n$ -wymiarową.

XXIII OM - III - Zadanie 6

Zawody matematyczne:

XXIII OM, 1971-1972

Etap:

III

Dowieść, że suma cyfr liczby $1972^n$ dąży do nieskończoności, gdy $n$ dąży do nieskończoności.

Rozwiązanie

Udowodnimy ogólnie, że jeżeli $a$ jest liczbą naturalną parzystą niepodzielną przez $5$ i $s_n$ oznacza sumę cyfr liczby $a^n$ dla $n = 1, 2, \ldots$ , to ciąg $s_n$ dąży do nieskończoności.

Niech $a_r, a_{r-1}, \ldots, a_2, a_1$ , gdzie $a \ne 0$ , będą kolejnymi cyframi liczby $a^n$ , tzn. niech

$ a^n = (a_r, a_{r-1}, \ldots a_2, a_1)_{10}. $

Cyfra $a_1$ jest różna od zera, ponieważ z założenia liczba $a$ nie jest podzielna przez $5$ , a więc i liczba $a_n$ nie jest podzielna przez $5$ . Mamy też $a^n < 10^r$ , czyli $r > n \log_{10} a \geq n \log_{10} 2$ .

Udowodnimy

Lemat.

Dla każdej liczby naturalnej $j$ spełniającej warunek

$ (1) \qquad j \leq \frac{1}{4} \min (r, n) $

co najmniej jedna z cyfr $a_{j+1}, a_{j+2}, \ldots, a_{4j}$ liczby $a^n$ jest różna od zera.

Dowód. Gdyby dla pewnej liczby naturalnej $j$ spełniającej (1) zachodziło $a_{j+1} = a_{j+2} = \ldots = a_{4j} = 0$ , to oznaczając

$ c = (a_j a_{j-1} \ldots a_2 a_1)_{10} $

mielibyśmy $a^n - c = (a_r a_{r-1} \ldots a_{4j+1} 0 \ldots 0)_{10}$ . Zatem $10^{4j} \mid a^n - c$ i tym bardziej $2^{4j} \mid a^n - c$ . Ponadto z $2 \mid a$ wynika, że $2^n \mid a^n$ . Stąd wobec $4^j \leq n$ otrzymujemy $2^{4j} \mid a^n - (a^n - c) = c$ . Jednak $2^{4j} = 16^j > 10^j > c$ . Zatem $c = 0$ . Jest to jednak niemożliwe, ponieważ ostatnia cyfra $a_1$ liczby $c$ jest różna od zera. Uzyskana sprzeczność kończy dowód lematu.

Z założenia i z tego lematu wynika w szczególności, że w każdym z następujących ciągów cyfr istnieje wyraz różny od zera:

$ (2) \qquad \begin{array}{l} a_1, \\ a_2,\ a_3,\ a_4, \\ a_5,\ a_6,\ \ldots,\ a_{16}, \\ \qquad\vdots \\ a_{4^k+1},\ a_{4^k+2},\ \ldots,\ a_{4^k+1}, \end{array} $

gdzie liczba $j = 4^k$ spełnia warunek (1), tzn. $4^k \leq \displaystyle \frac{1}{4} \min (r, n)$ . Ponieważ $\displaystyle \frac{1}{4} \min (r, n) \geq \frac{1}{4} \min (n \log_{10} 2, n) = \frac{1}{4} n \log_{10} 2 > \frac{1}{16} n$ , więc jako $k$ można przyjąć największą liczbę naturalną spełniającą jedną z następujących równoważnych nierówności

$ 4^k \leq \frac{1}{16} n,\ 4^{k+2} \leq n,\ k + 2 \leq \log_4 n,\ \textrm{tzn.} k + 2 = [\log_4 n]. $

Ciągi (2) zawierają różne cyfry liczby $a^n$ , ciągów tych jest $k + 2$ i każdy z nich zawiera cyfrę różną od zera. Zatem suma cyfr $s_n$ liczby $a^n$ jest nie mniejsza od $k + 2 = [\log_4 n]$ .

Ponieważ $s_n \geq [\log_4 n] > \log_4 n - 1$ i $\displaystyle \lim_{n \to \infty} \log_4 n = \infty$ , więc $\displaystyle \lim_{n \to \infty} s_n = \infty$ .