LX OM - III etap

III etap LX Olimpiady Matematycznej

Załącznik	Wielkość
LX OM III etap - Zadania [1]	95.3 KB
LX OM III etap - Zadania z rozwiązaniami [2]	186.29 KB

LX OM - III - Zadanie 1

Zawody matematyczne:

LX OM, 2008-2009

Etap:

III

Każdy z wierzchołków sześciokąta wypukłego jest środkiem koła o promieniu równym
długości nie dłuższego z boków sześciokąta zawierających ten wierzchołek. Udowodnić,
że jeśli część wspólna wszystkich sześciu kół (rozważanych wraz z brzegiem) jest
niepusta, to sześciokąt jest foremny.

Rozwiązanie

Oznaczmy kolejne wierzchołki danego sześciokąta literami $A, B, C, D, E$ oraz $F$ .
Załóżmy, że przecięcie sześciu kół, o których mowa w treści zadania jest niepuste i punkt
$P$ należy do tego przecięcia. Rozważmy dowolny bok sześciokąta, dla ustalenia uwagi niech to
będzie bok $AB$ . Z warunków zadania wynika, że $AP \leqslant AB$ oraz $BP \leqslant AB$ , czyli
jeśli $P$ nie leży na prostej $AB$ , to odcinek $AB$ jest najdłuższym bokiem trójkąta $ABP$ .
Kąt $\measuredangle APB$ jest zatem jego największym kątem, czyli $\measuredangle APB \geqslant 60^{\circ}$ .
Jeśli natomiast punkt $P$ leży na prostej $AB$ , to leży na odcinku $AB$ (w przeciwnym razie $AP >AB$ lub $BP >AB$ ).
Jeśli dodatkowo nie jest końcem tego odcinka, to $\measuredangle APB = 180^{\circ}$ . Podsumowując,
jeśli $P \neq A$ i $P \neq B$ , to $\measuredangle APB \geqslant 60^{\circ}$ . Analogiczne rozumowanie można
przeprowadzić dla pozostałych boków sześciokąta.

Wykażemy, że punkt $P$ nie leży na zewnątrz sześciokąta $ABCDEF$ . Gdyby tak było, to dla pewnych
wierzchołków $X, Y$ , kąt wypukły $\measuredangle XPY < 180^{\circ}$ pokryłby cały sześciokąt
(rys. 1.). Wobec wypukłości sześciokąta $ABCDEF$ zachodziłoby

$ 2\measuredangle XPY = \measuredangle APB + \measuredangle BPC + \measuredangle CPD + \measuredangle DPE + \measuredangle EPF + \measuredangle FPA \geqslant 6 \cdot 60^{\circ} = 360^{\circ} , $

co jest sprzeczne z tym, że $\measuredangle XPY < 180^{\circ}$ .

Skoro punkt $P$ nie leży poza sześciokątem to leży w jego wnętrzu lub na jego brzegu.
Najpierw rozważmy przypadek, gdy $P$ jest jednym z wierzchołków sześciokąta. Bez zmniejszania
ogólności rozumowania możemy założyć, że $P = A$ . Wówczas, wobec wypukłości sześciokąta, zachodzi

$ \measuredangle BAF = \measuredangle BPF = \measuredangle BPC + \measuredangle CPD + \measuredangle DPE + \measuredangle EPF \geqslant 4 \cdot 60^{\circ} > 180^{\circ}, $

co jest niemożliwe. Jeśli $P$ leży na brzegu sześciokąta $ABCDEF$ , ale nie jest jego wierzchołkiem,
to leży pomiędzy pewnymi jego kolejnymi wierzchołkami. Bez zmniejszania ogólności rozumowania możemy
założyć, że $P$ leży na boku $AB$ sześciokąta. Wówczas zachodzi

$ $180^{\circ} = \measuredangle BPA = \measuredangle BPC + \measuredangle CPD + \measuredangle DPE + \measuredangle EPF + \measuredangle FPA \geqslant 5 \cdot 60^{\circ} > 180^{\circ}, $

co również jest niemożliwe.

Zatem $P$ leży we wnętrzu sześciokąta. Kąty $\measuredangle APB$ , $\measuredangle BPC$ , $\measuredangle CPD$ ,
$\measuredangle DPE$ , $\measuredangle EPF$ oraz $\measuredangle FPA$ dają wówczas w sumie kąt pełny, a miara
każdego z nich jest nie mniejsza, niż $60^{\circ$ }. Wynika stąd, że miara każdego z nich wynosi
$60^{\circ}$ (rys. 2.). Ponieważ $\measuredangle APB = 60^{\circ}$ jest największym kątem trójkąta
$ABP$ , pozostałe kąty również mają miarę $60^{\circ}$ . Trójkąt $ABP$ jest więc równoboczny i analogicznie,
pozostałe trójkąty o wierzchołku $P$ i podstawie będącej jednym z boków też są równoboczne. Zatem sześciokąt
jest foremny.

LX OM - III - Zadanie 2

Zawody matematyczne:

LX OM, 2008-2009

Etap:

III

Niech $S$ będzie zbiorem wszystkich punktów płaszczyzny o obu współrzędnych całkowitych. Znaleźć
najmniejszą liczbę całkowitą dodatnią $k$ , dla której istnieje 60–elementowy podzbiór zbioru $S$
o następującej własności: Dla dowolnych dwóch różnych elementów $A$ i $B$ tego podzbioru istnieje taki punkt
$C \in S$ , że pole trójkąta $ABC$ jest równe $k$ .

Rozwiązanie

Niech $K$ będzie podzbiorem zbioru $S$ mającym dla zadanej liczby $k$ własność podaną w treści zadania.
Ustalmy dowolne dwa różne punkty $(a, b), (c, d) \in K$ . Wtedy dla pewnych liczb całkowitych
$x, y$ pole trójkąta o wierzchołkach $(a, b)$ , $(c, d)$ , $(x, y)$ wynosi $k$ , czyli zachodzi równość
$\frac{1}{2}|(a - c)(y - d) - (b - d)(x - c)| = k$ . Otrzymujemy stąd warunek, że równanie

$ (1) \qquad |(a - c)(y - d) - (b - d)(x - c)| =2k $

