LX OM

LX Olimpiada Matematyczna

Załącznik	Wielkość
Informacja o przebiegu LX Olimpiady Matematycznej [1]	135.67 KB
Sprawozdanie Komitetu Głównego [2]	600.49 KB

LX OM - I etap

I etap LX Olimpiady Matematycznej

Załącznik	Wielkość
LX OM I etap - Zadania [3]	100.33 KB
LX OM I etap - Zadania z rozwiązaniami [4]	218.46 KB

LX OM - I - Zadanie 1

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Na niektórych polach szachownicy rozmiaru $m\times n$ ustawiono wieże.
Wiadomo, że dowolna wieża znajduje się w polu rażenia co najwyżej
dwóch innych wież.

Wyznaczyć, w zależności od $m, n \geq 2$ , największą liczbę wież na szachownicy,
dla której taka sytuacja jest możliwa.

Rozwiązanie

Odpowiedź: $m+n$ wież.

Udowodnimy najpierw, że na prostokątnej szachownicy $m\times n$ $(m, n \geqslant 1)$ można ustawić
najwyżej $m+n$ wież tak, by każda wieża znajdowała się w polu rażenia nie więcej niż dwóch innych.
Dowód przeprowadzimy na trzy sposoby.

Sposób I

Nazwijmy wiersz związanym, jeżeli w wierszu tym ustawiona jest wieża $w$ znajdująca się w polu rażenia
dwóch innych wież stojących w tej samej kolumnie, co wieża $w$ . Analogicznie kolumną związaną nazywamy kolumnę,
która zawiera wieżę będącą w polu rażenia dwóch wież z tego samego wiersza.

Z warunków zadania wynika, że każda związana linia (wiersz lub kolumna) zawiera dokładnie jedną wieżę.
Niech $s$ i $t$ oznaczają odpowiednio liczbę wierszy i kolumn związanych. Wówczas liczba wszystkich wież
znajdujących się w związanych liniach nie przekracza $s+t$ .

Z drugiej strony, weźmy pod uwagę zbiór pól szachownicy nie znajdujących się w żadnej związanej linii.
Pola takie nazwijmy niezwiązanymi. Z określenia kolumn związanych wynika, że w każdym wierszu najwyżej dwie
wieże rozmieszczone są na polach niezwiązanych — mogą to bowiem być tylko „skrajne” wieże stojące w tym wierszu.
Ponadto wszystkie pola niezwiązane zawarte są w $m - s$ niezwiązanych wierszach. Zatem liczba wież znajdujących
się na niezwiązanych polach jest nie większa niż $2(m - s)$ . Podobnie uzasadniamy, że liczba tych wież nie
przekracza $2(n -t)$ .

Korzystając z nierówności $2\cdot\min\{x,y\}\leq x+y$ stwierdzamy ostatecznie, że liczba wszystkich
wież na szachownicy jest nie większa niż

$ s+t+2\cdot\min\{m-s,n-t\}\leq s+ t+(m -s)+(n-t)= m+n. $

Sposób II

Weźmy pod uwagę odcinki brzegowe, czyli boki pól danej szachownicy zawarte w jej brzegu.
Liczba odcinków brzegowych jest równa $2(m+n)$ .

Wieża stojąca na szachownicy wyznacza cztery odcinki brzegowe: dwa na górnym i dolnym końcu zajętej
przez nią kolumny oraz dwa na lewym i prawym końcu zajętego przez nią wiersza. Odcinek brzegowy wyznaczony
przez wieżę znajduje się w polu rażenia tej wieży, jeżeli w linii (pionowej bądź poziomej) pomiędzy
wieżą a odcinkiem nie znajduje się żadna inna wieża.

Odcinek brzegowy wyznacza jednoznacznie linię (wiersz albo kolumnę), w którym musi stać wieża mająca
ten odcinek w polu rażenia. Jeżeli w linii tej stoją przynajmniej dwie wieże, dany odcinek znajduje się
w polu rażenia tylko jednej z nich, a mianowicie wieży najbliższej odcinkowi. Każdy odcinek brzegowy
szachownicy znajduje się więc w polu rażenia najwyżej jednej wieży.

Z drugiej strony, zgodnie z warunkami zadania każda wieża znajduje się w polu rażenia najwyżej
dwóch innych wież. Oznacza to, że w polu rażenia dowolnej wieży znajdują się przynajmniej dwa odcinki
brzegowe. Jak wykazaliśmy wcześniej, odcinki znajdujące się w polu rażenia różnych wież są różne.
Ponieważ zaś liczba odcinków brzegowych wynosi $2(m+n)$ , liczba wież na szachownicy nie może przekraczać $m+n$ .

Sposób III

Tym razem zastosujemy indukcję ze względu na wielkość sumy $m+n$ .

Jeżeli przynajmniej jedna z liczb $m, n$ jest równa 1, to rozpatrywana teza jest prawdziwa,
gdyż liczba wszystkich pól szachownicy wynosi wówczas $m+n-1$ i tym bardziej liczba wież nie może
przekraczać $m+n-1$ .

Weźmy teraz pod uwagę szachownicę rozmiaru $m \times n$ (gdzie $m, n \geq 2$ ) z $t$ wieżami
rozmieszczonymi zgodnie z warunkami zadania.

Przypuśćmy najpierw, że w pewnym wierszu znajdują się przynajmniej trzy wieże. W wierszu tym znajdują
się zatem dwie wieże skrajne oraz co najmniej jedna wieża środkowa. Niech w oznacza jedną
z wież środkowych. Wieża $w$ znajduje się wówczas w polu rażenia dwóch wież stojących w
tym samym wierszu, co oznacza, że w kolumnie $K$ zajętej przez wieżę w nie mogą stać żadne inne wieże.
Wykreślając z szachownicy kolumnę $K$ otrzymujemy szachownicę rozmiaru $m\times (n-1)$ z $t-1$ wieżami
spełniającymi dany w treści zadania warunek. Na mocy założenia indukcyjnego mamy więc

$ t-1 \leq m+(n-1) = m+n-1. $

To daje $t \leq m+n$ , a więc uzyskaliśmy tezę indukcyjną. Podobne rozumowanie przeprowadzamy, gdy istnieje kolumna zawierająca przynajmniej trzy wieże. Pozostaje do rozpatrzenia przypadek, gdy w każdym wierszu i w każdej kolumnie znajdują się najwyżej dwie wieże. Wtedy jednak łączna ich liczba
nie przekracza $2\cdot\min\{m,n\}\leq m+n$ .

Zakończenie

By zakończyć rozwiązanie, należy jeszcze wskazać żądane rozmieszczenie m+n wież na szachownicy rozmiaru
$m\times n$ , gdzie $m, n\geq 2$ . Można je uzyskać stawiając wieże na lewym i górnym brzegu szachownicy
oraz w prawym dolnym rogu (rys. 1).

LX OM - I - Zadanie 2

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Dana jest liczba całkowita $n \geq 2$ . Niech $r_1, r_2, r_3, \cdots, r_{n-1}$ będą odpowiednio
resztami z dzielenia liczb

$ 1, 1+2, 1+2+3, \cdots, 1+2+ \cdots +(n-1) $

przez $n$ . Znaleźć wszystkie takie wartości $n$ , że ciąg $(r_1,r_2,\cdots,r_{n-1})$ jest permutacją
ciągu $(1, 2, \cdots,n-1)$ .

Rozwiązanie

Odpowiedź: $n =2^k$ dla $k =1,2,3,\cdots$ .

Wykażemy najpierw, że potęgi dwójki spełniają warunki zadania.
W tym celu wystarczy udowodnić, że jeżeli $n =2^k$ dla pewnego całkowitego $k \geq 1$ , to reszty
$r_1, r_2, r_3, \cdots, r_n-1$ są parami różne i żadna z nich nie jest równa zeru. Gdyby któraś z
tych reszt, powiedzmy $r_m$ , była równa zeru, to liczba

$ 1+2+\cdots+m = \frac{m(m+1)}{2} $

byłaby podzielna przez $2^kk$ . Zatem dla pewnej wartości $m \in \{1,2, \cdots,2k - 1\}$ iloczyn
$m(m+1)$ byłby podzielny przez $2^{k+1}$ . Lecz jedna z liczb $m$ , $m+1$ jest
parzysta, a druga — nieparzysta. Stąd jedna z nich musiałaby być podzielna przez $2^{k+1}$ ,
wbrew temu, że obie te dodatnie liczby nie przekraczają $2^k$ . Gdyby z kolei dwie z rozważanych
reszt były równe — powiedzmy $r_l = r_m$ , gdzie $1 \leq l< m \leq n-1$ , wówczas liczba

$ (1+2+\cdots+m) - (1+2+\cdots+l) = \frac{m(m+1)}{2} - \frac{l(l+1)}{2} = \frac{(m-l)(m+l+1)}{2} $

byłaby podzielna przez $2^k$ , a więc iloczyn $(m -l)(m+l +1)$ byłby podzielny przez $2^{k+1}$ .
Suma tych czynników wynosi $2^{m+1}$ , jest więc liczbą nieparzystą. Tak jak wcześniej wynika stąd,
że jedna z liczb $m - l$ , $m + l + 1$ musi być podzielna przez $2^{k+1}$ . Jednakże liczby $l$ i $m$
są różne, dodatnie i mniejsze od $2^k$ , i podobnie jak poprzednio otrzymujemy sprzeczność.

Aby dokończyć rozwiązanie zadania, wystarczy dowieść, że gdy liczba $n$ ma nieparzysty dzielnik pierwszy $p$ ,
to ciąg $(r_1,r_2,\cdots,r_{n-1})$ nie jest permutacją ciągu $(1,2,\cdots,n - 1)$ . Zauważmy w tym celu, że
dla dowolnej liczby całkowitej dodatniej $t$ liczby

$ 1+2+...+(tp-2)+(tp-1) = \frac{tp(tp-1)}{2}, $

$ 1+2+...+(tp-1)+tp = \frac{tp(tp+1)}{2} $

są podzielne przez p, gdyż nieparzysty czynnik pierwszy p w liczniku nie skraca się z mianownikiem.
W związku z tym reszty

$ r_{p-1},r_p,r_{2p-1},r_{2p},r_{3p-1},r_{3p}, \cdots, r_{n-p-1}, r_{n-p},r_{n-1} $

są podzielne przez p. Zatem w ciągu $(r_1,r_2,\cdots,r_{n-1})$ co
najmniej $2\cdot \frac{n}{p}-1$ liczb jest podzielnych przez $p$ .
W ciągu (1,2, \cdots,n-1) występuje zaś jedynie $n-1$ liczb podzielnych
przez $p$ . Tak więc liczba $n$ nie ma żądanej własności

