XXIV OM - II etap

II etap XXIV Olimpiady Matematycznej

XXIV OM - II - Zadanie 1

Zawody matematyczne:

XXIV OM, 1972-1973

Etap:

Udowodnić, że jeżeli liczby dodatnie $x, y, z$ spełniają nierówność

$ \frac{x^2+y^2-z^2}{2xy} + \frac{y^2+z^2-x^2}{2yz} + \frac{z^2+x^2-y^2}{2xz} > 1, $

to są one długościami boków pewnego trójkąta.

Rozwiązanie

\spos{1} Jak wiadomo, liczby dodatnie $x$ , $y$ , $z$ są długościami boków pewnego trójkąta wtedy i tylko wtedy, gdy każda z nich jest mniejsza od sumy dwóch pozostałych, tzn. gdy

$ (1) \qquad x < y + z,\ y < x + z \ \textrm{oraz}\ z < x + y. $

Przypuśćmy, że warunek ten nie jest spełniony, tzn. że jedna z liczb $x, y, z$ jest nie mniejsza od sumy liczb pozostałych. Bez zmniejszenia ogólności możemy przyjąć, że

$ (2) \qquad z \geq x + y. $

Wobec tego

$ (3) \qquad z - x \geq y \ \textrm{oraz} \ z - y \geq x. $

Dodając do pierwszego składnika lewej strony nierówności danej w zadaniu liczbę $1$ , a do każdego z dwóch pozostałych składników - liczbę $-1$ otrzymamy nierówność równoważną

$ (4) \qquad \frac{(x + y)^2-z^2}{2xy} + \frac{(z-y)^2-x^2}{2yz} + \frac{(z-x)^2 - y^2}{2xz} > 0. $

Na mocy (2) i (3) ułamki występujące po lewej stronie nierówności (4) są niedodatnie. Przeczy to nierówności (4).

Otrzymana sprzeczność dowodzi, że zachodzi warunek (1).

XXIV OM - II - Zadanie 2

Zawody matematyczne:

XXIV OM, 1972-1973

Etap:

W kwadracie danych jest dziewięć punktów, z których, żadne trzy nie są współliniowe. Dowieść, że trzy spośród nich są wierzchołkami trójkąta o polu nie przekraczającym $\frac{1}{8}$ pola kwadratu.

Rozwiązanie

Udowodnijmy najpierw

Lemat. Jeżeli trójkąt $ABC$ jest zawarty w pewnym prostokącie, to pole trójkąta jest nie większe od połowy pola tego prostokąta.

Dowód. Oznaczmy przez $A'$ , $B'$ , $C'$ odpowiednio rzuty wierzchołków trójkąta $ABC$ na jeden z boków prostokąta $PQRS$ zawierającego ten trójkąt (rys. 14). Niech np. $B' \in \overline{A'C'}$ i niech $D$ będzie punktem przecięcia prostej $AC$ z prostą prostopadłą do $PQ$ zawierającą punkt $B'$ .

Trójkąt $ABC$ jest sumą trójkątów $ABD$ i $CBD$ (jeden z nich może być zdegenerowany do odcinka, gdy $A' = B'$ lub $B' = C'$ ). Zatem $S_{ABC} = S_{ABD} + S_{BCD} = \displaystyle \frac{1}{2} A'B' \cdot BD + \frac{1}{2} B'C' \cdot BD = \frac{1}{2} A'C' \cdot BD$ .

Ponieważ $A'C' \leq PQ$ oraz $BD \leq QR$ , więc wynika stąd, że

$ S_{ABC} \leq \frac{1}{2} PQ \cdot QR. $

Przystępujemy teraz do rozwiązania zadania. Dzielimy dany kwadrat prostymi równoległymi do boków na cztery przystające kwadraty (lub cztery przystające prostokąty) - rys. 15. Pole takiego kwadratu (prostokąta) jest równe $\displaystyle \frac{1}{4}$ pola danego kwadratu. Z danych dziewięciu punktów co najmniej trzy należą do jednego z otrzymanych kwadratów (prostokątów). Pole trójkąta o wierzchołkach w tych punktach jest więc na mocy lematu nie większe od $\displaystyle \frac{1}{8}$ pola danego kwadratu.