ma dla dowolnych ustalonych i różnych $(a, b), (c, d) \in K$ rozwiązanie w liczbach całkowitych x, y.

Udowodnimy, że jeśli liczba $m$ nie dzieli $2k$ , to zbiór $K$ ma nie więcej niż $m^2$ elementów.
Rozważmy w tym celu pary $(a \mod m, b \mod m)$ reszt z dzielenia współrzędnych punktów zbioru $K$ przez $m$ .
Jest ich $m^2$ , więc jeśli $|K| >m^2$ , to na mocy zasady szufladkowej znajdziemy dwa różne punkty
$(a, b) \in K$ i $(c, d) \in K$ , takie że $a \equiv c \mod m$ i $b \equiv d \mod m$ . Dla takich punktów
równanie (1) nie ma rozwiązania, gdyż lewa jego strona dla dowolnych $x$ i $y$ dzieli się przez $m$ ,
a prawa nie. Zatem $|K|\leqslant m^2$ dla dowolnego $m$ nie będącego dzielnikiem $2k$ .

Z powyższych rozważań wynika, że jeżeli $|K| = 60$ , to $2k$ musi być podzielne przez wszystkie liczby
$m \leqslant 7$ , bowiem $60 > 7^2$ . Łatwo sprawdzić, że najmniejszą liczbą naturalną podzielną przez
2, 3, 4, 5, 6, 7 jest $22 \cdot 3 \cdot 5 \cdot 7 = 420$ , zatem $210|k$ .

Pokażemy, że dla każdego $k$ takiego, że $210|k$ , można skonstruować 60–elementowy zbiór $K$ mający
własność podaną w treści zadania. Niech $K'$ będzie zbiorem wszystkich tych elementów zbioru $S$ ,
których obie współrzędne znajdują się w zbiorze $\{0, 1,..., 7\}$ . Ustalmy dwa dowolne, różne punkty
$A =(a, b)$ i $B=(c, d)$ ze zbioru $K$ . Wtedy $a - c, b - d \in \{-7, -6,..., 6, 7\}$ , zatem jeśli
$a \neq c$ , to $a-c|420$ oraz jeśli $b = d$ , to $b-d|420$ . Bez straty ogólności możemy przyjąć, że $b = d$ .
Wówczas $b - d|2k$ , gdyż $420|2k$ . Punkt $C =(c + \frac{2k}{d-b} ,d)$ jest zatem elementem zbioru $S$ ,
zaś pole trójkąta $ABC$ wynosi

$ \frac{1}{2}\left| (a-c)(d-d) - (b-d)\left(c+ \frac{2k}{d-b} -c \right) \right|=k. $

Ponadto $|K'| = 64 > 60$ . Jako zbiór $K$ można wziąć dowolny 60–elementowy podzbiór zbioru $K$ .

Tym samym pokazaliśmy, że 60–elementowy zbiór mający żądaną własność istnieje tylko dla liczb
całkowitych dodatnich $k$ będących wielokrotnościami 210. Najmniejszą taką liczbą jest 210.

LX OM - III - Zadanie 3

Zawody matematyczne:

LX OM, 2008-2009

Etap:

III

Niech $P, Q, R$ będą wielomianami stopnia co najmniej jeden, o współczynnikach rzeczywistych,
spełniającymi dla każdej liczby rzeczywistej $x$ równości

$ P(Q(x)) = Q(R(x)) = R(P (x)). $

Wykazać, że $P = Q = R$ .

Rozwiązanie

Sposób I.

Udowodnimy najpierw, że jeśli wielomiany $W_1, W_2$ spełniają dla każdej liczby rzeczywistej x równość

$ (1) \qquad W_1(W_1(W_1(x))) = W_2(W_2(W_2(x))), $

to $W_1 = W_2$ .

Łatwo zauważyć, że wielomiany te mają ten sam stopień. Dla wielomianów stopnia 0 (stałych) nie ma
czego dowodzić. Załóżmy więc, że ich stopień jest równy co najmniej 1.