LX OM - I - Zadanie 3

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Okrąg wpisany w trójkąt $ABC$ jest styczny do boków $BC$ , $CA$ , $AB$ odpowiednio w punktach
$D$ , $E$ , $F$ . Punkty $M$ , $N$ , $J$ są odpowiednio środkami okręgów wpisanych w trójkąty
$AEF$ , $BDF$ , $DEF$ . Dowieść, że punkty $F$ i $J$ są symetryczne względem prostej $MN$ .

Rozwiązanie

Udowodnimy najpierw, że punkty $M$ i $N$ są odpowiednio środkami krótszych łuków $FE$ i $FD$
okręgu wpisanego w trójkąt $ABC$ .

Rzeczywiście, niech $M'$ będzie środkiem krótszego łuku $FE$ tego
okręgu. Prosta $AC$ jest doń styczna w punkcie $E$ , zatem (rys. 2)

$ (1) \qquad \measuredangle AEM' = \measuredangle EFM' . $

Ponieważ punkt $M'$ jest środkiem łuku $EF$ , więc trójkąt
$EM'F$ jest równoramienny. Wobec tego $\measuredangle EFM' = \measuredangle FEM'$ , co wraz
z równością (1) dowodzi, że punkt $M'$ leży na dwusiecznej kąta $\measuredangle AEF$ . Analogicznie dowodzimy,
iż punkt ten leży na dwusiecznej kąta $\measuredangle AFE$ , więc pokrywa się on
ze środkiem $M$ okręgu wpisanego w trójkąt $AEF$ . Podobnie rozumujemy
dla punktu $N$ .

Okrąg wpisany w trójkąt $ABC$ jest jednocześnie okręgiem opisanym
na trójkącie $DEF$ . Skoro $M$ jest środkiem krótszego łuku $EF$ tego
okręgu, prosta $DM$ zawiera dwusieczną kąta $\measuredangle EDF$ . Na tej prostej
leży więc punkt $J$ , który jest środkiem okręgu wpisanego w ten kąt.
Analogicznie dochodzimy do wniosku, że punkt $J$ leży na prostej $EN$ .

Aby uzasadnić, że punkty $J$ i $F$ są symetryczne względem prostej
$MN$ , wystarczy wykazać, iż trójkąty $MFN$ oraz $MJN$ są przystające,
gdyż będzie to oznaczało, że są one symetryczne względem prostej $MN$ .
Mamy jednak

$ \measuredangle JMN = \measuredangle DMN = \measuredangle FMN, $

gdzie druga równość wynika z tego, że $N$ jest środkiem łuku $FD$ .
Podobnie dostajemy $\measuredangle JNM =\measuredangle FNM$ . Trójkąty $MFN$ i $MJN$ mają więc
równe odpowiednie kąty oraz wspólny bok $MN$ , zatem są przystające
(cecha kąt-bok-kąt). Kończy to rozwiązanie zadania.

LX OM - I - Zadanie 4

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Udowodnić, że dla dowolnych nieujemnych liczb rzeczywistych
$a$ , $b$ , $c$ prawdziwa jest nierówność

$4(\sqrt{a^3b^3} + \sqrt{b^3c^3} + \sqrt{c^3a^3}) \leqslant 4c^3 +(a+b)^3.$

Rozwiązanie

Korzystając z nierówności $x+y \geqslant 2xy$ prawdziwej dla
dowolnych liczb nieujemnych $x$ , $y$ otrzymujemy

$ (a+b)^3 = a^3 + b^3 +3ab(a+b) \geqslant a^3 + b^3 + 3ab\cdot2\sqrt{ab} = a^3 + b^3 +6\sqrt{a^3b^3}. $

Wobec tego teza zadania wynika z następującego rachunku:

$ \begin{split} 4c^3 +(a+b)^3 &- 4(\sqrt{a^3b^3} + \sqrt{b^3c^3} + \sqrt{c^3a^3}) \geqslant \\ & 4c^3 + a^3 + b^3 +6\sqrt{a^3b^3} - 4(\sqrt{a^3b^3} + \sqrt{b^3c^3} + \sqrt{c^3a^3}) \\ & =4c^3 + a^3 + b^3 +2\sqrt{a^3b^3} -4\sqrt{b^3c^3} - 4\sqrt{c^3a^3} \\ & = (2\sqrt{c^3} - \sqrt{a^3} - \sqrt{b^3})^2 \geqslant 0. \end{split} $

LX OM - I - Zadanie 5

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Dla każdej liczby całkowitej $n \geqslant 1$ wyznaczyć największą
możliwą liczbę różnych podzbiorów zbioru $\{1,2,3, \cdots,n\}$ o
następującej własności: Dowolne dwa z tych podzbiorów są rozłączne
lub jeden z nich zawiera się w drugim.

Rozwiązanie

Odpowiedź: $2n$ podzbiorów.

Oznaczmy szukaną liczbę podzbiorów przez $a_n$ .

Nietrudno spostrzec, że dla $n =1,2,3,\cdots$ następujące $2n$
podzbiorów zbioru $\{1,2,3, \cdots,n\}$ ma daną w treści zadania własność:

$ \emptyset, \{1\}, \{2\}, \{3\}, \cdots, \{n\}, \{1,2\}, \{1,2,3\}, \cdots, \{1,2,3, \cdots,n\}. $

Rzeczywiście, dowolny z pierwszych $n+1$ zbiorów ma najwyżej jeden
element, zatem zawiera się w każdym zbiorze, z którym nie jest
rozłączny. Natomiast dla dowolnych dwóch spośród pozostałych
$n - 1$ zbiorów ten zbiór, który w powyższym ciągu jest wypisany
wcześniej, zawiera się w drugim zbiorze.

Udowodniliśmy w ten sposób, że

$ (1) a_n \geqslant 2n \text{ dla } n=1,2,3,\cdots. $

Z drugiej strony, niech $B_1, B_2, \cdots, B_t$ będą różnymi
podzbiorami zbioru $\{1, 2, \cdots,m\}$ o własności opisanej w treści
zadania. Jeżeli wśród wypisanych podzbiorów nie występuje zbiór
$\{1,2, \cdots,m\}$ , to możemy go dopisać zwiększając o $1$ liczbę tych
podzbiorów i nie naruszając prawdziwości postulowanego warunku.
Przyjmijmy więc, że $B_t = \{1,2, \cdots,m\}$ .

Spośród zbiorów $B_1, B_2, \cdots, B_{t-1}$ wybierzmy ten, który
ma najwięcej elementów. Dla ustalenia uwagi niech będzie to $B_1$
i niech $d$ oznacza liczbę jego elementów. Wówczas $d<n$ .
Ponadto równość $d = 0$ oznacza, że $B_1$ jest zbiorem pustym, co
z uwagi na wybór zbioru $B_1$ jest możliwe jedynie wtedy, gdy
$t = 2$ . W dalszej części rozumowania przyjmujemy więc, że $0<d<n$ .

Na mocy określenia zbioru $B_1$ każdy ze zbiorów
$B_i$ ( $i=1,2,\cdots,t - 1)$ albo jest podzbiorem zbioru $B_1$ ,
albo też jest z nim rozłączny. Dokonując przenumerowania możemy
założyć, iż zbiory $B_1, B_2, \cdots, B_r$ są podzbiorami zbioru
$B_1$ , natomiast zbiory $B_{r+1}, B_{r+2}, \cdots, B_{t-1}$ są
rozłączne z $B_1$ .

Zbiory $B_1, B_2, \cdots, B_r$ są różnymi podzbiorami
$d$ -elementowego zbioru $B_1$ , z których dowolne dwa albo są
rozłączne, albo jeden zawiera się w drugim. Wynika stąd nierówność
$r\leqslant a_d$ . Wśród $t-r-1$ zbiorów
$B_{r+1}, B_{r+2}, \cdots, B_{t-1}$ dowolne dwa albo są rozłączne,
albo jeden zawiera się w drugim, przy czym są one podzbiorami
$(m-d)$ -elementowego zbioru ${1, 2, \cdots,m}\setminus B_1$ ,
a ponadto nie występuje wśród nich zbiór pusty, jest on bowiem
podzbiorem $B_1$ . Stąd otrzymujemy
$t-r -1 \leqslant a_{m-d} -1$ i w konsekwencji

$ t = r +(t-r -1)+1 \leqslant a_d +(a_{m-d} -1)+1 = a_d +a_{m-d}. $

Skutkiem tego liczba podzbiorów zbioru $\{1,2, \cdots,m\}$
o żądanej własności nie przekracza liczby $a_d +a_{m-d}$ .

Wykazaliśmy zatem, że $a_m$ nie przekracza największej z liczb

$ a_d +a_{m-d} \text{ dla } d =1,2, \cdots,m-1. $

Jeżeli więc w nierówności (1) równość ma miejsce dla
$n =1, 2, \cdots,m - 1$ , to ma ona miejsce również dla $n = m$ .
Skoro dla $n = 1$ nierówność (1) staje się równością, stosując
indukcję stwierdzamy ostatecznie, że $a_n =2n$ dla $n =1,2,3, \cdots$ .

LX OM - I - Zadanie 6

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Dany jest trójkąt $ABC$ , w którym $AB = AC$ . Na półprostych
$AB$ i $AC$ obrano odpowiednio takie punkty $K$ i $L$ leżące poza bokami
trójkąta, że

$ (1)\qquad 4\cdot BK \cdot CL = BC^2. $

Punkt $M$ jest środkiem boku $BC$ . Proste $KM$ i $LM$ przecinają
po raz drugi okrąg opisany na trójkącie $AKL$ odpowiednio
w punktach $P$ i $Q$ . Wykazać, że proste $PQ$ i $BC$ są równoległe.

Rozwiązanie

Na mocy zależności (1) mamy (rys. 3)

$ (2) \qquad \frac{BM}{BK} = \frac{BC}{2\cdot BK} = \frac{2\cdot CL}{BC} = \frac{CL}{CM} $

Ponadto z założeń zadania wynika, że trójkąt $BAC$ jest
równoramienny, skąd uzyskujemy równość kątów $\measuredangle KBM =\measuredangle MCL$ .
Wraz z warunkiem (2) oznacza to, że trójkąty $KBM$ i $MCL$ są
podobne (cecha bok-kąt-bok). Korzystając z tego podobieństwa
otrzymujemy

$ (3) \qquad \measuredangle KML=180^{\circ}-\measuredangle BMK-\measuredangle LMC =180?-\measuredangle BMK-\measuredangle MKB =\measuredangle KBM $

oraz

$ (4) \qquad \frac{KM}{ML} = \frac{KB}{MC} = \frac{KB}{BM} $

