XXIX OM - I etap

I etap XXIX Olimpiady Matamatyczne

XXIX OM - I - Zadanie 1

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

Ciąg liczb $(p_n)$ określony jest następująco: $p_1 = 2$ , $p_n$ jest największym dzielnikiem pierwszym sumy $p_1p_2\ldots p_{n-1} + 1$ . Dowieść, że w ciągu $(p_n)$ nie wystąpi liczba 5.

Rozwiązanie

Mamy $p_1 = 2$ oraz $p_2 = 3$ , ponieważ $p_2$ jest największym dzielnikiem pierwszym liczby $p_1+ 1=3$ . Wobec tego dla $n > 2$ liczba $p_1p_2\ldots p_{n-1}+1 = 6p_3 \ldots p_n +1$ nie jest podzielna ani przez $2$ , ani przez $3$ . Gdyby więc dla pewnej liczby naturalnej $n$ największy dzielnik pierwszy liczby $p_1p_2 \ldots p_{n-1} + 1$ był równy $5$ , to byłby to jej jedyny dzielnik pierwszy, tzn. byłaby ona równa $5^r$ dla pewnego $r \geq 1$ . Zatem

$ (1) \qquad 6p_3 \ldots p_{n-1} = 5^r-1. $

Liczba $5^r - 1$ jest podzielna przez liczbę $5-1=4$ . Wobec tego z (1) wynika, że $p_k = 2$ dla pewnego $k \geq 3$ . Jest to niemożliwe, ponieważ liczba $p_k$ na mocy określenia jest dzielnikiem liczby $p_1p_2 \ldots p_{k-1} + 1 = 2p_2 \ldots p_{k-1} + 1$ , a ta jest nieparzysta.

Uzyskana sprzeczność dowodzi, że w ciągu $(p_n)$ nie wystąpi liczba 5.

XXIX OM - I - Zadanie 2

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

Dla danej liczby naturalnej $k>7$ skonstruować ciąg $S = (a_0, a_1, \ldots, a_{k-1})$ o tej własności, że dla każdego $i$ ( $0 < i < k - 1$ ) $a_i$ równe liczbie wyrazów ciągu $S$ równych $i$ .

Rozwiązanie

Dla dowolnej liczby naturalnej $k$ znajdziemy wszystkie ciągi $S$ spełniające warunki zadania.

Z warunków zadania wynika, że w ciągu $S$ jest $a_0$ wyrazów równych $0$ , $a_1$ wyrazów równych $1$ , $\ldots$ , $a_{k-1}$ wyrazów równych $k - 1$ i innych wyrazów nie ma. Zatem liczba wszystkich wyrazów ciągu $S$ jest równa $a_0 + a_1 + \ldots + a_{k-1}$ i stąd

$ (1) \qquad a_0 + a_1+ \ldots + a_{k-1} = k. $

Z określenia ciągu $S$ wynika, że $a_0 \ne 0$ . Niech $a_{i_1}, a_{i_2}, \ldots, a_{i_s}$ , gdzie $0 = i_1 < i_2 < \ldots < i_s$ będą wszystkimi różnymi od zera wyrazami ciągu $S$ . Wtedy $k - s$ wyrazów tego ciągu jest równych zero, a więc $a_{i_0} = a_0 = k - s$ i $a_{k-1} \geq 1$ .

Z (1) otrzymujemy, że $a_{i_1} + a_{i_2} + \ldots + a_{i_s} = k$ i wobec tego

$ (2) \qquad a_{i_2} + a_{i_3} + \ldots + a_{i_s} = k - a_{i_1} = s. $

Ponieważ liczby $a_{i_2}, \ldots, a_{i_s}$ są naturalne i jest ich $s - 1$ , więc z (2) wynika, ze $s - 2$ z tych liczb jest równych $1$ , a jedna jest równa $2$ .

1). Jeżeli $a_0 = 1$ , to w ciągu $S$ jeden wyraz jest równy $0$ , $s - 2$
wyrazy są równe $1$ i jeden wyraz równy jest $2$ . Wobec tego $a_2 = 1$ i $a_j = 0$ dla $j > 2$ . Wynika stąd, że $a_1 = 2$ (ponieważ tylko ten wyraz może być różny od $0$ i $1$ ) oraz $a_3 = 0$ i $k - 1 = 3$ (ponieważ tylko jeden wyraz ciągu $S$ jest równy $0$ ), Zatem $S = (1,2,1,0)$ .

Sprawdzamy bez trudu, że ten ciąg $S$ spełnia warunki zadania.

2). Jeżeli $a_0 = 2$ , to w ciągu $S$ dwa wyrazy są równe $0$ , $s - 2$ wyrazy są równe $1$ i dwa wyrazy są równe $2$ , wliczając $a_0$ . Wobec tego $a_2 = 2$ i $a_j = 0$ dla $j > 2$ , a także $a_1 \leq 1$ .

Jeżeli $a_1 = 0$ , to również $a_3 = 0$ i $k - 1 = 3$ (ponieważ nie ma wyrazów równych $1$ i są dwa wyrazy równe $0$ ). Otrzymujemy ciąg $S = (2, 0, 2, 0)$ , który oczywiście spełnia warunki zadania.

Jeżeli zaś $a_1 = 1$ , to $a_3 = a_4 = 0$ i $k - 1 =4$ (ponieważ są dwa wyrazy równe $0$ ). Otrzymujemy w tym przypadku ciąg $S = (2, 1, 2, 0, 0)$ który również spełnia warunki zadania.

