XXXVII OM - II etap

II etap XXXVII Olimpiady Matematycznej

XXXVII OM - II - Zadanie 1

Zawody matematyczne:

XXXVII OM, 1985-1986

Etap:

Wyznaczyć wszystkie funkcje $f : \mathbb{R} \to \mathbb{R}$ ciągłe w zerze i takie, że dla każdej liczby rzeczywistej $x$ zachodzi równość

$ 2f(2x) = f(x) + x. $

Rozwiązanie

Załóżmy, że funkcja $f : \mathbb{R} \to \mathbb{R}$ , ciągła w punkcie $0$ , spełnia dane równanie funkcyjne.

W celu pozbycia się drugiego składnika po prawej stronie równania wprowadzamy funkcję pomocniczą $h(x) =f(x)-\frac{1}{3}x$ ; jest ona również ciągła w punkcie $0$ . Wstawiając $f(x) = h(x) + \frac{1}{3} x$ , $f(2x) = h(2x) + \frac{2}{3} x$ do rozważanego równania, sprowadzamy je do postaci

$ 2h(2x) | + \frac{4}{3}x = h(x)+ \frac{1}{3}x+x, $

czyli

$ (1) \qquad h(2x) = \frac{1}{2} h(x) \ \textrm{dla} \ x \in \mathbb{R}. $

Weźmy dowolną liczbę $x_0 \in \mathbb{R}$ . Podstawiając w (1) $x = 2^{-n}x_0$ , $n = 0, 1, 2, \ldots$ , dostajemy

$ h(2^{-(n-1)} x_0)= \frac{1}{2} h(2^{-n}x_0), $

skąd przez indukcję

$ (2) \qquad h(x_0) = 2^{-n}h(2^{-n}x_0) \ \textrm{dla} \ n = 0, 1, 2, \ldots. $

Z ciągłości $h$ w punkcie $0$ wynika, że ciąg liczb otrzymanych po prawej stronie (2) dąży do $0$ przy $n \to \infty$ . A to oznacza, że $h(x_0) = 0$ . Ponieważ punkt $x_0$ był wybfany dowolnie, funkcja $h$ równa się tożsamościowo zeru. Zatem,

$ f(x) = \frac{1}{3} x \ \textrm{dla} \ x \in \mathbb{R} $

Bezpośrednie sprawdzenie pokazuje, że funkcja ta istotnie jest rozwiązaniem danego w zadaniu równania.

XXXVII OM - II - Zadanie 2

Zawody matematyczne:

XXXVII OM, 1985-1986

Etap:

W turnieju szachowym uczestniczy 66 zawodników, każdy z każdym rozgrywa jedną partią, rozgrywki odbywają się w czterech miastach. Udowodnić, że pewna trójka zawodników rozgrywa wszystkie partie między sobą w tym samym mieście.

Rozwiązanie

Wybierzmy jednego z zawodników, nazwijmy go $Z_1$ . Ma on do rozegrania $65$ partii, a więc co najmniej $17$ partii rozgrywa w jednym mieście. Oznaczmy to miasto symbolem $M_1$ . Weźmy pod uwagę przeciwników $Z_1$ w spotkaniach rozgrywanych w $M_1$ . Jest ich nie mniej niż $17$ . Jeśli istnieje wśród nich para rozgrywająca partię między sobą także w $M_1$ , to wespół z zawodnikiem $Z_1$ tworzą oni trójkę grającą ,,trójkąt spotkań'' w jednym mieście i twierdzenie jest udowodnione. Załóżmy wobec tego, że cała ta grupa $17$ (lub więcej) szachistów gra wszystkie mecze między sobą w pozostałych trzech miastach. Wybierzmy jednego z tej grupy i nazwijmy go $Z_2$ . Ma on w tej grupie co najmniej $16$ przeciwników, a więc z co najmniej $6$ z nich musi grać w jednym mieście, które oznaczymy symbolem $M_2$ . Jeśli któraś para wśród nich rozgrywa swoją partię także w $M_2$ , daje to ,,trójkąt spotkań'' w $M_2$ . No to przypuśćmy, że tak nie jest; znaczy to, że rozważana grupa $6$ (lub więcej) szachistów rozgrywa partie między sobą w pozostałych dwóch miastach. Powtarzamy więc jeszcze raz to samo rozumowanie. Wybieramy z tej grupy jednego zawodnika $Z_3$ i zauważamy, że mając w tej grupie co najmniej $5$ przeciwników, musi z co najmniej $3$ z nich grać w jednym mieście $M_3$ . Jeśli jest wśród nich para rozgrywająca swoją partię w $M_3$ , to wraz z zawodnikiem $Z_3$ tworzą oni trójkę grającą ,,trójkąt spotkań'' w $M_3$ . W przeciwnym razie cała ta grupa $3$ (lub więcej) szachistów rozgrywa spotkania między sobą w ostatnim pozostałym mieście $M_4$ . Tym samym twierdzenie zostało udowodnione.