Zależności (3) i (4) dowodzą, że trójkąty $KML$ i $KBM$ są podobne
(cecha bok-kąt-bok), co implikuje równość

$ (5) \qquad \measuredangle BMK = \measuredangle MLK. $

Z drugiej strony równość kątów wpisanych opartych na tym samym
łuku daje

$ (6) \qquad \measuredangle MLK = \measuredangle QLK = \measuredangle QPK. $

Łącząc zależności (5) i (6) stwierdzamy, że $\measuredangle BMK = \measuredangle QPK$ ,
skąd wprost wynika równoległość prostych $BC$ i $PQ$ .

LX OM - I - Zadanie 7

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Ciąg liczb całkowitych $f_0, f_1, f_2, \cdots$ jest określony
przez warunki: $f_0 = 0, f_1 = 1$ ,

$ (1) \qquad f_n = f_{n-1} + f_{n-2} \text{ dla } n =2,3,4, \cdots. $

Znaleźć wszystkie wielomiany W o współczynnikach całkowitych,
mające następującą własność: Dla każdego $n =0, 1, 2, \cdots$
istnieje taka liczba całkowita $k$ , że $W(k)= f_n$ .

Rozwiązanie

Odpowiedź: $W(x)= \varepsilon x+c$ , gdzie $\varepsilon \in \{-1,1\}$
oraz $c$ jest liczbą całkowitą.

Skorzystamy wielokrotnie z następującego faktu: jeżeli $F$
jest wielomianem o współczynnikach całkowitych, to dla dowolnych
różnych liczb całkowitych $u, v$ spełniona jest podzielność
$u-v|F(u)-F (v)$ .

Dla dowodu tego faktu wystarczy zauważyć, że jeżeli $F(x)$
jest sumą jednomianów postaci $a_mx^m$ , gdzie współczynniki
$a_m$ są całkowite, to różnica $F(u)-F(v)$ jest sumą wyrażeń
postaci $a_m(u^m - v^m)$ , a każda liczba postaci $u^m -v^m$
jest podzielna przez $u - v$ .

Ponadto będziemy stosować następujące własności ciągu
$f_0, f_1, f_2, \cdots$ :

Liczby $f_1, f_2, f_3, \cdots$ są dodatnie.
Ciąg $f_2, f_3, f_4, \cdots$ jest ściśle rosnący.
Dla $n =2,3,4, \cdots$ zachodzi nierówność
$f_{n-1} \geqslant \frac{1}{2} f_n$ .
Dla $n =4,5,6, \cdots$ zachodzi nierówność
$f_{n+1} < 3f_{n-1}$ .

Rzeczywiście, własność 1. jest oczywista i pociąga za sobą
własność 2., gdyż dla $n \geqslant 3$ mamy $f_{n-2} > 0$ ,
co daje $f_n = f_{n-1} + f_{n-2} > f_{n-1}$ . Wreszcie własności
3. i 4. wynikają z własności 2., na mocy wzoru (1) mamy bowiem
$2f_{n-1} \geqslant f_{n-1} + f_{n-2} = f_n$ dla $n \geqslant 2$
oraz

$ f_{n+1} = f_n +f_{n-1} =2f_{n-1} +f_{n-2} < 2f_{n-1} +f_{n-1} =3f_{n-1} \text{ dla } n \geqslant 4. $

Przechodzimy do zasadniczej części rozwiązania.

Niech $W$ będzie wielomianem spełniającym warunki zadania.
Istnieje więc liczba całkowita $a$ , dla której $W(a)= f_0 = 0$ ,
oraz liczba całkowita $b$ , dla której $W(b)= f_1 = 1$ .
Na podstawie sformułowanego wyżej faktu różnica $W(b)-W(a) = 1$
jest podzielna przez $b-a$ . Stąd wniosek, że $b-a = \pm 1$ , czyli
$b = a+\varepsilon$ , gdzie $\varepsilon \in \{1,-1\}$ . W tej
sytuacji wielomian $P$ określony wzorem

$ (2) \qquad P(x)= W (a+\varepsilon x) $

spełnia zależności $P(0) = W(a)=0$ i
$P(1) = W (a+\varepsilon)= W(b) = 1$ . Nietrudno ponadto spostrzec,
że zbiory wartości wielomianów $W$ i $P$ przyjmowanych dla
całkowitych argumentów są równe. Innymi słowy, dla każdego
$n =0,1,2, \cdots$ istnieje taka liczba całkowita $k$ , że $P(k)= f_n$ .

Niech $d$ i $e$ będą takimi liczbami całkowitymi, że
$P(d)= f_3 = 2$ oraz $P(e)= f_4 = 3$ . Wówczas

$ d-1|P(d)-P (1) = 2-1=1, \text{ skąd } d \in \{0,2\}; $

wartość $d = 0$ wykluczamy, gdyż $P(0) = 0 \neq 2$ . Zatem $d = 2$ ;
podobnie

$ e-2|P (e)-P(2) = 3-2=1, \text{ skąd } e \in\{1,3\} $

i w efekcie $e = 3$ . Doszliśmy w ten sposób do wniosku, że

$ (3) \qquad P(k)= k \text{ dla } k =0,1,2,3. $

Wykażemy przez indukcję, że

$ (4) \qquad P(f_n)= f_n \text{ dla } n =0,1,2, \cdots. $

Prawdziwość związku (4) dla $n \leqslant 4$ wynika wprost z
relacji (3). Przyjmijmy z kolei, iż równość (4) jest spełniona
dla $n =0,1, \cdots,m$ , gdzie $m \geqslant 4$ ; należy dowieść,
że $P(f_{m+1})= f_{m+1}$ .

Na podstawie założeń zadania istnieje liczba całkowita $k$ ,
dla której $P(k)= f_{m+1}$ . Przypuśćmy najpierw, że
$k < f_{m-1}$ ; na mocy własności 3. uzasadnionej na początku rozwiązania oraz
nierówności $m-1 > 2$ mamy wtedy

$ f_m - k >f_m - f_{m-1} = f_{m-2} \geqslant \frac{1}{2} f_{m-1}, $

a ponadto ma miejsce podzielność

$ f_m -k |P(f_m)-P(k)= f_m-f_{m+1} = -f_{m-1}. $

Liczba $f_m -k$ jest więc dzielnikiem liczby $f_{m-1}$ większym
od jej połowy, co implikuje równość $f_m - k = f_{m-1}$ . Wówczas
jednak $k = f_m - f_{m-1} = f_{m-2}$ , co nie jest możliwe, gdyż
założenie indukcyjne orzeka, że $P(f_{m-2})= f_{m-2}$ , natomiast
$P(k)= f_{m+1}$ .

Udowodniliśmy tym samym, że $k \geqslant f_{m-1}$ . Ponieważ
na mocy własności 4. oraz warunku $m \geqslant 4$ dostajemy

$ f_{m+1} = f_m +f_{m-1} =2f_{m-1} +f_{m-2} < 3f_{m-1}, $

więc nierówność $k \geqslant f_{m-1}$ pociąga za sobą nierównosć
$k> \frac{1}{3} f_{m+1}$ . Z drugiej strony, spełniona jest podzielność

$ k = k -0|P(k)-P(0) = f_{m+1}-0= f_{m+1}. $

W konsekwencji liczba $k$ jest dzielnikiem liczby $f_{m+1}$
większym od jej jednej trzeciej. Zatem $k = f_{m+1}$ lub
$k = \frac{1}{2} f_{m+1}$ . Pierwszy przypadek prowadzi do wniosku,
że $P(f_{m+1})= f_{m+1}$ , co jest tożsame z tezą indukcyjną.
Natomiast drugi przypadek jest niemożliwy: wynikałoby zeń bowiem,
że $k = 1$ lub

$ k-1= \frac{1}{2} f_{m+1}-1|P(k)-P(1) = f_{m+1}-1 = 2(\frac{1}{2}f_{m+1}-1)+1 = 2(k-1)+1, $

a zatem $k - 1|1$ , czyli $k \leqslant 2$ . W rezultacie
$f_{m+1} =2k \leqslant 4 < f_5$ , co przeczy założeniu $m \geqslant 4$ .

To kończy rozumowanie indukcyjne.

Udowodniona właśnie zależność (4) wraz z własnością 2. pozwala
stwierdzić, że równość $P(x)= x$ zachodzi dla nieskończenie wielu
liczb całkowitych $x$ . Skoro $P$ jest wielomianem, równość ta jest
prawdziwa dla każdej liczby rzeczywistej $x$ . Uwzględniając równość
(2) dostajemy teraz

$ (5)\qquad W(x)= \varepsilon (x-a) $

dla każdej liczby rzeczywistej $x$ , gdzie $\varepsilon \in \{-1,1\}$ oraz $a$
jest liczbą całkowitą. By zakończyć rozwiązanie, pozostaje już
tylko spostrzec, że każdy wielomian postaci (5) ma żądaną własność.

LX OM - I - Zadanie 8

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Przekątne podstawy $ABCD$ ostrosłupa $ABCDS$ przecinają się pod
kątem prostym w punkcie $H$ , będącym spodkiem wysokości ostrosłupa.
Niech $K$ , $L$ , $M$ , $N$ będą rzutami prostokątnymi punktu $H$
odpowiednio na ściany $ABS$ , $BCS$ , $CDS$ , $DAS$ . Dowieść, że proste
$KL$ , $MN$ i $AC$ są równoległe lub przecinają się w jednym punkcie.

Rozwiązanie

Na początku wykażemy, że proste $KL$ i $AC$ leżą w jednej
płaszczyźnie.

Z założeń zadania wynika, że proste $AC$ , $BD$ i $HS$ są
wzajemnie prostopadłe. Oznacza to, że dowolna prosta zawarta
w płaszczyźnie wyznaczonej przez dwie z tych prostych jest
prostopadła do trzeciej. W szczególności prosta $SB$ jest
prostopadła do prostej $AC$ i wobec tego istnieje płaszczyzna
$\pi$ przechodząca przez prostą AC i prostopadła do prostej SB.

Ponieważ prosta SB jest zawarta w płaszczyznach $ABS$ i $BCS$ ,
więc płaszczyzna $\pi$ jest prostopadła do obu tych płaszczyzn.
Wynika stąd, że prosta $HK$ , która jest prostopadła do płaszczyzny
$ABS$ , jest równoległa do płaszczyzny $\pi$ , a wobec relacji
$H \in \pi$ jest w tej płaszczyźnie zawarta. To oznacza, że punkt
$K$ leży w płaszczyźnie $\pi$ . Podobnie uzasadniamy, że $L \in \pi$ .
Zatem proste $KL$ i $AC$ są zawarte w płaszczyźnie $\pi$ (rys. 4).