3). Jeżeli $a_0 > 2$ , to w ciągu $S$ jest $a_0 = k - s$ wyrazów równych $0$ , $s- 2$ wyrazy równe $1$ i jeden wyraz jest równy $2$ . Wobec tego $a_2 = 1$ , $a_{k-s} = 1$ (i przy tym $k - s > 2$ ) oraz $a_j = 0$ dla $j > 2$ , $j \ne k - s$ . Wynika stąd, że $a_1 \geq 2$ . Zatem w ciągu $S$ dokładnie dwa wyrazy są równe $1$ , a więc $a_1 = 2$ i $s - 2 = 2$ , czyli $s = 4$ .

Otrzymujemy więc ciąg $S$ , w którym $a_0 = k - 4$ , $a_1 = 2$ , $a_2 = 1$ , $a_{k-4} = 1$ , a pozostałe wyrazy są równe zeru. Przy tym $k - 4 > 2$ , tzn. $k \geq 7$ . Sprawdzamy bez trudu, że na odwrót, dla każdej liczby naturalnej $k \geq 7$ określony wyżej ciąg $S$ spełnia warunki zadania.

Uwaga. Rozwiązaliśmy zadanie ogólniejsze. Udowodniliśmy, że dla $k \geq 7$ istnieje dokładnie jeden ciąg $S$ spełniający warunki zadania (i skonstruowaliśmy taki ciąg), ponadto dla $k = 4$ istnieją dwa takie ciągi $(2, 0, 2, 0)$ i $(1, 2, 1, 0)$ , a dla $k = 5$ jeden ciąg $(2, 1, 2, 0, 0)$ . Dla $k = 2$ , $3$ i $6$ takich ciągów $S$ nie ma.

XXIX OM - I - Zadanie 3

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

Niech $a, b, c, d$ będą długościami boków dowolnego czworokąta. Dowieść, że istnieje trapez, którego boki mają długości $a, b, c, d$ .

Rozwiązanie

Bez zmniejszenia ogólności możemy przyjąć, że $a \geq b \geq c \geq d$ . Wtedy

$ (1) \qquad a + b \geq c + d \ \textrm{oraz} \ a + c \geq b + d. $

Z równości $a + b = c + d$ wynika, że $(a - d) + (b - c) = 0$ i stąd $a = b = c = d$ , a z równości $a + c = b + d$ , że $(a - b) + (c - d) = 0$ i stąd $a = b$ i $c = d$ . Jeżeli więc w co najmniej jednej z nierówności (1) zachodzi równość, to $a = b$ i $c = d$ . Wobec tego czworokąt o kolejnych bokach długości $a$ , $c$ , $b$ , $d$ jest równoległobokiem, a więc tym bardziej - trapezem.

Załóżmy z kolei, że $a + b>c + d$ oraz $a + c>b + d$ , czyli

$ (2) \qquad (a-d) + b>c \ \textrm{i} \ (a-d) + c> b. $

Ponieważ $b \geq c$ , więc wynika stąd, że $a - d > 0$ . Ponadto mamy $a < b + c + d$ , czyli

$ (3) \qquad a - d $

ponieważ w czworokącie długość każdego boku jest mniejsza od sumy długości boków pozostałych.

Udowodniliśmy więc ((2) i (3)), że każda z liczb dodatnich $b$ , $c$ , $a - d$ jest mniejsza od sumy liczb pozostałych. Istnieje więc trójkąt o bokach długości $b$ , $c$ , $a - d$ . Umieszczając przy nim równoległobok o bokach długości $c$ i $d$ (rys. 5) otrzymamy szukany trapez.

XXIX OM - I - Zadanie 4

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

Niech $Y$ będzie figurą składającą się z odcinków domkniętych $\overline{OA}$ , $\overline{OB}$ , $\overline{OC}$ , przy czym punkt O leży wewnątrz trójkąta $ABC$ . Dowieść, że w żadnym kwadracie nie można umieścić nieskończenie wielu wzajemnie rozłącznych izometrycznych obrazów figury $Y$ .

Rozwiązanie

Niech $d$ będzie najmniejszą z liczb $OA$ , $OB$ , $OC$ . Obierzmy punkty $P \in \overline{OA}$ , $Q \in \overline{OB}$ , $R \in \overline{OC}$ takie, że $OP= OQ = OR= \frac{d}{2}$ (rys. 6)

Wtedy $PQ < OP + OQ = d$ i podobnie $PR < d$ oraz $QR < d$ . Jeżeli $Y'$ jest figurą składającą się z odcinków domkniętych $\overline{O'A'}$ , $\overline{O'B'}$ i $\overline{O'C'}$ izometryczną z figurą $Y$ oraz punkt $O'$ należy do trójkąta $OPQ$ , to każdy z odcinków $\overline{O'A'}$ , $\overline{O'B'}$ i $\overline{O'C'}$ przecina obwód trójkąta $OPQ$ , ponieważ w trójkącie nie jest zawarty żaden odcinek dłuższy od najdłuższego boku trójkąta. Z warunków zadania wynika, że każdy z kątów $\measuredangle A'O'B'$ , $\measuredangle B'O'C'$ i $\measuredangle C'O'A'$ ma miarę mniejszą od $\pi$ i w sumie dają one kąt pełny. Wobec tego co najmniej jeden z odcinków $\overline{O'A'}$ , $\overline{O'B'}$ i $\overline{O'C'}$ przecina bok $\overline{OP}$ lub $\overline{OQ}$ . Figury $Y$ i $Y'$ nie są więc rozłączne.

Analogicznie dowodzimy, że jeżeli punkt $O'$ należy do trójkąta $OPR$ lub $OQR$ , to figury $Y$ i $Y'$ nie są rozłączne. Jeżeli więc figury $Y$ i $Y'$ są rozłączne, to punkt $O'$ nie należy do trójkąta $PQR$ . Niech $r$ będzie długością promienia pewnego koła o środku w punkcie $O$ zawartego w trójkącie $PQR$ . Z powyższego wynika, że jeżeli figury $Y$ i $Y'$ są rozłączne, to punkty $O$ i $O'$ są odległe więcej niż o $r$ .