Zauważmy, że jeżeli równość (1) jest spełniona, to obydwa te wielomiany są zgodnie monotoniczne na
przedziale $(x_1, \infty)$ dla pewnego $x_1$ oraz są zgodnie monotoniczne na przedziale
$(-\infty,x_1')$ dla pewnego $x_1'$ . W przeciwnym razie $W_1(W_1(W_1(x)))$ i $W_2(W_2(W_2(x)))$
dla odpowiednio dużych $x$ przyjmowałyby wartości o przeciwnych znakach. Zatem możliwe są następujące sytuacje:

$W_1, W_2$ są ściśle rosnące na przedziale $(x_1, \infty)$ .
$W_1, W_2$ są ściśle rosnące na przedziale $(-\infty,x'_1 )$ .
Nie zachodzi ani pierwszy, ani drugi przypadek, czyli zarówno na $(-\infty,x_1)$ , jak i na
$(x_1, \infty)$ , oba wielomiany są malejące.

Przeprowadzimy dowód nie wprost. Załóżmy, że równość (1) jest spełniona, ale
$W_1 \neq W_2$ . Wówczas równanie $W_1(x) - W_2(x) = 0$ ma skończenie wiele rozwiązań. W przypadku 1
istnieje zatem taka liczba $x_2$ , że dla wszystkich liczb $x>x_2$ zachodzi $W_1(x) >W_2(x)$
(lub na odwrót, co nie ma znaczenia dla ogólności rozumowania).

Niech $x_3 = \max\{x_1,x_2\}$ i niech $x_0$ będzie taką liczbą rzeczywistą, że liczby
$x_0$ , $W_2(x_0)$ oraz $W_2(W_2(x_0))$ są większe od $x_3$ . Istnienie takiej liczby $x_0$ wynika
z tego, że $W_2$ jest wielomianem dodatniego stopnia, co wobec założenia dotyczącego monotoniczności
wielomianu $W_2$ daje $\lim_{x \to \infty} W_2(x) = \lim_{x\to \infty} W_2(W_2(x)) = +\infty$ .

Mamy więc $W_1(x_0) >W_2(x_0) >x_3$ . Stąd $W_1(W_1(x_0)) >W_1(W_2(x_0)) >W_2(W_2(x_0)) >x_3$ , zatem

$ W_1(W_1(W_1(x_0))) >W_1(W_1(W_2(x_0))) >W_1(W_2(W_2(x_0))) >W_2(W_2(W_2(x_0))). $

Otrzymana sprzeczność dowodzi, że $W_1 = W_2$ w przypadku 1.

W przypadku 2 rozumowanie przebiega podobnie. Pozostaje rozpatrzeć przypadek 3. Zauważmy, że wtedy
wielomiany $W_1'(x)= W_1(W_1(x))$ i $W_2'(x)= W_2(W_2(x))$ dążą do $+\infty$ dla $x \to \infty$ ,
więc są rosnące na przedziale $(x_1'', \infty)$ dla pewnego $x_1''$ . Możemy zatem porzeprowadzić
dla $W_1'$ i $W_2'$ rozumowanie takie samo jak w przypadku 1 i w ten sposób wykazać, że
$W_1' = W_2'$ . Stąd $W_1(W_1'(x))) = W_1(W_1(W_1(x))) = W_2(W_2(W_2(x))) = W_2(W_2'(x))$ ,
więc $W_1(W_1'(x))) = W_2(W_1'(x)))$ . Wynika z tego, że $W_1 = W_2$ , gdyż dla nieskończenie wielu
$y$ zachodzi $W_1(y)= W_2(y)$ . To kończy dowód lematu.

Przejdźmy do rozwiązania zadania. Podstawiając $y = P(x)$ w równości $P(Q(y)) = Q(R(y))$ otrzymujemy
$P(Q(P(x))) = Q(R(P(x)))$ . Z drugiej strony, równość $P(Q(x)) = R(P(x))$ implikuje równość
$Q(P(Q(x))) = Q(R(P(x)))$ . Oznacza to, że $P(Q(P(x))) = Q(P(Q(x)))$ , a w konsekwencji

$ P(Q(P(Q(P(Q(x)))))) = Q(P(Q(P(Q(P(x)))))). $

Stosując wcześniej dowiedzioną obserwację dla wielomianów $W_1(x)= P(Q(x))$ i $W_2(x)= Q(P(x))$
otrzymujemy $P(Q(x)) = Q(P(x))$ . Stąd $Q(P(x)) = R(P(x))$ , zatem $Q = R$ , gdyż, ponieważ $P$ nie jest
stały, dla nieskończenie wielu $y$ zachodzi $Q(y)= R(y)$ . Pozostałych równości dowodzimy w ten sam sposób.

Sposób II.

Niech $p = \deg(P)$ , $q = \deg(Q)$ oraz $r = \deg(R)$ będą stopniami wielomianów odpowiednio $P$ , $Q$ oraz $R$ i niech

$ P(x)= \sum_{k=0}^p p_kx^k,\; Q(x)= \sum_{k=0}^q q_kx^k,\; R(x)= \sum_{k=0}^r r_kx^k. $

Niech ponadto

$ P(Q(x)) = Q(R(x)) = R(P(x)) = \sum_{k=0}^m a_kx^k, $

przy czym $a_m \neq 0$ .

Zauważmy, że $P(Q(x))$ jest wielomianem stopnia $pq$ , czyli $m = pq$ . Podobnie, rozważając wielomiany
$Q(R(x))$ i $R(P(x))$ uzyskujemy $m = qr$ oraz $m = rp$ . Skoro $pq = qr = rp$ oraz $p,q,r > 0$ , to
$p = q = r$ . Dla przejrzystości oznaczmy tę wspólną wartość jako $n$ . Wówczas $m = pq = n^2$ .
Analizując współczynniki $a_m,a_{m-1},\cdots ,a_{m-n+1}$ , wykażemy kolejno, że dla $i = n, n - 1,\cdots , 1$
zachodzi $p_i = q_i = r_i$ .

Zacznijmy od obserwacji, że jeśli $t$ jest dodatnią liczbą całkowitą, to

$ \begin{split} (Q(x))^t = \left(\sum_{j=0}^q q_jx^j\right)^t &= \sum_{j_1,j_2,\cdots ,j_t \leqslant q} q_{j_1} q_{j_2} \cdots q_{j_t} x^{j_1+j_2+\cdots +j_t} = \\ &= \sum_{k=0}^{q\cdot t} x^k \cdot \sum_{\begin{array}{cc} j_1,j_2,\cdots ,j_t \leqslant q \\ j_1+j_2+\cdots +j_t = k\end{array}} q_{j_1} q_{j_2} \cdots q_{j_t}. \end{split} $

Występujące w powyższym wzorze liczby $j_1,j_2,\cdots ,j_t$ są nieujemnymi liczbami całkowitymi.
Zdefniujmy wielomian $P'(x)= P(x) - p^nx^n$ . Wtedy

$ (2) \qquad P(Q(x)) = p_n(Q(x))^n + P'(Q(x)). $

$P'(x)$ jest wielomianem stopnia co najwyżej $n - 1$ , stąd $\deg(P'(Q(x))) \leqslant n(n - 1)$ .
Wynika z tego, że w celu wyznaczenia współczynników $a_k$ dla $k>m - n = n(n - 1)$ wystarczy skupić
uwagę na współczynnikach wielomianu $p_n(Q(x))^n$ , czyli

$ (3) \qquad a_k = p_n \sum_{\begin{array}{cc} j_1,j_2,\cdots ,j_n \leqslant q \\ j_1+j_2+\cdots +j_n=k\end{array}} q_{j_1} q_{j_2} \cdots q_{j_n},\quad \text{gdy }n(n - 1) <k \leqslant n^2. $

Mamy $a_{n^2}= p_nq_n^n= q_nr_n^n= r_np_n^n$ . Liczby $p_n,q_n,r_n$ są różne od 0, zatem zachodzi równość

$ p_n^{n(n-1)+1} = \frac{(p_nq_n^n)(r_np_n^n)^n}{p_n^nq_n^nr_n^n} = \frac{(q_nr_n^n)(p_nq_n^n)^n}{p_n^nq_n^nr_n^n} = q_n^{n(n-1)+1} $

Identycznie uzyskujemy równość $q_n^{n(n-1)+1}=r_n^{n(n-1)+1}$ . Wykładnik $n(n - 1) + 1$ jest liczbą
nieparzystą, więc $p_n = q_n = r_n$ .