Niech $G$ oznacza punkt wspólny płaszczyzny $\pi$ i prostej $SB$ .
Wówczas

$ HK \perp AG, HL \perp CG \text{ oraz } GH \perp AC. $

Punkty $K$ i $L$ leżą więc na okręgu o o średnicy $GH$ ,
stycznym do prostej AC.

Zauważmy teraz, że proste $KL$ i $AC$ są równoległe wtedy i
tylko wtedy, gdy $KL \perp GH$ . Ale punkty $K$ i $L$ leżą na okręgu
o średnicy $GH$ , więc warunek $KL \perp GH$ jest równoważny temu,
że trójkąty $GKH$ i $GLH$ są symetryczne względem prostej $GH$ .
To z kolei ma miejsce wtedy i tylko wtedy, gdy $\measuredangle AGH = \measuredangle CGH$ ,
co jest równoznaczne z równoramiennością trójkąta $AGC$ , a więc
z tym, że punkt $H$ jest środkiem odcinka $AC$ .

Przyjmijmy zatem, że punkt $H$ nie jest środkiem odcinka $AC$ .
Dalsza część rozumowania rozgrywa się w płaszczyźnie $\pi$ (rys. 5).
Dokończymy rozwiązanie zadania dwoma sposobami.

Sposób I

Niech $E$ oznacza punkt przecięcia prostych $KL$ i $AC$ . Z
twierdzenia o siecznej i stycznej zastosowanego do okręgu $o$
uzyskujemy wówczas

$ (1) \qquad EH^2 = EK\cdot EL. $

Z drugiej strony, podobieństwo trójkątów prostokątnych
$GKH$ i $GHA$ daje

$ (2) \qquad \frac{GK}{GH} = \frac{GH}{GA}, \text{ czyli } GK\cdot GA = GH^2 $

zaś z podobieństwa trójkątów prostokątnych $GLH$ i $GHC$ dostajemy

$ (3) \qquad \frac{GL}{GH} = \frac{GH}{GC}, \text{ czyli } GL\cdot GC = GH^2. $

Porównując stronami równości (2) i (3) stwierdzamy, że

$ GK \cdot GA = GL \cdot GC. $

To dowodzi, że punkty $A, K, L, C$ leżą na jednym okręgu, co implikuje, że

$ (4) \qquad EK \cdot EL = EA\cdot EC. $

Łącząc teraz zależności (1) i (4) otrzymujemy warunek

$ (5) \qquad EH^2 = EA\cdot EC. $

Punkt $E$ na prostej $AC$ jest określony jednoznacznie przez
równość (5). Wprowadzając bowiem na prostej $AC$ strukturę osi
liczbowej i przyjmując, że punktowi $X$ odpowiada liczba $x$ ,
zapisujemy warunek (5) w postaci

$ (6) \qquad (e-h)^2 =(e-a)(e-c), $

czyli $(a+c-2h)e = ac-h^2$ ; skoro zaś punkt $H$ nie jest środkiem
odcinka $AC$ , mamy $a+c-2h \neq 0$ i w efekcie istnieje dokładnie
jedna liczba rzeczywista $e$ spełniająca równanie (6).

Sposób II

Pozostając przy oznaczeniach rys. 5 oraz stosując twierdzenie
Menelausa (zob. L Olimpiada Matematyczna, Sprawozdanie Komitetu
Głównego, Warszawa 2000, Dodatek H, str. 122) do trójkąta $ACG$
przeciętego prostą przechodzącą przez punkty $E$ , $L$ , $K$
uzyskujemy równość

$ \frac{AE}{EC} = \frac{AK}{KG}\cdot \frac{GL}{LC} = \frac{AK}{KH} \cdot \frac{KH}{KG} \cdot \frac{GL}{LH} \cdot \frac{LH}{LC} $

Ponadto podobieństwo trójkątów prostokątnych $AKH$ , $HKG$ i $AHG$
pozwala wnioskować, że

$ (8) \qquad \frac{AK}{KH} = \frac{KH}{KG} = \frac{AH}{GH} $

zaś podobieństwo trójkątów prostokątnych GLH, HLC i GHC daje GL LH GH

$ (9) \qquad \frac{GL}{LH} = \frac{LH}{LC} = \frac{GH}{CH} $

Łącząc zależności (7), (8) i (9) widzimy, że

$ (10) \qquad \frac{AE}{EC} = \frac{AH}{GH} \cdot \frac{AH}{GH} \cdot \frac{GH}{CH} \cdot \frac{GH}{CH} \left(\frac{AH}{CH}\right)^2 . $

Podobnie jak w sposobie I równość (10) pozwala stwierdzić, że
punkt $E$ na prostej $AC$ jest wyznaczony jednoznacznie.
Odpowiednikiem równania (6) będzie w tym przypadku równanie

$ \frac{e-a}{e-c} = \left(\frac{AH}{CH}\right)^2 $

które ma dokładnie jedno rozwiązanie rzeczywiste $e$ wobec faktu,
że jego prawa strona jest różna od $1$ , jako że punkt $H$ nie jest
środkiem odcinka $AC$ .

Przeprowadzając analogiczne rozumowanie dla prostej $MN$
dochodzimy ostatecznie do następującego wniosku:
Proste $KL$ , $MN$ i $AC$

są równoległe, jeżeli punkt $H$ jest środkiem odcinka $AC$ ;
przecinają się w punkcie $E$ leżącym na prostej $AC$ i
wyznaczonym przez warunek $EH^22 = EA\cdot EC$ (wynikający ze
sposobu I), bądź też przez równoważny warunek

$ \frac{AE}{EC} = \left(\frac{AH}{CH}\right)^2 $

(wynikający ze sposobu II), jeżeli punkt $H$ nie jest środkiem
odcinka $AC$ .

LX OM - I - Zadanie 9

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Dana jest tablica $2008 \times 2008$ . Dwaj gracze na przemian
wykonują ruchy, z których każdy polega na wybraniu białego albo
czarnego pionka i postawieniu go na wybranym wolnym polu. Wygrywa
ten, którego ruch doprowadził do powstania ciągu 5 kolejnych
pionków tego samego koloru w linii pionowej, poziomej lub ukośnej.

Zbadać, czy istnieje strategia dla gracza rozpoczynającego grę
zapewniająca mu zwycięstwo.

Rozwiązanie

Odpowiedź: Nie istnieje.

Wskażemy strategię gry dla gracza nie rozpoczynającego
(zwanego w dalszej części rozwiązania drugim graczem), która
uniemożliwi graczowi rozpoczynającemu (pierwszemu) zwycięstwo.

Strategię tę można opisać następująco: Jeżeli drugi gracz może
wykonać ruch prowadzący do powstania ciągu 5 kolejnych pionków
tego samego koloru w jednej linii, wykonuje on taki ruch i wygrywa
grę. W przeciwnym razie drugi gracz stawia pionek na polu symetrycznym
względem środka szachownicy do pola, które przed chwilą zajął
pierwszy gracz, i w kolorze przeciwnym niż pionek postawiony
właśnie przez pierwszego gracza.

Rozmiary szachownicy są liczbami parzystymi, więc pole
symetryczne względem jej środka do danego pola jest innym polem.
Opisana strategia jest zatem poprawnie określona: po każdym ruchu
drugiego gracza dowolna para pól szachownicy symetrycznych względem
jej środka składa się albo z dwóch wolnych, albo z dwóch zajętych
pól, wobec czego po ruchu pierwszego gracza pole symetryczne do
pola przezeń zajętego jest wolne.

Wykażemy, że nie jest możliwe, by przy takiej strategii drugiego
gracza gracz rozpoczynający mógł odnieść zwycięstwo.

Przypuśćmy przeciwnie, że pewien ruch pierwszego gracza
zapewnił mu zwycięstwo. Rozpatrzmy pozycję na szachownicy przed
wykonaniem tego ruchu. Jak wykazaliśmy, w tej pozycji dowolne
pole jest zajęte przez pionek wtedy i tylko wtedy, gdy pole doń
symetryczne jest zajęte przez pionek przeciwnego koloru. Zatem
układowi 4 pionków jednego koloru $k$ , który pierwszy gracz przez
postawienie pionka na polu $P$ powiększył do wygrywającego układu
5 kolejnych pionków koloru $k$ w jednej linii, odpowiada w tej
pozycji układ 4 pionków koloru $k'$ przeciwnego do $k$ , a przy tym
pole $P'$ symetryczne do pola $P$ jest wolne. Wówczas jednak, zgodnie
z opisaną strategią, ostatni ruch drugiego gracza powinien polegać
na postawieniu na polu $P'$ pionka w kolorze $k'$ , co prowadzi
do powstania ciągu 5 kolejnych pionków koloru $k'$ w jednej linii,
i w konsekwencji do wygranej drugiego gracza — wbrew założeniu,
że zwycięstwo odniósł pierwszy gracz wykonując kolejny ruch.

Uzyskana sprzeczność dowodzi, że przy takiej strategii drugiego
gracza gracz rozpoczynający nie może zapewnić sobie zwycięstwa w grze.

LX OM - I - Zadanie 10

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Punkt $P$ jest środkiem krótszego łuku $BC$ okręgu opisanego na
trój kącie $ABC$ , w którym $\measuredangle BAC =60^{\circ}$ . Punkt $M$ jest środkiem
odcinka łączącego środki dwóch okręgów dopisanych do danego trójkąta,
stycznych odpowiednio do boków $AB$ i $AC$ . Wykazać, że $PM =2\cdot BP$

(Uwaga: Okrąg dopisany do trójkąta to okrąg styczny do jednego
z boków trójkąta oraz do przedłużeń dwóch pozostałych boków.)

Rozwiązanie

Niech $O_1$ i $O_2$ oznaczają środki okręgów dopisanych do
trójkąta $ABC$ stycznych odpowiednio do boków $AC$ i $AB$ , niech $I$
będzie środkiem okręgu wpisanego w trójkąt $ABC$ oraz niech $D$ i $E$
będą odpowiednio punktami, w których proste $BI$ i $CI$ przecinają po
raz drugi okrąg o opisany na trójkącie $ABC$ (rys. 6).

Wówczas zachodzi równość $DI = DC$ (zob. LI Olimpiada Matematyczna,
Sprawozdanie Komitetu Głównego, Warszawa 2001, Dodatek E, str. 113),
zaś z drugiej strony kąt $\measuredangle ICO_11$ jest prosty, gdyż proste $CI$ i
$CO_1$ zawierają dwusieczne kątów odpowiednio wewnętrznego i
zewnętrznego trójkąta $ABC$ przy wierzchołku $C$ . Wynika stąd, że
punkt $D$ jest środkiem okręgu o średnicy $IO_1$ opisanego na
trójkącie prostokątnym $ICO_1$ . W szczególności $ID = DO_1$ .
Podobnie dowodzimy, że $EI = EB$ oraz $IE = EO_2$ .