Rozpatrzmy teraz kwadrat $K$ o boku długości $a$ . Obierzmy liczbę naturalną $n$ większą od $\displaystyle \frac{a}{r} \sqrt{2}$ i podzielmy kwadrat $K$ prostymi równoległymi do boków na $n^2$ małych kwadratów. Długość boku takiego małego kwadratu jest więc równa $\displaystyle \frac{a}{n}$ , a długość jego przekątnej $\displaystyle \frac{a}{n} \sqrt{2}$ . Ponieważ $n > \frac{a}{r} \sqrt{2}$ , więc $\frac{a}{n} \sqrt{2} < r$ . Odległość dowolnych dwóch punktów należących do kwadratu nie przekracza długości jego przekątnej. Wobec tego odległość dowolnych dwóch punktów należących do małego kwadratu jest mniejsza od $r$ . Z początkowej części rozwiązania wynika więc, że jeżeli $f_1$ i $f_2$ są izometriami figury $Y$ w kwadrat $K$ oraz figury $f_1(Y)$ i $f_2(Y)$ są rozłączne, to punkty $f_1(0)$ i $f_2(0)$ są odległe więcej niż o $r$ . Punkty te nie należą więc do jednego małego kwadratu. Zatem w kwadracie $K$ można umieścić co najwyżej $n^2$ wzajemnie rozłącznych obrazów izometrycznych figury $Y$ .

XXIX OM - I - Zadanie 5

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

Dla jakich liczb naturalnych $n$ istnieją niezerowe wielomiany
$f(x_1,x_2, \ldots ,x_n)$ , $g(x_1,x_2, \ldots ,x_n)$ o współczynnikach całkowitych spełniające równość

$ \left(\sum_{i=1}{n} x_i\right)\cdot f(x_1,x_2, \ldots ,x_n) = g(x_1^2,x_2^2, \ldots ,x_n^2) ? $

Rozwiązanie

Udowodnimy najpierw prosty

Lemat. Jeżeli wielomian $W(x_1, x_2, \ldots , x_n)$ nie ulega zmianie, gdy na miejsce zmiennej $x_i$ podstawimy w nim $(-x_i)$ , to zmienna ta występuje w nim tylko z wykładnikami parzystymi; to znaczy istnieje taki wielomian $V(x_1,x_2, \ldots, x_n)$ , że $W(x_1, x_2, \ldots , x_i, \ldots , x_n) = V (x_1, x_2, \ldots, x_i^2, \ldots, x_n)$ .

Dowód. Dany wielomian jest sumą jednomianów postaci $a x_1^{a_1} x_2^{a_2} \ldots x_n^{a_n}$ , gdzie $a \ne 0$ . Z założenia mamy

$ a x_1^{a_1} x_2^{a_2} \ldots x_i^{a_i} \ldots x_n^{a_n} = a x_1^{a_1} x_2^{a_2} \ldots (-x_i)^{a_i} \ldots x_n^{a_n}. $

Wobec tego $(-1)^{a_i} = 1$ , czyli liczba $a_1$ jest parzysta. Zatem w każdym jednomianie wielomianu $W(x_1, x_2, \ldots , x_n)$ zmienna $x_i$ występuje z wykładnikiem parzystym. Wynika stąd teza lematu.

Przystępujemy teraz do rozwiązania zadania. Udowodnimy, że dla każdej liczby naturalnej $n$ istnieją wielomiany $f(x_1, x_2, \ldots, x_n)$ i $g(x_1, x_2, \ldots, x_n)$ spełniające warunki zadania.

Rozpatrzmy wielomian $F(x_1, x_2, \ldots, x_n)$ będący iloczynem wszystkich wielomianów postaci $c_1x_1 + c_2x_2 + \ldots + c_nx_n$ , gdzie współczynniki $c_1, c_2, \ldots, c_n$ przybierają wartości $1$ i $-1$ . Wielomian $F(x_1, x_2, \ldots , x_n)$ ma więc współczynniki całkowite i jeżeli w nim na miejsce dowolnej zmiennej $x_i$ podstawimy $(-x_i)$ , to oczywiście otrzymamy znów wielomian $F(x_1,x_2, \ldots ,x_n)$ . Wobec tego na mocy lematu w wielomianie $F(x_1, x_2, \ldots , x_n)$ każda zmienna występuje tylko z wykładnikami parzystymi, to znaczy istnieje taki wielomian o współczynnikach całkowitych $g(x_1, x_2, \ldots, x_n)$ , że $F(x_1, x_2, \ldots, x_n) = g(x_1^2, x_2^2, \ldots, x^2_n)$ . Jednym z czynników wielomianu $F(x_1, x_2, \ldots , x_n)$ jest z określenia $x_1 + x_2 + \ldots + x_n$ , a iloczyn pozostałych czynników jest wielomianem o współczynnikach całkowitych. Oznaczając ten iloczyn przez $f(x_1, x_2, \ldots , x_n)$ otrzymujemy $(x_1 + x_2 + \ldots + x_n) \cdot f(x_1, x_2, \ldots ,x_n) = F(x_1, x_2, \ldots ,x_n) = = g(x_1^2, x_2^2, \ldots ,x_n^2) \ne 0$ .

Zachodzi więc teza zadania.

Uwaga 1. Można opisać wszystkie wielomiany $f(x_1, x_2, \ldots, x_n)$ i $g(x_1, x_2, \ldots, x_n)$ spełniające warunki zadania.