Uwaga. W podobny sposób można wykazać, że teza zadania pozostanie prawdziwa, jeżeli liczby $9$ i $\displaystyle \frac{1}{8}$ zastąpić odpowiednio liczbami $2n+1$ i $\displaystyle \frac{1}{2n}$ . Wystarczy wtedy rozpatrzyć podział kwadratu prostymi równoległymi do boków na $n$ przystających prostokątów.

XXIV OM - II - Zadanie 3

Zawody matematyczne:

XXIV OM, 1972-1973

Etap:

Niech $f:\mathbb{R} \to \mathbb{R}$ będzie funkcją rosnącą spełniającą warunki:
1. $f(x+1) = f(x) + 1$ dla każdego $x \in \mathbb{R}$ ,
2. istnieje taka liczba całkowita p, że $f(f(f(O))) = p$ . Dowieść, że dla każdej liczby rzeczywistej $x$

$ \lim_{n\to \infty} \frac{x_n}{n} = \frac{p}{3}. $

gdzie $x_1 = x$ oraz $x_n =f(x_{n-1})$ dla $n = 2, 3, \ldots$ .

Rozwiązanie

Podamy najpierw kilka własności funkcji $f$ spełniającej warunek $1^\circ$ zadania. Niech $f_n(x)$ będzie $n$ -krotnym złożeniem funkcji $f$ , tzn. niech $f_1(x) = f(x)$ oraz $f_{n+1}(x) = f_n(f_1(x))$ dla $n = 1, 2, \ldots$ . Wynika stąd, że jeżeli $n = k + m$ , gdzie $k$ i $m$ są liczbami naturalnymi, to

$ (1) \qquad f_n(x)= f_k ( f_m (x)) \ \textrm{dla}\ x \in R. $

Udowodnimy, że dla dowolnej liczby całkowitej $r$ zachodzi wzór

$ (2) \qquad f(x+r) = f(x) + r \ \textrm{dla} \ x \in R. $

Rozpatrzmy najpierw przypadek, gdy $r$ jest liczbą naturalną. Zastosujemy metodę indukcji. Dla $r = 1$ wzór (2) wynika z warunku $1^\circ$ zadania. Załóżmy, że dla pewnej liczby naturalnej $r$ zachodzi wzór (2). Udowodnimy analogiczny wzór dla liczby $r + 1$ . Z warunku $1^\circ$ i z założenia indukcyjnego otrzymujemy

$ f(x + r+ 1) = f(x + r) + 1 =f(x) + r + 1. $

Zatem na mocy zasady indukcji wzór (2) zachodzi dla każdej liczby naturalnej $r$ .

Jeżeli $r = 0$ , to wzór (2) jest oczywiście prawdziwy. Jeżeli wreszcie $r = -s$ jest liczbą całkowitą ujemną, to $s$ jest liczbą naturalną i wobec tego

$ f(y + s) =f(y) + s\ \textrm{dla}\ y \in \mathbb{R}. $

Podstawiając tu $y = x - s$ otrzymujemy $f(x)=f(x - s) + s$ , czyli $f(x - s) =f(x) - s$ . Jest to wzór (2) dla $r = -s$ .

Przez indukcję ze względu na $n$ ze wzoru (2) wynika, że dla dowolnej liczby całkowitej $r$ i naturalnej $n$ zachodzi

$ (3) \qquad f_n(x + r) =f_n(x) + r \ \textrm{dla}\ x \in \mathbb{R}. $

Przystępujemy teraz do rozwiązania zadania. Zauważmy najpierw, że $x_{n+1} = f_n(x)$ dla $n = 1,2, \ldots$ , a więc należy znaleźć granicę ciągu
$\displaystyle \frac{f_n (x)}{n+1}$ . Udowodnimy najpierw, że