Uwaga. Podany dowód ma charakter indukcyjny, składa się z kilku kroków, w których powielany jest ten sam schemat rozumowania. To spostrzeżenie prowadzi do następującego naturalnego uogólnienia; wygodnie formułować je w języku tzw. teorii grafów.

Niech $(n_k)$ będzie ciągiem liczb określonym wzorem rekurencyjnym $n_1 = 2$ , $n_k = kn_{k-1}+1$ dla $k \geq 2$ . Przypuśćmy, że $G$ jest zbiorem $n$ punktów w przestrzeni, $n > n_k$ , i że każdy z odcinków łączących punkty zbioru $G$ został pokolorowany jednym z $k$ kolorów. Wówczas istnieją w zbiorze $G$ trzy punkty takie, że trójkąt o wierzchołkach w tych punktach ma wszystkie boki jednego koloru.

(Początkowymi wyrazami ciągu $(n_k)$ są liczby $2$ , $5$ , $16$ , $65$ , czyli liczby pojawiające się w rozwiązaniu zadania; dla $k = 4$ otrzymujemy twierdzenie dane w zadaniu, przy czym oczywiście szachistów należy interpretować jako punkty zbioru $G$ , rozgrywane partie jako odcinki, a miasta jako kolory).

Sformułowane przed chwilą ogólne twierdzenie łatwo udowodnić przez indukcję stosując schemat rozumowania użyty w rozwiązaniu zadania.

Warto nadmienić, że ciąg $(n_k)$ określony podanym wzorem rekurencyjnym nie jest optymalny; jeśli $k \geq 4$ , to istnieją liczby $n \leq n_k$ takie, że dla dowolnego $n$ -elementowego zbioru punktów $G$ prawdziwa jest konkluzja twierdzenia (z $k$ kolorami); w szczególności, twierdzenie z zadania pozostaje prawdziwe przy zastąpieniu liczby $66$ liczbą $65$ . Nie jest jednak znany żaden wzór dający nietrywialne dolne ograniczenie dopuszczalnych wartości $n$ , ani asymptotyczne zachowanie tych minimalnych wartości, gdy $k \to \infty$ .

XXXVII OM - II - Zadanie 3

Zawody matematyczne:

XXXVII OM, 1985-1986

Etap:

Niech S będzie sferą opisaną na czworościanie foremnym o krawędzi długości większej od 1. Sferę $S$ przedstawiono w postaci sumy czterech zbiorów. Udowodnić, że do pewnego z tych zbiorów należą takie punkty $P$ , $Q$ , że długość odcinka $PQ$ przekracza 1.

Rozwiązanie

Udowodnimy najpierw lemat stanowiący jednowymiarową wersję tego twierdzenia.

Lemat. Okrąg $\omega$ opisany na trójkącie równobocznym o krawędzi długości większej od $1$ przedstawiono w postaci sumy trzech zbiorów: $\omega = U \cup V \cup W$ . Wówczas do pewnego ze zbiorów $U$ , $V$ , $W$ należą punkty $P$ , $Q$ , takie, że $|PQ| > 1$ .

Dowód lematu. Dla dowolnych dwóch nieantypodycznych punktów $X, Y \in \omega$ będziemy oznaczać symbolem $\breve{XY}$ łuk domknięty okręgu $\omega$ o końcach $X$ i $Y$ , zawarty w półokręgu. Przypuśćmy, że teza lematu nie jest prawdziwa i weźmy dowolny trójkąt równoboczny $ABC$ wpisany w $\omega$ . Jego wierzchołki muszą należeć do różnych zbiorów (spośród $U$ , $V$ , $W$ ); możemy założyć, że $A \in U$ , $B \in V$ , $C \in W$ . Wówczas $W \cap \breve{AB} = \emptyset$ (bo odległość każdego punktu łuku $\breve{AB}$ od punktu $C$ przekracza $1$ ). Niech