Niech teraz $i \in\{1, 2,\cdots ,n - 1\}$ i załóżmy, że $p_j = q_j = r_j$ dla $j>i$ . Wtedy, korzystając
z (3), otrzymujemy

$ (4) \qquad \begin{split} a_{n(n-1)+i} &= \sum_{\begin{array}{cc} j_1,j_2,\cdots ,j_n \leqslant n \\ j_1+j_2+\cdots +j_n = n(n-1)+i\end{array}} p_n q_{j_1} q_{j_2} \cdots q_{j_n} \\ &= \sum_{\begin{array}{cc} j_1,j_2,\cdots ,j_n \leqslant n \\ j_1+j_2+\cdots +j_n = n(n-1)+i\end{array}} q_n r_{j_1} r_{j_2} \cdots r_{j_n} \\ &= \sum_{\begin{array}{cc} j_1,j_2,\cdots ,j_n \leqslant n \\ j_1+j_2+\cdots +j_n = n(n-1)+i\end{array}} r_n p_{j_1} p_{j_2} \cdots p_{j_n} \end{split} $

Jedynymi sposobami przedstawienia liczby $n(n-1)+i$ w postaci sumy
$j_1 +j_2 +\cdots +j_n$ nieujemnych liczb całkowitych, z których żadna nie przekracza
$n$ i nie wszystkie są większe niż $i$ , są te, w których jeden składnik wynosi $i$ , a pozostałe są równe $n$ .
Takich przedstawień jest $n$ , gdyż $i$ może być dowolną spośród liczb $j_1,j_2,\cdots ,j_n$ .
Założyliśmy, że $p_j = q_j = r_j$ dla $j>i$ , więc z równości (4) wynika

$ np_nq_iq_n^{n-1} = nq_nr_ir_n^{n-1} = nr_np_ip_n^{n-1}, $

co wobec tego, że $p_n = q_n = r_n \neq 0$ , pociąga za sobą równość $p_i= q_i = r_i$ . To kończy dowód kroku indukcyjnego.

Pokażemy teraz, że p_0 = q_0 = r_0. W przypadku gdy $n> 1$ , wystarczy w tym celu rozważyć współczynnik
$a_{n(n-1)}$ . Analizując (2), widzimy, że w wielomianie $P'(Q(x))$ współczynnikiem przy
$x^{n(n-1)}$ jest $p_{n-1}q_n^n$ , zatem $a_{n(n-1)}$ jest sumą $p_{n-1}q_n^n$ i współczynnika przy
$x^{n(n-1)}$ w wielomianie $p_n(Q(x))^n$ . Stąd

$ a_{n(n-1)} = p_{n-1}q_n^{n-1} + \sum_{\begin{array}{cc} j_1,j_2,\cdots ,j_n \leqslant n \\ j_1+j_2+\cdots +j_n = n(n-1)\end{array}} p_n q_{j_1} q_{j_2} \cdots q_{j_n} $

i analogicznie

$ \begin{split} a_{n(n-1)} &= q_{n-1}r_n^{n-1} + \sum_{\begin{array}{cc} j_1,j_2,\cdots ,j_n \leqslant n \\ j_1+j_2+\cdots +j_n = n(n-1)\end{array}} q_n r_{j_1} r_{j_2} \cdots r_{j_n} \\ &= r_{n-1}p_n^{n-1} + \sum_{\begin{array}{cc} j_1,j_2,\cdots ,j_n \leqslant n \\ j_1+j_2+\cdots +j_n = n(n-1)\end{array}} r_n p_{j_1} p_{j_2} \cdots p_{j_n} \end{split} $

Wiemy, że $p_j = q_j = r_j$ dla $j> 0$ , więc, podobnie jak poprzednio, dostajemy
$np_nq_0q_n^{n-1} = nq_nr_0r_n^{n-1} = nr_np_0p_n^{n-1}$ , skąd $p_0 = q_0 = r_0$ .
Pokazaliśmy zatem, że gdy $n> 1$ , wielomiany $P$ , $Q$ oraz $R$ mają odpowiednie współczynniki równe,
więc $P = Q = R$ .

Przypadek $n = 1$ wymaga oddzielnego rozważenia. Jeśli wielomiany
$P(x)= p_1x + p_0$ , $Q(x)= q_1x + q_0$ oraz $R(x)= r_1x + r_0$ spełniają warunki zadania, to, jak
pokazaliśmy wcześniej, $p_1 = q_1 = r_1 \neq 0$ . Porównując wyrazy wolne wielomianów
$P(Q(x))$ , $Q(R(x))$ i $R(P(x))$ dostajemy $p_1q_0 + p_0 = p_1r_0 + q_0 = p_1p_0 + r_0$ ,
a stąd łatwo uzyskujemy, że $p_0 = q_0 = r_0$ .

LX OM - III - Zadanie 4

Zawody matematyczne:

LX OM, 2008-2009

Etap:

III

Niech $x_1,x_2,\cdots ,x_n$ będą liczbami nieujemnymi, których suma wynosi 1. Udowodnić, że istnieją
liczby $a1,a2,\cdots ,an \in \{0, 1, 2, 3, 4\}$ takie, że $(a_1,a_2,\cdots ,a_n) \neq (2, 2,\cdots , 2)$ oraz

$ 2 \leqslant a_1x_1 + a_2x_2 + \cdots + a_nx_n \leqslant 2+ \frac{2}{3^n-1}. $

Rozwiązanie

Rozważmy wszystkie możliwe ciągi $t =(t_1,t_2,\cdots ,t_n)$ takie, że $t_1,t_2,\cdots ,t_n \in \{0, 1, 2\}$ .
Jest ich $3n$ . Dla każdego z nich niech $S_t$ oznacza sumę $t_1x_1 +t_2x_2 +\cdots +t_nx_n$ .
Ponieważ liczby $x_1,x_2,\cdots ,x_n$ są nieujemne i ich suma wynosi 1, więc zachodzą nierówności

$ 0=0 \cdot x_1 +0 \cdot x_2 + \cdots +0 \cdots x_n \leqslant S_t \leqslant 2 \cdot x_1 +2 \cdot x_2 + \cdots +2 \cdot x_n =2. $