$ (4) \qquad \lim_{n \to \infty} \frac{f_n(0)}{n+1} = \frac{p}{3}. $

Niech $r$ będzie resztą z dzielenia liczby naturalnej $n$ przez $3$ , tzn. niech $n = 3k + r$ , gdzie $r = 0, 1$ lub $2$ oraz $k \geq 0$ . Przez indukcję względem $k$ udowodnimy, że

$ (5) \qquad f_n(0) = kp + f_r(0). $

Jeżeli $k = 0$ , to $n = r$ i wzór (5) jest prawdziwy. Jeżeli zaś wzór (5) zachodzi dla pewnej liczby $k \geq 0$ , to wzór ten dla liczby $k + 1$ ma postać

$ (6) \qquad f_{n+3}(0)= (k+ 1)p+ f_r(0). $

Wzór (6) wynika z (1), (3) i (5), ponieważ $f_{n+3}(0) =f_n (f_3(0)) = f_n(p) = f_n(0 + p) = f_n(0) + p = kp + f_r(0) + p = (k + 1)p + f_r(0)$ .

Zatem na mocy zasady indukcji wzór (5) zachodzi dla dowolnej liczby $k \geq 0$ .

Ponieważ $k = \displaystyle \frac{n-r}{3} = \frac{n+1}{3} - \frac{1-r}{3}$ , więc z (5) wynika, że

$ (7) \qquad \frac{f_n(0)}{n+1} = \frac{n-r}{3(n+1)} p + \frac{f_r(0)}{n+1} = \frac{p}{3} + \frac{(1-r)p + 3f_r(0)}{3(n+1)}. $

Ponieważ wyrażenie $(1-r)p + 3f_r(0)$ przybiera tylko trzy wartości (przy $r = 0, 1, 2$ ), więc jest ono ograniczone. Zatem

$ \lim_{n \to \infty} \frac{(1-r)p + 3f_r(0)}{3(n+1)} = 0 $

i z (7) wynika (4).

Teraz dla dowolnego $x \in \mathbb{R}$ niech, $a = [x]$ . Wtedy $a \leq x < a + 1$ . Ponieważ funkcja $f$ , a więc i $f_n$ , jest rosnąca, więc wynika stąd, że

$ (8) \qquad f_n(a) \leq f_n(x) < f_n(a+ 1). $

Liczba $a$ jest całkowita. Wobec tego z (3) i (8) otrzymujemy

$ \frac{a+f_n(0)}{n+1} \leq \frac{f_n(x)}{n+1} < \frac{a+1+f_n(0)}{n+1}. $

Ponieważ $\displaystyle \lim_{n \to \infty} \frac{a}{n+1} = 0$ , więc z (4) i (9) na mocy twierdzenia o trzech ciągach otrzymujemy, że $\displaystyle \lim_{n \to \infty} \frac{f_n(x)}{n+1} = 3$ .

XXIV OM - II - Zadanie 4

Zawody matematyczne:

XXIV OM, 1972-1973

Etap:

Niech $x_n = (p + \sqrt{q})^n - [(p + \sqrt{q})^n]$ dla $n = 1, 2, 3, \ldots$ . Dowieść, że jeżeli $p$ , $q$ są liczbami naturalnymi spełniającymi warunek $p - 1 < \sqrt{q} < p$ , to $\lim_{n\to \infty} x_n = 1$ .
Uwaga. Symbol $[a]$ oznacza największą liczbę całkowitą nie większą od $a$ .

Rozwiązanie

Udowodnimy najpierw

Lemat. Jeżeli $p$ i $q$ są liczbami całkowitymi, to liczba

$ (1) \qquad a_n = (p + \sqrt{q})^n +(p- \sqrt{q})^n $

jest całkowita dla $n = 0, 1, 2, \ldots$ .

Dowód. Korzystając ze wzoru dwumianowego otrzymujemy