$ (1) \qquad a =\sup \{ |CM| \colon M \in \breve{CA} \cup W \} $

$ a =\sup \{ |CM| \colon M \in \breve{CB} \cup W \} $

i niech $E \in \breve{CA}$ , $F \in \breve{CB}$ będą punktami takimi, że $|CE| = a$ , $|CF| = b$ (rysunek 7). Odcinek $EF$ ma długość nie większą od $1$ ; gdyby bowiem było $|EF| > 1$ , to ponieważ, zgodnie z (1), dowolnie blisko punktów $E$ i $F$ leżą punkty zbioru $W$ , znaleźlibyśmy punkty $P, Q \in W$ takie, że $|PQ| > 1$ - wbrew naszemu przypuszczeniu. Zatem $|EF | \leq 1$ , a więc łuk $EF$ jest mniejszy, niż $1/3$ okręgu. (Jest to oczywiście ten z łuków o końcach $E$ i $F$ , który zawiera punkt $C$ , bo drugi z tych łuków zawiera punkty $A$ i $B$ ). Istnieją zatem punkty $P, Q, R \in \omega$ leżące poza łukiem $\breve{EF}$ i będące wierzchołkami trójkąta równobocznego.

Z definicji liczb $a$ i $b$ oraz punktów $E$ i $F$ wynika, że $W \cap \breve{CA} \subset \breve{CE}$ , $W \cap \breve{CB} \subset \breve{CF}$ , a ponieważ $W \cap \breve{AB} = \emptyset$ , wnosimy stąd, że $W \subset \breve{EF}$ . Wobec tego punkty $P$ , $Q$ , $R$ należą do sumy zbiorów $U$ i $V$ , a zatem dwa z nich muszą należeć do jednego z tych zbiorów. Kończy to dowód lematu, bo $|PQ| = |QR| = |RP| > 1$ .

Z lematu natychmiast wynika teza zadania: bierzemy czworościan foremny $ABCD$ wpisany w sferę $S$ oraz okrąg $\omega$ opisany na trójkącie $ABC$ . Punkt $D$ należy do jednego z czterech rozważanych zbiorów. Jeżeli ten zbiór zawiera jakikolwiek punkt $X \in \omega$ , to $|DX| > 1$ . W przeciwnym razie okrąg $\omega$ jest zawarty w sumie pozostałych trzech zbiorów i na mocy lematu jeden z tych zbiorów zawiera punkty $P$ , $Q$ takie, że $|PQ| > 1$ .

XXXVII OM - II - Zadanie 4

Zawody matematyczne:

XXXVII OM, 1985-1986

Etap:

Liczby naturalne $x, y, z$ , których największy wspólny dzielnik jest równy 1, spełniają równanie

$ \frac{1}{x} + \frac{1}{y} = \frac{1}{z} $

Dowieść, że $x + y$ jest kwadratem liczby naturalnej.

Rozwiązanie

Równanie przepisujemy w postaci

$ (1) \qquad (x+y)z = xy. $

Niech $k$ oznacza największy wspólny dzielnik liczb $x$ i $y$ : $k = NWD (x,y)$ . Mamy więc

$ x = km,\ y = kn,\ NWD (m, n) = 1. $

Zauważmy, że

$ (2) \qquad NWD (m + n, mn) = 1,\ NWD (k, z) = 1. $