Z zasady szufladkowej Dirichleta wynika, że istnieją dwa różne ciągi $b =(b_1,b_2,\cdots ,b_n)$
oraz $c = (c_1,c_2,\cdots ,c_n)$ o wyrazach w zbiorze $\{0, 1, 2\}$ takie, że odpowiadające im sumy
$S_{b}$ oraz $S_{c}$ należą do tego samego spośród $3n -1$ przedziałów
$[0, \frac{2}{3^n-1})$ , $[\frac{2}{3^n-1}, \frac{4}{3^n-1})$ , $[\frac{4}{3^n-1}, \frac{6}{3^n-1})$ ,
$\cdots, [\frac{2(3^n-5)}{3^n-1}, \frac{3^n-3}{3^n-1})$ , $[\frac{2(3^n-3)}{3^n-1}, 2]$ .
Bez zmniejszania ogólności rozumowania możemy założyć, że $S_{b}$ . $S_{c}$ i wówczas

$ (1) \qquad 0 \leqslant S_{c} - S_{b} \leqslant \frac{2}{3^n-1}. $

Pokażemy, że warunki zadania spełnia ciąg $a =(a_1,a_2,\cdots ,a_n)$ określony wzorem

$ a_i =2+ c_i - b_i \quad \text{ dla }i =1, 2, \cdots , n. $

Każdy z jego wyrazów jest liczbą ze zbioru $\{0, 1, 2, 3, 4\}$ . Ponadto $b\neq (2, 2,\cdots , 2)$ ,
gdyż ciągi $b$ i $c$ są różne. Zachodzi także równość

$ S_{a} = \sum_{i=1}^n (2+ c_i - b_i)x_i =\sum_{i=1}^n 2x_i + \sum_{i=1}^nc_ix_i - \sum_{i=1}^n b_ix_i =2+ S_{c} - S_{b}, $

skąd, wobec (1), dostajemy $2 \leqslant a_1x_1 + a_2x_2 + \cdots + a_nx_n \leqslant 2 + \frac{2}{3^n-1}$ .

LX OM - III - Zadanie 5

Zawody matematyczne:

LX OM, 2008-2009

Etap:

III

Sfera wpisana w czworościan $ABCD$ jest styczna do jego ścian $BCD, ACD, ABD, ABC$ odpowiednio w punktach
$P, Q, R, S$ . Odcinek $PT$ jest średnicą tej sfery, zaś punkty $A',Q',R',S'$ są punktami przecięcia prostych
$TA, TQ, TR, TS$ z płaszczyzną $BCD$ . Wykazać, że $A'$ jest środkiem okręgu opisanego na trójkącie $Q'R'S'$ .

Rozwiązanie

Sposób I.

Niech $\Theta$ będzie sferą wpisaną w czworościan $ABCD$ i niech $O$ będzie środkiem tej sfery.
Ponieważ punkty $A, T$ i $A'$ są współliniowe oraz $A \neq T$ , więc istnieje jednokładność $\varphi$ o środku
$A$ przekształcająca punkt $T$ na punkt $A'$ . Niech $\Theta_1 = \varphi(\Theta)$ i niech $\Pi$ będzie taką
płaszczyzną, że jej obrazem w jednokładności $\varphi$ jest płaszczyzna $BCD$ . Wówczas płaszczyzny $BCD$
i $\Pi$ są równoległe, a ponadto $T \in \Pi$ . Skoro $PT$ jest średnicą sfery $\Theta$ i płaszczyzna
$BCD$ jest styczna do tej sfery w punkcie $P$ , to płaszczyzna $\Pi$ jest do niej styczna w punkcie $T$ .
Zatem $\varphi(\Pi)$ jest styczna do sfery $\varphi(\Theta) = \Theta_1$ w punkcie $\varphi(T)= A'$ .

Rozważmy przekrój czworościanu $ABCD$ , płaszczyzny $\Pi$ oraz sfer $\Theta$ i $\Theta_1$ płaszczyzną
$ATQ$ (rys. 1.).

Niech $Z$ będzie punktem przecięcia prostej $AQ$ i płaszczyzny $BCD$ . Niech ponadto $Q_1 = \varphi(Q)$ .
Wówczas $Q_1$ jest punktem styczności prostej $AQ$ i sfery $\Theta_1$ , zatem $ZA' = ZQ_1$ , czyli trójkąt
$Q_1ZA'$ jest trójkątem równoramiennym. Zauważmy, że proste $A'Q_1$ i $TQ$ są równoległe, gdyż pierwsza z nich
jest obrazem drugiej w jednokładności $\varphi$ . Wynika stąd, że trójkąty $QZQ'$ oraz $Q_1ZA'$ są podobne,
czyli trójkąt $QZQ'$ również jest równoramienny. Zachodzą równości:

$ A'Q' = A'Z + ZQ' = Q_1Z + ZQ = Q_1Q = AQ_1 - AQ = k \cdot AQ - AQ =(k - 1) \cdot AQ, $

gdzie k jest skalą jednokładności $\varphi$ . W podobny sposób pokazujemy, że
$A'R' =(k - 1) \cdot AR$ oraz $A'S' =(k - 1) \cdot AS$ . Ponieważ proste $AQ$ , $AR$ oraz $AS$ są styczne
do sfery $\Theta$ odpowiednio w punktach $Q$ , $R$ oraz $S$ , więc $AQ = AR = AS$ . Zatem
$A'Q' = A'R' = A'S'$ , czyli $A'$ jest środkiem okręgu opisanego na trójkącie $Q'R'S'$ .

Sposób II.

Wystarczy wykazać, że proste $BA' , CA' i DA'$ są symetralnymi boków zawartego w płaszczyźnie $BCD$
trójkąta $Q'R'S'$ . Ponieważ dla wszystkich trzech prostych rozumowanie jest identyczne, ograniczymy się
do pokazania, że prosta $BA$ . jest symetralną boku $R'S'$ . Dokonamy tego, wskazując na prostej $BA'$
dwa różne punkty równoodległe od punktów $R'$ i $S'$ . Jednym z nich jest punkt $B$ , a drugim rzut punktu
$T$ na płaszczyznę $BCD$ w kierunku równoległym do prostej $AB$ .