Przypuśćmy najpierw, że $n > 1$ i wielomiany $f(x_1, x_2, \ldots , x_n)$ i $g(x_1,x_2, \ldots ,x_n)$ spełniają warunki zadania. Zachodzi więc równość (1). Podstawiając w niej na miejsce zmiennej $x_i$ jednomian $c_ix_i$ , gdzie $c_i = 1$ lub $-1$ oraz $i = 2, 3, \ldots , n$ stwierdzamy, że wielomian $g (x_1^2, x_2^2, \ldots, x_n^2)$ jest podzielny przez każdy z wielomianów

$ (3) \qquad x_1 + c_2x_2 + \ldots + c_nx_n, \ \textrm{gdzie}\ c_i=1 \ \textrm{lub} \ -1. $

Ponieważ wielomiany (3) są parami względnie pierwsze, więc wielomian $g(x_1^2, x_2^2, \ldots, x_n^2)$ jest również podzielny przez ich iloczyn

$ (4) \qquad h(x_1, x_2, \ldots, x_n) = \prod_{c_i = \pm 1} (x_1 + c_2x_2 + \ldots + c_nx_n). $

Iloczyn ten zawiera $2^{n-1}$ czynników, ponieważ tyle jest układów $(c_2, c_3, \ldots , c_n)$ , gdzie $c_i = 1$ lub $-1$ . Zmiana znaku jednej ze zmiennych $x_2,x_3, \ldots , x_n$ nie zmienia oczywiście wielomianu $h(x_1, x_2, \ldots , x_n)$ . Na mocy lematu więc każda z tych zmiennych występuje w wielomianie $h(x_1, x_2, \ldots, x_n)$ tylko z wykładnikami parzystymi.

Jeżeli $n > 1$ , to również zmienna $x_1$ występuje w wielomianie $h(x_1, x_2, \ldots , x_n)$ tylko z wykładnikami parzystymi, ponieważ

$ \begin{split} h(-x_1, x_2, \ldots, x_n)&= \prod_{c_i = \pm 1} (-x_1 + c_2x_2 + \ldots + c_nx_n) = \\ & = (-1)^{2^{n-1}} \prod_{c_i = \pm 1} (x_1 - c_2x_2 - \ldots - c_nx_n) =\\ &= h(x_1, -x_2, \ldots, -x_n) = h(x_1, x_2, \ldots, x_n). \end{split} $

Istnieje więc taki wielomian niezerowy o współczynnikach całkowitych $g_0(x_1, x_2, \ldots , x_n)$ , że

$ (5) \qquad h(x_1, x_2, \ldots , x_n) = g_0 (x_1^2, x_2^2, \ldots , x_n^2). $

Na mocy (4) jednym z czynników wielomianu $h(x_1, x_2, \ldots , x_n)$ jest $x_1 + x_2 + \ldots + x_n$ . Oznaczając iloczyn pozostałych czynników przez $f_0 (x_1, x_2, \ldots , x_n)$ stwierdzamy na mocy (4) i (5), że

$ (6) \qquad (x_1 + x_2 + \ldots +x_n) \cdot f_0 (x_1, x_2, \ldots, x_n) = g_0 (x_1^2, x_2^2, \ldots, x_n^2). $

Udowodniliśmy więc, że wielomiany $f_0 (x_1, x_2, \ldots , x_n)$ oraz $g_0(x_1, x_2, \ldots, x_n)$ spełniają warunki zadania oraz, że jeżeli pewne wielomiany $f(x_1, x_2, \ldots , x_n)$ i $g(x_1, x_2, \ldots ,x_n)$ spełniają warunki zadania, to wielomian $g(x_1, x_2, \ldots,x_n)$ jest podzielny przez $g_0(x_1, x_2, \ldots , x_n)$ . Mamy więc

$ (7) \qquad g (x_1, x_2, \ldots, x_n) = g_0 (x_1, x_2, \ldots , x_n) \cdot g_1 (x_1, x_2, \ldots, x_n), $

gdzie $g_1 (x_1, x_2, \ldots , x_n)$ jest pewnym wielomianem o współczynnikach całkowitych.

Z (1), (6) i (7) wynika, że

$ (8) \qquad f(x_1, x_2, \ldots, x_n) = f_0 (x_1, x_2, \ldots , x_n) \cdot g_1(x_1^2, x_2^2, \ldots , x_n^2). $

Na odwrót, jeżeli $g_1(x_1, x_2, \ldots, x_n)$ jest dowolnym wielomianem niezerowym o współczynnikach całkowitych, to wielomiany $f(x_1, x_2, \ldots ,x_n)$ i $g(x_1,x_2, \ldots ,x_n)$ określone wzorami (7) i (8) na mocy (6) spełniają warunki zadania.

W przypadku $n > 1$ wzory (7) i (8) opisują więc wszystkie wielomiany spełniające warunki zadania. W przypadku $n = 1$ oczywiście wszystkie wielomiany $f(x_1)$ i $g(x_1)$ spełniające warunki zadania są postaci $f(x_1) = x_1 g_1 (x_1^2)$ , $g(x_1) = x_1g_1(x_1)$ , gdzie $g_1(x_1)$ jest dowolnym
wielomianem niezerowym o współczynnikach całkowitych.

Uwaga 2. Prawdziwe są twierdzenia ogólniejsze. Na przykład:

Twierdzenie 1. Dla dowolnej liczby naturalnej $n$ i wielomianu niezerowego o współczynnikach całkowitych $w(x_1,x_2, \ldots ,x_n)$ istnieją wielomiany niezerowe o współczynnikach całkowitych $f(x_1, x_2, \ldots, x_n)$ i $g(x_1,x_2, \ldots ,x_n)$ spełniające

