XXI OM - II etap

II etap XXI Olimpiady Matematycznej

XXI OM - II -Zadanie 1

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

Udowodnić, że

$ (1) \qquad |\cos n\beta - \cos n\alpha| \leq n^2 |\cos \beta - \cos\alpha|, $

gdzie $n$ jest liczbą naturalną. Zbadać, dla jakich wartości $n$ , $\alpha$ , $\beta$ zachodzi równość.

Rozwiązanie

Udowodnimy przez indukcję, że dla każdej liczby naturalnej $n > 1$ i liczby $x \ne k\pi$ ( $k \in \mathbb{C}$ ) zachodzi nierówność

$ (2) \qquad | \sin nx | < n | \sin x |. $

Załóżmy prawdziwość (2) dla pewnej liczby naturalnej $n > 1$ ; udowodnimy prawdziwość analogicznej nierówności dla liczby $n + 1$ . Mamy

$ \begin{split} |\sin(n + 1)x| & = |\sin nx \cos x + \cos nx \sin x| \leq |\sin nx| \cdot |\cos x| + |\cos nx| \cdot |\sin x| \leq \\ & \leq |\sin nx| + |\sin x| < n |\sin x| + |\sin x| = (n + 1)|\sin x|. \end{split} $

Zatem, jeśli $\alpha + \beta \ne 2k\pi$ i $\alpha - \beta \ne 2k\pi$ i $n > 1$ , to korzystając z tożsamości

$ \cos a - \cos b = -2 \sin \frac{a+b}{2} \sin \frac{a-b}{2} $

i z nierówności (2) otrzymujemy

$ \begin{split} | \cos n \beta - & \cos n \alpha | = 2 \left|\sin n \cdot \frac{\beta + \alpha}{2} \right| \left| \sin n \cdot \frac{\beta - \alpha}{2} \right| \leq \\ & \leq 2n^2 \left| \sin \frac{\beta + \alpha}{2} \right| \left| \sin \frac{\beta - \alpha}{2} \right| = n^2 \left| -2 \sin \frac{\beta + \alpha}{2} \sin \frac{\beta - \alpha}{2} \right| = \\ & = n^2 |\cos \beta - \cos \alpha|. \end{split} $

Jeśli zaś $n = 1$ , to oczywiście w (1) zachodzi równość. Podobnie, jeśli $\alpha + \beta = 2k\pi$ lub $\alpha - \beta = 2k\pi$ , to $\cos \alpha = \cos \beta$ oraz $\cos n \alpha = \cos n \beta$ i też w (1) zachodzi równość.

XXI OM - II -Zadanie 2

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

Na bokach $n$ -kąta foremnego obrano $n + 1$ punktów dzielących obwód na równe części. Przy jakim położeniu obranych punktów pole wielokąta wypukłego o tych $n + 1$ wierzchołkach jest a) największe, b) najmniejsze?

Rozwiązanie

Oznaczmy przez $a$ $(n + 1)$ -szą część długości boku $n$ -kąta foremnego $A_1A_2 \ldots A_n$ (rys. 10), tzn. niech, długość boku tego $n$ -kąta będzie równa $(n + 1)a$ . Wtedy obwód $n$ -kąta będzie równy $n(n + 1)a$ . Wobec tego wierzchołki $(n + 1)$ -kąta dzielą obwód $n$ -kąta foremnego na części równe $na$ .

Ponieważ $na < (n + 1 )a < 2na$ , więc do każdego boku $n$ -kąta należy co najmniej jeden i co najwyżej dwa wierzchołki $(n + 1)$ -kąta. Z drugiej strony do pewnego boku, np. $\overline{A_1A_n}$ , $n$ -kąta należą co najmniej dwa wierzchołki $(n + 1 )$ -kąta, ponieważ $n + 1 > n$ .

Oznaczmy przez $B_1$ ten z wierzchołków $(n + 1 )$ -kąta należących do boku $\overline{A_1A_n}$ , który jest położony bliżej punktu $A_1$ niż pozostały
wierzchołek $(n + 1)$ -kąta należący do $\overline{A_1A_n}$ . Oznaczmy przez $x$ długość odcinka $\overline{A_1B_1}$ Z powyższego wynika, że $0 \leq x \leq a$ . Wreszcie oznaczmy przez $B_2$ wierzchołek $(n + 1)$ -kąta różny od $B_1$ należący do boku $A_1A_2$ i dalej przez $B_3, \ldots, B_{n+1}$ - kolejne wierzchołki $(n + 1)$ -kąta.

Różnica pól $n$ -kąta i $(n + 1)$ -kąta $S_n - S_{n+1}$ jest równa sumie pól trójkątów $B_1A_1B_2, B_2A_2B_3, \ldots, B_nA_nB_{n+1}$ . W każdym takim trójkącie mamy:

$ B_iA_iB_{i+1}= \alpha \textrm{ jest kątem } n \textrm{-kąta foremnego, oraz} $

$ (1) \qquad B_iA_i + A_iB_{i+1} = na \textrm{ dla } i = 1, 2, \ldots, n. $

Wobec tego pole $P_i$ trójkąta $B_iA_iB_{i+1}$ jest równe

$ (2) \qquad P_i = \frac{1}{2} B_i A_i \cdot A_i B_{i+1} \cdot \sin \alpha. $

Ponieważ

$ (3) \qquad A_iB_{i+1} + B_{i+1}A_{i+1} = A_iA_{i+1} = (n+1)a \textrm{ dla } i = 1, 2, \ldots, n - 1, $

więc z (1) i (3) otrzymujemy kolejno

$ B_1A_1 + A_1B_2 = na,\textrm{ czyli }x + A_1B_2 = na. $

Stąd $A_1B_2 = na - x$ . $A_1B_2 + B_2A2 = (n + 1)a$ i stąd
$B_2A_2 = (n + 1)a - A_1B_2 = a + x$ , $B_2A2 + A_2B_3 = na$ i stąd $A_2B_3 = na - (a + x) = (n - 1)a - x$ ,
$A_2B_2 + B_3A_3 = (n + 1)a$ i stąd $B_3A_3 = (n + 1)a - ((n - 1)a - x) = 2a + x$
i przez łatwą indukcję ogólnie

$ (4) \qquad A_iB_{i+1} = (n - i + 1)a - x \textrm{ oraz } B_iA_i = (i - 1)a + x \textrm{ dla } i = 1,\ldots, n. $

Wobec tego z (4) i (2) otrzymujemy

$ \begin{split} S_n - S_{n+1} &= \sum_{i=1}^n P_i = \sum_{i=1}^n \frac{1}{2} ((i-1) a + x) (( n-i+1)a -x) \sin \alpha =\\ & = \frac{1}{2} \sin \alpha \sum_{i=0}^{n-1} (ia + x) ((n-i)a -x) =\\ & = \frac{1}{2} \sin \alpha \sum_{i=0}^{n-1} (-x^2 + (n-2i) ax + i(n-i) a^2) =\\ & = \frac{1}{2} \sin \alpha \left[ -nx^2 + \left( n^2 - 2 \sum_{i=0}^{n-1} i \right) ax + \sum_{i=0}^{n-1} i(n - i) a^2 \right]. \end{split} $

Oznaczmy przez $Ax^2 + Bx + C$ trójmian kwadratowy zapisany w ostatnim nawiasie kwadratowym. Wtedy $A = -n$ i $B = \left( n^2 - 2 \frac{n(n-1)}{2} \right) a = na$ . Otrzymujemy więc, że

$ S_n - S_{n+1} = \frac{1}{2} \sin \alpha \cdot (-nx^2 + nax + C), $

czyli

$ \begin{split} S_{n+1} & = S_n - \frac{1}{2} \sin \alpha \cdot (-nx^2 + nax + C) = \left( \frac{1}{2} \sin \alpha \cdot n \right) x^2 + \\ & + \left(- \frac{1}{2} \sin \alpha \cdot na \right) x + \left( S_n - \frac{1}{2} \sin \alpha \cdot C \right) = px^2 + qx + r. \end{split} $

Pole $(n + 1)$ -kąta $S_{n+1}$ jest więc funkcją kwadratową $S_{n+1}(x) = px^2 + qx + r$ zmiennej $x$ rozpatrywaną w przedziale $0 \leq x \leq a$ .

Ponieważ $p = \frac{1}{2} \sin \alpha \cdot n > 0$ , więc funkcja ta przyjmuje wartość najmniejszą dla $x = \frac{-q}{2p} = \frac{\frac{1}{2} \sin \alpha \cdot na}{\sin \alpha \cdot na} = \frac{a}{2}$ . Punkt $\frac{a}{2}$ jest środkiem przedziału $\langle 0,\ a \rangle$ . Wobec tego liczby $S_{n+1} (0)$ i $S_{n+1} (a)$ są równe i są to największe wartości przyjmowane przez funkcję $S_{n+1} (x)$ w przedziale $\langle 0,\ a \rangle$ .

Zatem pole $(n + 1)$ -kąta jest największe, gdy $x = 0$ lub $x = a$ , tzn. gdy jeden z jego wierzchołków jest wierzchołkiem $n$ -kąta foremnego. Pole $(n + 1)$ -kąta jest najmniejsze, gdy $x = \frac{a}{2}$ , tzn. gdy jeden z boków $(n + 1)$ -kąta leży na boku $n$ -kąta foremnego tak, że środki tych boków pokrywają się.

XXI OM - II -Zadanie 3

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