Niech $O$ będzie środkiem sfery wpisanej w czworościan $ABCD$ . Ponieważ proste $BP$ i $BR$ są styczne do
tej sfery odpowiednio w punktach $P$ oraz $R$ , więc $BP = BR$ . Wynika to z przystawania trójkątów prostokątnych
$BOP$ i $BOR$ . Niech $X$ będzie rzutem prostokątnym punktu $B$ na płaszczyznę $TPR$ (rys. 2.). Płaszczyzna
ta jest prostopadła do płaszczyzny $BCD$ , a ich przecięciem jest prosta $PR'$ . Wynika stąd, że punkt $X$
leży na prostej $PR'$ . Trójkąty prostokątne $BXP$ i $BXR$ mają wspólną przyprostokątną $BX$ i równe
przeciwprostokątne. Są zatem przystające i $XP = XR$ . Punkt $X$ leży na prostej $PR$ . zawierającej
przeciwprostokątną trójkąta prostokątnego $PRR'$ i jest równoodległy od dwóch jego wierzchołków: $P$ i $R$ .
Jest więc środkiem okręgu opisanego na tym trójkącie, czyli środkiem jego przeciwprostokątnej $PR'$ .
Punkt $X$ jest także spodkiem wysokości trójkąta $PBR'$ opuszczonej z wierzchołka $B$ . Skoro wysokość
ta połowi jego bok $PR'$ , to trójkąt ten jest równoramienny, czyli $BP = BR'$ . Analogicznie pokazujemy, że
$BP = BS'$ . Wynika stąd, że $BR' = BS'$ , co oznacza, że punkt $B$ leży na symetralnej odcinka $R'S'$ .

Niech $\Sigma$ będzie płaszczyzną zawierającą punkt $T$ i równoległą do płaszczyzny $ABD$ . Płaszczyzna
$ABD$ (a więc także i płaszczyzna $\Sigma$ ) jest prostopadła do prostej $OR$ , gdyż jest w punkcie $R$ styczna
do sfery, której środkiem jest punkt $O$ . Wynika stąd, że płaszczyzny $\Sigma$ i $TPR$ są prostopadłe, gdyż
ta ostatnia zawiera prostą $OR$ . Niech $Y$ będzie rzutem punktu $T$ na płaszczyznę $BCD$ w kierunku
równoległym do prostej $AB$ , czyli takim punktem płaszczyzny $BCD$ , że $TY || AB$ . Ponieważ punkt $T$ nie leży
na prostej $AB$ , więc $Y\neq B$ . Punkt $Y$ leży na płaszczyznach $BCD$ oraz $ABT$ , więc leży na będącej
ich przecięciem prostej $BA'$ . Punkt $Y$ leży także na płaszczyźnie $\Sigma$ . Niech $Z$ będzie rzutem
prostokątnym punktu $Y$ na płaszczyznę $TPR$ (rys. 3.). Ponieważ $Y$ leży na płaszczyźnie $BCD$ , która jest
prostopadła do płaszczyzny $TPR$ , więc $Z$ należy do przecięcia tych płaszczyzn, czyli do prostej $PR'$ .
Z prostopadłości płaszczyzn $TPR$ i $\Sigma$ wynika z kolei, że skoro $Y \in \Sigma$ , to również
$Z \in \Sigma$ . Trójkąt $POR$ jest trójkątem równoramiennym, gdyż jego boki $OP$ i $OR$ są promieniami
tej samej sfery. Proste zawierające boki trójkąta $R'ZT$ są prostopadłe do prostych zawierających boki
trójkąta $POR$ : Prosta $PO$ jest prostopadła do płaszczyzny $BCD$ , a więc również do zawartej w niej prostej
$R'Z$ . Prosta $RP$ jest prostopadła do prostej $TR'$ , a prosta $OR$ jest prostopadła do prostej $ZT$ ,
gdyż ta ostatnia zawarta jest w płaszczyźnie $\Sigma$ , a jak wcześniej zauważyliśmy, płaszczyzna
$\Sigma$ jest prostopadła do prostej $OR$ . Wynika stąd, że trójkąty $POR$ i $R'ZT$ są podobne, w szczególności
trójkąt $R'ZT$ jest równoramienny i $ZT = ZR'$ . Trójkąty prostokątne $YZT$ i $YZR'$ są przystające, bo mają
wspólną przyprostokątną $YZ$ oraz $ZT = ZR'$ . Mają więc równe przeciwprostokątne, czyli $YT = YR'$ .
Analogicznie pokazujemy, że $YT = YS'$ . Wynika stąd, że $YR' = YS'$ , co oznacza, że punkt $Y$ leży na
symetralnej odcinka $R'S'$ .

Wskazaliśmy dwa różne punkty leżące na prostej $BA'$ i równoodległe od punktów $R'$ i $S'$ .
Zatem prosta $BA'$ jest położoną w płaszczyźnie $BCD$ symetralną boku $R'S'$ trójkąta $Q'R'S'$ .
Analogiczne rozumowanie pokazuje, że symetralnymi dwóch pozostałych boków tego trójkąta są proste
$CA'$ i $DA'$ . Punkt $A'$ jest więc środkiem okręgu opisanego na trójkącie $Q'R'S'$ .

$CA'$ i $DA'$ . Punkt $A'$ jest więc środkiem okręgu opisanego na trójkącie Q'R'S'.

LX OM - III - Zadanie 6

Zawody matematyczne:

LX OM, 2008-2009

Etap:

III

Niech $n \geqslant$ 3 będzie liczbą naturalną. Ciąg liczb nieujemnych
$(c_0,c_1,\cdots ,c_n)$ spełnia warunek

$ (1) \qquad c_pc_s + c_rc_t = c_{p+r}c_{r+s} $

dla wszystkich $p, r, s, t \geqslant 0$ takich, że $p + r + s + t = n$ . Wyznaczyć wszystkie możliwe
wartości $c_2$ , jeśli $c_1 =1$ .

Rozwiązanie

Sposób I.

Pokażemy, że dla każdej liczby naturalnej $n \geqslant 3$ istnieje dokładnie jeden ciąg spełniający
warunki zadania, a jedyna możliwa wartość $c_2$ wynosi $2 \cos(\pi/n)$ .