$ w(x_1, x_2, \ldots, x_n) cdot f(x_1, x_2, \ldots, x_n) = g(x_1^2, x_2^2, \ldots ,x_n^2). $

Twierdzenie 2. Dla dowolnych liczb naturalnych $n$ i $r$ istnieją takie wielomiany niezerowe o współczynnikach całkowitych $f(x_1, x_2, \ldots , x_n)$ i $g(x_1, x_2, \ldots ,x_n)$ , że

$ (x_1 + x_2+ \ldots + x_n) \cdot f(x_1, x_2, \ldots ,x_n)= g(x_1^r, x_2^r, \ldots, x_n^r). $

Dowód pierwszego z tych twierdzeń przebiega podobnie do rozwiązania zadania, szczegółowe jego przeprowadzenie pozostawiamy czytelnikowi jako ćwiczenie. Dowód drugiego twierdzenia można przeprowadzić używając liczb zespolonych.

XXIX OM - I - Zadanie 6

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

Dowieść, że na płaszczyźnie dowolna łamana zamknięta o długości 1 zawiera się w pewnym kole o promieniu długości $\frac{1}{4}$

Rozwiązanie

Niech punkty $A$ i $B$ należące do łamanej zamkniętej długości $1$ dzielą tę łamaną na dwie części równej długości i niech $C$ będzie dowolnym punktem tej łamanej. Ponieważ odcinek jest najkrótszą łamaną łączącą dwa punkty, więc $AC + BC \leq \frac{1}{2}$ .

Niech $P$ będzie środkiem odcinka $\overline{AB}$ , $C'$ - punktem symetrycznym do $C$ względem punktu $P$ (rys. 7). Wtedy $CP = C'P$ i $BC= AC'$ . Wobec tego

$ 2CP = CC' \leq AC + AC' = AC + BC \leq \frac{1}{2} $

i stąd $CP \leq \frac{1}{4}$ .

Udowodniliśmy więc, że dowolny punkt $C$ danej łamanej jest odległy od punktu $P$ nie więcej niż o $\frac{1}{4}$ . Wobec tego ta łamana jest zawarta w kole o środku $P$ i promieniu długości $\frac{1}{4}$ .

Uwaga. Analogiczne zadanie było podane na zawodach VII Olimpiady Matematycznej jako zadanie 23 (5).

XXIX OM - I - Zadanie 7

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

Dla ustalonej liczby nąturalnej $n>2$ określamy: $x_1 = n$ , $y_1=1$ , $x_{i+1} = \left[\frac{1}{2}(x_i+y_i)\right]$ , $y_{i+1} = \left[ \frac{n}{x_{i+1}}\right]$ Dowieść że najmniejsza z liczb $x_1 x_2, \ldots, x_n$ jest równa [\sqrt{n}].
Uwaga. $[a]$ oznacza największą liczbę całkowitą nie większą od $a$ .

Rozwiązanie

Dla dowolnej liczby całkowitej $k$ liczba $\left[ \frac{k}{2} \right]$ jest równa $\frac{k}{2}$ lub $\frac{k-1}{2}$ w zależności od tego, czy liczba $k$ jest parzysta, czy nieparzysta. Wobec tego $\left[ \frac{k}{2} \right] \geq \frac{k-1}{2}$ dla każdej liczby całkowitej $k$ . Mamy też $a \geq [a] > a - 1$ na mocy określenia symbolu $[a]$ . Wreszcie $\frac{1}{2} \left( x_i + \frac{n}{x_i} \right) \geq \sqrt{n}$ , ponieważ średnia geometryczna liczb
dodatnich $x_i$ i $\frac{n}{x_i}$ nie przekracza ich średniej arytmetycznej.

Biorąc powyższe pod uwagę otrzymujemy, że

$ \begin{split} x_{i+1} &= \left[ \frac{1}{2} (x_i + y_i) \right] \geq \frac{1}{2} (x_i +y_i -1 )=\frac{1}{2} \left( x_i + \left[ \frac{n}{x_i} \right] - 1 \right) >\\ &>\frac{1}{2} \left( x_i + \frac{n}{x_i} - 2 \right) \geq \sqrt{n} - 1 \geq [\sqrt{n}] - 1, \end{split} $

to znaczy $x_{i+1} > [\sqrt{n}] - 1$ . Wynika stąd, że $x_{i+1} \geq [\sqrt{n}]$ dla $i = 1, 2, \ldots , n -1$ . Mamy też $x_1 = n \geq \sqrt{n} \geq [\sqrt{n}]$ .

Z drugiej strony, jeżeli dla pewnego $i = 1, 2, \ldots , n- 1$ zachodzi $x_i > [\sqrt{n}]$ , to $x_i > \sqrt{n}$ i wobec tego

$ \begin{split} x_{i+1}&= \left[ \frac{1}{2} (x_i + y_i) \right] \leq \frac{1}{2} (x_i + y_i) = \frac{1}{2} \left( x_i + \left[ \frac{n}{x_i} \right] \right) \leq \\ &\leq\frac{1}{2} \left( x_i + \frac{n}{x_i} \right)< \frac{1}{2} \left( x_i + \frac{x_i^2}{x_i} \right) = x_i, \end{split} $

to znaczy $x_{i+1} < x_i$ .

Gdyby więc wszystkie wyrazy ciągu $x_1, x_2, \ldots, x_n$ były większe od $[\sqrt{n}]$ , to byłby on ciągiem malejącym liczb naturalnych większych od $[\sqrt{n}]$ . Jest to niemożliwe, ponieważ $x_1 = n$ i ciąg ma $n$ wyrazów. Wobec tego pewien wyraz ciągu jest równy $[\sqrt{n}]$ i jest to najmniejsza
z liczb $x_1, x_2, \ldots, x_n$ .