$ \begin{split} a_n &= \sum_{i=0}^n \binom{n}{i} p^{n-i} (\sqrt{q})^i + \sum_{i=0}^n \binom{n}{i} p^{n-i} (-\sqrt{q})^i =\\ &=\sum_{i=0}^n \binom{n}{i} p^{n-i} ((\sqrt{q})^i + (-\sqrt{q})^i). \end{split} $

Jeżeli liczba $i$ jest parzysta, $i = 2m$ , to $(\sqrt{q})^i + (-\sqrt{q})^i = 2q^m$ Jeżeli zaś liczba $i$ jest nieparzysta, to $(\sqrt{q})^i + (-\sqrt{q})^i =(\sqrt{q})^i - (\sqrt{q})^i = 0$ . Zatem

$ a_n = \sum_{0 \leq m \leq \frac{n}{2}} \binom{n}{2m} p^{n-2m} \cdot 2q^m. $

Wynika stąd, że liczba $a_n$ jest całkowita.

XXIV OM - II - Zadanie 5

Zawody matematyczne:

XXIV OM, 1972-1973

Etap:

Dowieść, że jeżeli w czworościanie $ABCD$ mamy $AB = CD$ , $AC = BD$ , $AD = BC$ , to wszystkie ściany czworościanu są trójkątami ostrokątnymi.

Rozwiązanie

Udowodnimy najpierw

Lemat. Niech $\alpha, \beta, \gamma$ będą liczbami z przedziału $(0; \pi)$ . Istnieje kąt trójścienny, którego kąty płaskie mają miary równe $\alpha, \beta,\gamma$ wtedy i tylko wtedy, gdy każda z liczb $\alpha, \beta,\gamma$ jest mniejsza od sumy dwóch pozostałych.

Dowód. Bez zmniejszenia ogólności możemy przyjąć, że $\alpha \geq \beta \geq \gamma$ . Wtedy oczywiście $\beta < \alpha + \gamma$ i $\gamma < \alpha + \beta$ . Mamy więc udowodnić, że istnieje kąt trójścienny, którego kąty płaskie mają miary równe $\alpha, \beta,\gamma$ wtedy i tylko wtedy, gdy $\alpha < \beta + \gamma$ .

Niech $t$ będzie półprostą o początku w punkcie $P$ . Półproste o początku w punkcie $P$ tworzące z $t$ kąt o danej mierze $\mu$ są tworzącymi stożka obrotowego o wierzchołku w punkcie $P$ , osi $t$ i kącie przy wierzchołku o mierze $2\mu$ . Na odwrót każda tworząca tego stożka tworzy kąt o mierze $\mu$ z półprostą $t$ (rys. 16).

Niech półproste $k$ i $m$ zawarte w płaszczyźnie $\pi$ mają początek w punkcie $O$ i tworzą kąt o mierze $\alpha$ (rys. 17). Rozważmy stożek obrotowy $S_1$ o wierzchołku w punkcie $O$ , osi $k$ i kącie przy wierzchołku o mierze $2\beta$ oraz stożek obrotowy $S_2$ o wierzchołku w punkcie $O$ , osi $m$ i kącie przy wierzchołku o mierze $2 \gamma$ . Częścią wspólną powierzchni tych stożków jest albo punkt $O$ (gdy $\beta +\gamma < \alpha$ ), albo pewna półprosta zawarta w płaszczyźnie $\pi$ (gdy $\beta +\gamma = \alpha$ ), albo para półprostych $p_1$ , $p_2$ , z których żadna nie jest zawarta w płaszczyźnie $\pi$ (gdy $\beta +\gamma > \alpha$ ). W tym ostatnim przypadku półproste $k$ , $m$ , $p_1$ wyznaczają kąt trójścienny, którego kąty płaskie przy wierzchołku mają miary równe $\alpha, \beta, \gamma$ . Jeżeli zaś $\alpha \geq \beta + \gamma$ , to taki kąt trójścienny nie istnieje, ponieważ odpowiednie stożki nie mają w tym przypadku wspólnej tworzącej nie zawartej w płaszczyźnie $\pi$ .