Zauważmy, że dla $p = n$ oraz $r = s = t = 0$ warunek (1) przyjmuje postać
$c_nc_0 + c^2_0 = c_nc_0$ , skąd dostajemy $c_0 = 0$ . Z kolei dla dowolnego $k \in\{1, 2,\cdots ,n\}$ ,
z warunku (1) dla $p = 0, r = 1, s = k - 1, t = n - k$ wynika, że $c_0c_{k-1} + c_1c_{n-k} = c_1c_k$ ,
czyli $c_{n-k} = c_k$ . W szczególności, dla $k = n$ dostajemy $0 = c_0 = c_n$ .

Niech $d$ będzie liczbą dodatnią, $\varphi = \frac{\pi}{n}$ oraz niech $c'_k = d \sin(k\varphi)$ dla
$k =0, 1,\cdots ,n$ . Pokażemy, że tak zdefiniowany ciąg $(c'_0,c'_1,\cdots ,c'_n)$ spełnia warunek
(1). W tym celu wystarczy dowieść tożsamości trygonometrycznej

$ (2) \qquad \sin \alpha \sin \gamma + \sin \beta \sin \delta = \sin(\alpha + \beta) \sin(\beta + \gamma), $

dla $\alpha + \beta + \gamma + \delta = \pi$ . Przekształcając lewą stronę tożsamości, mamy

$ \begin{split} 2 \sin \alpha \sin \gamma + 2 \sin \beta \sin \delta &= \cos(\alpha - \gamma) - \cos(\alpha + \gamma) + \cos(\beta - \delta) - \cos(\beta + \delta) \\ &= \cos(\alpha - \gamma) + \cos(\beta - \delta) \\ &= \cos(\alpha - \gamma) - \cos(\alpha +2\beta + \gamma) = 2 \sin(\alpha + \beta) \sin(\beta + \gamma). \end{split} $

Korzystaliśmy tu kilkakrotnie z tożsamości
$2 \sin \alpha \sin \beta = \cos(\alpha - \beta) - \cos(\alhpa + \beta)$ oraz z faktu, że
$\alpha + \beta + \gamma + \delta = \pi$ . Zatem dowiedliśmy (2).

Przyjmując $d = \frac{1}{\sin\varphi}$ , otrzymujemy $c'_1 = 1$ oraz $c'_k > 0$ dla
$k =0, 1,\cdots ,n$ , a wtedy ciąg $(c_0,c_1,\cdots ,c_n)$ spełnia wszystkie warunki zadania. Uzasadnimy,
że jest to jedyny taki ciąg.

Przypuśćmy, że $d =(d_0,d_1,\cdots ,d_n)$ jest ciągiem liczb nieujemnych spełniającym warunki nałożone
na ciąg $c =(c_0,c_1,\cdots ,c_n)$ , ale $d \neq c$ . Podstawiając w (1) $p = s = 1$ oraz $t = n-r -2$
i korzystając z wcześniej udowodnionej zależności $c_{n-k} = c_k$ , otrzymujemy
$c^2_{r+1} = 1+c_rc_{n-r-2} = 1+c_rc_{r+2}$ . Z tego wynika, że $c_{r+1} \geqslant 1$ oraz

$ (3) \qquad \frac{c_{r+2}/c_{r+1}}{c_{r+1}/c_r} = 1-\frac{1}{c_{r+1}^2}\quad \text{dla }1\leqslant r\leqslant n-2. $

Ponadto, jeżeli znamy $c_2$ , to pozostałe wyrazy $c_r$ , dla $r =3,\cdots ,n$ , są wyznaczone jednoznacznie.
Skoro $d \neq c$ , możemy zatem założyć, że $d_2 >c_2$ (przypadek $d_2 <c_2$ jest analogiczny). Uzasadnimy
indukcyjnie, że wtedy $\frac{d_{r+1}}{d_r} > \frac{c_{r+1}}{c_r}$ oraz $d_{r+1} >c_{r+1}$ dla $0 <r<n$ .

Dla $r = 1$ obie nierówności są spełnione, bo $d_1 = c_1 = 1$ . Załóżmy, że nierówności te spełnione są
dla pewnego $r \geqslant 1$ . Wtedy z zależności (3), analogicznej zależności dla ciągu $d$ oraz korzystając
z założenia indukcyjnego, otrzymujemy

$ \frac{d_{r+2}/d_{r+1}}{d_{r+1}/d_r} = 1-\frac{1}{d_{r+1}^2} > 1-\frac{1}{c_{r+1}^2} =\frac{c_{r+2}/c_{r+1}}{c_{r+1}/c_r} $

Stąd i z faktu, że wyrazy ciągu $d$ (poza skrajnymi) są dodatnie, mamy

$ \frac{d_{r+2}}{d_{r+1}}=\frac{d_{r+2}/d_{r+1}}{d_{r+1}/d_r}\cdot\frac{d_{r+1}}{d_r} >\frac{c_{r+2}/c_{r+1}}{c_{r+1}/c_r}\cdot\frac{c_{r+1}}{c_r} > \frac{c_{r+2}}{c_{r+1}} $

oraz $d_{r+2} = \frac{d_{r+2}}{d_{r+1}} \cdot d_{r+1} > \frac{c_{r+2}}{c_{r+1}} \cdot c_{r+1}$ ,
co kończy dowód kroku indukcyjnego.

Uzyskaliśmy $d_{r+1} >c_{r+1}$ dla $0 <r<n$ , ale to prowadzi do sprzeczności, bo $d_n =0= c_n$ .
Zatem istnieje najwyżej jeden ciąg spełniający warunki zadania.

Wobec powyższych rozważań, jedyną możliwą wartością $c_2$ jest
$\frac{\sin(2\pi/n)}{\sin(\pi/n)} = 2 \cos(\pi/n)$ .

Sposób II.

Stosując warunek (1) dla $p = n$ oraz $r = s = t = 0$ otrzymujemy $c_nc_0 + c^2_0 = c_nc_0$ ,
czyli $c_0 = 0$ . Następnie w (1) podstawiamy $t = 0$ oraz $p = s = l \leqslant n/2$ , $r = n - 2l$ .
Otrzymujemy $c_l^2 = c^2_{n-l}$ , czyli $c_l = c_{n-l}$ , gdyż $c_l,c_{n-l} \geqslant 0$ . Z kolei dla
$p = 1, r = k - 2, s = 1, t = n - k$ uzyskujemy tożsamość

$ (4) \qquad 1+ c_kc_{k-2} = c^2_{k -1} \quad \text{dla }k =2, 3, \cdots , n. $

Zatem $c_i \geqslant 1$ dla $i =1, 2,\cdots ,n-1$ . Gdyby zachodziła nierówność $c_2 \geqslant 2$ ,
wówczas prosty argument indukcyjny, oparty na wynikającej z (4) równości
$c_k =\frac{c_{k-1}-1}{c_{k-2}}(c_{k-1} + 1)$ , pokazałby, że $c_k \geqslant c_{k-1} +1$ dla
$k =1, 2,\cdots ,n$ , czyli ciąg $(c_k)$ byłby rosnący, co przeczy temu, że $c_0 = c_n$ . Zatem
$c_2 < 2$ . Z warunku (4) płynie jeszcze jeden wniosek: Skoro $c_0 = 0$ , $c_1 = 1$ oraz $c_i \geqslant 1$
dla $i =1, 2,\cdots ,n -1$ , zatem jeżeli ustalimy liczbę $c_2$ , to warunek (4) jednoznacznie wyznacza
pozostałe wyrazy ciągu.

Narysujmy na płaszczyźnie trójkąt $A_0A_1A_2$ o bokach $A_0A_1 = 1$ , $A_1A_2 = 1$ oraz $A_0A_2 = c_2$ .
Taki trójkąt istnieje, gdyż $|1 - 1| =0 <c_2 < 2 = 1 + 1$ . Opiszmy na nim okrąg o o środku $O$ i rozważmy
punkty $A_3,A_4,\cdots ,A_n$ leżące na okręgu o takie, że kąty skierowane $\measuredangle A_iOA_{i+1}$
są równe. Wykażemy indukcyjnie, że $c_k = A_0A_k$ dla $k =0, 1,\cdots ,n$ . Dla $k =0, 1, 2$ teza zachodzi.
Załóżmy, że zachodzi ona dla każdego $l \leqslant k$ . Jeżeli czworokąt $A_0A_1A_{k-1}A_k$ jest wypukły, to
stosując twierdzenie Ptolemeusza dostajemy
$A_0A_1 \cdot A_{k-1}A_k + A_0A_k \cdot A_1A_{k-1} = A_0A_{k-1} \cdot A_1A_k$ , czyli
$1 + A_0A_k \cdot c_{k-2} = c^2_{k-1}$ . Równość ta zachodzi również wtedy, gdy czworokąt
$A_0A_1A_{k-1}Ak$ jest zdegenerowany i $A_k = A_0$ . Zatem gdy czworokąty $ A_0A_1A_2A_3, A_0A_1A_3A_4, \cdots , A_0A_1A_{k-1}A_k$ są wypukłe (lub zdegenerowane) to $c_k = A_0A_k$ .

Rozważmy dwa przypadki ze względu na miarę kąta A_0OA_1.

Jeśli $\measuredangle A_0OA_1 \leqslant 2\pi/n$ , to czworokąt $A_0A_1A_{k-1}A_k$ jest wypukły dla
każdego $k \in\{3, 4,\cdots ,n\}$ (lub $A_k = A_0$ , gdy $k = n$ oraz $\measuredangle A_0OA_1 =2\pi/n$ )
i wtedy $c_k = A_0A_k$ dla $k =0, 1, 2,\cdots ,n$ . Jednocześnie $0 = c_0 = c_n = A_0A_n$ , czyli
$A_0 = A_n$ , co oznacza, że $\measuredangle A_0OA_1 =2\pi/n$ , a zatem $c_2$ jest długością najkrótszej
przekątnej w $n$ –kącie foremnym.
Jeśli $\measuredangle A_0OA_1 > 2\pi/n$ , to dla pewnego $m \in\{1, 2,\cdots ,n -1\}$ punkt
$A_0$ znajduje się wewnątrz kąta $A_mOA_{m+1}$ lub $A_0 = A_m$ . W obydwu tych wypadkach $A_0A_m < 1$ .
Wybierzmy najmniejsze takie $m$ . Wówczas dla $k \leqslant m$ odpowiednie czworokąty $A_0A_1A_{k-1}A_k$
są wypukłe, zatem $A_0A_m = c_m \geqslant 1$ . Otrzymana sprzeczność dowodzi, że ten przypadek nie zachodzi.

Podsumowując, dla ustalonego $n$ , jeżeli istnieje ciąg spełniający warunki zadania, to jest tylko jeden
i wyraża się wzorem $c_k = A_0A_k$ dla $k =0, 1,\cdots ,n$ , gdzie $A_0,A_1,\cdots ,A_{n-1}$ są wierzchołkami
$n$ –kąta foremnego o boku 1. Pozostaje sprawdzić, że tak zdefiniowany ciąg spełnia zależność (1).

Jeżeli liczby całkowite $p, r, s, t$ są dodatnie i $p + r + s + t = n$ , to z twierdzenia Ptolemeusza dla
czworokąta $A_0A_pA_{p+r}A_{p+r+s}$ , który jest wpisany w okrąg opisany na rozważanym $n$ –kącie, otrzymujemy

$ A_0A_p \cdot A_{p+r}A_{p+r+s} + A_pA_{p+r} \cdot A_0A_{p+r+s} = A_0A_{p+r} \cdot A_pA_{p+r+s}, $

a stąd, ponieważ $n$ –kąt jest foremny,

$ (5) \qquad A_0A_p \cdot A_0A_s + A_0A_r \cdot A_0A_t = A_0A_{p+r} \cdot A_0A_{r+s}, $

czyli warunek (1) jest spełniony dla dodatnich $p, r, s, t$ . Łatwo sprawdzić, że zależność (5) jest
prawdziwa również w przypadku, gdy przynajmniej jedna z liczb $p, r, s, t$ jest równa 0. Ponadto każdy wyraz
$c_k = A_0A_k$ jest nieujemny, zatem rozważany ciąg spełnia założenia zadania.

Z powyższych rozważań wynika, że $c_2$ jest długością najkrótszej przekątnej w $n$ –kącie foremnym
o boku 1, czyli $c_2 = 2 \cos(\pi/n)$ .