Uwaga. Z powyższego rozwiązania wynika, że jeżeli dla pewnego $i = 1,2, \ldots ,n- 1$ zachodzi nierówność $x_{i+1} \geq x_i$ , to jest najmniejszym wyrazem ciągu $x_1, x_2, \ldots , x_n$ i wobec tego $x_i= [\sqrt{n}]$ .

Z tego zadania na mocy powyższej uwagi wynika stosunkowo prosty sposób obliczania przybliżonych wartości pierwiastków kwadratowych z liczb naturalnych. Pokażemy go na przykładzie liczby $n = 1977$ . Obliczamy początkowe wyrazy ciągów $(x_i)$ i $(y_i)$ podanych w zadaniu i wyniki umieszczamy w tabelce:

$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline x_i & 1977 & 989 & 495 & 249 & 128 & 71 & 49 & 44 & 44 \\ y_i & 1 & 1 & 3 & 7 & 15 & 27 & 40 & 44 & 44 \\ \hline \end{array} $

Ponieważ $x_9 = x_8$ , więc wynika stąd, że $[\sqrt{1977}] = x_8 = 44$ . Wystarczyło więc obliczyć tylko $9$ wyrazów ciągu $(x_1, x_2, \ldots , x_{1977})$ , by znaleźć $[\sqrt{1977}]$ , zamiast wszystkich $1977$ jego wyrazów. W tym przykładzie zresztą mamy $x_i = 44$ dla $8 \leq i \leq 1977$ . Nie zawsze jednak ciąg $(x_i)$ jest monotoniczny. Czytelnik zechce znaleźć odpowiedni przykład.

XXIX OM - I - Zadanie 8

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

Niech $(a_n)$ będzie takim ciągiem niemalejącym liczb naturalnych, że ciąg $\left(\frac{n}{a_n}\right)$ jest nieograniczony. Udowodnić, że wśród wyrazów ciągu $\left(\frac{n}{a_n}\right)$ jest nieskończenie wiele liczb całkowitych.

Rozwiązanie

Pierwszy wyraz ciągu $\binom{n}{a_n}$ jest nie większy od $1$ , ponieważ $a_1 \geq 1$ . Ciąg ten jest nieograniczony i wobec tego dla każdej liczby naturalnej $m$ istnieje taka liczba naturalna $r$ , że

$ (1) \qquad \frac{r}{a_r} \leq m < \frac{r+1}{a_{r+1}}. $

Mianowicie, wystarczy $r$ tak obrać, by $\frac{r+1}{a_{r+1}}$ był najwcześniejszym wyrazem ciągu $\binom{n}{a_n}$ większym od $m$ .

Mnożąc nierówności (1) stronami przez $a_r$ i korzystając z tego, że ciąg $(a_n)$ jest niemalejący otrzymujemy:

$ r \leq ma_r < (r + 1) \frac{a_r}{a_{r+1}} \leq r + 1. $

Tak więc liczba naturalna $ma_r$ należy do przedziału $\langle r, r+1 \rangle$ ,
skąd wynika, że $ma_r = r$ , czyli $m = \frac{r}{a_r}$ .

Udowodniliśmy zatem, że każda liczba naturalna $m$ jest wyrazem ciągu $\binom{n}{a_n}$ .

XXIX OM - I - Zadanie 9

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

Udowodnić, że z każdego ciągu liczb naturalnych można wybrać podciąg, którego każde dwa wyrazy są względnie pierwsze, lub podciąg, którego wszystkie wyrazy mają wspólny dzielnik większy od 1.

Rozwiązanie

Niech $p$ będzie ustaloną liczbą pierwszą. Jeżeli nieskończenie wiele wyrazów ciągu jest podzielnych przez $p$ , to wyrazy podzielne przez $p$ tworzą podciąg, którego wszystkie wyrazy mają wspólny dzielnik większy od $1$ .

Rozpatrzmy więc przypadek, gdy dla każdej liczby pierwszej $p$ tylko skończona liczba wyrazów ciągu jest podzielna przez $p$ . Wtedy określamy indukcyjnie podciąg $b_1, b_2,\ldots$ danego ciągu, jak następuje. Jako $b_1$ bierzemy pierwszy wyraz danego ciągu. Jeżeli już zostały wybrane wyrazy $b_1, b_2, \ldots , b_n$ podciągu tak, że każde dwa z nich są względnie pierwsze, to jako $b_{n+1}$ bierzemy taki wyraz danego ciągu, który nie jest podzielny przez żaden czynnik pierwszy liczby $b_1b_2 \ldots b_n$ . Wtedy oczywiście liczba $b_{n+1}$ będzie względnie pierwszą z każdą z liczb $b_1, b_2, \ldots, b_n$ . Wobec tego na mocy zasady indukcji istnieje podciąg nieskończony $b_1, b_2, \ldots$ , którego każde dwa wyrazy są względnie pierwsze.

XXIX OM - I - Zadanie 10

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

Punkt $O$ jest punktem wewnętrznym czworokąta wypukłego $ABCD$ , $A_1$ , $B_1$ , $C_1$ , $D_1$ są rzutami prostokątnymi punktu $O$ odpowiednio na proste $AB$ , $BC$ , $CD$ i $DA$ , $A_{i+1}$ , $B_{i+1}$ , $C_{i+1}$ , $D_{i+1}$ są odpowiednio rzutami prostokątnymi punktu $O$ na proste $A_iB_i$ , $B_iC_i$ , $C_iD_i$ , $D_iA_i$ . Dowieść, że czworokąty $A_4B_4C_4D_4$ i $ABCD$ są podobne.