Przystępujemy teraz do rozwiązania zadania. Z równości podanych w treści zadania wynika, że każde dwie ściany czworościanu $ABCD$ mają po trzy krawędzie odpowiednio równe (rys. 18). Są więc trójkątami przystającymi. Stąd w szczególności

$ \measuredangle BAC = \measuredangle BDC,\ \measuredangle ABC = \measuredangle ADC,\ \measuredangle ACB = \measuredangle ADB. $

Ponieważ suma miar kątów trójkąta $ABC$ równa jest $\pi$ , więc wynika stąd, że suma miar kątów płaskich przy wierzchołku $D$ jest równa $\pi$ . Zatem na mocy lematu

$ \measuredangle BDC < \measuredangle ADC + \measuredangle ADB = \pi - \measuredangle BDC. $

Stąd $\measuredangle BDC < \displaystyle \frac{\pi}{2}$ .

Analogicznie dowodzimy, że każdy z pozostałych kątów płaskich jest ostry.

Uwaga. Teza zadania wynika bezpośrednio z zadania 12 z XII Olimpiady Matematycznej.

XXIV OM - II - Zadanie 6

Zawody matematyczne:

XXIV OM, 1972-1973

Etap:

Udowodnić, że dla każdej liczby całkowitej nieujemnej $m$ istnieje taki wielomian w o współczynnikach całkowitych, że $2^m$ jest największym wspólnym dzielnikiem liczb

$ a_n = 3^n + w(n), n = 0, 1, 2, \ldots . $

Rozwiązanie

Udowodnimy najpierw kilka lematów.

Lemat 1. Dla $r = 1, 2, \ldots$ liczba $2^r$ nie jest dzielnikiem liczby $r!$ .

Dowód. Jak wiadomo (patrz np. W. Sierpiński, Arytmetyka teoretyczna, wyd. 2, 1959, str. 89 lub rozwiązanie zadania 19(1) z XVIII Olimpiady Matematycznej, str. 43), liczba $2$ wchodzi do $r!$ z wykładnikiem

$ \alpha = \left[ \frac{r}{2} \right] + \left[ \frac{r}{4} \right] + \left[ \frac{r}{8} \right] + \ldots + \left[ \frac{r}{2^k} \right], $

gdzie $2^k \leq r < 2^{k+1}$ . Stąd

$ \alpha \leq \frac{r}{2} + \frac{r}{4} + \frac{r}{8} + \ldots + \frac{r}{2^k} = r \left( 1 - \frac{1}{2^k} \right) < r. $

Lemat 2. Jeżeli $k$ jest liczbą nieparzystą, a $t$ - liczbą naturalną, to istnieje taka liczba całkowita $s$ , że liczba $ks - 1$ jest podzielna przez $2^t$ .

Dowód. Z założenia $k = 1 - 2w$ , gdzie $w$ jest pewną liczbą całkowitą. Przyjmując $s = 1 + (2w) + (2w)^2 + \ldots + (2w)^{t-1}$ otrzymamy, że $ks = 1 - (2w)^t$ . Wobec tego liczba $ks - 1$ jest podzielna przez $2^t$ .

Lemat 3. Jeżeli dla pewnego wielomianu $f$ o całkowitych współczynnikach liczba $3^n + f(n)$ jest podzielna przez $2^{m+1}$ dla $n = 0,1, 2, \ldots$ , to wielomian $w(x) = f(x) + 2^m$ ma własność, że największy wspólny dzielnik liczb $a_n = 3^n + w(n)$ , gdzie $n = 0, 1, 2, \ldots$ , jest równy $2^m$ .

Dowód. Z założenia dla $n = 0, 1, 2, \ldots$ istnieje taka liczba całkowita $b_n$ , że $3^n + f(n) = 2^{m+1}b_n$ . Z zadania 3 wiemy, że największy wspólny dzielnik liczb $a_n$ jest potęgą dwójki o całkowitym wykładniku. Ponadto $a_n = 3^n + w(n) = 3^n + f(n) + 2^m = 2^{m+1}b_n + 2^m = 2^m (2b_n + 1)$ . Zatem każda z liczb $a_n$ jest podzielna przez $2^m$ i żadna z nich nie jest podzielna przez $2^{m+1}$ . Wobec tego największy wspólny dzielnik liczb $a_n$ jest równy $2^m$ .

