LX OM - I etap

I etap LX Olimpiady Matematycznej

Załącznik	Wielkość
LX OM I etap - Zadania [1]	100.33 KB
LX OM I etap - Zadania z rozwiązaniami [2]	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.