Udowodnić twierdzenie: Nie istnieje taka liczba naturalna $n > 1$ , że liczba $2^n - 1$ dzieli się przez $n$ .

Rozwiązanie

\spos{1} Załóżmy, że $n$ jest najmniejszą liczbą naturalną większą od jedności taką, że $n \mid 2^n - 1$ , zaś $k$ - najmniejszą liczbą naturalną taką, że $n \mid 2^k - 1$ . Na mocy twierdzenia danego do dowodu w zadaniu 9 na zawodach stopnia I mamy $k < n$ .

Niech $n = km + r$ , gdzie $0 \leq r < k$ . Ponieważ $n \mid 2^n - 1$ i $n \mid 2^{km} - 1$ , więc $n \mid 2^n - 2^{km} = 2^{km} (2^r - 1)$ i wobec nieparzystości $n$ otrzymujemy, że $n \mid 2^r - 1$ . Stąd wobec określenia liczby $k$ i nierówności $r < k$ , wynika, że $r = 0$ . Zatem $k \mid n$ , $k \mid 2^k - 1$ i wobec określenia liczby $n$ i nierówności $k < n$ mamy $k = 1$ . Stąd $n \mid 2^1 - 1$ , $n = 1$ i otrzymujemy sprzeczność.

%Sposób 2. Niech w będzie najmniejszą liczbą naturalną większą od jedności taką, że n | 2^n - 1, zaś k- dowolną liczbą naturalną taką, że n | 2k - 1 i k < n. Niech d będzie największym wspólnym dzielnikiem liczb n i k. Na mocy twierdzenia danego do dowodu w za-
%daniu przygotowawczym B serii II istnieją takie liczby naturalne a i b, że ąn - bk = d. Ponieważ n | 2an - 1 i n | 2ik - 1, więc n | 2an - - 2bk = 2M(2 %Zatem n j 21 - 1 i n = 1. Otrzymujemy sprzeczność.
%Sposób 3. Niech n > 1 będzie dowolną liczbą naturalną taką, że n | 2^n - 1, zaś p - jej najmniejszym dzielnikiem pierwszym. Na mocy twierdzenia danego do dowodu w zadaniu 9 na zawodach stopnia I lub na mocy małego twierdzenia Fermata mamy p | 2k - 1, gdzie k jest pewną liczbą naturalną mniejszą od p. Z określenia liczby p wynika, że liczby k i n są względnie pierwsze. Zatem na mocy twierdzenia danego do dowodu w zadaniu przygotowawczym B serii II istnieją takie liczby naturalne a i b, że an - bk - 1. Ponieważ p | 2an - 1 i p|2bk -|, więc p | 2™ - 2hk = 2bh, czyli p = 2. Otrzymaliśmy sprzeczność, ponieważ n jest liczbą nieparzystą.

XXI OM - II -Zadanie 4

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

Dowieść, że jeżeli trójkąt $T_1$ zawiera trójkąt $T_2$ , to obwód trójkąta $T_1$ jest nie mniejszy od obwodu trójkąta $T_2$ .

Rozwiązanie

W wierzchołkach trójkąta $T_2$ wystawiamy proste prostopadłe do jego boków (rys. 11). Proste te wyznaczają punkty $A_1$ , $B_1$ , $B_2$ , $C_2$ , $C_3$ , $A_3$ na brzegu trójkąta $T_1$ . Ponieważ $AB \bot AA_1$ i $AB \bot BB_1$ więc długość odcinka $\overline{AB}$ jest nie większa od długości łamanej $A_1B_1$ . Analogicznie długości odcinków $\overline{BC}$ i $\overline{CA}$ są nie większe od długości łamanych odpowiednio $B_2C_2$ i $C_3A_3$ . Tym bardziej obwód trójkąta $T_2$ jest nie większy od obwodu trójkąta $T_1$ .

XXI OM - II -Zadanie 5

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

Dany jest wielomian $P(x) = \frac{1}{2} - \frac{1}{3}x + \frac{1}{6}x^2$ . Niech $Q(x) = \sum_{k=0}^{m} b_k x^k$ będzie wielomianem określonym wzorem

$ Q(x) = P(x) \cdot P(x^3) \cdot P(x^9) \cdot P(x^{27}) \cdot P(x^{81}). $

Obliczyć $\sum_{k=0}^m |b_k|$ .

Rozwiązanie

Wykorzystamy następujące oczywiste fakty:

(1) Iloczyn wielomianów o współczynnikach dodatnich jest wielomianem o współczynnikach dodatnich.

(2) Suma współczynników wielomianu $f(x)$ równa jest $f(1)$ .

(3) Moduły odpowiednich współczynników wielomianów $f(x)$ i $f(-x)$ są równe.

Ponieważ wielomian $P(-x) = \frac{1}{2} + \frac{1}{3} x + \frac{1}{6} x^2$ ma współczynniki dodatnie, więc na podstawie (1) wielomian $R(x) = Q(-x) = P(-x) \cdot P(- x^3) \cdot P(- x^9) \cdot P(- x^{27}) \cdot P(- x^{81})$ ma współczynniki dodatnie.

Na podstawie (2) suma współczynników wielomianu $R (x)$ równa jest $R(1) = P(- 1) \cdot P(- 1) \cdot P(- 1) \cdot P(- 1) \cdot P(-1) = 1$ . Zatem na podstawie (3) suma modułów współczynników wielomianu $Q(x)$ równa jest sumie współczynników wielomianu $Q(- x) = R(x)$ , czyli $1$ .

XXI OM - II -Zadanie 6

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

Jeśli $A$ jest podzbiorem zbioru $X$ , to przyjmujemy $A^1 = A$ , $A^{-1} = X - A$ . Podzbiory $A_1, A_2, \ldots, A_k$ nazywamy wzajemnie niezależnymi, jeśli iloczyn $A_1^{\varepsilon_1} \cap A_2^{\varepsilon_2} \ldots A_k^{\varepsilon_k}$ jest niepusty dla każdego układu liczb $\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_k$ , takiego, że $|\varepsilon_2| = 1$ dla $i = 1, 2, \ldots, k$ .
Jaka jest maksymalna liczba wzajemnie niezależnych podzbiorów zbioru $2^n$ -elementowego?

Rozwiązanie

Ponieważ liczba wszystkich ciągów $n$ -wyrazowych o wartościach $-1$ i $1$ równa jest $2^n$ (patrz zadanie przygotowawcze D serii III), więc możemy przyjąć, że elementami rozważanego zbioru $2^n$ -elementowego $X$ są takie ciągi.

Oznaczmy dla $i = 1, 2, \ldots, n$ przez $A_i$ zbiór wszystkich ciągów należących do $X$ , których $i$ -ty wyraz jest $1$ . Wykażemy, że podzbiory $A_1, A_2, \ldots, A_n$ są wzajemnie niezależne.

Ciąg $(\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_n)$ , gdzie $|\varepsilon_j| = 1$ , należy do każdego ze zbiorów $A_i^{\varepsilon_i}$ dla $i = 1, 2, \ldots, n$ . Jeśli bowiem $\varepsilon_i= 1$ , to rozważany ciąg ma $i$ -ty wyraz równy $1$ , a więc należy do $A_i^{\varepsilon_i} = A_i^1$ ; jeśli zaś $\varepsilon_i = -1$ , to rozważany ciąg ma $i$ -ty wyraz równy $- 1$ , czyli należy do $X - A_i = A_i^{-1}$ . Wobec tego zbiór $A_1^{\varepsilon_1} \cap A_2^{\varepsilon_2} \cap \ldots \cap A_n^{\varepsilon_n}$ zawiera ciąg $(\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_n)$ , a więc jest niepusty.

Wykażemy z kolei, że jeśli $r > n$ i $B_1, B_2, \ldots, B_r$ są pewnymi podzbiorami zbioru $X$ , to nie są one wzajemnie niezależne. Jeśli ciągi $(\varepsilon_1, \varepsilon_2, \ldots, \varepsilon_r)$ i $(\varepsilon'_1, \varepsilon'_2, \ldots, \varepsilon'_r)$ o wartościach $-1$ i $1$ są różne, to zbiory

$ B = B_1^{\varepsilon_1} \cap B_2^{\varepsilon_2} \cap \ldots \cap B_r^{\varepsilon_r} \textrm{ i } B' = B_1^{\varepsilon'_1} \cap B_2^{\varepsilon'_2} \cap \ldots \cap B_r^{\varepsilon'_r} $

są rozłączne. Mianowicie, jeśli np. $\varepsilon_i = 1$ , a $\varepsilon_i' = - 1$ , to mamy $B \subset B_i^{\varepsilon_i} = B_i$ oraz $B' \subset B_i^{-1} = X - B_i$ , a zbiory $B_i$ i $X - B_i$ oczywiście są rozłączne.

Zatem, gdyby zbiory $B_1, B_2, \ldots, B_r$ były wzajemnie niezależne, to wszystkie zbiory postaci $B_1^{\varepsilon_1} \cap B_2^{\varepsilon_2} \cap \ldots \cap B_r^{\varepsilon_r}$ byłyby niepuste i parami rozłączne. Zbiorów tych jest $2^r > 2^n$ . Jest to niemożliwe, ponieważ zbiór $X$ zawiera tylko $2^n$ elementów.

Udowodniliśmy więc, że $n$ jest maksymalną liczbą wzajemnie niezależnych podzbiorów zbioru $2^n$ -elementowego.