Pierwsza z równości (2) wynika z tego, że $NWD (m, n) = 1$ (każdy dzielnik pierwszy iloczynu $mn$ musi dzielić $m$ lub $n$ , więc nie może dzielić sumy $(m + n)$ ; druga równość (2) jest konsekwencją założenia $NWD (x, y, z) = 1$ .

Podstawiając $x = km$ , $y = kn$ do (1) i dzieląc stronami przez $k$ dostajemy

$ (m + n)z = kmn, $

a stąd, na mocy (2),

$ m + n = k,\ z = mn. $

Ostatecznie więc

$ x + y = k(m + n) = k^2. $

XXXVII OM - II - Zadanie 5

Zawody matematyczne:

XXXVII OM, 1985-1986

Etap:

Udowodnić, że jeżeli wielomian $f$ nie równy tożsamościowo zeru spełnia dla każdego rzeczywistego $x$ równość $f(x)f(x + 3) = f(x^2 + x + 3)$ , to nie ma on pierwiastków rzeczywistych.

Rozwiązanie

Przypuśćmy, że pewien wielomian $f$ spełniający podane założenia ma pierwiastki rzeczywiste. Niech $x_0$ będzie największym z nich. Liczba $y_0 = x_0^2 + x_0+ 3 > x_0$ także jest pierwiastkiem wielomianu $f$ , bo

$ f(y_0) =f(x_0)f(x_0 + 3) = 0 $

- wbrew temu, że $x_0$ jest największym pierwiastkiem. Otrzymana sprzeczność dowodzi, że $f$ nie może mieć pierwiastków rzeczywistych.

XXXVII OM - II - Zadanie 6

Zawody matematyczne:

XXXVII OM, 1985-1986

Etap:

W trójkącie $ABC$ wybrano punkt $A'$ na boku $BC$ , punkt $B'$ na boku $AC$ , punkt $C'$ na boku $AB$ tak, że proste $AA'$ , $BB'$ , $CC'$ przecinają się w jednym punkcie, czyli równoważnie $|BA'| \cdot |CB'| \cdot |AC'| = |CA'| \cdot |AB'| \cdot |BC'|$ . Udowodnić, że pole trójkąta $A'B'C'$ jest nie większe od $1/4$ pola trójkąta $ABC$ .

Rozwiązanie

Uwaga. Równoważność między podanymi w założeniach warunkami jest treścią twierdzenia Cevy. Pokażemy dwa sposoby rozwiązania; w pierwszym wykorzystamy równość podanych iloczynów (nie korzystając bezpośrednio
z tego, żc trzy rozważane proste mają punkt wspólny), a w drugim sposobie postąpimy przeciwnie.

Wprowadźmy oznaczenia (jak na rysunku 8):

$ \begin{split} & |BC| = a,\ |CA| = b,\ |AB| = c,\\ & |BA'| = x,\ |CB'| =y,\ |AC'| = z\\ & (\textrm{więc} \ |A'C|=a-x,\ |B'A| = b-y,\ |C'B| = c-z),\\ & S = \textrm{pole trójkąta} \ ABC,\ S' = \textrm{pole trójkąta}\ A'B'C,\\ & S1 = \textrm{pole}\ (AB'C'),\ S_2 = \textrm{pole}\ (BC'A'),\ S_3 = \textrm{pole}\ (CA'B'). \end{split} $

Zgodnie z założeniem,

$ \begin{split} (1) \qquad xyz & = (a-x)(b-y)(c-z) =\\ & = abc- (abz + bcx + cay) + (ayz + bzx + cxy)-xyz, \end{split} $

czyli

$ (2) \qquad abc-2xyz = (abz+bcx+cay)- (ayz+bzx+cxy). $

Zauważmy dalej, że

$ S-1 = \frac{1}{2}(b - y)z \sin \measuredangle A, \ S = \frac{1}{2} bc \sin \measuredangle A, $

skąd

$ S_1 = \frac{(b-y)z}{bc} \cdot S $

i podobnie (przez cykliczne przestawienie symboli)

$ S_2 = \frac{(c-z)x}{ca} \cdot S, \ S_3 = \frac{(a-x)y}{ab} \cdot S. $

Zatem

$ S-S' = S_1+S_2+S_3 = \frac{S}{abc} [a(b- y)z+b(c-z)x+c(a-x)y] $

Ale wyrażenie w nawiasie kwadratowym to dokładnie prawa strona równości (2). Mamy więc

$ S-S' = \frac{S}{abc} (abc - 2xyz) = S - \frac{2xyz}{abc} \cdot S, $

czyli

$ (3) \qquad \frac{S'}{S} = \frac{2xyz}{abc}. $

Korzystając jeszcze raz ze wzoru (1) i stosując nierówność między średnią geometryczną i arytmetyczną (pary liczb) dostajemy

$ \begin{split} xyz = \sqrt{xyz(a - x)(b - y)(c - z)} & =\sqrt{x(a - x)} \cdot \sqrt{y(b - y)} \cdot \sqrt{z(c - z)} \leq \\ & \frac{x+(a - x)}{2} \cdot \frac{y+(b - y)}{2} \cdot \frac{z+(c -z)}{2}=\frac{abc}{8}. \end{split} $

W połączeniu z wzorem (3) daje to żądaną nierówność $S' \leq S/4$ .