Niech $M'$ oznacza drugi punkt przecięcia prostej $O_1O_2$
z okręgiem $o$ . (Jeżeli prosta ta jest styczna do okręgu o w punkcie
$A$ , to przyjmujemy $M' = A$ .) Udowodnimy, że punkty $M'$ i $M$
pokrywają się.

Punkty $A, I, P$ leżą na dwusiecznej kąta wewnętrznego trójkąta
$ABC$ przy wierzchołku $A$ , a punkty $O_1, A, M', O_2$ — na
dwusiecznej kąta zewnętrznego przy tym wierzchołku. Dwusieczne te
są prostopadłe, zatem kąt $\measuredangle M'AP$ jest prosty. W efekcie odcinek
$M'P$ jest średnicą okręgu $o$ . (Nietrudno spostrzec, iż stwierdzenie
to zachowuje moc w przypadku, gdy $M' = A$ .)

Punkt $P$ jest środkiem krótszego łuku $BC$ okręgu $o$ , więc
punkt $M'$ jest środkiem dłuższego łuku $BC$ tego okręgu. Ponadto
krótsze łuki $CD$ i $DA$ mają jednakowe długości (z uwagi na to,
że punkt $D$ leży na dwusiecznej kąta $\measuredangle ABC$ ) i analogicznie krótsze
łuki $AE$ i $AB$ mają jednakowe długości. Te cztery łuki okręgu o
tworzą łącznie dłuższy łuk $BC$ , którego środkiem jest punkt $M'$ .
Stąd wniosek, że krótsze łuki $BE$ i $M'D$ mają równe długości oraz
krótsze łuki $CD$ i $M'E$ mają jednakowe długości. W konsekwencji
$M'D = EB = EI$ oraz $M'E = DC = DI$ , czyli czworokąt $EIDM'$ jest
równoległobokiem. Ponieważ punkty $D$ i $E$ są odpowiednio środkami
boków $IO_1$ i $IO_2$ trójkąta $IO_1O_2$ , więc punkt $M'$ jest
środkiem trzeciego boku $O_1O_2$ . Uzyskaliśmy w ten sposób równość
$M' = M$ .

Pozostaje zauważyć, że skoro odcinek $PM$ jest średnicą okręgu $o$ ,
to trójkąt $BPM$ ma kąt prosty przy wierzchołku $B$ ; ponieważ zaś

$ \measuredangle BMP = \measuredangle BAP = \frac{1}{2}\measuredangle BAC = 30? , $

więc trójkąt $BPM$ jest połową trójkąta równobocznego o boku $PM$
i wysokości $MB$ . Stąd bezpośrednio uzyskujemy żądaną równość
$PM =2\cdot BP$ .

LX OM - I - Zadanie 11

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Udowodnić, że dla dowolnych liczb całkowitych
$k>m \geqslant 1$ spełniona jest nierówność

$ \frac{\sqrt[k]{k!}}{\sqrt[m]{m!}} < \frac{k}{m} $

Rozwiązanie

Daną do udowodnienia nierówność możemy przepisać w postaci

$ \frac{\sqrt[k]{k!}}{k} < \frac{\sqrt[m]{m!}}{m}, \quad \text{gdzie } k > m. $

Zatem teza zadania sprowadza się do wykazania, że ciąg $(a_n)$ dany wzorem

$ a_n=\frac{\sqrt[n]{n!}}{n} $

jest ściśle malejący. Innymi słowy, wystarczy dowieść nierówności

$ (1) \qquad \frac{\sqrt[n+1]{(n+1)!}}{n+1} < \frac{\sqrt[n]{n!}}{n} \quad \text{dla } n =1,2,3, \cdots. $

Dalsze rozumowanie przeprowadzimy dwoma sposobami.

Sposób I

Ustalmy liczbę $t =1,2, \cdots,n$ i zastosujmy nierówność pomiędzy średnią arytmetyczną
a średnią geometryczną do następujących $n$ liczb:

$ (2) \qquad \underbrace{\frac{t+1}{n+1}, \frac{t+1}{n+1}, \cdots, \frac{t+1}{n+1}}_{t \text{ liczb}}, \underbrace{\frac{t}{n+1}, \frac{t}{n+1}, \cdots, \frac{t}{n+1}}_{n-t \text{ liczb}} $

Średnia arytmetyczna tych liczb jest równa

$ \frac{1}{n}\left(t\cdot \frac{t+1}{n+1} + (n-t)\cdot \frac{t}{n+1} \right)= \frac{1}{n}\frac{t^2+t+nt-t^2}{n+1} = \frac{t(1+n)}{n(n+1)} = \frac{t}{n}, $

natomiast średnia geometryczna wynosi

$ \sqrt[n]{\left(\frac{t+1}{n+1}\right)^t \left(\frac{t}{n+1}\right)^{n-t}}= \frac{1}{n+1}\sqrt[n]{(t+1)^tt^{n-t}} = \frac{t}{n+1}\sqrt[n]{\frac{(t+1)^t}{t^t}} $

Na podstawie nierówności pomiędzy średnimi uzyskujemy stąd zależności

$ (3) \qquad \frac{t}{n} \geqslant \frac{t}{n+1} \sqrt[n]{\frac{(t+1)^t}{t^t}} \quad \text{dla } t =1,2, \cdots,n. $

Mnożąc stronami wszystkie nierówności (3) dochodzimy do wniosku, że

$ \begin{split} \frac{n!}{n} &= \frac{1}{n}\cdot \frac{2}{n} \cdot\cdots \cdot \frac{n}{n} \\ &\geqslant \frac{1}{n+1} \cdot \frac{2}{n+1} \cdot \cdots \cdot \frac{n}{n+1} \sqrt[n]{\frac{2^1}{1^1}\cdot\frac{3^2}{2^2}\cdot\frac{4^3}{3^3}\cdot \cdots \cdot \frac{(n+1)^n}{n^n}} \\ &= \frac{n!}{(n+1)^n}\cdot \sqrt[n]{\frac{(n+1)^n}{1\cdot 2\cdot 3 \cdot \cdots \cdot n}} \\ &= \frac{(n+1)!}{(n+1)^n\sqrt[n]{n!}} \end{split} $

Wyciągając teraz pierwiastek stopnia $n$ otrzymujemy

$ (4) \qquad \frac{\sqrt[n]{n!}}{n} \geqslant \frac{\sqrt[n]{(n+1)!}}{n+1}\cdot \frac{1}{\sqrt[n^2]{n!}} $

i widzimy, że aby z udowodnionej właśnie nierówności (4) wywnioskować zależność (1), wystarczy sprawdzić, że

$ (5) \qquad \sqrt[n]{(n+1)!} > \sqrt[n+1]{(n+1)!}\cdot \sqrt[n^2]{n!}. $

Podnosząc stronami zależność (5) do potęgi $n^3+n^2$ i wykonując przekształcenia otrzymujemy
następujące jej postaci równoważne:

$ \begin{split} (n+1)!^{n^2+n} &> (n+1)!^{n^2}\cdot (n!)^{n+1},\\ (n+1)!^n &> (n!)^{n+1},\\ (n+1)^n \cdot (n!)^n &> n!\cdot(n!)^n,\\ (n+1)^n &> n!. \end{split} $

Ostatnia nierówność jest spełniona, gdyż jej prawa strona jest iloczynem $n$ liczb
mniejszych od $n+1$ , zaś lewa strona jest iloczynem $n$ liczb równych $n+1$ .
W efekcie uzyskujemy kolejno nierówności (5) i (1), co daje tezę zadania.

Sposób II

Podnosząc stronami dowodzoną nierówność (1) do potęgi $n(n +1)$ uzyskujemy
równoważną nierówność

$ (6) \qquad \frac{(n+1)!^n}{(n!)^{n+1}} < \left(\frac{n+1}{n}\right)^{n(n+1)} $

Lewa strona zależności (6) jest równa

$ \frac{(n!)^n \cdot(n+1)^n}{(n!)^n\cdot n!} = \frac{(n+1)^n}{n!} $

a więc nierówność (6) możemy przepisać w postaci

$ \frac{(n+1)^n}{n!}<\left(\frac{n+1}{n}\right)^{n(n+1)} $

lub równoważnie

$ n!>\frac{n^{n(n+1)}}{(n+1)^{n^2}} $

Wystarczy zatem dowieść nierówności (7) dla $n =1,2,3, \cdots$ . W tym celu
zastosujemy indukcję. Dla $n = 1$ zależność (7) przybiera postać $1 > \frac{1}{2}$
i jest prawdziwa. Aby wykonać krok indukcyjny, należy z nierówności (7) wywnioskować nierówność

$ (8) \qquad (n+1)!>\frac{(n+1)^{(n+1)(n+2)}}{(n+2)^{(n+1)^2}} $

a do tego dostateczne będzie sprawdzenie, że dla $n =1, 2,3, \cdots$ spełniona jest nierówność

$ (9) \qquad n+1 >\frac{(n+1)^{(n+1)(n+2)}}{(n+2)^{(n+1)^2}} \: \frac{n^{n(n+1)}}{(n+1)^{n^2}} =\frac{(n+1)^{2n^2+3n+2}}{(n+2)^{(n+1)^2}\cdot n^{n(n+1)}} $

gdyż wówczas mnożąc stronami zależności (7) i (9) uzyskamy nierówność (8).

Pozostaje więc wykazać prawdziwość zależności (9). W tym celu przekształcamy ją równoważnie w następujący sposób:

$ \begin{split} (n+2)^{(n+1)^2}\cdot n^{n(n+1)} &> (n+1)^{2n^2+3n+1},\\ (n+2)^{(n+1)^2}\cdot n^{n(n+1)} &> (n+1)^{(2n+1)(n+1)},\\ (n+2)^{n+1}\cdot n^n &> (n+1)^{2n+1},\\ \left(\frac{n(n+2)}{(n+1)^2}\right) &> \frac{n+1}{n+2} \end{split} $

Stosując teraz nierówność Bernoulliego (zob. LII Olimpiada Matematyczna, Sprawozdanie Komitetu Głównego, Warszawa 2002, Dodatek A, str. 99) uzyskujemy

$ \left(\frac{n(n+2)}{(n+1)^2}\right)^n = \left( 1-\frac{1}{(n+1)^2}\right)^n \geqslant 1-\frac{n}{(n+1)^2} =\frac{n^2+n+1}{(n+1)^2} $

Aby zatem zakończyć dowód poprzedniej nierówności, wystarczy już tylko sprawdzić, że

$ \frac{n^2+n+1}{(n+1)^2}>\frac{n+1}{n+2}, $

lecz to sprowadza się do prawdziwej zależności

$ (n^2+n+1)(n+2) = n^3+3n^2+3n+2 >n^3+3n^2+3n+1 =(n+1)^3. $

Stąd kolejno wynikają nierówności (9), (7), (6) i (1), co kończy rozwiązanie.

LX OM - I - Zadanie 12

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Dana jest liczba pierwsza $p$ . Po lewej stronie tablicy napisano liczby $1, 2, 3, \cdots, p - 1$ ,
zaś po prawej stronie liczbę $0$ . Wykonujemy ciąg $p - 1$ ruchów, z których każdy przebiega
następująco: Wybieramy jedną z liczb napisanych po lewej stronie tablicy, dodajemy ją do wszystkich
pozostałych liczb na tablicy, po czym wymazujemy wybraną liczbę.

Rozstrzygnąć, dla jakich wartości
$p$ można w kolejnych ruchach wybierać liczby w taki sposób, by liczba pozostała na tablicy po
wykonaniu wszystkich ruchów była podzielna przez p.

Rozwiązanie

Odpowiedź: Dla wszystkich liczb pierwszych p oprócz 2 i 3.

Niech $t_i$ dla $i=1,2, \cdots,p-1$ oznacza początkową wartość tej liczby, która
została wymazana z tablicy w $i$ -tym ruchu. Zatem ciąg $(t_1,t_2,t_3 ...,t_{p-1})$ jest permutacją
ciągu $(1,2,3, \cdots,p-1)$ oraz jednoznacznie określa sposób wyboru zmazywanych liczb w kolejnych ruchach.

Wprowadźmy oznaczenie

$ s_i = t_i +2t_{i-1} +4t_{i-2} + \cdots +2^{i-2}t_2 +2^{i-1}t_1 \quad \text{dla } i=1,2, \cdots,p-1. $

Wykażemy indukcyjnie, że po wykonaniu $i$ -tego ruchu wszystkie liczby na tablicy są większe
o $s_i$ od swych początkowych wartości.

Istotnie: stwierdzenie to jest prawdą dla $i = 1$ , gdyż w pierwszym ruchu wymazano liczbę
$t_1$ , zwiększając uprzednio wszystkie pozostałe liczby o $s_1 = t_1$ . Jeżeli natomiast po
wykonaniu $i$ -tego ruchu wszystkie liczby na tablicy były większe o $s_i$ od początkowych wartości,
to w szczególności liczba początkowo równa $t_{i+1}$ po wykonaniu $i$ -tego ruchu miała wartość
$t_{i+1} + s_i$ . Wobec tego w wyniku $(i+1)$ -szego ruchu dodano do wszystkich pozostałych liczb wielkość
$t_{i+1} + s_i$ . Ponieważ zaś liczby te po $i$ -tym ruchu były większe o $s_i$ od początkowych wartości,
więc po $(i+1)$ -szym ruchu stały się one większe o $t_{i+1}+s_i+s_i$ od swych początkowych wartości.
Pozostaje spostrzec, że

$ \begin{split} t_{i+1}+2s_i &= t_{i+1}+2(t_i +2t_{i-1} +4t_{i-2}+ \cdots +2^{i-2}t_2 +2^{i-1}t_1)=\\ &= t_{i+1} +2t+i +4t_{i-1} +8t_{i-2} + ...+2^{i-1}t_2 +2^it_1 = \\ &= s_{i+1}, \end{split} $

co kończy dowód indukcyjny. Udowodniliśmy tym samym, że po wykonaniu wszystkich $p$ ruchów liczba
pozostała po prawej stronie tablicy wynosi

$ (1) \qquad t_{p-1} +2t_{p-2} +4t_{p-3} + \cdots +2^{p-3}t_2 +2^{p-2}t_1. $

Sprowadziliśmy zatem zadanie do wyznaczenia wszystkich liczb pierwszych $p$ , dla których istnieje taka permutacja
$(t_1,t_2,t_3, \cdots,t_{p-1})$ ciągu $(1,2,3, \cdots,p-1)$ , że liczba (1) jest podzielna przez $p$ .

Bezpośrednio sprawdzamy, że dla $p=2$ i $p=3$ nie jest możliwe otrzymanie liczby podzielnej przez $p$ :
dla $p = 2$ liczba (1) wynosi $1$ , a dla $p = 3$ może ona być równa $1+2\cdot 2=5$ albo $2+2\cdot 1 = 4$ .

Wykażemy, że jeśli $p$ jest liczbą pierwszą większą od $3$ , to dla permutacji

$ (2) \qquad (t_1,t_2,t_3,t_4, \cdots,t_{p-2},t_{p-1})=(p-2,p -1,p-4,p-3, \cdots, 5,6,3,4,2, 1), $

powstałej z ciągu $(1,2,3,4, \cdots,p - 2,p - 1)$ przez zamianę miejsc w parach $(2j-1,2j)$ dla
$j \geqslant 2$ i następnie odwrócenie kolejności, liczba (1) jest podzielna przez $p$ .

Rzeczywiście, dla permutacji (2) liczba (1) ma wartość

$ L =1+2\cdot 2+2^2 \cdot4+2^3 \cdot 3 + 2^4 \cdot 6+2^5 \cdot 5+ \cdots +2^{p-3}(p-1)+2^{p-2}(p-2). $

Dla $j =2,3, \cdots, \frac{1}{}2(p-1)$ prawdziwa jest zależność

$ \begin{split} 2^{2j-2}\cdot 2j +2^{2j-1}(2j -1) &= 2^{2j-2}(2j -1)+2^{2j-1} \cdot 2j +2^{2j-2} -2^{2j-1} =\\ &= 2^{2j-2}(2j -1)+2^{2j-1}\cdot 2j -2^{2j-2}, \end{split} $

z której wynika, że $L = M - N$ , gdzie $M$ jest sumą liczb postaci $2^{i-1}i$ dla
$i =1,2, \cdots,p-1$ , natomiast $N =2^2 +2^4 +2^6 + \cdots +2^{p-3}$ . Korzystając ze wzoru na sumę kolejnych
wyrazów ciągu geometrycznego obliczamy, że

$ \begin{split} M &= (2^0 + ...+2^{p-2})+(2^1 + \cdots +2^{p-2})+ \cdots +(2^{p-3} +2^{p-2})+2^{p-2} = \\ &= 2^0(2^{p-1} -1)+2^1(2^{p-2} -1)+ \cdots+2^{p-3}(2^2 -1)+2^{p-2}(2^1 -1) = \\ &= (p-1)2^{p-1} -(2^0 +2^1 + \cdots +2^{p-3} +2^{p-2})= \\ &= (p-1)2^{p-1} -(2^{p-1} -1) = \\ &= p\cdot 2^{p-1} -2\cdot 2^{p-1} +1 \\ \end{split} $

oraz

$ N=2^2(4^0+4^1+\cdots 4^{\frac{p-7}{2}}+4^{\frac{p-5}{2}}) = 2^2\cdot \frac{4^{\frac{p-3}{2}}}{3} =2^2\cdot \frac{2^{p-3}-1}{3} = \frac{2^{p-1}-4}{3}. $

W efekcie

$ (3) \qquad L=M-N = p\cdot 2^{p-1}+\frac{-6\cdot 2^{p-1}+3-2^{p-1}+4}{3} = p\cdot 2^{p-1} - \frac{7(2^{p-1}-1)}{3}. $

Na mocy małego twierdzenia Fermata (zob. LI Olimpiada Matematyczna, Sprawozdanie Komitetu Głównego,
Warszawa 2001, Dodatek A, str. 102) liczba $2^{p-1} -1$ jest podzielna przez $p$ . Skoro zaś $p$
jest liczbą pierwszą większą od $3$ , ułamek występujący po prawej stronie zależności (3) jest liczbą
podzielną przez $p$ . Zatem prawa strona tej zależności jest liczbą podzielną przez $p$ , co kończy
rozwiązanie zadania.

LX OM - II etap

II etap LX Olimpiady Matematycznej

Załącznik	Wielkość
LX OM II etap - Zadania [5]	70.92 KB
LX OM II etap - Zadania z rozwiązaniami [6]	138.95 KB

LX OM - II - Zadanie 1

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Liczby rzeczywiste $a_1, a_2, \cdots , a_n$ $(n \geqslant 2)$ spełniają warunek
$a_1 \geqslant a_2 \geqslant \cdots \geqslant a_n > 0$ . Udowodnić nierówność

$ a_1a_2 \cdots a_{n-1} +(2a_2 -a_1)(2a_3 -a_2) \cdots (2a_n -a_{n-1}) \geqslant 2a_2a_3 \cdots a_n. $

Rozwiązanie

Zastosujemy indukcję matematyczną ze względu na wartość liczby $n$ .

Dla $n = 2$ teza zadania jest prawdziwa, gdyż obie strony dowodzonej zależności są równe $2a_2$ .

Przechodząc do kroku indukcyjnego rozpatrzmy liczby rzeczywiste
$a_1, a_2, \cdots , a_{n+1}$ , dla których $a_1 \geqslant a_2 \geqslant \cdots \geqslant a_{n+1} >0$ .
Należy udowodnić nierówność

$ (1) \qquad a_1a_2 \cdots a_n +(2a_2 -a_1)(2a_3 -a_2) \cdots (2a_{n+1} -a_n) \geqslant 2a_2a_3 \cdots a_na_{n+1}. $

Wprowadźmy oznaczenia

$ t = a_1 -a_2, \quad K = a_2a_3 \cdots a_n, \quad L = (2a_3 -a_2) \cdots (2a_{n+1} -a_n); $

wówczas lewą stronę zależności (1) możemy zapisać w postaci

$ (2) a_1K +(2a_2 -a_1)L =(a_2 +t)K +(a_2 -t)L = a_2(K +L)+t(K -L). $

Stosując założenie indukcyjne do $n$ liczb $a_2 \geqslant a_3 \geqslant \cdots \geqslant a_{n+1} \geqslant 0$
uzyskujemy

$ \begin{split} K+L &= a_2a_3 \cdots a_n +(2a_3 -a_2)(2a_4 -a_3) \cdots (2a_{n+1} -a_n) \geqslant \geqslant 2a_3 \cdots a_na_{n+1}. \end{split} $

Ponadto dla dowolnych liczb rzeczywistych $x\geqslant y>0$ prawdziwa jest podwójna nierówność
$-x \leqslant -x+2(x-y)= x-2y<x$ , skąd $|x-2y|\leqslant x$ i w konsekwencji

$ |L| = |2a_3 -a_2|\cdot |2a_4 -a_3|\cdot \cdots \cdot|2a_{n+1} -a_n|\leqslant a_2 \cdot a_3 \cdot \cdots \cdot a_n = K. $

Oznacza to, że liczba $K - L$ jest nieujemna. Liczba $t = a_1 - a_2$ jest również nieujemna, zatem
kontynuując zależność (2) i wykorzystując (3) dostajemy

$ a_2(K +L)+t(K -L) \geqslant a_2 \cdot 2a_3 \cdots a_na_{n+1}. $

Otrzymaliśmy prawą stronę nierówności (1), co kończy dowód indukcyjny.

LX OM - II - Zadanie 2

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Dane są takie liczby całkowite $a$ i $b$ , że $a>b> 1$ oraz liczba $ab +1$ jest podzielna przez $a+b$ ,
zaś liczba $ab-1$ jest podzielna przez $a-b$ .

Wykazać, że $a<b\sqrt{3}$ .

Rozwiązanie

Zauważmy najpierw, że

$ (a+b)b-(ab+1) = b^2 -1\quad \text{oraz} \quad (ab-1)-b(a-b)= b^2 -1. $

Zatem z danych w treści zadania podzielności wynika, że liczba $b^2 - 1$ jest podzielna przez
$a+b$ i przez $a-b$ .

Liczby $a$ i $b$ są względnie pierwsze. Jeżeli bowiem $d$ jest ich wspólnym dzielnikiem dodatnim,
to liczby $a + b$ i $ab$ są podzielne przez $d$ ; z drugiej strony, liczba $ab+1$ jest podzielna przez liczbę
$a+b$ podzielną przez $d$ . Zatem liczby $ab$ i $ab+1$ są podzielne przez $d$ , skąd wynika, że $d = 1$ .

Niech $e$ oznacza największy wspólny dzielnik liczb $a+b$ i $a-b$ . Wówczas $e$ jest dzielnikiem sumy
i różnicy tych dwóch liczb, równych odpowiednio $2a$ i $2b$ . Skoro liczby $a$ i $b$ są względnie pierwsze,
otrzymujemy $e = 1$ lub $e = 2$ . Stąd wniosek, że jeśli liczba całkowita jest podzielna przez
$a + b$ i $a - b$ , to dwukrotność tej liczby jest podzielna przez $(a+b)(a-b)= a^2 - b^2$ .

Jak zauważyliśmy wcześniej, liczba $b^2-1$ jest podzielna przez $a+b$ i przez $a-b$ . Oznacza to,
że liczba $2(b^2-1)$ jest podzielna przez $a^2-b^2$ . Ponadto $b>1$ , a więc liczba $2(b^2 -1)$ jest
dodatnia i wobec tego jest nie mniejsza niż $a^2 -b^2$ . Zapisując nierówność
$2(b^2 - 1) \geqslant a^2 -b^2$ w równoważnej postaci $a^2 \leqslant 3b^2 - 2$
widzimy, że $a<3b^2$ , co jest równoznaczne z tezą zadania.

LX OM - II - Zadanie 3

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Rozłączne okręgi $o_1$ i $o_2$ o środkach odpowiednio $I_1$ i $I_2$ są styczne do prostej
$k$ odpowiednio w punktach $A_1$ i $A_2$ oraz leżą po tej samej jej stronie. Punkt $C$ leży na odcinku
$I_1I_2$ , przy czym $\meqsuredangle A_1CA_2 =90^{\circ}$ . Dla $i=1,2$ niech $B_i$ będzie punktem różnym od
$A_i$ , w którym prosta $A_iC$ przecina okrąg $o_i$ . Dowieść, że prosta $B_1B_2$ jest styczna do okręgów
$o_1$ i $o_2$ .

Rozwiązanie

Niech prosta styczna do okręgu $o_1$ w punkcie $B_1$ przecina prostą $A_1A_2$ w punkcie $D$ .
(Punkt przecięcia istnieje, gdyż punkt $C$ nie leży na prostej $A_1I_1$ , a więc odcinek $A_1B_1$
nie jest średnicą okręgu $o_1$ .) Trójkąt $A_1B_1D$ jest wówczas równoramienny, gdyż dwa jego boki
są odcinkami stycznych do okręgu $o_1$ poprowadzonymi z punktu $D$ . Wobec tego prosta
$DI_1$ jako dwusieczna kąta $\measuredangle A_1DB_1$ jest prostopadła do cięciwy $A_1B_1$ ,
a więc równoległa do prostej $CA_2$ .

Udowodnimy, że proste $A_1B_1$ i $DI_2$ są równoległe.

Jeżeli $A_1A_2 || I_1I_2$ , to $A_1A_2 = I_1I_2$ i czworokąt $I_1CA_2D$ jest równoległobokiem.
W takim razie $CI_2 = A_1D$ i czworokąt $CI_2DA_1$ także jest równoległobokiem. W szczególności
więc $A_1B_1 || DI_2$ .

Jeżeli natomiast proste $A_1A_2$ i $I_1I_2$ przecinają się w punkcie $E$ , to stosując dwukrotnie
twierdzenie Talesa do kąta $\measuredangle A_1EI_1$ przeciętego prostymi równoległymi $I_1D$ , $CA_2$
oraz $I_1A_1$ , $I_2A_2$ otrzymujemy

$ \frac{EC}{EI_2}= \frac{EC}{EI_1}\cdot \frac{EI_1}{EI_2} = \frac{EA_2}{ED} \cdot \frac{EA_1}{EA_2} = \frac{EA_1}{ED} $

co w połączeniu z twierdzeniem odwrotnym do twierdzenia Talesa znowu daje zależność $A_1B_1 || DI_2$ .

Wykazana właśnie równoległość wraz z danym w treści zadania warunkiem $\measuredangle A_1CA_2 = 90^{\circ}$
pozwala wnioskować, że proste $DI_2$ i $B_2A_2$ są prostopadłe. Zauważmy teraz, że prosta $DI_2$ przechodzi
przez środek okręgu $o_2$ . W efekcie punkty $B_2$ i $A_2$ są symetryczne względem prostej $DI_2$
(gdyż są końcami cięciwy prostopadłej do tej prostej) oraz proste $DB_2$ i $DA_2$ są symetryczne
względem tej prostej. Skoro zaś prosta $DA_2$ jest styczna do okręgu $o_2$ , to również prosta $DB_2$
jest doń styczna, co kończy rozwiązanie zadania.

LX OM - II - Zadanie 4

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Odcinek $AB$ jest średnicą okręgu o opisanego na czworokącie wypukłym $ABCD$ , którego przekątne
przecinają się w punkcie $E$ . Proste styczne do okręgu o w punktach $C$ i $D$ przecinają się w punkcie
$P$ .

Udowodnić, że $PC = PE$ .

Rozwiązanie

Niech $Q$ będzie punktem przecięcia prostych $AD$ i $BC$ .

Zauważmy najpierw, że na mocy warunków zadania proste $AC$ i $BD$ są wysokościami trójkąta $ABQ$ .
Zatem prosta $QE$ jest jego trzecią wysokością i wobec tego przecina prostą $AB$ w pewnym punkcie $F$
pod kątem prostym.

W trójkącie $ECQ$ kąt przy wierzchołku $C$ jest prosty, a środek $P'$ odcinka $QE$ jest środkiem
przeciwprostokątnej. Stąd uzyskujemy zależności $\measuredangle P'CQ=\measuredangle P'QC =\measuredangle FQB$ .
Ponadto trójkąty prostokątne $ACB$ i $QFB$ mają wspólny kąt ostry przy wierzchołku $B$ ,
zatem ich pozostałe kąty ostre są równe: $\measuredangle FQB = \measuredangle CAB$ .
Udowodniliśmy tym samym, że

$ \measuredangle P'CQ = \measuredangle CAB. $

To oznacza, że prosta $P'C$ jest styczna do okręgu o w punkcie $C$ .

Podobnie dowodzimy, że prosta $P'D$ jest styczna do okręgu o w punkcie $D$ .
Stąd i z określenia punktu $P$ wynika, że $P'=P$ . Innymi słowy, punkt $P$ jest środkiem przeciwprostokątnej
w trójkącie prostokątnym $ECQ$ , skąd natychmiast wynika żądana równość $PC = PE$ .

LX OM - II - Zadanie 5

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Wyznaczyć wszystkie liczby całkowite $n\geqslant 4$ o następującej własności: Spośród dowolnych $n$
różnych 3-elementowych podzbiorów zbioru $n$ -elementowego można wybrać dwa podzbiory, które mają dokładnie
jeden element wspólny.

Rozwiązanie

Niech $A_1, A_2, \cdots , A_k$ będą różnymi 3-elementowymi podzbiorami ustalonego zbioru $n$ -elementowego.
Przypuśćmy ponadto, że dowolne dwa z tych zbiorów albo są rozłączne, albo mają dokładnie dwa wspólne elementy.

Oznaczmy $\mathcal{A} = \{A_1,A_2, \cdots ,Ak\}$ i wprowadźmy następujące oznaczenie:
$X\sim Y$ wtedy i tylko wtedy, gdy przekrój $X\cap Y$ jest zbiorem niepustym (a więc mającym co najmniej
2 elementy),

dla (niekoniecznie różnych) zbiorów $X,Y \in \mathcal{A}$ .

Dla dowolnych zbiorów $X,Y,Z \in \mathcal{A}$ zachodzą następujące własności:

$X \sim X$ ;
jeżeli $X \sim Y$ , to $Y \sim X$ ;
jeżeli $X \sim Y$ oraz $Y \sim Z$ , to $X \sim Z$ .

Istotnie, własności 1) i 2) są oczywiste, a by uzasadnić własność 3), wystarczy spostrzec, że z faktu,
iż zbiory $X, Y , Z$ mają 3 elementy, a przekroje $X \cap Y$ i $Y \cap Z$ mają przynajmniej 2 elementy, wynika,
iż przekrój $X \cap Z$ jest zbiorem niepustym. Na mocy przyjętego na początku rozwiązania założenia przekrój ten
zawiera zatem przynajmniej 2 elementy, co oznacza, że $X \sim Z$ .