Rozwiązanie

Konstrukcja podana w zadaniu nie zawsze jest wykonalna. Na przykład trzy z punktów $A_{i+1}$ , $B_{i+1}$ , $C_{i+1}$ , $D_{i+1}$ mogą należeć do jednej prostej. Wtedy zadanie traci sens. Podamy więc rozwiązanie zadania przy dodatkowym założeniu, że wszystkie rozważane czworokąty istnieją i są wypukłe.
Ponieważ $\measuredangle OD_1A + \measuredangle OA_1A = \frac{\pi}{2} + \frac{\pi}{2} = \pi$ , więc na czworokącie $OA_1AD_1$ można opisać koło. Miary kątów wpisanych w koło i opartych na tym samym łuku są równe. Wobec tego $\measuredangle OAD = \measuredangle OA_1D_1$ (rys. 8). Analogicznie dowodzimy, że $\measuredangle OA_2D_2 = \measuredangle OA_2D_2 = \measuredangle OA_3D_3 = \measuredangle OA_4D_4$ .

Rozumując podobnie otrzymujemy $\measuredangle ODA = \measuredangle OC_1D_1 = \measuredangle OB_2C_2 = \measuredangle OA_3B_3 = \measuredangle OD_4A_4$ . Trójkąty $OAD$ i $OA_4D_4$ są podobne, ponieważ po dwa odpowiednie kąty w tych trójkątach mają równe miary. Wobec tego $\displaystyle \frac{OA}{AD} = \frac{OA_4}{A_4D_4}$ . Analogicznie dowodzimy, że $\displaystyle \frac{OA}{AB} = \frac{OA_4}{A_4B_4}$ . Zatem $\displaystyle \frac{AB}{A_4B_4} = \frac{AD}{A_4D_4}$ , i podobnie $\displaystyle \frac{AB}{A_4B_4} = \frac{BC}{B_4C_4} = \frac{CD}{C_4D_4}$ .

Udowodniliśmy też, że $\measuredangle OAD = \measuredangle OA_4D_4$ . Podobnie dowodzi się, że $\measuredangle OAB = \measuredangle OA_4B_4$ i stąd $\measuredangle BAD = \measuredangle OAB + \measuredangle OAD = \measuredangle OA_4B_4 + \measuredangle OA_4D_4 = \measuredangle B_4A_4D_4$ . Analogicznie można wykazać, że miary pozostałych kątów czworokąta $ABCD$ są równe miarom odpowiednich kątów czworokąta $A_4B_4C_4D_4$ .

Tak więc odpowiednie boki tych czworokątów są proporcjonalne, a miary odpowiednich kątów są równe. Wobec tego czworokąty te są podobne.

XXIX OM - I - Zadanie 11

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

Niech $f: \mathbb{R} \to \mathbb{R}$ będzie funkcją ciągłą, dla której istnieje liczba $x$ spełniająca warunki: $f(f(f(x))) = x$ , $f(x) \neq x$ .
Udowodnić, że istnieją takie liczby $y_1$ , $y_2$ , $y_3$ , że $y_i \neq y_j$ dla $i \neq j$ oraz $f(f(y_k))=y_k$ dla $k = 1, 2, 3$ .
Uwaga. Wiadomo, że każda funkcja ciągła $g: \mathbb{R} \to \mathbb{R}$ ma własność Darboux, to znaczy jeżeli $a < b$ i $d$ jest zawarte pomiędzy $g(a)$ i $g(b)$ , to istnieje taka liczba $c \in [a, b]$ , że $g(c) = d$ .

Rozwiązanie

Gdyby zachodziło $ff(x) = x$ , to mielibyśmy $fff(x) = f(x)$ , czyli $x =f(x)$ wbrew założeniu. Zatem $ff(x) \ne x$ . Podobnie z równości $ff(x) = f(x)$ wynika, że $fff(x) = ff(x)$ , czyli $x = ff(x)$ . Udowodniliśmy jednak, że ta ostatnia równość nie zachodzi. Zatem $ff(x) \ne f(x)$ .

Wobec tego liczby $x$ , $f(x)$ , $f(x)$ są parami różne. Oznaczmy najmniejszą z nich przez $a$ , największą przez $c$ , a pozostałą przez $b$ . Zatem $a < b < c$ . Z warunków zadania wynika, że funkcja $f$ określa permutację zbioru $\{a, b, c\}$ i $f(a) \ne a$ , $f(b) \ne b$ , $f(c) \ne c$ .

Rozpatrzmy przypadek, gdy $f(a) = c$ . Jeżeli $f(a) = b$ , to rozumowanie przebiega podobnie. Mamy więc $f(b) = a$ i $f(c) = b$ .

Funkcja ciągła $f(t)$ na końcach przedziału $\langle a, b \rangle$ przybiera wartości $c$ i $a$ . Wobec tego na mocy własności Darboux w pewnym punkcie z tego przedziału funkcja $f(t)$ przybiera wartość pośrednią $b$ , to znaczy $a < z < b$ i $f(z) = b$ . Dla rozwiązania zadania wystarczy oczywiście udowodnić, że funkcja $g(t) =ff(t) - t$ ma co najmniej trzy miejsca zerowe. Mamy

$ \begin{split} & g(a) = ff(a)- a = b - a > 0,\\ & g(z) = ff(z)- z = f(b) - z = a - z < 0,\\ & g(b) = ff(b)- b = c- b > 0 ,\\ & g(c) = ff(c)- c = a-c < 0. \end{split} $

Tak więc funkcja $g(t)$ na końcach każdego z przedziałów $\langle a, z \rangle$ , $\langle z, b \rangle$ , $\langle b, c \rangle$ przybiera wartości przeciwnych znaków. Wobec tego na mocy własności Darboux ma ona w każdym z tych przedziałów co najmniej jedno miejsce zerowe.