Przystępujemy teraz do rozwiązania zadania. Z lematu 3 wynika, że wystarczy znaleźć taki wielomian $f$ o całkowitych współczynnikach, że każda z liczb $3^n + f(n)$ , gdzie $n = 0, 1, 2, \ldots$ , jest podzielna przez $2^{m+1}$ .

Niech $\displaystyle f_j(x) = \frac{x(x-1) \ldots (x-j+1)}{j!}$ dla $j = 1, 2, \ldots, m$ .

Wtedy $\displaystyle f_j(n) = \binom{n}{j}$ dla $n \geq j$ oraz $f_j(n) = 0$ dla $n = 0, 1, 2, \ldots, j-1$ .

Na mocy wzoru dwumianowego mamy dla $n \geq m$ :

$ \begin{split} 3^n =& (1 + 2)^n = 1 + 2 \binom{n}{1} + 2^2 \binom{n}{2} + \ldots + 2^m \binom{n}{m}+ 2^{m+1} \binom{n}{m+1} + \\ & + \ldots + 2^n = 1 + 2f_1(n) + 2^2f_2(n) + \ldots + 2^mf_m(n) + 2^{m+1}A, \end{split} $

gdzie $A$ jest pewną liczbą całkowitą.

Dla $n < m$ mamy podobnie:

$ \begin{split} 3^n & = (1 + 2)^n = 1 + 2 \binom{n}{1} + 2^2 \binom{n}{2} + \ldots + 2^n \binom{n}{n} = \\ & = 1 + 2f_1(n) + 2^2f_2(n) + \ldots + 2^nf_n(n) + 2^{n+1}f_{n+1}(n) + \ldots + 2^mf_m(x), \end{split} $

ponieważ $f_{n+1}(n) = \ldots = f_m(n) = 0$ .

Zatem wielomian $g(x) = - (1 + 2f_1(x) + 2^2 f_2(x) + \ldots + 2^mf_m (x))$ ma własność, że każda z liczb $3^n + g (n)$ , gdzie $n = 0, 1,2, \ldots$ , jest podzielna przez $2^{m+1}$ . Na ogół jednak współczynniki wielomianu $g$ nie są liczbami całkowitymi.

Z lematu 1 wynika, że współczynniki wielomianu $2^rf_r (x)$ , gdzie $r = 1, 2, \ldots, m$ , są liczbami wymiernymi o nieparzystych mianownikach. Niech $k$ będzie najmniejszym wspólnym mianownikiem wszystkich współczynników wielomianu $g(x)$ . Wtedy $g(x) = \displaystyle \frac{h(x)}{k}$ , gdzie $h (x)$ jest wielomianem o współczynnikach całkowitych. Liczba $k$ jest nieparzysta. Zatem na mocy lematu 2 istnieje taka liczba całkowita $s$ , że $2^{m+1} \mid ks - 1$ .

Wykażemy, że jako wielomian $f(x)$ wystarczy przyjąć $sh(x)$ . Ma on oczywiście współczynniki całkowite. Ponadto dla $n = 0, 1, 2, \ldots$ liczba

$ 3^n + f(n) = 3^n + sh(n) = 3^n + ksg(n) = (3^n + g(n)) + (ks - 1) \cdot g(n) $

jest podzielna przez $2^{m+1}$ , ponieważ $2^{m+1} \mid 3^n + g (n)$ oraz $2^{m+1} \mid ks - 1$ .

Na mocy lematu 3 największy wspólny dzielnik liczb $3^n + f (n) + 2^m$ , gdzie $n = 0, 1, 2, \ldots$ , jest równy $2^m$ , a więc można przyjąć $w(x) =f(x) + 2^m$ .