Własności 1)—3) dowodzą, że zbiory $A_1, A_2, \cdots , A_k$ można podzielić na parami rozłączne
klasy równoważności w taki sposób, by dowolne dwa zbiory $X, Y$ należące do tej samej klasy spełniały
relację $X \sim Y$ , natomiast dowolne dwa zbiory należące do różnych klas tej relacji nie spełniały.

Niech $\mathcal{B}_1, \mathcal{B}_2, \cdots , \mathcal{B}_m$ będą tak zadanymi klasami równoważności oraz niech
$C_i$ $(i =1,2, \cdots ,m)$ będzie sumą wszystkich zbiorów należących do klasy \mathcal{B}_i. Wówczas zbiory
$C_1, C_2, \cdots , C_m$ są parami rozłączne, bowiem zbiory należące do różnych klas są rozłączne.
Ponadto każdy z tych zbiorów zawiera przynajmniej 3 elementy, gdyż jest sumą zbiorów 3-elementowych.

Dla każdego zbioru $C_i$ rozpatrzmy następujące trzy możliwości:

Zbiór $C_i$ ma dokładnie 3 elementy.
Zbiór $C_i$ ma dokładnie 4 elementy.
Zbiór $C_i$ ma przynajmniej 5 elementów.

W przypadku 1. rodzina $\mathcal{B}_i$ składa się z jednego zbioru, mianowicie z tego zbioru
$A_j$ $(j =1,2, \cdots ,k)$ , który jest równy zbiorowi $C_i$ .