Uwaga. Dla dowolnej liczby naturalnej $n$ niech $f_n$ będzie $n$ -krotną iteracją funkcji $f$ , to znaczy $f_n(x) =f(f(\ldots (f(x))\ldots))$ ( $n$ razy). Powiemy, że liczba rzeczywista $x$ ma okres $n$ , jeżeli $f_n(x) = x$ oraz $f_m(x) \ne x$ dla $m < n$ . Nasze zadanie można więc sformułować tak: {\it Dowieść, że jeżeli dla funkcji ciągłej $f \colon \mathbb{R} \to \mathbb{R}$ istnieje liczba $x$ okresu $3$ , to istnieją trzy liczby $y_1, y_2, y_3$ okresu $2$ lub $1$ .}

Zachodzi następujące ogólne twierdzenie Szarkowskiego: Ustawmy wszystkie liczby naturalne, jak następuje

$ (1) \qquad 3, 5, 7, 11, \ldots, 2 \cdot 3, 2 \cdot 5, 2 \cdot 7, \ldots , 4 \cdot 3, 4 \cdot 5, \ldots , 8, 4, 2, 1. $

Na początku jest ciąg rosnący wszystkich liczb pierwszych, potem ciąg liczb pierwszych pomnożonych przez $2$ , przez $4$ , itd., wreszcie - ciąg malejący wszystkich potęg liczby $2$ .

Twierdzenie Szarkowskiego mówi, że jeżeli dla funkcji ciągłej $f \colon \mathbb{R} \to \mathbb{R}$ istnieje liczba okresu $n$ , to istnieje też liczba okresu $m$ , o ile w ciągu (1) liczba $m$ występuje po liczbie $n$ .

XXIX OM - I - Zadanie 12

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

Wyznaczyć kres górny zbioru takich liczb $\alpha \leq \frac{\pi}{2}$ , że każdy kąt ostry $MON$ o mierze $\alpha$ i każdy trójkąt $T$ na płaszczyźnie mają następującą własność. Istnieje trójkąt $ABC$ izometryczny z $T$ taki, że bok $\overline{AB}% jest równoległy do$ OM $oraz proste prostopadłe do$ ON $i przechodzące przez środki ciężkości trójkątów$ ABC $oraz$ ABC' $odpowiednio przecinają odcinek$ \overline{AB}; $C'$ jest obrazem symetrycznym wierzchołka $C$ względem symetralnej boku $\overline{AB}$ .
Uwaga. Fizycznie zadanie oznacza: Jaki ma być kąt nachylenia równi pochyłej, aby dla dowolnego trójkąta można było wybrać pewien bok tak, że trójkąt przyłożony tym bokiem do równi nie przewróci się.

Rozwiązanie

Zauważmy najpierw, że jeżeli $Q$ jest środkiem boku $\widehat{AC}$ i $AB \geq AC$ , to $\measuredangle ABQ \leq \frac{\pi}{6}$ . Istotnie, oznaczając przez $D$ rzut punktu $A$ na prostą $BQ$ otrzymujemy $AD \leq AQ= \frac{1}{2} AC \leq \frac{1}{2} AB$ (rys. 9).

Wobec tego $\sin \measuredangle ABQ = \frac{AD}{AB} \leq \frac{1}{2}$ . Ponieważ kąt $ABC$ nie jest największym kątem trójkąta $ABC$ , więc jest on ostry. Tym bardziej kąt $ABQ$ jest ostry. Wobec tego z nierówności $\sin \measuredangle ABQ \leq \frac{1}{2}$ otrzymujemy, że $\measuredangle ABQ \leq \frac{\pi}{6}$ .

Niech $\overline{AB}$ będzie najdłuższym bokiem trójkąta $ABC$ izometrycznego z trójkątem $T$ , niech $P$ będzie środkiem ciężkości trójkąta $ABC$ , a $P'$ - środkiem ciężkości trójkąta $ABC'$ . Możemy przyjąć, że $A = O$ , ponieważ to nie zmienia warunków zadania (rys. 10).

Z początkowej uwagi wynika, że każdy z kątów $BOP$ i $BOP'$ ma miarę nie większą niż $\frac{\pi}{6}$ . Wobec tego, jeżeli $\measuredangle MON \leq \frac{\pi}{3}$ , to $\measuredangle NOP = \measuredangle MON + \measuredangle BOP \leq \frac{\pi}{2}$ i podobnie $\measuredangle NOP \leq \frac{\pi}{2}$ . Wynika stąd, że proste prostopadłe do $ON$ i przechodzące przez punkty $P$ i $P'$ odpowiednio przecinają odcinek $\overline{AB}$ . Zatem poszukiwany kres górny liczb $\alpha$ jest nie mniejszy od $\frac{\pi}{3}$ .

Na odwrót, jeżeli prosta prostopadła do $ON$ przechodząca przez punkt $P$ przecina odcinek $\overline{AB}$ , to $\measuredangle NOP \leq \frac{\pi}{2}$ . Wobec tego $\measuredangle MON = \measuredangle NOP - \measuredangle BOP \leq \frac{\pi}{2} - \measuredangle BOP$ . W szczególności, jeżeli $T$ jest trójkątem równobocznym, to $\measuredangle BOP = \frac{\pi}{6}$ i wobec tego
$\measuredangle MON \leq \frac{\pi}{2} - \frac{\pi}{6} = \frac{\pi}{3}$ . Wynika stąd, że poszukiwanym kresem górnym liczb $\alpha$ jest liczba $\frac{\pi}{63}$ .