W przypadku 2. każdy zbiór należący do rodziny $\mathcal{B}_i$ jest 3-elementowym podzbiorem 4-elementowego
zbioru $C_i$ . Zatem w rodzinie tej znajdują się najwyżej 4 zbiory.

Rozpatrzmy z kolei przypadek 3.. Wybierzmy różne zbiory $X,Y \in \mathcal{B}_i$ . Są to zbiory 3-elementowe,
których przekrój $X\cap Y$ ma 2-elementy, a więc suma $X \cap Y$ jest zbiorem 4-elementowym. To oznacza, że w
rodzinie $\mathcal{B}_i$ istnieje zbiór $Z$ zawierający element, który nie należy do sumy $X \cap Y$ .
Stąd wniosek, że 2-elementowe przekroje $X \cap Y$ , $X \cap Z$ , $Y \cap Z$ muszą się pokrywać, a więc
można napisać

$ X = \{p,q,x\},\quad Y = \{p,q,y\}, \quad Z = \{p,q,z\}, $

gdzie elementy $p, q, x, y, z$ są różne. Weźmy teraz pod uwagę dowolny zbiór $S$ należący do rodziny
$\mathcal{B}_i$ i różny od zbiorów $X, Y , Z$ . Wówczas $S$ nie jest zbiorem $\{x,y,z\}$ , gdyż ten ostatni
ma dokładnie jeden element wspólny ze zbiorem $X$ . Wobec tego przynajmniej jeden z elementów $x, y, z$
nie należy do zbioru $S$ . Przyjmijmy, nie zmniejszając ogólności dalszego rozumowania, iż jest to element $x$ .
Skoro przekrój $X\cap S$ jest zbiorem 2-elementowym oraz $x \notin S$ , musimy mieć $X \cap S = \{p,q\}$ .
Ale to, wobec dowolności wyboru $S$ , oznacza, że każdy zbiór należący do rodziny $\mathcal{B}_i$
zawiera elementy $p$ i $q$ . Stąd wniosek, że liczba elementów tej rodziny nie przekracza liczby elementów zbioru
$C_i$ pomniejszonej o 2.

Udowodniliśmy w ten sposób, że każda z rodzin $\mathcal{B}_i$ zawiera najwyżej tyle zbiorów, ile jest
elementów w zbiorze $C_i$ , przy czym równość może mieć miejsce tylko wtedy, gdy zbiór $C_i$ ma 4 elementy.

Ponadto zbiory $C_1, C_2, \cdots , C_m$ są parami rozłączne, a ich suma zawiera się w ustalonym na
początku rozwiązania zbiorze $n$ -elementowym, więc suma liczb elementów tych zbiorów nie przekracza $n$ .
Tym bardziej suma liczb elementów rodzin $\mathcal{B}_1, \mathcal{B}_2, \cdots , \mathcal{B}_m$ nie przekracza
$n$ , przy czym równość jest możliwa tylko w przypadku, gdy każdy ze zbiorów $C_i$ oraz każda z rodzin
$\mathcal{B}_i$ $(i =1,2, \cdots ,m)$ ma dokładnie 4 elementy,

Jednakże każdy ze zbiorów $A_1, A_2, \cdots , A_k$ należy do dokładnie jednej z tych rodzin. Stąd wniosek,
że $k \leqslant n$ , przy czym równość może mieć miejsce tylko wtedy, gdy każda z rodzin $\mathcal{B}_i$
$(i =1, 2, \cdots ,m)$ ma dokładnie 4 elementy oraz suma ilości elementów tych rodzin jest równa $n$ .
Jest to możliwe tylko wtedy, gdy zachodzi równość $n=4m$ . Jeśli zatem istnieje układ $n$ trójelementowych
podzbiorów zbioru $n$ -elementowego, z których żadne dwa nie mają dokładnie jednego elementu wspólnego,
to liczba $n$ jest podzielna przez $4$ .

Implikacja odwrotna również jest prawdziwa: jeżeli $n =4s$ dla pewnej liczby całkowitej $s \geqslant 1$ ,
to definiujemy zbiory $A_1, A_2, \cdots , A_{4s}$ warunkami

$ \begin{split} A_{4j-3} = \{4j -2,4j -1,4j\},&\quad A_{4j-1} = \{4j -3,4j -2,4j\},\\ A_{4j-2} = \{4j -3,4j -1,4j\},&\quad A_{4j} = \{4j -3,4j -2,4j -1\} \end{split} $

dla $j =1,2, \cdots ,s$ . Wówczas dowolne dwa z określonych wyżej zbiorów albo są rozłączne, albo mają
dokładnie dwa wspólne elementy.

Odpowiedź: Liczba $n \geqslant 4$ spełnia warunki zadania wtedy i tylko wtedy, gdy nie jest
podzielna przez 4.

LX OM - II - Zadanie 6

Zawody matematyczne:

LX OM, 2008-2009

Etap:

Dla każdej liczby całkowitej $n \geqslant 3$ wyznaczyć wszystkie ciągi liczb rzeczywistych
$(x_1,x_2, \cdots ,x_n)$ , dla których

$ \sum_{i=1}^n x_i = n \quad \text{ oraz } \sum_{i=1}^n (x_{i-1} -x_i + x_{i+1})^2 = n, $

gdzie przyjmujemy $x_0 = x_n$ i $x_{n+1} = x_1$ .

Rozwiązanie

Przypuśćmy, że ciąg $(x_1,x_2, \cdots ,x_n)$ ma żądaną własność. Przyjmijmy

$ (1) \qquad y_i = x_{i-1} -x_i + x_{i+1} -1 \quad \text{ dla } \quad i =1,2, \cdots ,n. $

Wówczas zachodzi równość $y_1 + y_2 + \cdots +y_n = x_1 + x_2 + \cdots + x_n -n$ , a zatem
z danych w treści zadania dwóch równości wynika, że

$ y_1 +y_2 + \cdots +y_n =0 \text{ oraz }(1+ y_1)^2 +(1+y_2)^2 + \cdots +(1+y_n)^2 = n, $

skąd uzyskujemy

$ \sum_{i=1}^n y_i^2 = \sum_{i=1}^n [(1+y_i)^2 -2y_i -1]= \sum_{i=1}^n (1+y_i)^2 -2\sum_{i=1}^n y_i - \sum_{i=1}^n 1= n-0-n =0. $

Zatem $y_1 = y_2 = \cdots = y_n = 0$ , co z uwagi na wzór (1) daje

$ (2) \qquad x_i-1 -x_i + x_i+1 = 1 \text{ dla } i =1,2, \cdots ,n. $

Na odwrót, każdy ciąg $(x_1,x_2, \cdots ,x_n)$ spełniający warunek (2) spełnia także równości dane w zadaniu.
Pozostaje więc wyznaczyć wszystkie ciągi, dla których zachodzi warunek (2).

Oznaczmy $x_0 = a$ oraz $x_1 = b$ . Wówczas stosując zależność (2) w postaci
$x_{i+1} =1 -x_i-1 + x_i$ dla $i =1,2, 3,4,5,6$ otrzymujemy

$ x_2 =1 -a+b,\; x_3 =2-a,\; x_4 =2-b,\; x_5 =1+a-b,\; x_6 = a,\; x_7 = b. $

Kontynuując to postępowanie stwierdzamy, że ciąg $x_0, x_1, x_2, \cdots$ jest okresowy:
$x_{k+6} =x_k$ dla $k =0,1,2, \cdots$ . Ponieważ $x_0 = x_n$ oraz $x_1 =x_{n+1}$ , więc para
$(x_0,x_1)$ pokrywa się z parą $(x_r,x_{r+1})$ , gdzie $r$ jest resztą z dzielenia liczby $n$ przez 6.

Korzystając z wyliczonych wyżej wartości $x_0, x_1, x_2, x_3, x_4, x_5, x_6$ sprawdzamy bezpośrednio,
że dla dowolnej wartości $r =1,2,3,4,5$ jedynym rozwiązaniem układu równań
$x_0 = x_r, x_1 = x_{r+1}$ , czyli odpowiednio układów

$ \begin{cases} a=b\\ b=1-a+b \end{cases}, \begin{cases} a=1-a+b\\ b=2-a \end{cases}, \begin{cases} a=2-a\\ b=2-b \end{cases}, \begin{cases} a=2-b\\ b=1+a-b \end{cases}, \begin{cases} a=1+a-b\\ b=a \end{cases}, $

są liczby $a = b = 1$ . W tej sytuacji oczywiście $x_1 = x_2 = \cdots = x_n = 1$ i liczby te mają
żądane w treści zadania własności.

Jeżeli natomiast $r = 0$ , a więc gdy liczba $n$ jest podzielna przez 6, to możemy wybrać dowolne
wartości rzeczywiste $x_0 = x_n$ i $x_1$ i korzystając ze wzoru (2) wyznaczyć jednoznacznie wartości
$x_2, x3, \cdots , x_{n+1}$ . Nietrudno spostrzec, że warunek (2) będzie wówczas spełniony.

Odpowiedź: Dla każdej liczby całkowitej $n \geqslant 3$ rozwiązaniem zadania jest ciąg
$(x_1,x_2, \cdots ,x_n) = (1,1, \cdots ,1)$ ; ponadto dla liczb $n$ podzielnych przez 6 istnieją rozwiązania
o okresie długości 6 następującej postaci:

$ (x_1,x_2, \cdots ,x_n)=(b,1 -a +b,2-a,2-b,1+ a-b,a,b,1-a+b, \cdots ,a). $

LX OM - III etap

III etap LX Olimpiady Matematycznej

Załącznik	Wielkość
LX OM III etap - Zadania [7]	95.3 KB
LX OM III etap - Zadania z rozwiązaniami [8]	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)$ .