Opublikowane na Archiwum Olimpiady Matematycznej (https://archom.ptm.org.pl)

Strona główna > Wersja do wydruku > Wersja do wydruku

XLVIII OM

XLVIII Olimpiada Matematyczna

Opracowanie rozwiązań: Marcin E. Kuczma

XLVIII OM - I etap

II etap XLVIII Olimpiady Matematycznej

ZałącznikWielkość
XLVIII OM I etap - Zadania [1]55.91 KB

XLVIII OM - I - Zadanie 1

Zawody matematyczne: 
XLVIII OM, 1996-1997
Etap: 
I

Rozwiązać układ równań

\[<br /> \left\{<br /> \begin{split}<br /> &x \cdot |x|+y \cdot |y| =1,\\<br /> &[x] + [y] =1.<br /> \end{split}<br /> \right.<br /> \]

Uwaga: $ [t] $ jest największą liczbą całkowitą nie większą od $ t $.

Rozwiązanie

Przypuśćmy, że liczby $ x $, $ y $ spełniają dany układ równań.

Weźmy najpierw pod uwagę przypadek, gdy co najmniej jedna z tych liczb jest ujemna; przypuśćmy na przykład, że $ y < 0 $. Wówczas $ [y] \leq -1 $, i w takim razie na mocy drugiego równania układu zachodzi nierówność

\[<br /> [x]=1-[y] \geq 2.<br /> \]

Wobec tego $ x \geq 2 $.

Skoro $ x $ jest liczbą dodatnią, a $ y $ jest liczbą ujemną, pierwsze równanie układu przybiera w tym przypadku postać

\[<br /> \qquad (1) x^2-y^2=1.<br /> \]

Z nierówności $ x \geq 2 $, $ y < 0 $ wynika ponadto, że $ x - y > 2 $.

Oczywiście $ x + y \geq [x] + [y] = 1 $. Zatem

\[<br /> x^2-y^2=(x + y)(x-y)>2.<br /> \]

Otrzymaliśmy sprzeczność z równaniem (1). Jest ona wynikiem przypuszczenia, że któraś z liczb $ x $, $ y $ jest ujemna. Ten przypadek zajść więc nie może.

Pozostaje do rozpatrzenia przypadek, gdy liczby $ x $ i $ y $ są obie nieujemne. Pierwsze równanie układu teraz ma postać

\[<br /> x^2 + y^2 = 1;<br /> \]

zatem $ x,y \in \langle 0,\ 1 \rangle $ i z drugiego równania wynika, że jedna z liczb $ [x] $, $ [y] $ musi być równa $ 1 $, a druga $ 0 $. Stąd łatwy wniosek, że

\[<br /> \left\{<br /> \begin{split}<br /> &x=1,\\<br /> &y=0,<br /> \end{split}<br /> \right.<br /> \quad \textrm{lub}\quad<br /> \left\{<br /> \begin{split}<br /> &x=0,\\<br /> &y=1.<br /> \end{split}<br /> \right.<br /> \]

Te dwie pary spełniają układ i są jego jedynymi rozwiązaniami.

XLVIII OM - I - Zadanie 2

Zawody matematyczne: 
XLVIII OM, 1996-1997
Etap: 
I

Punkt $ P $ leży wewnątrz równoległoboku $ ABCD $, przy czym zachodzi równość $ |\measuredangle ABP| = |\measuredangle ADP| $. Wykazać, że $ |\measuredangle PAB| = |\measuredangle PCB| $.

Rozwiązanie

Sposób I

Przesuwamy trójkąt $ ADP $ równolegle tak, by obrazem boku $ AD $ był odcinek $ BC $. Obraz wierzchołka $ P $ oznaczmy przez $ Q $. Mamy zatem równość $ |\measuredangle ADP| = |\measuredangle BCQ| $ (rysunek 1). Odcinki $ AB $ i $ PQ $ są równoległe, więc $ |\measuredangle ABP| = |\measuredangle QPB| $.

Jednocześnie $ |\measuredangle ABP| = |\measuredangle ADP| $ (w myśl warunku zadania). Wobec tego $ |\measuredangle BCQ| = |\measuredangle QPB| $.

Odcinek $ BQ $ jest więc widoczny pod jednakowym kątem z punktów $ P $ i $ C $, leżących po tej samej stronie prostej $ BQ $. Wniosek: punkty $ B $, $ P $, $ C $, $ Q $ leżą na jednym okręgu. Stąd, wobec faktu, że punkty $ C $ i $ Q $ leżą po tej samej stronie prostej $ PB $, wynika równość $ |\measuredangle PCB|=|\measuredangle PQB| $.

Pozostaje zauważyć, że czworokąt $ PABQ $ jest równoległobokiem, a więc $ |\measuredangle PQB| =| \measuredangle PAB| $. Otrzymujemy równość $ | \measuredangle PAB| = | \measuredangle PCB| $, która była dana do udowodnienia.

Sposób II

Przez punkt $ P $ prowadzimy proste równoległe do boków równoległoboku $ ABCD $. Przecinają one boki $ AB $, $ BC $, $ CD $, $ DA $ odpowiednio w punktach $ K $, $ L $, $ M $, $ N $ (rysunek 2).

Trójkąt $ PKB $ jest podobny do trójkąta $ PND $, bo $ |\measuredangle PKB| = |\measuredangle PND| $ (kąty o ramionach parami równoległych) oraz $ |\measuredangle NDP| = |\measuredangle KBP| $ (warunek zadania). Zatem

\[<br /> \qquad (1) \frac{|PK|}{|PN|}=\frac{|KB|}{|ND|}.<br /> \]

Teza zadania, czyli równość $ |\measuredangle PAK| = |\measuredangle PCL| $, będzie udowodniona, jeśli wykażemy, że trójkąty $ PAK $ i $ PCL $ są podobne.

Uwaga: tu i dalej, mówiąc, że trójkąty $ XYZ $ i $ X'Y'Z' $ są podobne, rozumiemy, że w tym podobieństwie wierzchołki $ X' $, $ Y' $, $ Z' $ są odpowiednio obrazami wierzchołków $ X $, $ Y $, $ Z $.

Ponieważ $ |\measuredangle PKA| = |\measuredangle PLC| $ (kąty o ramionach parami równoległych), wystarczy dowieść, że

\[<br /> \qquad (2) \frac{|PK|}{|KA|}=\frac{|PL|}{|LC|}.<br /> \]

Otóż z określenia punktów $ K $, $ L $ i $ N $ wynika, że $ |PN| = |KA| $, $ |KB| = |PL| $, $ |ND| = |LC| $, i wobec tego równość (2) jest identyczna z równością (1). To kończy dowód.

Sposób III

Dana w założeniu równość $ |\measuredangle ABP| = |\measuredangle ADP| $ jest równoważna równości $ |\measuredangle CBP| = |\measuredangle CDP| $. Role punktów $ A $ i $ C $ są więc symetryczne, tak w założeniach, jak i w tezie zadania. Można wobec tego przyjąć, nie tracąc ogólności, że $ P $ jest punktem trójkąta $ ABD $. Przyjmimy dodatkowo, że jest to punkt wewnętrzny trójkąta $ ABD $; niezbędne modyfikacje rozumowania w przypadku granicznym, gdy $ P $ leży na przekątnej $ BD $, pozostawiamy Czytelnikowi.

Półproste $ DP $ i $ BP $ przecinają boki $ AB $ i $ AD $ odpowiednio w punktach $ U $ i $ V $ (rysunek 3). Z danej w założeniu równości kątów (którą można przepisać jako $ |\measuredangle PBU| = |\measuredangle PDV| $, bądź też jako $ |\measuredangle ABV| = |\measuredangle ADU| $) wynika, że trójkąt $ PBU $ jest podobny do $ PDV $, a trójkąt $ ABV $ jest podobny do $ ADU $. Mamy więc proporcje:

\[<br /> \frac{|PB|}{|PU|} = \frac{|PD|}{|PV|} \ \textrm{oraz} \ \frac{|AB|}{|AV|}=\frac{|AD|}{|AU|}.<br /> \]

Pozwalają one wywnioskować, że trójkąt $ PUV $ jest podobny do $ PBD $, a trójkąt $ AUV $ - do $ ADB $. Otrzymujemy związki:

\[<br /> \begin{split}<br /> \qquad (3) \frac{|PB|}{|PU|} = & \frac{|BD|}{|UV|}=\frac{|AD|}{|AU|} =\frac{|CB|}{|AU|},\\<br /> \qquad (4) |\measuredangle PUV| = |\measuredangle PBD|, & \ |\measuredangle AUV| = |\measuredangle ADB| = |\measuredangle CBD|.<br /> \end{split}<br /> \]

Dodajemy stronami równości (4) i dostajemy równość $ |\measuredangle PUA| = |\measuredangle PBC| $, która w połączeniu z zależnością (3) pokazuje, że trójkąt $ PUA $ jest podobny do trójkąta $ PBC $. Stąd, ostatecznie, $ |\measuredangle PCB| = |\measuredangle PAU| = |\measuredangle PAB| $.

XLVIII OM - I - Zadanie 3

Zawody matematyczne: 
XLVIII OM, 1996-1997
Etap: 
I

Udowodnić, że dla dowolnych liczb rzeczywistych $ a, b \geq 1 $, $ c\geq 0 $ oraz dla każdej liczby naturalnej $ n \geq 1 $ zachodzi nierówność

\[<br /> (ab + c)^n-c \leq ((b + c)^n-c)a^n.<br /> \]

Rozwiązanie

Sposób I

Daną do udowodnienia nierówność przepisujemy w postaci

\[<br /> \qquad (1) (ab + ac)^n-(ab + c)^n \geq c(a^n-1).<br /> \]

Oznaczmy: $ \alpha = ab + ac $, $ \beta = ab + c $. Skoro $ a \geq 1 $, $ b \geq 1 $, $ c\geq 0 $, zatem $ \alpha \geq a $, $ \beta \geq 1 $; ponadto $ \alpha-\beta= (a-1)c $, i wobec tego

\[<br /> \begin{split}<br /> \alpha^n -\beta^n&= (\alpha -\beta)\sum_{k=0}^{n-1}\alpha^k\beta^{n-1-k} \geq (\alpha -\beta)\sum_{k=0}^{n-1}\alpha^k \geq\\<br /> &\geq (\alpha -\beta)\sum_{k=0}^{n-1}a^k=c(a-1)\sum_{k=0}^{n-1}a^k=c(a^n-1);<br /> \end{split}<br /> \]

otrzymaliśmy nierówność (1).

Sposób II

Dowód będzie oparty na znanej nierówności Bernoulli'ego:

\[<br /> \qquad (2) (1 + x)^n \geq 1 + nx \ \textrm{dla}\ x \geq -1;\ n = 1,2,3,\dots .<br /> \]

Oznaczając sumę $ 1 + x $ przez $ y $ możemy tę nierówność przepisać tak:

\[<br /> \qquad (3) y^n - 1\geq n(y-1) \ \textrm{dla}\ y \geq 0;\ n = 1,2,3,\dots .<br /> \]

Przechodzimy do nierówności (1). Szacujemy z dołu jej lewą stronę, wykorzystując nierówność (3) (dla $ y = \frac{ab+ac}{ab+c} $):

\[<br /> \begin{split}<br /> (ab+ac)^n-(ab+c)^n&=(ab+c)^n \left[\left(\frac{ab+ac}{ab+c}\right)^n-1\right] \geq \\<br /> &\geq (ab+c)^n\cdot n\left(\frac{ab+ac}{ab+c} -1 \right)=\\<br /> &=n(ab+c)^{n-1}(a-1)c.<br /> \end{split}<br /> \]

Stąd (wobec faktu, że $ ab+c\geq ab $):

\[<br /> \qquad (4) (ab+ac)^n - (ab +c)^n \geq n(ab)^{n-1}(a-1)c,<br /> \]

i dalej (skoro $ b \geq 1 $):

\[<br /> \qquad (5) (ab+ac)^n - (ab +c)^n \geq na^{n-1}(a-1)c.<br /> \]

Jeszcze raz stosujemy nierówność Bernoulli'ego (3) przyjmując $ y = 1/a $:

\[<br /> \frac{1}{a^n}-1\geq n\left(\frac{1}{a}-1\right);<br /> \]

po przekształceniu:

\[<br /> \qquad (6) na^{n-1}(a-1)\geq a^n-1.<br /> \]

Z zależności (5) i (6) natychmiast wynika dowodzona nierówność (1).

Uwaga: Nierówność (4) można także uzasadnić stosując wzór dwumianowy:

\[<br /> \begin{split}<br /> (ab + ac)^n - (ab + c)^n &= \sum_{k=0}^n \binom{n}{k} (ab)^{n-k}(ac)^n -\sum_{k=0}^n \binom{n}{k} (ab)^{n-k}c^k =\\<br /> &= \sum_{k=0}^n \binom{n}{k} (ab)^{n-k}(a^k-1)c^k;<br /> \end{split}<br /> \]

wszystkie składniki tej sumy są liczbami nieujemnymi; a składnik odpowiadający wartości $ k = 1 $ to dokładnie prawa strona wzoru (4).

Sposób III

Przeprowadzimy indukcyjny dowód nierówności (1), którą teraz wygodnie będzie zapisać tak:

\[<br /> \qquad (7) (ab + ac)^n-(ab + c)^n + c(1-a^n) \geq 0;<br /> \]

$ a $, $ b $, $ c $ są danymi liczbami rzeczywistymi, $ a, b \geq 1 $, $ c \geq 0 $.

Dla $ n = 1 $ mamy równość we wzorze (7). Ustalmy liczbę naturalną $ n \geq 1 $, oznaczmy: $ u = (ab + ac)^n $, $ v = (ab + c)^n $, $ w = a^n $ i przyjmijmy indukcyjnie, że dla tej liczby $ n $ zdanie (7) jest prawdziwe:

\[<br /> u - v + c - cw \geq 0.<br /> \]

Teza indukcyjna, czyli nierówność (7) z $ n $ zastąpionym przez $ n+1 $, ma postać:

\[<br /> \qquad (8) (ab + ac)u - (ab+c)v + c - acw \geq 0.<br /> \]

Otóż lewa strona (8) jest równa

\[<br /> a(u - v + c - cw) + a(u - v)(b + c- 1) + (a - 1)(v - 1)c;<br /> \]

pomijamy czysto mechaniczne sprawdzenie. W tej ostatniej sumie wszystkie trzy składniki są liczbami nieujemnymi: pierwszy - na podstawie założenia indukcyjnego, a pozostałe dwa - w wyniku założeń o liczbach $ a $, $ b $, $ c $. To dowodzi słuszności związku (8) i kończy dowód indukcyjny.

Sposób IV

Dzielimy daną w treści zadania nierówność stronami przez $ a^n $ i otrzymujemy nierówność równoważną:

\[<br /> \left(b+\frac{c}{a}\right)^n-\frac{c}{a^n}\leq (b+c)^n-c.<br /> \]

Weźmy pod uwagę funkcję

\[<br /> f(x) = (cx + b)^n-cx^n\ \textrm{dla}\ x>0<br /> \]

($ a $, $ b $, $ c $, $ n $ są ustalonymi parametrami spełniającymi podane warunki). Zadanie sprowadza się do wykazania, że $ f(1/a) \leq f(1) $.

Funkcja $ f $ jest w przedziale $ (0,\ 1\rangle $ niemalejąca, bowiem

\[<br /> f'(x) = nc(cx + b)^{n-1}-ncx^{n-1} \geq 0\ \textrm{dla}\ x \in (0,\ 1\rangle;<br /> \]

Ostatnia nierówność wynika z tego, że $ cx + b\geq 1 \geq x $ gdy $ 0<x \leq 1 $.

Tak więc $ f(x) \leq f(1) $ dla $ x \in (0,\ 1\rangle $. Podstawiamy $ x = 1/a $ i mamy nierówność, którą chcieliśmy otrzymać.

XLVIII OM - I - Zadanie 4

Zawody matematyczne: 
XLVIII OM, 1996-1997
Etap: 
I

Udowodnić, że liczba naturalna $ n \geq 2 $ jest złożona wtedy i tylko wtedy, gdy istnieją liczby naturalne $ a,b,x,y \geq 1 $ spełniające warunki: $ a+b=n $, $ \frac{x}{a}+\frac{y}{b}=1 $.

Rozwiązanie

Niech $ n $ będzie liczbą złożoną: $ n = qr $, $ q \geq 2 $, $ r \geq 2 $. Przyjmijmy:

\[<br /> a = r, \qquad b=(q-1)r, \qquad x = 1, \qquad y = (q-1)(r-1);<br /> \]

są to dodatnie liczby całkowite o własnościach:

\[<br /> \qquad (1) a + b = n, \qquad \frac{x}{a}+\frac{y}{b}=1.<br /> \]

Wykazaliśmy więc, że jeżeli $ n\geq 2 $ jest liczbą złożoną, to istnieją liczby całkowite $ a,b,x,y\geq 1 $ spełniające warunki (1).

Pozostała do dowodu implikacja przeciwna. Załóżmy, że dla pewnej liczby całkowitej $ n \geq 2 $ istnieje czwórka liczb całkowitych $ a,b,x,y\geq 1 $ spełniających równania (1). Z drugiego z tych równań wynika, że $ x < a $, $ y<b $ oraz

\[<br /> \qquad (2) ay = b(a-x).<br /> \]

Oznaczmy przez $ d $ największy wspólny dzielnik liczb $ a $ i $ b $ oraz przyjmijmy: $ a = \alpha d $, $ b = \beta d $. Liczby $ \alpha $ i $ \beta $ są względnie pierwsze. Pierwsze równanie (1) daje zależność: $ n = (\alpha + \beta )d $. Czynnik $ \alpha + \beta $ jest większy od $ 1 $. Aby uzyskać wymaganą konkluzję, że $ n $ jest liczbą złożoną, wystarczy wobec tego wykazać, że $ d > 1 $.

Równanie (2) po podzieleniu przez $ d $ przybiera postać $ \alpha y = \beta (a-x) $. Zatem liczba $ \beta $, jako względnie pierwsza z $ \alpha $, musi być dzielnikiem liczby $ y $. Stąd $ \beta \leq y $. Skoro zaś $ y<b $, dostajemy nierówność $ \beta<b $, iw konsekwencji $ d = b/\beta>1 $.

Wniosek: Z istnienia liczb $ a,b,x,y\geq 1 $ spełniających warunki (1) wynika, że $ n $ jest liczbą złożoną. W połączeniu z udowodnioną wcześniej implikacją przeciwną daje to tezę zadania.

XLVIII OM - I - Zadanie 5

Zawody matematyczne: 
XLVIII OM, 1996-1997
Etap: 
I

Dwusieczne kątów wewnętrznych $ A $, $ B $, $ C $ trójkąta $ ABC $ przecinają przeciwległe boki odpowiednio w punktach $ D $, $ E $, $ F $, a okrąg opisany na trójkącie $ ABC $ - odpowiednio w punktach $ K $, $ L $, $ M $. Dowieść, że

\[<br /> \frac{|AD|}{|DK|}+\frac{|BE|}{|EL|}+\frac{|CF|}{|FM|}\geq 9.<br /> \]

Rozwiązanie

Sposób I

Daną do udowodnienia nierówność geometryczną sprowadzimy do prostej nierówności algebraicznej. Zauważmy, że $ |AD| = |AK|-|DK| $, $ |BE| = |BL| -|EL| $, $ |CF| = |CM|-|FM| $, i wobec tego

\[ \frac{|AD|}{|DK|} = \frac{|AK|}{|DK|}-1, \quad \frac{|BE|}{|EL|}=\frac{|BL|}{|EL|}-1, \quad \frac{|CF|}{|FM|}=\frac{|CM|}{|FM|}-1.\]

Nierówność, którą mamy udowodnić, jest więc równoważna nierówności

\[ \frac{|AK|}{|DK|} + \frac{|BL|}{|EL|} + \frac{|CM|}{|FM|} \geq 12.\]

Oznaczmy długości boków $ BC $, $ CA $, $ AB $ odpowiednio przez $ a $, $ b $, $ c $. Punkt $ D $, jako koniec dwusiecznej $ AD $, dzieli bok $ BC $ w stosunku $ \frac{|BD|}{|CD|}=\frac{c}{b} $; stąd obliczamy: $ |BD| = \frac{ac}{b+c} $, $ |CD|=\frac{ab}{b+c} $ i otrzymujemy równość

\[<br /> |AD| \cdot |DK| = |BD| \cdot |DC| = \frac{a^2bc}{(b+c)^2}.<br /> \]

Trójkąt $ ABD $ jest podobny do trójkąta $ AKC $, bowiem $ |\measuredangle ABD| = |\measuredangle AKC| $, $ |\measuredangle DAB| = |\measuredangle CAK| $ (rysunek 4). Zatem $ \frac{|AB|}{|AK|}=\frac{|AD|}{|AC|} $, czyli

\[<br /> |AD| \cdot |AK| = bc.<br /> \]

Dzieląc uzyskane równości stronami dostajemy zależność

\[<br /> \frac{|AK|}{|DK|} = \left( \frac{b+c}{a} \right) ^2;<br /> \]

analogicznie daje się wyrazić drugi i trzeci składnik sumy po lewej stronie nierówności (1) . Zadanie sprowadza się do wykazania, że

\[<br /> \left( \frac{b+c}{a} \right) ^2 + \left( \frac{c+a}{b} \right) ^2 + \left( \frac{a+b}{c} \right) ^2 \geq 12.<br /> \]

Wystarczy teraz kilkakrotnie skorzystać z nierówności między średnią arytmetyczną i średnią geometryczną, najpierw dla par liczb, a następnie dla trójki liczb: $ b + c \geq 2 \sqrt{bc} $, $ c + a \geq 2 \sqrt{ca} $, $ a + b \geq 2 \sqrt{ab} $; stąd

\[<br /> \begin{split}<br /> \left( \frac{b+c}{a} \right) ^2 + & \left( \frac{c+a}{b} \right) ^2 + \left( \frac{a+b}{c} \right) ^2 \geq \frac{4bc}{a^2} + \frac{4ca}{b^2} + \frac{4ab}{c^2} = \\<br /> & = 12 \cdot \frac{1}{3} \left( \frac{bc}{a^2} + \frac{ca}{b^2} + \frac{ab}{c^2} \right) \geq 12 \cdot \sqrt[3]{\frac{bc}{a^2} \cdot \frac{ca}{b^2} \cdot \frac{ab}{c^2}}=12.<br /> \end{split}<br /> \]

Dowód jest zakończony.

Uwaga: Jak widać, nierówność (2) zachodzi dla każdej trójki liczb dodatnich $ a, b, c $, niekoniecznie będących długościami boków trójkąta. Można ją uzasadnić kilkoma sposobami (różniącymi się niezbyt istotnie). Można na przykład powołać się na {\it nierówność Jensena} $ f(a) + f(b) + f(c) \geq 3f(s/3) $, słuszną dla dowolnych liczb nieujemnych $ a, b, c, s $ związanych zależnością $ a + b + c = s $ oraz dla każdej funkcji $ f $ wypukłej w przedziale $ \langle 0,\ s \rangle $.

(Obszerny komentarz na temat funkcji wypukłych i nierówności Jensena, wraz z jej dowodem, można znaleźć na przykład w publikacji: XXXVII Olimpiada Matematyczna. Sprawozdanie Komitetu Głównego, Warszawa 1989, str. 41-42). W rozważanej sytuacji wystarczy przyjąć $ f(x) =\left( \frac{s}{x} -1 \right)^2 $ , aby uzyskać nierówność (2); szczegóły pozostawiamy Czytelnikowi.

Sposób II

Jak w sposobie pierwszym, zastępujemy nierówność daną w zadaniu nierównością równoważną (1). Oznaczmy długości boków $ BC $, $ CA $, $ AB $ trójkąta $ ABC $ jak poprzednio przez $ a $, $ b $, $ c $, a miary jego kątów odpowiednio przez $ \alpha $, $ \beta $, $ \gamma $.

Punkt $ K $ jest środkiem łuku $ BC $ okręgu opisanego na trójkącie $ ABC $; oznaczmy środek i promień tego okręgu odpowiednio przez $ O $ i $ R $. Prosta $ OK $ przecina bok $ BC $ pod kątem prostym w punkcie $ N $ będącym środkiem tego boku.

Niech $ S $ będzie spodkiem wysokości trójkąta $ ABC $ opuszczonej z wierzchołka $ A $ (rysunek 5). Z podobieństwa trójkątów prostokątnych $ ASD $ i $ KND $ otrzymujemy proporcję $ \frac{|AD|}{|DK|}=\frac{|AS|}{|NK|} $.

Kąt środkowy $ BOK $ jest dwukrotnie większy od kąta wpisanego $ BAK $: $ | \measuredangle BOK| = \alpha $. Gdy $ \alpha \leq 90^ \circ $ (jak na rysunku 5), wówczas

\[<br /> |NK| = |OK|-|ON| = |OK|-|OB|\cdot \cos |\measuredangle BOK| = R(1-\cos \alpha).<br /> \]

Gdy $ \alpha > 90^\circ $, rysunek i rachunek wymagają drobnych modyfikacji, ale równość $ |NK|=R(1-\cos \alpha) $ nadal zachodzi.

Zgodnie ze wzorem sinusów, $ |AS| = |AC| \cdot \sin \gamma = 2R \cdot \sin \beta \cdot \sin \gamma $. Zatem

\[<br /> \begin{split}<br /> \frac{|AD|}{|DK|}= & \frac{|AS|}{|NK|}= \frac{2 \sin \beta \sin \gamma}{1-\cos \alpha} = \frac{2 \sin \beta \sin \gamma}{2 \sin^2 \frac{\alpha}{2}} = \frac{\cos(\beta-\gamma)- \cos(\beta + \gamma)}{2 \cos^2 \frac{\beta+\gamma}{2}}= \\<br /> & \frac{(2\cos^2 \frac{\beta-\gamma}{2}-1)-(2\cos^2 \frac{\beta+\gamma}{2}-1)}{2 \cos^2 \frac{\beta+\gamma}{2}} =<br /> \left( \frac{\cos \frac{\beta-\gamma}{2}}{\cos \frac{\beta+\gamma}{2}} \right)^2 - 1.<br /> \end{split}<br /> \]

Ponieważ $ \frac{|AK|}{|DK|} = \frac{|AD|}{|DK|}+1 $, dowodzona nierówność (1) przybiera postać

\[<br /> \left( \frac{\cos \frac{\beta-\gamma}{2}}{\cos \frac{\beta+\gamma}{2}} \right)^2<br /> +<br /> \left( \frac{\cos \frac{\gamma-\alpha}{2}}{\cos \frac{\gamma+\alpha}{2}} \right)^2<br /> +<br /> \left( \frac{\cos \frac{\alpha-\beta}{2}}{\cos \frac{\alpha+\beta}{2}} \right)^2<br /> \geq 12.<br /> \]

Przekształcamy dalej ułamek w pierwszym nawiasie:

\[<br /> \frac{\cos \frac{\beta}{2}-\frac{\gamma}{2}}{\cos \frac{\beta}{2}+\frac{\gamma}{2}} =<br /> \frac{\cos \frac{\beta}{2} \cos \frac{\gamma}{2} + \sin \frac{\beta}{2} \sin \frac{\gamma}{2}}{\cos \frac{\beta}{2} \cos \frac{\gamma}{2} - \sin \frac{\beta}{2} \sin \frac{\gamma}{2}}=<br /> \frac{1+ \tan \frac{\beta}{2} \tan \frac{\gamma}{2}}{1- \tan \frac{\beta}{2} \tan \frac{\gamma}{2}}=<br /> \frac{2}{1- \tan\frac{\beta}{2} \tan \frac{\gamma}{2}}-1.<br /> \]

Przyjmijmy oznaczenia:

\[<br /> u=\frac{1}{2} (1- \tan\frac{\beta}{2} \tan \frac{\gamma}{2}), \quad<br /> v=\frac{1}{2} (1- \tan\frac{\gamma}{2} \tan \frac{\alpha}{2}), \quad<br /> w=\frac{1}{2} (1- \tan\frac{\alpha}{2} \tan \frac{\beta}{2});<br /> \]

nierówność (3) sprowadza się do następującej:

\[<br /> \left( \frac{1}{u}-1 \right)^2 + \left( \frac{1}{v}-1 \right)^2 + \left( \frac{1}{w}-1 \right)^2 \geq 12.<br /> \]

Miary kątów trójkąta spełniają znany wzór

\[<br /> \tan\frac{\beta}{2} \tan \frac{\gamma}{2} +<br /> \tan\frac{\gamma}{2} \tan \frac{\alpha}{2} +<br /> \tan\frac{\alpha}{2} \tan \frac{\beta}{2} = 1.<br /> \]

(Czytelnikom, którzy go nie znają, proponujemy samodzielne wyprowadzenie tego wzoru; to nietrudne ćwiczenie). Wynika z niego, że $ u,v,w $ są liczbami dodatnimi, związanymi zależnością: $ u + v + w = 1 $.

Średnia harmoniczna tych liczb nie przekracza ich średniej arytmetycznej, równej $ 1/3 $. Tak więc $ \frac{1}{u}+\frac{1}{v}+\frac{1}{w} \geq 9 $. Oznaczmy: $ U = \frac{1}{u}-1,\ V = \frac{1}{v}-1 ,\ W = \frac{1}{w}-1 $; zatem $ U + V + W \geq 6 $. Stąd

\[<br /> (U^2 + V^2 + W^2) + 2(VW + WU + UV) = (U + V + W)^2 \geq 36.<br /> \]

Jednocześnie

\[<br /> 2(U^2 + V^2 + W^2)-2(VW + WU + UV) = (V - W)^2 + (W - U)^2 + (U - V)^2 \geq 0.<br /> \]

Dodajemy stronami te dwie ostatnie nierówności i otrzymujemy zależność $ U^2 +V^2 +W^2 \geq 12 $, czyli nierówność (4) , którą chcieliśmy wykazać.

Uwaga: Składniki sumy (3) dokładnie odpowiadają kolejnym składnikom sumy (2) . Tak więc początkowe fragmenty obu rozwiązań dają dowód związków

\[<br /> \frac{b+c}{a} = \frac{\cos \frac{\beta-\gamma}{2}}{\cos \frac{\beta+\gamma}{2}}, \quad<br /> \frac{c+a}{b} = \frac{\cos \frac{\gamma-\alpha}{2}}{\cos \frac{\gamma+\alpha}{2}}, \quad<br /> \frac{a+b}{c} = \frac{\cos \frac{\alpha-\beta}{2}}{\cos \frac{\alpha+\beta}{2}},<br /> \]

zwanych wzorami Mollweide'a. Na odwrót, przyjmując te wzory za znane, można w dowolny sposób kombinować początkowe oraz końcowe fragmenty rozwiązań. Na przykład - sprowadzić zadanie do nierówności (3) , jak w sposobie drugim; przepisać tę nierówność w równoważnej postaci (2) i udowodnić ją, jak w końcówce pierwszego rozwiązania.

XLVIII OM - I - Zadanie 6

Zawody matematyczne: 
XLVIII OM, 1996-1997
Etap: 
I

Wielomian $ P(x) $ stopnia $ n $ spełnia warunek

\[<br /> P(k)=\frac{1}{k}\ \textrm{dla}\ k = 1,2,4,8,\dots,2^n.<br /> \]

Obliczyć $ P(0) $.

Rozwiązanie

Sposób I

Niech $ P(x) = a_0 + a_1x + \dots + a_nx^n $. Weźmy pod uwagę wielomian

\[<br /> \qquad (1) T(x)=xP(x)-1 = -1+a_0x + a_1x^2 + \dots + a_nx^{n+1}.<br /> \]

Podstawiając w miejsce zmiennej $ x $ liczby $ k = 1,2,4,\dots ,2^n $ otrzymujemy, na podstawie warunku zadania, równości

\[<br /> T(k) =kP(k)-1=k\cdot\frac{1}{k}- 1=0.<br /> \]

Zatem liczby te są pierwiastkami wielomianu $ T(x) $. Jest to wielomian stopnia $ n+1 $, a więc daje się przedstawić jako iloczyn

\[<br /> \qquad (2) T(x) = a_n(x-1)(x-2)(x-4) \cdot \ldots \cdot (x-2^n).<br /> \]

Wymnażając dwumiany w nawiasach otrzymamy ,,zwykłe'' przedstawienie wielomianu $ T(x) $ w postaci rozwiniętej. Będzie nas interesował współczynnik przy $ x $ (w pierwszej potędze); jest on równy $ a_n(-1)^n \cdot (q_0 + q_1 +\ldots + q_n) $, gdzie $ q_j $ jest iloczynem liczb $ 1, 2, 4, \ldots ,2^n $, z usuniętym czynnikiem $ 2^j $.

Jednocześnie - zgodnie ze wzorem (1) - współczynnik przy $ x $ w wielomianie $ T(x) $ jest równy $ a_0 $. Tak więc

\[<br /> \begin{split}<br /> a_0 &= a_n(-1)^n(q_0 + q_1 +\ldots+q_n) =\\<br /> &= a_n(-1)^n \left(\frac{1\cdot 2 \cdot 4 \cdot \ldots \cdot 2^n}{2^0} + \frac{1\cdot 2 \cdot 4 \cdot \ldots \cdot 2^n}{2^1}+ \ldots +\frac{1\cdot 2 \cdot 4 \cdot \ldots \cdot 2^n}{2^n}\right).<br /> \end{split}<br /> \]

Podstawiając zaś we wzorach (1) i (2) $ x = 0 $, i przyrównując otrzymane wartości, dostajemy równość

\[<br /> -1 = a_n(-1)^{n+1}(1\cdot 2 \cdot 4 \cdot \ldots\cdot 2^n).<br /> \]

Z uzyskanych zależności wynika, że

\[<br /> a_0 = \frac{1}{2^0}+\frac{1}{2^1}+ \ldots +\frac{1}{2^n}=2-\frac{1}{2^n}.<br /> \]

Jest to szukana wartość $ P(0) $.

Sposób II

Zastosujemy postępowanie rekurencyjne. Oznaczmy rozważany wielomian $ P(x) $ przez $ P_n(x) $. Dla $ n = 0 $ mamy wielomian stały $ P_n(x) = 1 $. Ustalmy liczbę naturalną $ n\geq 1 $. Dzielimy wielomian $ P_n(x) $ przez dwumian $ (x - 2^n) $ (dzielenie z resztą); ilorazem jest pewien wielomian $ Q_n(x) $, stopnia $ n-1 $, a reszta jest równa $ P_n(2^n) $, czyli $ 2^{-n} $:

\[<br /> \qquad (3) P_n(x) = Q_n(x)\cdot(x-2^n) + 2^{-n}.<br /> \]

Podstawiamy kolejno $ x = 2^i $ dla $ i = 0,1,2,\ldots,n-1 $. Traktując otrzymane związki jako równania względem $ Q_n(2^i) $ obliczamy - korzystając z warunku zadania -

\[<br /> Q_n(2^i)= \frac{P_n(2^i)-P_n(2^n)}{2^i-2^n} = \frac{2^{-i}-2^{-n}}{2^i-2^n} = - \frac{1}{2^{n+i}} \ \textrm{dla}\ i = 0,1,2,\dots,n-1.<br /> \]

Weźmy pod uwagę wielomian $ P_{n-1}(x) $. Spełnia on warunki $ P_{n-1}(k) = 1/k $ dla $ k = 1,2,4,\dots ,2^{n-1} $. To pozwala przepisać poprzednią równość jako

\[<br /> 2^nQ_n(2^i) = -2^{-i} = -P_{n-1}(2^i) \ \textrm{dla}\ i = 0,1,2,\ldots,n-1.<br /> \]

Tak więc wielomiany $ 2^nQ_n(x) $ oraz $ -P_{n-1}(x) $, stopnia $ n-1 $, przyjmują równe wartości w $ n $ różnych punktach, i wobec tego są równe. Możemy w takim razie zastąpić czynnik $ Q_n(x) $ przez $ -2^{-n}P_{n-1}(x) $ we wzorze (3):

\[<br /> P_n(x) = -2^{-n} P_{n-1}(x) \cdot (x-2^n) + 2^{-n}.<br /> \]

Podstawiamy $ x=0 $ i otrzymujemy zależność rekurencyjną:

\[<br /> P_n (0) = P_{n-1}(0) + 2^{-n}.<br /> \]

Wzór ten jest słuszny dla każdej liczby naturalnej $ n \geq 1 $. A skoro $ P_0(0) = 1 $, dostajemy wynik:

\[<br /> P_n(0) = 1 + 2^{-1} + 2^{-2} + \ldots + 2^{-n} = 2-2^{-n}.<br /> \]

Sposób III

Zachowujemy z poprzedniego rozwiązania oznaczenie $ P_n(x) $. Wyprowadzimy inną zależność rekurencyjną. Jak poprzednio, zauważamy, że $ P_0(x) = 1 $; w szczególności $ P_0(0) = 1 $.

Ustalmy $ n \geq 1 $. Wielomiany $ P_n(x) $ i $ P_{n-1}(x) $ przyjmują jednakowe wartości dla $ x = 1,2,4,\ldots,2^{n-1} $. Te liczby $ (1, 2, 4, \ldots ,2^{n-1}) $ są więc pierwiastkami wielomianu $ P_n(x)-P_{n-1}(x) $ (stopnia $ n $).

Oznaczając przez $ a_n $ współczynnik przy $ x^n $ w wielomianie $ P_n(x) $ (zatem także w wielomianie $ P_n(x) -P_{n-1}(x) $) otrzymujemy równość

\[<br /> P_n(x) - P_{n-1}(x) = a_n (x - 1)(x - 2)(x - 4)\cdot \ldots \cdot (x - 2^{n-1}).<br /> \]

Przyjrzyjmy się teraz wielomianowi $ R_n(x) = 2P_n(2x) $; jest to także wielomian stopnia $ n $, ze współczynnikiem przy $ x^n $ równym $ 2^{n+1}a_n $. Dla $ x = 2^i $ (gdzie $ i $ przebiega wartości $ 0,1,2,\ldots ,n-1 $) mamy

\[<br /> R_n(2^i) = 2P_n(2^{i+1}) = 2 \cdot 2^{-(i+1)} = 2^{-i} = P_{n-1}(2^i).<br /> \]

To znaczy, że liczby $ 1, 2, 4,\ldots ,2^{n-1} $ są jednocześnie pierwiastkami wielomianu $ R_n(x) - P_{n-1}(x) $, czyli wielomianu $ 2P_n(2x)-P_{n-1}(x) $, i wobec tego

\[<br /> \begin{split}<br /> 2P_n(2x) -P_{n-1}(x) & = 2^{n+1} a_n (x-1)(x-2)(x-4)\cdot \ldots \cdot (x-2^{n-1}) =\\ & = 2^{n+1}(P_n(x)-P_{n-1}(x)).<br /> \end{split}<br /> \]

Podstawiamy $ x = 0 $ i po prostym przekształceniu dostajemy równość

\[<br /> P_n(0) = \frac{2^{n+1}-1}{2^{n+1}-2} P_{n-1}(0) = \frac{1}{2} \cdot \frac{2^{n+1}-1}{2^{n}-1} P_{n-1}(0).<br /> \]

Wiedząc, że $ P_0(0) = 1 $, obliczamy:

\[<br /> P_n(0) = \prod_{m=1}^n \left( \frac{1}{2} \cdot \frac{2^{m+1}-1}{2^m-1} \right) =<br /> \frac{1}{2^n} \cdot \frac{2^2-1}{2^1-1} \cdot \frac{2^3-1}{2^2-1} \cdot \ldots \cdot \frac{2^{n+1}-1}{2^n-1} = \frac{2^{n+1}-1}{2^n}.<br /> \]

Sposób IV

Rozwiązanie wykracza poza program szkolny; przedstawimy je szkicowo. Będziemy korzystali z najprostszych faktów z teorii równań liniowych i wyznaczników (literatura: dowolny akademicki podręcznik algebry liniowej).

Niech $ P(x) = a_0 + a_1x + \ldots + a_nx^n $. Dane w założeniach zadania warunki

\[<br /> \qquad (4) P(2^i) = \sum_{j=0}^n a_j (2^i)^j = \left( \frac{1}{2} \right)^i \ \textrm{dla}\ i = 0,1,\ldots,n<br /> \]

traktujemy jak układ $ n+1 $ równań liniowych z niewiadomymi $ a_0, a_1,\ldots, a_n $. Wyznacznik tego układu $ D = det [2^{ij}]_{0 \leq i,j \leq n} $ jest różny od zera; wynika to z następującego ogólnego faktu:

Jeśli $ t_0,t_1,\ldots,t_n $ są dowolnymi liczbami rzeczywistymi, to

\[<br /> V(t_0, t_1, \ldots, t_n) = \det[t_i^j]_{0 \leq i,j \leq n} =<br /> \left|<br /> \begin{array}{cccc}<br /> 1 & 1 & \ldots & 1 \\<br /> t_0 & t_1 & \ldots & t_n \\<br /> t_0^2 & t_1^2 & \ldots & t_n^2 \\<br /> \vdots & \vdots & \ddots & \vdots \\<br /> t_0^n & t_1^n & \ldots & t_n^n \\<br /> \end{array}<br /> \right|<br /> = \prod_{l,m: 0 \leq l<m \leq n} (t_m-t_l);<br /> \]

jest to tzw. wyznacznik Vandermonde'a. W rozważanej tu sytuacji

\[<br /> D=\left|<br /> \begin{array}{cccc}<br /> 1 & 1 & \ldots & 1 \\<br /> 1 & 2 & \ldots & 2^n \\<br /> 1 & 2^2 & \ldots & 2^{2n} \\<br /> \vdots & \vdots & \ddots & \vdots \\<br /> 1 & 2^n & \ldots & 2^{n^2} \\<br /> \end{array}<br /> \right|<br /> = V(1,2,4, \ldots, 2^n) = \prod_{l,m: 0 \leq l<m \leq n} (2^m-2^l) \neq 0.<br /> \]

Zatem układ równań (4) ma jednoznaczne rozwiązanie. Interesuje nas tylko niewiadoma $ a_0 $; wyraża się ona wzorem $ a_0 = D_0/D $, gdzie $ D_0 $ jest wyznacznikiem macierzy otrzymanej z macierzy układu (4) w wyniku zastąpienia jej skrajnej lewej kolumny (złożonej z samych jedynek) przez kolumnę złożoną z liczb znajdujących się po prawych stronach równań (4) . W konsekwencji $ D_0 $ także jest wyznacznikiem Vandermonde'a:

\[<br /> \begin{split}<br /> D=\left|<br /> \begin{array}{cccc}<br /> 1 & 1 & \ldots & 1 \\<br /> 1/2 & 2 & \ldots & 2^n \\<br /> 1/2^2 & 2^2 & \ldots & 2^{2n} \\<br /> \vdots & \vdots & \ddots & \vdots \\<br /> 1/2^n & 2^n & \ldots & 2^{n^2} \\<br /> \end{array}<br /> \right|<br /> & = V(\frac{1}{2},2,4, \ldots, 2^n) = \\<br /> & = \prod_{m: 1 \leq m \leq n} (2^m-\frac{1}{2})\cdot \prod_{l,m: 1 \leq l<m \leq n} (2^m-2^l).<br /> \end{split}<br /> \]

W takim razie

\[<br /> a_0=\frac{D_0}{D} = \prod_{m: 1 \leq m \leq n} \frac{2^m-\frac{1}{2}}{2^m-2^1} =<br /> \prod_{m=1}^n \left( \frac{1}{2} \cdot \frac{2^{m+1}-1}{2^m-1} \right).<br /> \]

Otrzymaliśmy ten sam iloczyn, co w końcówce poprzedniego rozwiązania. Wynik (wartość $ a_0 = P(0) $) — jak we wszystkich poprzednich rozwiązaniach.

XLVIII OM - I - Zadanie 7

Zawody matematyczne: 
XLVIII OM, 1996-1997
Etap: 
I

Obliczyć kres górny objętości czworościanów zawartych w kuli o danym promieniu $ R $, których jedną z krawędzi jest średnica tej kuli.

Rozwiązanie

Niech $ ABCD $ będzie jednym z rozważanych czworościanów. Przyjmijmy, że krawędź $ AB $ jest średnicą danej kuli. Oznaczmy odległość punktu $ C $ od prostej $ AB $ przez $ w $, a odległość punktu $ D $ od płaszczyzny $ ABC $ - przez $ h $. Objętość czworościanu $ ABCD $ jest równa

\[<br /> V = \frac{1}{3} \cdot\ \textrm{pole} (ABC) \cdot h = \frac{1}{3}( \frac{1}{2} \cdot |AB| \cdot w) \cdot h = \frac{1}{3} Rwh.<br /> \]

Oczywiście $ w \leq R $, $ h \leq R $, i wobec tego $ V \leq \frac{1}{3} R^3 $.

Czworościan $ ABCD $ był wybrany dowolnie; zatem kres górny objętości rozważanych czworościanów nie przekracza liczby $ \frac{1}{3} R^3 $.

Gdy $ ABC $ jest trójkątem prostokątnym równoramiennym o przeciwprostokątnej $ AB $, wówczas $ w = R $. Gdy z kolei $ ABD $ jest trójkątem prostokątnym równoramiennym o przeciwprostokątnej $ AB $, leżącym w płaszczyźnie prostopadłej do płaszczyzny $ ABC $, wówczas także $ h = R $. Gdy oba te warunki są spełnione, zachodzi równość $ V= \frac{1}{3} R^3 $.

Wniosek: kres górny rozważanych objętości jest równy $ \frac{1}{3} R^3 $.

XLVIII OM - I - Zadanie 8

Zawody matematyczne: 
XLVIII OM, 1996-1997
Etap: 
I

Niech $ a_n $ będzie liczbą wszystkich niepustych podzbiorów zbioru $ \{1,2,\ldots,6n\} $, których suma elementów daje przy dzieleniu przez 6 resztę 5 oraz niech $ b_n $ będzie liczbą wszystkich niepustych podzbiorów zbioru $ \{1,2,\ldots,7n\} $, których iloczyn elementów daje przy dzieleniu przez 7 resztę 5. Obliczyć iloraz $ a_n/b_n $.

Rozwiązanie

Sposób I

Dla skończonego zbioru liczb $ A $ symbole $ s(A) $ oraz $ p(A) $ będą oznaczały odpowiednio sumę oraz iloczyn wszystkich liczb w tym zbiorze. Niech $ n $ będzie ustaloną liczbą naturalną. Zgodnie z treścią zadania,

\[<br /> \begin{split}<br /> a_n = \textrm{liczba zbiorów}\ A \subset \{1,2,\ldots,6n\}\ \textrm{takich, że}\ s(A)\equiv 5 (\mathrm{mod} 6), \\<br /> b_n = \textrm{liczba zbiorów}\ B \subset \{1,2,\ldots,7n\}\ \textrm{takich, że}\ p(B) = 5 (\mathrm{mod} 7).<br /> \end{split}<br /> \]

Zauważmy, że w określeniu liczby $ b_n $ można ze zbioru $ \{1,2,\ldots,7n\} $ usunąć wszystkie wielokrotności liczby $ 7 $; jeśli bowiem zbiór $ B $ zawiera jakąkolwiek liczbę podzielną przez $ 7 $, to warunek $ p(B) \equiv 5 (\mathrm{mod} 7) $ na pewno nie jest spełniony. Przyjmując oznaczenia

\[<br /> \begin{split}<br /> X_k = \{6k+1, 6k+2, 6k+3, 6k+4, 6k+5, 6k+6\},\\<br /> Y_k = \{7k+1, 7k+2, 7k+3, 7k+4, 7k+5, 7k+6\},<br /> \end{split}<br /> \]

oraz

\[<br /> X = X_0 \cup X_1 \cup \ldots \cup X_{n-1} ( = \{1,2,\ldots,6n\}),\quad<br /> Y = Y_0 \cup Y_1 \cup \ldots \cup Y_{n-1},<br /> \]

można zatem przepisać określenie liczb $ a_n $ i $ b_n $, jak następuje:

\[<br /> \begin{split}<br /> a_n = \textrm{liczba zbiorów}\ A \subset X\ \textrm{takich, że}\ s(A)\equiv 5 (\mathrm{mod} 6), \\<br /> b_n = \textrm{liczba zbiorów}\ B \subset Y\ \textrm{takich, że}\ p(B) \equiv 5 (\mathrm{mod} 7).<br /> \end{split}<br /> \]

Weźmy pod uwagę dowolną liczbę $ x \in X $. Jest ona elementem dokładnie jednego ze zbiorów $ X_0, X_1,\ldots, X_{n-1} $. Liczba $ 3^x $ nie dzieli się przez $ 7 $, a więc w każdym ze zbiorów $ Y_0, Y_1, \ldots, Y_{n-1} $ istnieje dokładnie jeden element przystający do $ 3^x $ modulo $ 7 $. Spośród nich wybieramy element $ y $ należący do zbioru $ Y_k $ o tym samym numerze $ k $, co numer zbioru $ X_k $ zawierającego $ x $. Oznaczmy ten element $ y $ przez $ h(x) $. W ten sposób została określona funkcja $ h: X \to Y $ o własności:

\[<br /> \qquad (2) \textrm{jeśli}\ x \in X_k,\ \textrm{to}\ h(x) \in Y_k,\ h(x) \equiv 3^x (\mathrm{mod} 7).<br /> \]

Wykażemy, że jest ona różnowartościowa.

Przypuśćmy, że $ h(u) = h(v) $ dla pewnych liczb $ u,v \in X $. Przyjmijmy, że $ u \leq v $ oraz $ u \in X_k $, $ v \in X_l $. Wówczas $ h(u) \in Y_k $, $ h(v) \in Y_l $, więc z równości $ h(u) = h(v) $ wynika, że $ k=l $, a ponadto

\[<br /> \qquad (3) 3^u \equiv 3^v (\mathrm{mod} 7).<br /> \]

Kluczem do dalszych rozważań będzie następująca, łatwa do sprawdzenia, własność:

\[<br /> \qquad (4) 3^6 \equiv 1 (\mathrm{mod} 7);\ 3^r \not\equiv 1 (\mathrm{mod} 7)\ \textrm{dla}\ r = 1,2,3,4,5.<br /> \]

Skoro $ u \leq v $ oraz $ u,v \in X_k $, zatem $ 0 \leq v-u \leq 5 $. Mnożymy związek (3) stronami przez liczbę całkowitą $ 3^{6(k+1)-u} $:

\[<br /> 3^{6(k+1)} \equiv 3^{6(k+1)} \cdot 3^{v-u} (\mathrm{mod} 7).<br /> \]

Stąd na podstawie wzorów (4) wnosimy najpierw, że $ 1 \equiv 3^{v-u} (\mathrm{mod} 7) $, a następnie, że $ v - u = 0 $, czyli $ u = v $. Różnowartościowość funkcji $ h $ została wykazana.

Funkcja $ h $ odwzorowuje zbiór $ X $, liczący $ 6n $ elementów, w zbiór $ Y $, liczący także $ 6n $ elementów. Stąd wniosek, że jest ona różnowartościowym odwzorowaniem zbioru $ X $ na cały zbiór $ Y $.

Niech teraz $ A $ będzie dowolnym niepustym podzbiorem zbioru $ X $ i niech $ h(A) $ będzie obrazem zbioru $ A $ w odwzorowaniu $ h $. Udowodnimy, że zachodzi implikacja:

\[<br /> \qquad (5) \textrm{jeżeli}\ s(A) \equiv r(\mathrm{mod} 6),\ 0 \leq r<6,\ \textrm{to}\ p(h(A)) \equiv 3^{r} (\mathrm{mod} 7).<br /> \]

Przyjmijmy, że $ A = \{x_1,\ldots,x_m\} $. Zatem $ h(A) =\{y_1, \ldots, y_m\} $, gdzie

\[<br /> y_i = h(x_i) \equiv 3^{x_i} (\mathrm{mod} 7)<br /> \]

(por. (2)). Jeżeli $ s(A) \equiv r (\mathrm{mod} 6) $, $ 0 \leq r<6 $, to istnieje taka liczba całkowita $ q \geq 0 $, że $ x_1 + \ldots + x_m = 6q + r $. Korzystając ponownie z pierwszego wzoru (4) obliczamy:

\[<br /> p(h(A)) = y_1 \cdot \ldots \cdot y_m \equiv 3^{x_1} \cdot \ldots \cdot 3^{x_m}= 3^{x_1 + \ldots + x_m} = 3^{6q} \cdot 3^r \equiv 3^r (\mathrm{mod} 7);<br /> \]

to dowodzi słuszności implikacji (5).

Korzystając z własności (4) nietrudno się przekonać, że $ 3^5 \equiv 5 (\mathrm{mod} 7) $ oraz $ 3^r \not\equiv 5 (\mathrm{mod} 7) $ dla $ r \neq 5 \ (0 \leq r<6) $. Ze zdania (5) wynika zatem, że

\[<br /> s(A) \equiv 5 (\mathrm{mod} 6)\ \textrm{wtedy i tylko wtedy, gdy}\ p(h(A)) \equiv 5 (\mathrm{mod} 7).<br /> \]

A ponieważ $ h $ jest wzajemnie jednoznacznym odwzorowaniem zbioru $ X $ na $ Y $, wnosimy stąd, że w zbiorze $ X $ jest tyle samo podzbiorów $ A $ spełniających warunek $ s(A) \equiv 5 (\mathrm{mod} 6) $, ile jest w zbiorze $ Y $ podzbiorów $ B $ spełniających warunek $ p(B) \equiv 5 (\mathrm{mod} 7) $. To znaczy, że $ a_n = b_n $.

Otrzymujemy odpowiedź: dla każdej liczby naturalnej $ n $ iloraz $ a_n/b_n $ jest równy $ 1 $.

Uwaga: Własność (5) można tak wyrazić słowami —-- sugestywnie, choć nie ściśle: odwzorowanie $ h $ „przeprowadza'' dodawanie modulo $ 6 $ na mnożenie modulo $ 7 $. Czytelnicy, którym nie są obce najprostsze fakty oraz język teorii grup, wiedzą, że zbiór $ \{0,\ldots,5\} $ jest grupą przy działaniu dodawania modulo $ 6 $, a zbiór $ \{1,\ldots,6\} $ jest grupą przy działaniu mnożenia modulo $ 7 $.

Wspomniana własność, już w ścisłej terminologii, mówi, że operacja, która liczbie $ x \in \{0,\ldots ,5\} $ przyporządkowuje resztę z dzielenia liczby $ 3^x $ przez 7, jest {\it izomorfizmem} pierwszej z tych grup na drugą - i na tym spostrzeżeniu opiera się całe powyższe rozwiązanie.

Istotną rolę gra przy tym fakt, że potęgi trójki $ 3^0, 3^1, \ldots, 3^5 $ dają przy dzieleniu przez 7 różne reszty - por. wzory (4) . Tę samą własność ma też piątka; można więc wszędzie konsekwentnie zastąpić potęgowanie o podstawie 3 potęgowaniem o podstawie 5, i tak zmodyfikowane rozwiązanie też będzie poprawne.

Sposób II

Zachowajmy z poprzedniego rozwiązania oznaczenia: $ s(A),\ p(A),\ X_k,\ Y_k $ oraz

\[<br /> X = X_0 \cup X_1 \cup \ldots \cup X_{n-1},\quad Y = Y_0 \cup Y_1 \cup \ldots \cup Y_{n-1}.<br /> \]

Powtarzamy początkowy fragment tamtego rozwiązania i dochodzimy do wzorów (1) . Celem rozważań będzie wyprowadzenie zależności rekurencyjnych dla ciągów $ (a_n) $ i $ (b_n) $ (przy zmieniającym się $ n $).

Przyjmijmy dodatkowo oznaczenia:

\[<br /> \begin{split}<br /> &a(n,r) =\ \textrm{liczba zbiorów}\ A \subset X\ \textrm{takich, że}\ s(A) \equiv r (\mathrm{mod} 6)\\<br /> &\qquad \textrm{(dla}\ r = 0,1,2,3,4,5)\ \textrm{oraz} \\<br /> &b(n,q) = \textrm{liczba zbiorów}\ B \subset Y\ \textrm{takich, że}\ p(B) \equiv q (\mathrm{mod} 7)\\<br /> & \qquad \textrm{(dla}\ q = 1,2,3,4,5,6);\ \textrm{tak więc}<br /> \end{split}<br /> \]
\[<br /> a_n=a(n,5), \ b_n = b(n,5).<br /> \]

Nie ograniczamy przy tym uwagi do zbiorów niepustych; dla $ r = 0 $ zbiór $ A $ może być pusty; podobnie dla $ q = 1 $ zbiór $ B $ może być pusty.

(Przyjmujemy zwykłą umowę, że $ s(\varnothing) = 0,\ p(\varnothing) = 1 $).

Ustalmy liczbę naturalną $ n $ i weźmy pod uwagę analogiczne zagadnienie dla liczby $ n+1 $. Oznaczmy:

\[<br /> \widetilde{X} = X_0\cup X_1\cup\ldots \cup X_{n-1}\cup X_{n},\ \widetilde{Y} = Y_0\cup Y_1\cup\ldots \cup Y_{n-1}\cup Y_{n}.<br /> \]

Każdy zbiór $ \widetilde{A}\subset \widetilde{X} $ jest sumą rozłącznych zbiorów $ A_0 $ i $ A $, gdzie $ A_0 = \widetilde{A}\cap X_0 $, $ A = \widetilde{A} \cap (X_1 \cup \ldots \cup X_n) $; przy tym $ s(\widetilde{A}) = s (A_0) + s(A) $. Jeśli reszta z dzielenia liczby $ s(A_0) $ przez $ 6 $ wynosi $ j $, to reszta z dzielenia liczby $ s(A) $ przez $ 6 $ wynosi $ r \ominus j $ tym symbolem będziemy oznaczać jedyną liczbę $ j' \in \{0,1,\ldots,5\} $ spełniającą warunek $ j+j' \equiv r (\mathrm{mod} 6) $. (Działanie $ \ominus $ jest więc namiastką zwykłego odejmowania).

Ustalmy zbiór $ \widetilde{A}\subset \widetilde{X} $ oraz ustalmy na chwilę wartość reszty $ j \in \{0,\ldots,5\} $. Policzymy, ile jest sposobów przedstawienia zbioru $ \widetilde{A} $ w postaci sumy $ A_0\cup A $, gdzie $ A_0\subset X_0 $, $ A \subset (X_1\cup \ldots \cup X_n) $, $ s(A_0) \equiv j $, $ s(A) \equiv r\ominus j (\mathrm{mod} 6) $.

Zbiór $ A_0 $ można wybrać na $ a(1,j) $ sposobów. Liczba podzbiorów $ A $ zbioru $ X_1\cup\ldots\cup X_n $ spełniających warunek $ s(A) = r \ominus j (\mathrm{mod} 6) $ jest dokładnie taka sama, jak liczba podzbiorów zbioru $ X_0\cup\ldots\cup X_{n-1} $ spełniających analogiczny warunek. Wynika to stąd, że zbiór $ X_1 \cup \ldots \cup X_n $ - to po prostu zbiór $ X_0\cup\ldots\cup X_{n-1} $ przesunięty o $ 6 $ jednostek. Mamy zatem $ a(n, r\ominus j) $ możliwości wyboru zbioru $ A $. Dla ustalonej wartości $ j $ daje to $ a(1, j) \cdot a(n, r \ominus j) $ sposobów przedstawienia zbioru $ \widetilde{A} $ w rozważanej postaci.

Liczba wszystkich zbiorów $ \widetilde{A} $ zawartych w zbiorze $ \widetilde{X} $ oraz spełniających warunek $ s(\widetilde{A}) \equiv r (\mathrm{mod} 6) $ jest sumą takich iloczynów przy zmieniającym się $ j=0,\ldots,5 $:

\[<br /> \qquad (6) a(n+1,r) = \sum_{j=0}^5 a(1,j) \cdot a(n, r \ominus j).<br /> \]

Dokładnie takie samo rozumowanie prowadzi do podobnego wzoru dla $ b(n+1,q) $:

\[<br /> \qquad (7) b(n+1,q) = \sum_{i=0}^6 b(1,i) \cdot b(n, q\oslash i);<br /> \]

literki $ q $ oraz $ i $ oznaczają teraz możliwe reszty z dzielenia przez $ 7 $ (jak pamiętamy, reszta zerowa została wykluczona); zaś dla $ q,i \in \{1,2,...,6\} $ symbol $ q\oslash i $ oznacza jedyną liczbę $ i' \in \{1,2,\ldots,6\} $ spełniającą warunek $ i\cdot i' \equiv q (mod 7) $. (Działanie $ \oslash $ jest namiastką dzielenia). Wyprowadzenie wzoru (7) tym się tylko różni od wyprowadzenia wzoru (6), że zamiast zbiorów $ X_0 $ i $ X_1\cup\ldots\cup X_n $ rozważa się zbiory $ Y_0 $ i $ Y_1 \cup\ldots \cup Y_n $, zamiast sum $ s(A) $ — iloczyny $ p(B) $, a zamiast przystawania modulo $ 6 $ — przystawanie modulo $ 7 $.

Wartości $ a(1,j) $ oraz $ b(1,i) $ można wyznaczyć empirycznie, wypisując wszystkie możliwe podzbiory zbiorów $ X_0 $ oraz $ Y_0 $. (Można je też wyznaczyć metodą mniej pracochłonną - pozostawiamy to sprytowi Czytelnika.)

Oto wynik zliczania:

\[<br /> a(1,j)=\left\{<br /> \begin{array}{ll}<br /> 10&\textrm{dla}\ j=1,2,4,5, \\<br /> 12&\textrm{dla}\ j=0,3,<br /> \end{array}<br /> \right.<br /> \quad<br /> b(1,i)=\left\{<br /> \begin{array}{ll}<br /> 10&\textrm{dla}\ j=2,3,4,5, \\<br /> 12&\textrm{dla}\ j=1,6.<br /> \end{array}<br /> \right.<br /> \]

Podstawiając te wartości do wzorów (6) oraz (7) dostajemy kolejne wzory

\[<br /> \begin{split}<br /> a(n+1,r) &= \sum_{j=1,2,4,5} 10 \cdot a(n, r\ominus j) + \sum_{j=0,3} 12\cdot a(n, r\ominus j) =\\<br /> &= 10 \sum_{j=0}^5 a(n,r\ominus j) + 2a(n,r)+2a(n,r\ominus 3)<br /> \end{split}<br /> \]

(bowiem $ r\ominus 0 = r $) oraz

\[<br /> \begin{split}<br /> b(n+1,q) &= \sum_{i=2,3,4,5} 10 \cdot b(n, q\oslash i) + \sum_{i=1,6} 12\cdot b(n, q\oslash i) =\\<br /> &= 10 \sum_{i=1}^6 b(n,q\oslash i) + 2b(n,q)+2b(n,q\oslash 6)<br /> \end{split}<br /> \]

(bowiem $ q\oslash 1 = q $).

Gdy $ j $ przebiega wartości od $ 0 $ do $ 5 $, czyli wszystkie możliwe reszty z dzielenia przez $ 6 $, wówczas także $ r \ominus j $ przebiega wszystkie możliwe reszty z dzielenia przez $ 6 $ (przy ustalonej wartości $ r $). Zatem suma $ \sum_{j=0}^5 a(n, r \ominus j) $ jest liczbą wszystkich podzbiorów zbioru $ X = X_0 \cup \ldots \cup X_{n-1} $.

Gdy $ i $ przebiega wartości od $ 1 $ do $ 6 $, czyli wszystkie {\it niezerowe} reszty z dzielenia przez $ 7 $, wówczas $ q \oslash i $ przebiega wszystkie {\it niezerowe} reszty z dzielenia przez $ 7 $ (przy ustalonej wartości $ q $). Zatem suma $ \sum_{i=1}^6 b(n, q \oslash i) $ jest liczbą wszystkich podzbiorów zbioru $ Y = Y_0 \cup \ldots \cup Y_{n-1} $; korzystamy tu z faktu, że dla każdego zbioru $ B \subset Y $ wartość $ p(B) $ jest niepodzielna przez $ 7 $ (wielokrotności siódemki zostały odrzucone przy definiowaniu zbioru $ Y $).

Zbiory $ X $ i $ Y $ są ($ 6n $)-elementowe; mają zatem po $ 2^{6n} $ podzbiorów. Uzyskane wzory przybierają prostszą postać

\[<br /> \begin{split}<br /> a(n+1, r) = 10 \cdot 2^{6n} + 2a(n,r) + 2a(n,r \ominus 3),\\<br /> b(n+1, q) = 10 \cdot 2^{6n} + 2b(n,q) + 2b(n,q \ominus 6).<br /> \end{split}<br /> \]

Zauważmy, że
$ r \ominus 3 =<br /> \left\{<br /> \begin{array}{ll}<br /> 5 & \textrm{dla}\ r=2, \\<br /> 2 & \textrm{dla}\ r=5,<br /> \end{array}<br /> \right. $
oraz także
$ q \oslash 6 =<br /> \left\{<br /> \begin{array}{ll}<br /> 5 & \textrm{dla}\ q=2, \\<br /> 2 & \textrm{dla}\ q=5.<br /> \end{array}<br /> \right. $

Dostajemy więc zależności

\[<br /> \begin{split}<br /> a(n+1,2)=10 \cdot 2^{6n} + 2a(n,2) + 2a(n,5), \\<br /> a(n+1,5)=10 \cdot 2^{6n} + 2a(n,5) + 2a(n,2), \\<br /> b(n+1,2)=10 \cdot 2^{6n} + 2b(n,2) + 2b(n,5), \\<br /> b(n+1,5)=10 \cdot 2^{6n} + 2b(n,5) + 2b(n,2).<br /> \end{split}<br /> \]

Ponieważ $ a(1,2) = a(1,5) = 10 $ oraz $ b(1,2) =b(1,5) = 10 $, zatem pierwsze dwa wzory (spośród czterech wypisanych powyżej) prowadzą przez indukcję do wniosku, że $ a(n,2) = a(n,5) = a_n $ dla wszystkich $ n $, natomiast dwa dalsze wzory dają wniosek, że $ b(n,2) = b(n,5) = b_n $ dla wszystkich $ n $. Wzór drugi oraz wzór czwarty możemy teraz tak przepisać:

\[<br /> a_{n+1} = 10 \cdot 2^{6n} + 4 a_n,\ b_{n+1}=10 \cdot 2^{6n}+4b_n.<br /> \]

Tak więc ciągi $ (a_n) $ i $ (b_n) $ spełniają dokładnie tę samą zależność rekurencyjną. A skoro $ a_1 = b_1 = 10 $, przez indukcję wnosimy, że $ a_n = b_n $ dla wszystkich $ n $. Wniosek: iloraz $ a_n/b_n $ jest równy $ 1 $.

XLVIII OM - I - Zadanie 9

Zawody matematyczne: 
XLVIII OM, 1996-1997
Etap: 
I

Wyznaczyć wszystkie funkcje $ f: \langle 1,\ \infty) \to \langle 1,\ \infty) $, które spełniają następujące warunki:

  • [(i)] $ f(x+1) = \frac{(f(x))^2-1}{x} $ dla $ x \geq 1 $;
  • [(ii)] funkcja $ g(x)=\frac{f(x)}{x} $ jest ograniczona.

Rozwiązanie

Sposób I

Łatwo zauważyć, że podane warunki są spełnione przez funkcję $ f(x) = x + 1 $. Pokażemy, że nie ma innych takich funkcji.

Załóżmy więc, że $ f: \langle 1,\ \infty) \to \langle 1,\ \infty) $ jest dowolną funkcją spełniającą warunki (i) i (ii). Określamy funkcję $ h: \langle 1,\ \infty) \to \langle 0, \infty) $ wzorem

\[<br /> \qquad (1) f(x)=(x+1)h(x)\ \textrm{dla} \ x \geq 1.<br /> \]

Wówczas $ h(x) =\frac{f(x)}{x+1}= \frac{x}{x+1} \cdot g(x) $ i wobec ograniczoności funkcji $ g $ (warunek (ii)) widzimy, że także $ h $ jest funkcją ograniczoną.

Z warunku (i) wynika zależność

\[<br /> \qquad (2) h(x+1)= \frac{f(x+1)}{x+2} = \frac{(f(x))^2-1}{x(x+2)} \ \textrm{dla} \ x \geq 1;<br /> \]

stąd

\[<br /> \begin{split}<br /> \qquad (3) h(x+1)-1= & \frac{(f(x))^2-1-x(x+2)}{x(x+2)}= \frac{(f(x))^2-(x+1)^2}{x(x+2)}=\\<br /> &= \frac{f(x)-(x+1)}{x} \cdot \frac{f(x)+(x+1)}{x+2}=\\<br /> &= \frac{(x+1)(h(x)-1)}{x} \cdot \frac{f(x)+x+1}{x+2}.<br /> \end{split}<br /> \]

Przyjmijmy $ \varphi(x) = \frac{h(x)-1}{x} $; równość (3) , podzielona stronami przez $ x + 1 $, przybiera postać

\[<br /> \varphi(x+1)=\varphi(x) \cdot \frac{f(x)+x+1}{x+2} \ \textrm{dla}\ x \geq 1.<br /> \]

Ułamek po prawej stronie ma wartość nie mniejszą od $ 1 $ (bo wartości funkcji $ f $ z założenia leżą w przedziale $ \langle 1,\ \infty) $). Zatem

\[<br /> |\varphi(x+1)| \geq |\varphi(x)| \ \textrm{dla}\ x \geq 1.<br /> \]

Dla dowolnie wybranej liczby $ x_0 \in \langle 1,\ \infty) $ otrzymujemy stąd ciąg nierówności

\[<br /> \qquad (4) |\varphi(x_0)| \leq |\varphi(x_0+1)| \leq | \varphi(x_0 + 2)| \leq |\varphi(x_0 + 3)| \leq \ldots.<br /> \]

Wcześniej stwierdziliśmy, że funkcja $ h $ jest ograniczona. Z określenia funkcji $ \varphi $, wynika więc, ze $ \lim_{x \to \infty} \varphi(x) = 0 $. To znaczy, że ciąg (4) jest niemalejącym ciągiem liczb nieujemnych, zbieżnym do zera. A to jest możliwe tylko wówczas, gdy wszystkie wyrazy tego ciągu są zerami; w szczególności $ \varphi(x_0)=0 $.

Liczba $ x_0 $ była dowolnie wybrana z przedziału $ \langle 1,\ \infty) $. Stąd wniosek, że $ \varphi $ jest funkcją tożsamościowo równą zeru. Z jej określenia oraz z równości (1) wnosimy kolejno, że $ h(x) = 1 $ oraz $ f(x) = x +1 $ dla $ x \geq 1 $.

Jak zauważyliśmy na początku, funkcja $ f(x) = x + 1 $ spełnia oba zadane warunki; jest więc jedynym rozwiązaniem rozpatrywanego zagadnienia.

Sposób II

Rozpoczynamy, jak w sposobie pierwszym: zakładamy, że funkcja $ f $ spełnia postulowane warunki, określamy funkcję $ h $ wzorem (1) , zauważamy, że $ h $ jest funkcją ograniczoną o wartościach dodatnich, i dochodzimy do wzoru (2) . Zastępujemy w nim $ f(x) $ przez prawą stronę wzoru (1) i dostajemy związek

\[<br /> h(x+1)= \frac{((x+1)h(x))^2-1}{x(x+2)} = \frac{(x^2+2x)(h(x))^2+(h(x))^2-1}{x^2+2x},<br /> \]

czyli

\[<br /> \qquad (5) h(x + 1) = (h(x))^2+ \frac{(h(x))^2-1}{x^2+2x} \ \textrm{dla}\ x \geq 1.<br /> \]

Jeżeli dla pewnej liczby $ x \geq 1 $ zachodzi nierówność $ h(x) > 1 $, to oczywiście także $ (h(x))^2 > 1 $; licznik ułamka po prawej stronie wzoru (5) jest dodatni, mianownik też, więc otrzymujemy nierówność $ h(x + 1) > (h(x))^2 $.

Jeżeli dla pewnej liczby $ x \geq 1 $ mamy $ h(x) < 1 $, to także $ (h(x))^2 < 1 $; korzystamy tu ze spostrzeżenia, że $ h(x) > 0 $ dla wszystkich $ x \geq 1 $. Licznik ułamka we wzorze (5) jest teraz ujemny i dostajemy nierówność $ h(x + 1) < (h(x))^2 $.

Wykazaliśmy więc, że:

\[<br /> \begin{split}<br /> \textrm{jeśli}\ h(x)>1,\ \textrm{to}\ h(x + 1) > (h(x))^2> 1; \\<br /> \textrm{jeśli}\ h(x)<1,\ \textrm{to}\ h(x + 1) < (h(x))^2 <1.<br /> \end{split}<br /> \]

Chcemy dowieść, że funkcja $ h $ jest tożsamościowo równa $ 1 $. Przypuśćmy, że istnieje liczba $ x_0 \geq 1 $, dla której $ h(x_0) \neq 1 $. Uzyskane przed chwilą implikacje prowadzą przez oczywistą indukcję do następujących wniosków:

\[<br /> \begin{split}<br /> & \qquad (6) \textrm{jeśli}\ h(x_0)>1,\ \textrm{to}\ h(x_0+n)> (h(x_0))^{2^n}\ \textrm{dla}\ n = 1,2,3,\ldots ;\\<br /> & \qquad (7) \textrm{jeśli}\ h(x_0)<1,\ \textrm{to}\ h(x_0+n)< (h(x_0))^{2^n}\ \textrm{dla}\ n = 1,2,3,\ldots.<br /> \end{split}<br /> \]

W sytuacji opisanej przez nierówności (6) ciąg $ ((h(x_0))^{2^n}:\ n= 1,2,3,\ldots) $ dąży do nieskończoności; daje to sprzeczność z ograniczonością funkcji $ h $.

W sytuacji opisanej przez nierówności (7) mamy, w myśl określenia (1) ,

\[<br /> \qquad (8) f(x_0+n)=(x_0+n+1)h(x_0+n)< (x_0+n+1)(h(x_0))^{2^n}\ \textrm{dla}\ n=1,2,3,\ldots.<br /> \]

W otrzymanym iloczynie czynnik $ (x_0 + n + 1) $ dąży do nieskończoności, ale drugi czynnik $ (h(x_0))^{2^n} $ dąży znacznie szybciej do zera. Temu nieprecyzyjnemu sformułowaniu nadajemy bardziej ścisłą postać na przykład powołując się na {\it nierówność Bernoulli'ego}:

\[<br /> \qquad (9) (1 + \delta)^m \geq 1 + m\delta\ \textrm{dla}\ \delta \geq -1;\ m = 1,2,3,\ldots.<br /> \]

Liczba dodatnia $ h(x_0) $ jest mniejsza od $ 1 $, więc może być zapisana w postaci $ 1/(1 + \delta) $, gdzie $ \delta>0 $.

Korzystając z tego, że $ 2^n \geq n^2 $ dla $ n \geq 4 $ (łatwy dowód indukcyjny) otrzymujemy na podstawie związków (8) i (9) :

\[<br /> f(x_0+n) < \frac{x_0+1+n}{(1+\delta)^{2^n}} \leq \frac{x_0+1+n}{1+2^n\delta} \leq \frac{x_0+1+n}{1+n^2\delta} =<br /> \frac{\frac{x_0+1}{n^2}+\frac{1}{n}}{\frac{1}{n^2} + \delta} \<br /> \textrm{dla}\ n \geq 4.<br /> \]

Gdy $ n $ dąży do nieskończoności, ostatni iloraz dąży do zera. Dostajemy sprzeczność z warunkiem, że wartości funkcji $ f $ leżą w przedziale $ \langle 1,\ \infty) $.

Przypuszczenie, że dla pewnego $ x_0 \geq 1 $ wartość $ h(x_0) $ jest różna od $ 1 $, prowadzi w każdym przypadku do sprzeczności. Zatem $ h(x) = 1 $ dla wszystkich $ x \geq 1 $, i w konsekwencji (por. wzór (1) ) $ f(x) = x + 1 $ dla $ x \geq 1 $.

Uwaga: Konkluzję rozwiązania można zapisać tak: funkcja $ f(x)=x + 1 $ jest jedyną funkcją $ f: \langle 1,\ \infty) \to \langle 0,\ \infty) $ spełniającą dane w warunku (i) równanie funkcyjne oraz podwójną nierówność

\[<br /> 1 \leq f(x) \leq cx\ \textrm{dla}\ x \geq 1,<br /> \]

dla pewnej stałej dodatniej $ c $.

Otóż implikacje (6) i (7) , otrzymane dla funkcji $ h(x) = f(x)/(x + 1) $ w drugim sposobie rozwiązania, pozwalają uzyskać następujące wzmocnienie tego twierdzenia: $ f(x)=x + 1 $ jest jedyną funkcją $ f: \langle 1,\ \infty) \to \langle 0,\ \infty) $ spełniającą równanie (i) wraz z oszacowaniami:

\[<br /> a^{x^\alpha} \leq f(x) \leq b^{x^\beta}\ \textrm{dla}\ x \geq 1,<br /> \]

dla pewnych stałych dodatnich $ a,\ b,\ \alpha,\ \beta $. Szczegółowe uzasadnienie pozostawiamy Czytelnikowi.

XLVIII OM - I - Zadanie 10

Zawody matematyczne: 
XLVIII OM, 1996-1997
Etap: 
I

Punkty $ P $, $ Q $ leżą wewnątrz trójkąta ostrokątnego $ ABC $, przy czym $ |\measuredangle ACP| = |\measuredangle BCQ| $ oraz $ |\measuredangle CAP| = |\measuredangle BAQ| $. Punkty $ D $, $ E $, $ F $ są rzutami prostokątnymi punktu $ P $ odpowiednio na boki $ BC $, $ CA $, $ AB $. Dowieść, że kąt $ DEF $ jest prosty wtedy i tylko wtedy, gdy punkt $ Q $ jest punktem przecięcia wysokości trójkąta $ BDF $.

Rozwiązanie

Sposób I

Dane w założeniach równości

\[<br /> |\measuredangle ACP| = |\measuredangle BCQ| \ \textrm{oraz} \ |\measuredangle CAP| = |\measuredangle BAQ|<br /> \]

są równoważne równościom

\[<br /> |\measuredangle ACQ| = |\measuredangle BCP| \ \textrm{oraz} \ |\measuredangle CAQ| = |\measuredangle BAP|.<br /> \]

Kąty $ ACP $ i $ BCQ $, rozpatrywane jako obszary płaszczyzny, mogą być przy tym rozłączne (jak na rysunku 6), bądź też mogą na siebie nachodzić; nie ma to żadnego znaczenia. Podobna uwaga odnosi się do każdej z pozostałych trzech par kątów figurujących w związkach (1) i (2).

Oznaczmy przez $ U $, $ V $, $ W $ punkty symetryczne do $ P $ odpowiednio względem prostych $ BC $, $ CA $, $ AB $. Tak więc $ |CU| = |CP| = |CV| $ oraz $ |AW| = |AP| = |AV| $, a ponadto

\[<br /> \qquad (3) |\measuredangle BCU| = |\measuredangle BCP| \ \textrm{oraz} \ |\measuredangle BAW| = |\measuredangle BAP|,<br /> \]

i podobnie

\[<br /> \qquad (4) |\measuredangle ACV| = |\measuredangle ACP| \ \textrm{oraz}\ |\measuredangle CAV| = |\measuredangle CAP|.<br /> \]

Korzystając z pierwszej równości (3), pierwszej równości (2), pierwszej równości (4) i pierwszej równości (1) obliczamy:

\[<br /> |\measuredangle UCQ| = |\measuredangle BCU| + |\measuredangle BCQ| = |\measuredangle BCP| + |\measuredangle BCQ| = |\measuredangle ACQ| + |\measuredangle BCQ|,<br /> \]
\[<br /> |\measuredangle VCQ| = |\measuredangle ACV| + |\measuredangle ACQ| = |\measuredangle ACP| + |\measuredangle ACQ| = |\measuredangle BCQ| + |\measuredangle ACQ|.<br /> \]

Kąty $ UCQ $ i $ VCQ $ są więc równe. (Każdy z nich ma miarę $ |\measuredangle ACB| $; ta informacja nie będzie wszelako przydatna).

Wiemy także, że $ |CU| = |CV| $. Stąd wynika, że trójkąt $ UCQ $ przystaje do trójkąta $ VCQ $, i wobec tego $ |QU| = |QV| $.

Analogicznie — korzystając z drugich równości (3), (2), (4), (1) - wykazujemy, że kąty $ WAQ $ i $ VAQ $ są równe; wiedząc, że $ |AW| = |AV| $, wnosimy stąd, że trójkąt $ WAQ $ przystaje do trójkąta $ VAQ $, a zatem $ |QW| = |QV| $.

W takim razie punkt $ Q $ jest środkiem okręgu opisanego na trójkącie $ UVW $. Jednokładność o środku $ P $ i skali $ 1/2 $ przekształca go na okrąg $ \omega $ opisany na trójkącie $ DEF $; środkiem okręgu $ \omega $ jest środek $ S $ odcinka $ PQ $.

Wypiszemy teraz ciąg zdań, z których każde kolejne jest równoważne poprzedniemu:

  • $ Q $ jest punktem przecięcia wysokości trójkąta $ BDF $;
  • $ QD\perp FB $ oraz $ QF\perp BD $;
  • $ QD\parallel PF $ oraz $ QF \parallel PD $;
  • czworokąt $ PDQF $ jest równoległobokiem;
  • środek odcinka $ DF $ pokrywa się z punktem $ S $;
  • odcinek $ DF $ jest średnicą okręgu $ \omega $;
  • kąt $ DEF $ jest prosty.

Równoważność między zdaniem pierwszym i ostatnim jest tezą zadania.

Sposób II

Jak poprzednio, przepisujemy równości (1) (dane jako warunek zadania) w postaci (2). Oznaczmy rzuty prostokątne punktu $ P $ na boki $ BC $, $ CA $, $ AB $ odpowiednio przez $ K $, $ L $, $ M $. Z równości (1) i (2) wynika, że trójkąt prostokątny $ ECP $ jest podobny do trójkąta $ KCQ $, trójkąt $ EAP $ — do trójkąta $ MAQ $, trójkąt $ LCQ $ - do $ DCP $, a trójkąt $ LAQ $ - do $ FAP $ (rysunek 7). Dostajemy więc proporcje

\[<br /> \frac{|CE|}{|CK|}=\frac{|CP|}{|CQ|}=\frac{|CD|}{|CL|}\<br /> \textrm{oraz}\<br /> \frac{|AE|}{|AM|}=\frac{|AP|}{|AQ|}=\frac{|AF|}{|AL|}.<br /> \]

Zatem $ |CE|\cdot|CL|=|CD|\cdot|CK| $ oraz $ |AE|\cdot|AL| = |AF|\cdot|AM| $. Tak więc punkty $ E $, $ L $, $ D $, $ K $ leżą na jednym okręgu, i podobnie punkty $ E $, $ L $, $ F $, $ M $ leżą na jednym okręgu. Środkiem pierwszego z tych okręgów jest punkt przecięcia symetralnych odcinków $ EL $ i $ DK $, a środkiem drugiego - punkt przecięcia symetralnych odcinków $ EL $ i $ FM $.

Zauważmy teraz, że symetralne tych trzech odcinków ($ DK $, $ EL $, $ FM $) przecinają się w jednym punkcie; jest nim środek $ S $ odcinka $ PQ $. Stąd wynika, że owe dwa wzmiankowane okręgi to jeden i ten sam okrąg. Wniosek: istnieje okrąg $ \omega $ przechodzący przez punkty $ D $, $ E $, $ F $, $ K $, $ L $, $ M $.

Jak w pierwszym sposobie, wypisujemy ciąg kolejno równoważnych zdań:

  • $ Q $ jest punktem przecięcia wysokości trójkąta $ BDF $;
  • punkt $ D $ leży na prostej $ QM $, a punkt $ F $ leży na prostej $ QK $;
  • kąty $ DKF $ oraz $ DMF $ są proste;
  • odcinek $ DF $ jest średnicą okręgu $ \omega $;
  • kąt $ DEF $ jest prosty.

Równoważność między zdaniem pierwszym i ostatnim jest tezą zadania.

Uwaga 1: W obu tych rozwiązaniach kluczową rolę grają własności okręgu $ \omega $ opisanego na trójkącie $ DEF $. Aż do momentu uzyskania tych własności rozumowanie jest niezależne od spełnienia (lub niespełnienia) warunków, których równoważność należy udowodnić. Przy tym założenie ostrokątności trójkąta $ ABC $ nie jest potrzebne (w przypadku trójkąta rozwartokątnego trzeba jedynie mówić o rzutach punktów $ P $ i $ Q $ na proste $ BC $, $ CA $, $ AB $, niekoniecznie na boki trójkąta); w każdym przypadku rzuty punktów $ P $ i $ Q $ na te proste leżą na okręgu $ \omega $, którego środkiem jest środek odcinka $ PQ $.

Uwaga 2: Pierwsza równość (1) wyraża fakt, że proste $ CP $ i $ CQ $ są położone symetrycznie względem dwusiecznej kąta $ BCA $; mówimy, że te proste są {\it izogonalne} (względem kąta $ BCA $). Druga równość (1) orzeka, że proste $ AP $ i $ AQ $ są izogonalne względem kąta $ CAB $. Własności okręgu $ \omega $ są konsekwencją tych dwóch warunków izogonalności.

Nietrudno pokazać, że automatycznie jest wówczas spełniony trzeci warunek izogonalności: proste $ BP $ i $ BQ $ są izogonalne względem kąta $ ABC $. Oto uzasadnienie: punkty $ D $, $ F $, $ M $, $ K $ leżą na okręgu $ \omega $, więc zachodzi równość $ |BD|\cdot|BK| = |BF| \cdot |BM| $; wynika z niej, że czworokąt $ BD'P'F' $ będący obrazem czworokąta $ BDPF $ w symetrii względem dwusiecznej kąta $ ABC $ jest jednokładny do czworokąta $ BMQK $, i wobec tego prosta $ BQ $ pokrywa się z prostą $ BP' $ symetryczną do $ BP $ względem owej dwusiecznej.

Punkty $ P $ i $ Q $ mające tę własność, że proste $ AP $, $ BP $, $ CP $ są odpowiednio izogonalne do prostych $ AQ $, $ BQ $, $ CQ $ (względem kątów $ A $, $ B $, $ C $), noszą nazwę {\it punktów izogonalnych} trójkąta $ ABC $. Ważnym przykładem pary punktów izogonalnych jest środek okresu opisanego i punkt przecięcia wysokości trójkąta; okrąg przechodzący przez rzuty tych dwóch punktów na proste zawierające boki trójkąta - to {\it okrąg Eulera} danego trójkąta (zwany też {\it okręgiem dziewięciu punktów} albo {\it okręgiem Feuerbacha}).

Sposób III

(Szkic rozwiązania). Rozumowanie będzie oparte na własnościach elips. Podamy tylko kluczowe punkty dowodu, pomijając uzasadnienia. Ich uzupełnienie według podanych wskazówek może być ciekawym i chyba nietrudnym ćwiczeniem. (Także wykonanie rysunków pozostawiamy Czytelnikowi).

Własność 1: Jeśli prosta $ \ell $ jest styczna w punkcie $ X $ do elipsy o ogniskach $ P $ i $ Q $, to punkt $ P' $ symetryczny do $ P $ względem $ \ell $ leży na prostej $ QX $.

[Wskazówka: promień światła wypuszczony z ogniska elipsy trafia po odbiciu od niej w drugie ognisko.]

Własność 2: Jeśli proste styczne w punktach $ X $ i $ Y $ do elipsy o ogniskach $ P $ i $ Q $ przecinają się w punkcie $ A $, to $ |\measuredangle PAX| = |\measuredangle QAY| $.

[Wskazówka: niech $ P' $ i $ Q' $ będą punktami symetrycznymi do $ P $ i $ Q $ odpowiednio względem prostych $ AX $ i $ AY $; z własności 1 nietrudno wynika, że trójkąty $ AP'Q $ i $ APQ' $ mają boki odpowiednio równe, i wobec tego są przystające.]

Własność 3: Jeśli dla punktów $ P $ i $ Q $ leżących w trójkącie $ ABC $ spełnione są związki (1), to elipsa $ \mathcal{E} $ o ogniskach $ P $ i $ Q $, styczna do boku $ CA $, jest też styczna do boków $ AB $ i $ BC $.

[Łatwy wniosek z własności 2.]

Własność 4: W sytuacji, o której mowa we własności 3: jeśli $ S $ jest środkiem odcinka $ PQ $, a dłuższa oś elipsy $ \mathcal{E} $ ma długość $ 2a $, to okrąg $ \omega $ o środku $ S $ i promieniu a przechodzi przez rzuty punktów $ P $ i $ Q $ na proste $ AB $, $ BC $, $ CA $.

[Wskazówka: na przykład rzut $ D $ punktu $ P $ na prostą $ BC $ jest środkiem boku $ PP' $ trójkąta $ PP'Q $, w którym $ |QP'| = 2a $ (wniosek z własności 1); zatem $ |SD| = a $.]

Gdy już mamy okrąg $ \omega $, pozostaje tylko powtórzyć końcówkę pierwszego sposobu rozwiązania, aby otrzymać tezę zadania.

Uwaga 3: Ostatnie rozwiązanie jest bardziej skomplikowane niż poprzednie dwa; ma jednak swoje zalety: własności 2 i 3 dają dowód tego, że z dwóch warunków izogonalności (wzory (1)) wynika trzeci; dowód nie korzysta bezpośrednio z istnienia okręgu $ \omega $ i przez to jest odmienny od dowodu naszkicowanego w Uwadze 2. Te same dwie własności dają ponadto ciekawą charakteryzację punktów izogonalnych:

Dwa punkty trójkąta są izogonalne wtedy i tylko wtedy, gdy są ogniskami elipsy stycznej do jego trzech boków.

XLVIII OM - I - Zadanie 11

Zawody matematyczne: 
XLVIII OM, 1996-1997
Etap: 
I

Dana jest liczba naturalna $ m\geq 1 $ oraz wielomian $ P(x) $ stopnia dodatniego o współczynnikach całkowitych mający co najmniej trzy różne pierwiastki całkowite. Dowieść, że wielomian $ P(x) + 5^m $ ma co najwyżej jeden pierwiastek całkowity.

Rozwiązanie

Załóżmy, że liczby całkowite $ a $, $ b $, $ c $ są różnymi pierwiastkami wielomianu $ P(x) $. Przypuśćmy, wbrew dowodzonej tezie, że wielomian $ P(x) + 5^m $ ma dwa różne pierwiastki całkowite $ u $ i $ v $. Można przyjąć, że $ u>v $.

Dla każdej pary różnych liczb całkowitych $ x_1 $, $ x_2 $ liczba $ P(x_1)-P(x_2) $ dzieli się przez $ x_1-x_2 $. [Uzasadnienie: jeżeli $ P(x) = a_0 + a_1x + \ldots + a_nx^n $ ($ a_i $, całkowite), to różnica $ P(x_1)-P(x_2) $ jest sumą składników $ a_i(x_1^i-x_2^i $) dla $ i = 1,\ldots,n $, a każdy z tych składników dzieli się przez $ x_1 -x_2 $.]

Biorąc jako $ x_1 $ liczby $ u $ i $ v $, a jako $ x_2 $ liczby $ a $, $ b $ i $ c $, dostajemy za każdym razem różnicę $ P(x_1) - P(x_2) $ równą $ -5^m $. Skoro ma się ona dzielić przez każdą z rozważanych różnic $ x_1 -x_2 $, muszą zachodzić równości

\[ (1) \quad<br /> \begin{array}{lll}<br /> |u-a| = 5^j,& |u-b| = 5^k,& |u-c|=5^l,\\<br /> |v-a| = 5^n,& |v-b| = 5^p,& |v-c|=5^q\\<br /> \end{array}<br /> \]

dla pewnych wykładników całkowitych $ j, k,l,n,p,q\geq 0 $.

Zapiszmy różnicę $ u-v $ w postaci $ u-u = 5^\alpha w $;, gdzie $ \alpha \geq 0 $, $ w > 0 $ są liczbami całkowitymi, przy czym $ w $ nie dzieli się przez $ 5 $. Z dwóch pierwszych równości (1) wynika, że

\[<br /> u-v=(u-a)-(v-a) = (\pm 5^j) - (\pm 5^n) = 5^{\min\{j, n\}} (\pm 5^{|j-n|} \pm1).<br /> \]

Liczba w ostatnim nawiasie nie dzieli się przez $ 5 $; jest więc równa $ w $, a wykładnik $ \min\{j,n\} $ jest równy $ \alpha $. A ponieważ $ w>0 $, znak $ \pm $ przed $ 5^{|j-n|} $ można pominąć.

Pisząc następnie liczbę $ u - v $ jako $ (u-b) - (v-b) $ oraz jako $ (u-c) - (v-c) $ i korzystając z pozostałych zależności (1) otrzymujemy analogicznie związki

\[<br /> \qquad (2) \alpha = \min\{j,n\} = \min\{k,p\} = \min\{l,q\},<br /> \]
\[<br /> \qquad (3) w = 5^{|j-n|} \pm 1 = 5^{|k-p|}\pm 1 = 5^{|l-q|} \pm 1.<br /> \]

Zauważmy wszelako, że liczba $ w $ może mieć tylko jedno przedstawienie postaci $ 5^\delta+\varepsilon $ ($ \delta \geq 0 $ całkowite, $ \varepsilon \in \{+1,-1\} $). Z równości (3) wynika więc, że wykładniki $ |j-n| $, $ |k-p| $, $ |l-q| $ są równe. Oznaczmy ich wspólną wartość przez $ \delta $ oraz przyjmijmy $ \beta=\alpha+\delta $.

W myśl związków (2), w każdej z trzech par $ \{j,n\} $, $ \{k,p\} $, $ \{l,q\} $ jedna liczba równa się $ \alpha $; pozostała musi się równać $ \beta $. Zatem pewne dwie spośród liczb $ j $, $ k $, $ l $ są równe; niech na przykład $ j = k $. Wówczas $ n = p $ (jeśli $ j = k = \alpha $, to $ n = p = \beta $, a jeśli $ j = k = \beta $, to $ n = p = \alpha $) i wobec związków (1):

\[<br /> |u - a| = |u - b| \ \textrm{oraz} \ |v - a| = |v - b|.<br /> \]

Zgodnie z założeniem, liczby $ a $ i $ b $ nie są równe; otrzymane równości oznaczają w takim razie, że $ (u-a) = (b-u) $ oraz $ (v - a) = (b-v) $. Stąd $ 2u = a + b $ oraz $ 2v = a+b $, wbrew temu, że $ u>v $. Sprzeczność kończy dowód.

XLVIII OM - I - Zadanie 12

Zawody matematyczne: 
XLVIII OM, 1996-1997
Etap: 
I

Grupa złożona z $ n $ osób stwierdziła, że codziennie przez pewien okres czasu trzy z nich mogą wspólnie zjeść obiad w restauracji, przy czym każde dwie z nich spotkają się na dokładnie jednym obiedzie. Dowieść, że liczba $ n $ przy dzieleniu przez $ 6 $ daje resztę $ 1 $ lub $ 3 $.

Rozwiązanie

Niech $ m $ będzie liczbą dni, w ciągu których osoby z owej grupy zamierzają chodzić trójkami na obiady. Z $ n $ osób można utworzyć $ \frac{1}{2}n(n-1) $ par. Każdego dnia trzy pary spotkają się na obiedzie, a więc $ \frac{1}{2}n(n- 1) = 3m $.

Każda osoba spotka na obiadach w omawianym okresie wszystkie pozostałe $ n -1 $ osób. Na jednym obiedzie spotka dwie spośród nich; nikogo nie spotka dwukrotnie. Zatem $ n -1 $ jest liczbą parzystą, i wobec tego

\[<br /> n \equiv 1 (\mod 6) \ \textrm{lub} \ n \equiv 3 (\mod 6) \ \textrm{lub}\ n \equiv 5 (\mod 6).<br /> \]

Ostatnia możliwość prowadzi do wniosku, że $ n(n -1) \equiv 5 \cdot 4 \equiv 2 (\mod 6) $, wbrew temu, że $ n(n - 1) = 6m $. Tak więc $ n \equiv 1 $ lub $ n \equiv 3 (\mod 6) $.

XLVIII OM - II etap

II etap XLVIIIOlimpiady Matematycznej

ZałącznikWielkość
XLVIII OM II etap - Zadania [2]42.17 KB
XLVIII OM II etap - Rozwiązania [3]74.74 KB

XLVIII OM - II - Zadanie 1

Zawody matematyczne: 
XLVIII OM, 1996-1997
Etap: 
II

Dla każdej liczby rzeczywistej $ a $ wyznaczyć liczbę uporządkowanych trójek liczb rzeczywistych $ (x, y, z) $ spełniających układ równań

\[<br /> \left\{\begin{array}{l}<br /> x + y^2 + z^2 = a\\<br /> x^2 + y + z^2 = a\\<br /> x^2 + y^2 + z = a<br /> \end{array}<br /> \right.<br /> \]

Rozwiązanie

Podstawienie: $ x=u+\frac{1}{2} $, $ y=v+\frac{1}{2} $, $ z=w+\frac{1}{2} $ sprowadza dany układ równań do postaci:

\[<br /> (*) \qquad \left\{<br /> \begin{split}<br /> v^2 + w^2 + u + v + w + 1 = a\\<br /> w^2 + u^2 + u + v + w + 1 = a\\<br /> u^2 + v^2 + u + v + w + 1 = a\\<br /> \end{split}<br /> \right.<br /> \]

skąd przez odejmowanie stronami: $ u^2 = v^2 = w^2 $. Zatem każde rozwiązanie $ (u, v, w) $ układu (*) ma dokładnie jedną z następujących postaci:

\[<br /> (1) \qquad (t,t,t);\qquad t\in \mathbb{R};<br /> \]
\[<br /> (2) \qquad (-t,t,t) \quad \textrm{lub}\quad (t,-t,t)\quad \textrm{lub}\quad (t,t,-t); \qquad t\in \mathbb{R}, t \neq 0.<br /> \]

Dla $ u = v = w = t $ układ (*) sprowadza się do równania

\[<br /> (1') \qquad 2t^2 + 3t + (1-a) = 0;<br /> \]

gdy zaś dwie z liczb $ u $, $ v $, $ w $ są równe $ t $, trzecia $ -t $ ($ t \neq 0 $), układ (*) sprowadza się do równania

\[<br /> (2')\qquad 2t^2 + t + (1 - a) = 0.<br /> \]

Liczba rozwiązań $ (u,v,w) $ układu (*) mających postać (1) jest równa liczbie pierwiastków równania (1'); oznaczmy ją przez $ N_1 $. Liczba rozwiązań $ (u,v,w) $ postaci (2) jest równa $ 3N_2 $ gdzie $ N_2 $ oznacza liczbę pierwiastków równania (2') różnych od zera. Obliczamy wyróżniki trójmianów (1') i (2'): $ \Delta_1 = 8a + 1 $, $ \Delta_2 = 8a - 7 $. Zatem:

\[<br /> N_1=\left\{\begin{array}{lll}<br /> 0&\textrm{gdy}&a<-1/8,\\<br /> 1&\textrm{gdy}&a=-1/8,\\<br /> 2&\textrm{gdy}&a>-1/8,<br /> \end{array}<br /> \right.\<br /> N_2=\left\{\begin{array}{lll}<br /> 0&\textrm{gdy}&a<7/8,\\<br /> 1&\textrm{gdy}&a=7/8\ \textrm{lub}\ a=1,\\<br /> 2&\textrm{gdy}&a>7/8,\ a\neq 1.<br /> \end{array}<br /> \right.<br /> \]

Liczba rozwiązań układu (*) jest więc równa:

\[<br /> N=N_1+3N_2=\left\{\begin{array}{lll}<br /> 0&\textrm{gdy}&a<-1/8,\\<br /> 1&\textrm{gdy}&a=-1/8,\\<br /> 2&\textrm{gdy}&-1/8<a<7/8,\\<br /> 5&\textrm{gdy}&a=7/8\ \textrm{lub}\ a=1,\\<br /> 8&\textrm{gdy}&a>7/8\ \textrm{lub}\ a\neq 1.<br /> \end{array}<br /> \right.<br /> \]

XLVIII OM - II - Zadanie 2

Zawody matematyczne: 
XLVIII OM, 1996-1997
Etap: 
II

Punkt $ P $ leży wewnątrz trójkąta $ ABC $ i spełnia warunki:

\[<br /> \measuredangle PBA = \measuredangle PCA = \frac{1}{3}(\measuredangle ABC + \measuredangle ACB).<br /> \]

Udowodnić, że

\[<br /> \frac{AC}{AB+PC}=\frac{AB}{AC+PB}.<br /> \]

Rozwiązanie

Oznaczmy przez $ K $ punkt przecięcia prostych $ BP $ i $ AC $, zaś przez $ L $ punkt przecięcia prostych $ CP $ i $ AB $. Na mocy warunków zadania mamy:

\[<br /> \begin{split}<br /> \measuredangle KPC &= \measuredangle PBC + \measuredangle PCB = \measuredangle ABC - \measuredangle ABP + \measuredangle ACB - \measuredangle ACP =\\<br /> &= \measuredangle ABC + \measuredangle ACB - 2 \cdot \frac{1}{3}(\measuredangle ABC + \measuredangle ACB) = \\<br /> &= \frac{1}{3}(\measuredangle ABC + \measuredangle ACB) = \measuredangle PCK,<br /> \end{split}<br /> \]

co dowodzi, że $ KP = KC $. Analogicznie $ LP = LB $. Trójkąty $ ABK $ oraz $ ACL $ są podobne, więc dostajemy

\[<br /> \frac{AB}{AC}=\frac{AK+KB}{AL+LC}=\frac{AC-KC+KP+PB}{AB-LB+LP+PC}=\frac{AC+PB}{AB+PC},<br /> \]

czyli równość, którą należało udowodnić.

XLVIII OM - II - Zadanie 3

Zawody matematyczne: 
XLVIII OM, 1996-1997
Etap: 
II

Dany jest zbiór $ n $ punktów ($ n \geq 2 $), z których żadne trzy nie leżą na jednej prostej. Kolorujemy wszystkie odcinki o końcach w tym zbiorze tak, by każde dwa odcinki o wspólnym końcu miały różne kolory. Wyznaczyć najmniejszą liczbę kolorów, dla której istnieje takie pokolorowanie.

Rozwiązanie

Przyjmijmy, że dane punkty są wierzchołkami pewnego $ n $-kąta (jeśli $ n = 2 $, wystarczy oczywiście jeden kolor). Wszystkie odcinki o jednakowym kolorze wyznaczają rozłączne pary wierzchołków wielokąta. Maksymalna liczba rozłącznych podzbiorów dwuelementowych zbioru $ n $-elementowego wynosi $ [n/2] $. Zatem liczba kolorów jest nie mniejsza niż

\[<br /> {n \choose 2}\left[\frac{n}{2}\right]^{-1}=\left\{<br /> \begin{array}{cl}<br /> n & \textrm{dla $n$ nieparzystych},\\<br /> n-1 & \textrm{dla $n$ parzystych}.<br /> \end{array}\right.<br /> \]

Wykażemy, że ta liczba kolorów wystarcza do spełnienia żądanego warunku.

Gdy $ n $ jest liczbą nieparzystą, bierzemy zbiór wierzchołków $ n $-kąta foremnego i malujemy jednakowym kolorem bok i wszystkie równoległe do niego przekątne; odcinki nierównoległe malujemy różnymi kolorami. Użyliśmy $ n $ kolorów.

Gdy $ n $ jest liczbą parzystą, bierzemy zbiór wierzchołków $ (n-1) $-kąta foremnego $ V $ oraz jeszcze jeden punkt $ P_0 $. Kolorujemy boki i przekątne wielokąta $ V $ w sposób opisany powyżej, używając $ n - 1 $ kolorów. Dla każdej rodziny równoległych odcinków jednakowego koloru $ k_i $, pozostaje jeden wierzchołek $ P_i $ wielokąta $ V $ nie będący końcem żadnego z tych odcinków. Malujemy odcinek $ P_0P_i $, kolorem $ k_i $. Użyliśmy $ n - 1 $ kolorów, spełniając wymagany warunek.

XLVIII OM - II - Zadanie 4

Zawody matematyczne: 
XLVIII OM, 1996-1997
Etap: 
II

Wyznaczyć wszystkie trójki liczb całkowitych dodatnich mających następującą własność: iloczyn dowolnych dwóch z nich daje resztę $ 1 $ przy dzieleniu przez trzecią liczbę.

Rozwiązanie

Niech $ a $, $ b $, $ c $ będą liczbami, jakich szukamy. Z podanych warunków wynika, że są to liczby większe od $ 1 $, parami względnie pierwsze. Liczba $ bc+ca+ab- 1 $ dzieli się przez $ a $, przez $ b $ i przez $ c $, dzieli się więc także przez iloczyn $ abc $:

\[<br /> (1) \qquad bc +ca +ab = kabc+1 \ (\textrm{$k$ - liczba całkowita}).<br /> \]

Po podzieleniu stronami przez $ abc $:

\[<br /> (2) \qquad \frac{1}{a} + \frac{1}{b} + \frac{1}{c} = k+\frac{1}{abc}.<br /> \]

Suma po lewej stronie równości (1) jest większa od $ 1 $, więc $ k > 0 $. Suma po lewej stronie (2) jest mniejsza od $ 2 $, więc $ k < 2 $. Zatem $ k = 1 $. Prawa strona (2) jest większa od $ 1 $, więc największa z liczb $ 1/a $, $ 1/b $, $ 1/c $ przekracza $ 1/3 $. Przyjmując, że $ a > b > c $ wnosimy stąd, że $ c = 2 $. Równość (1) przybiera postać $ 2a + 2b + ab = 2ab + 1 $, czyli $ (a - 2)(b - 2) = 3 $. Stąd $ a = 5 $, $ b = 3 $, $ c = 2 $. Te liczby spełniają warunki zadania i są (z dokładnością do permutacji) jego jedynym rozwiązaniem.

XLVIII OM - II - Zadanie 5

Zawody matematyczne: 
XLVIII OM, 1996-1997
Etap: 
II

Rzucamy $ k $ kostkami sześciennymi białymi i $ m $ czarnymi. Obliczyć prawdopodobieństwo tego, że reszta z dzielenia przez $ 7 $ łącznej liczby oczek wyrzuconych na kostkach białych jest równa reszcie z dzielenia przez $ 7 $ łącznej liczby oczek wyrzuconych na kostkach czarnych.

Rozwiązanie

Zbiorem zdarzeń elementarnych w tym zadaniu jest

\[<br /> \Omega=\{(b_1,\ldots,b_k,c_1,\ldots,c_m) : b_1,\ldots,b_k,c_1,\ldots,c_m \in \{1,2,\ldots,6\}\},<br /> \]

gdzie wszystkie zdarzenia elementarne są jednakowo prawdopodobne. Niech $ A $ oznacza zdarzenie, którego prawdopodobieństwa szukamy:

\[<br /> A = \{(b_1,\ldots,b_k,c_1,\ldots,c_m) \in \Omega : 7|(b_1+\ldots+b_k-c_1-\ldots-c_m)\}.<br /> \]

Niech zaś $ B $ będzie zdarzeniem, że łączna liczba wyrzuconych oczek na wszystkich $ k + m $ kostkach jest podzielna przez $ 7 $:

\[<br /> B = \{(b_1,\ldots,b_k,c_1,\ldots,c_m) \in \Omega : 7|(b_1+\ldots+b_k+c_1+\ldots+c_m)\}.<br /> \]

Przekształcenie dane wzorem

\[<br /> (b_1,\ldots,b_k,c_1,\ldots,c_m)\mapsto (b_1,\ldots,b_k,7-c_1,\ldots,7-c_m)<br /> \]

jest odwzorowaniem wzajemnie jednoznacznym zbioru $ A $ na zbiór $ B $. Zbiory $ A $ i $ B $ są więc równoliczne, a zatem prawdopodobieństwa zdarzeń $ A $ i $ B $ są jednakowe.

Oznaczmy przez $ p_{n,r} $ ($ n \geq 1 $, $ r = 0,1,\ldots, 6 $) prawdopodobieństwo tego, że przy rzucie $ n $ kostkami reszta przy dzieleniu przez $ 7 $ łącznej liczby wyrzuconych oczek jest równa $ r $. Wówczas $ p_{1,0} = 0 $, $ p_{1,1} = p_{1,2} = \ldots = p_{1,6} = 1/6 $.

Ze wzoru na prawdopodobieństwo całkowite dostajemy dla $ n = 1,2,3,\ldots $ równość:

\[<br /> (*)\qquad p_{n+1,0}=p_{1,0}\cdot p_{n,0}+\sum_{r=1}^6p_{1,7-r}\cdot p_{n,r}=\frac{1}{6} \sum_{r=1}^6 p_{n,r}=\frac{1}{6}(1-p_{n,0}).<br /> \]

Wprowadzając oznaczenie $ q_n = p_{n,0} - \frac{1}{7} $, ze wzoru (*) otrzymujemy równość

\[<br /> q_{n+1} = q_n \cdot \left(-\frac{1}{6}\right)\qquad \textrm{dla}\ n \geq 1.<br /> \]

Stąd przez łatwą indukcję

\[<br /> q_n = q_1 \left(-\frac{1}{6}\right)^{n-1}=\frac{(-1)^n}{7\cdot 6^{n-1}}\qquad \textrm{dla}\ n \geq 1.<br /> \]

Ostatecznie więc

\[<br /> P(A) = P(B) = p_{k+m,0} = \frac{1}{7} + q_{k+m} = \frac{1}{7} + \frac{(-1)^{k+m}}{7\cdot 6^{k+m-1}}<br /> \]

XLVIII OM - II - Zadanie 6

Zawody matematyczne: 
XLVIII OM, 1996-1997
Etap: 
II

W sześcianie o krawędzi długości $ 1 $ leży osiem punktów. Wykazać, że pewne dwa z nich są końcami odcinka o długości nie większej niż $ 1 $.

Rozwiązanie

Oznaczmy wierzchołki danego sześcianu $ \mathcal{C} $ przez $ A_1,\ldots, A_8 $. Oznaczmy przez $ \mathcal{C}_i $ sześcian o krawędzi długości $ \frac{1}{2} $, mający jeden wierzchołek w punkcie $ A_i $ oraz trzy ściany zawarte w ścianach sześcianu $ \mathcal{C} $. Niech $ P_1,\ldots,P_8 $ będą ośmioma danymi punktami.

Każdy sześcian $ \mathcal{C}_i $ ma średnicę $ \frac{1}{2}\sqrt{3} < 1 $. Jeśli więc pewne dwa różne punkty $ P_k $, $ P_l $ leżą w którymś z sześcianów $ \mathcal{C}_i $, to $ P_kP_l < 1 $; wymagany warunek jest spełniony.

Załóżmy zatem, że każdy z tych sześcianów zawiera dokładnie jeden punkt $ P_i $. Ustalmy numerację tak, by $ P_i \in \mathcal{C}_i $ dla $ i = 1,\ldots, 8 $. Sześcian $ \mathcal{C}_i $ ma dokładnie trzy ściany wspólne z powierzchnią sześcianu $ \mathcal{C} $; punkt $ P_i $, jest odległy od każdej z tych trzech ścian o nie więcej niż $ 1/2 $. Oznaczmy te trzy odległości przez $ a_i $, $ b_i $, $ c_i $. Niech $ d $ będzie największą spośród $ 24 $ liczb: $ a_1,b_1,c_1,\ldots,a_8,b_8,c_8 $. Bez straty ogólności możemy przyjąć, że $ d = P_1Q $, gdzie $ Q $ jest rzutem prostokątnym punktu $ P_1 $ na pewną ścianę sześcianu $ \mathcal{C} $, oraz że $ A_1A_2 $ jest krawędzią sześcianu $ \mathcal{C} $ równoległą do prostej $ P_1Q $.

Niech $ R $ będzie rzutem prostokątnym punktu $ P $ na prostą $ A_1A_2 $. Weźmy pod uwagę prostopadłościan, którego jedną krawędzią jest odcinek $ A_2R $, a jedną ze ścian prostopadłych do $ A_2R $ jest kwadrat o wierzchołku $ A_2 $ i boku długości $ d $, zawarty w ścianie sześcianu $ \mathcal{C} $. Z określenia liczby $ d $ wynika, że ów prostopadłościan zawiera punkty $ P_1 $ i $ P_2 $. Jego średnica jest równa

\[<br /> \sqrt{d^2 + d^2 + (1 - d)^2} = \sqrt{d(3d - 2) + 1} \leq 1,<br /> \]

gdyż $ 0 \leq d \leq \frac{1}{2} < \frac{2}{3} $. Zatem $ P_1P_2 \leq 1 $, co kończy dowód.

XLVIII OM - III etap

III etap XLIX Olimpiady Matematycznej

ZałącznikWielkość
XLVIII OM III etap - Zadania [4]51.06 KB
XLVIII OM III etap - Rozwiązania [5]74.04 KB

XLVIII OM - III - Zadanie 1

Zawody matematyczne: 
LVIII OM, 2006-2007
Etap: 
III

Liczby całkowite dodatnie $ x_1 $, $ x_2 $, $ x_3 $, $ x_4 $, $ x_5 $, $ x_6 $, $ x_7 $ spełniają warunki:

\[<br /> x_6 = 144\ \textrm{oraz}\ x_{n+3} = x_{n+2}(x_{n+1} + x_n) \ \textrm{dla} \ n = 1, 2, 3,4.<br /> \]

Wyznaczyć $ x_7 $.

Rozwiązanie

Oznaczmy: $ a = x_1+x_2 $, $ b = x_3 $, $ c = x_2+x_3 $. Wówczas $ x_2 = c - b $, $ x_1 = a-x_2=a+b-c $. Są to z założenia liczby dodatnie. Tak więc

\[<br /> (1)\qquad 0<b<c<a + b.<br /> \]

Dalej, $ x_4 = ab, x_5 = abc, x_6 = abc(ab + b) = a(a + 1)b^2c $. Z nierówności (1) wynika, że $ a > 1 $. Jedynymi dzielnikami liczby $ 144 $ mającymi postać $ a(a + 1) $ (gdzie $ a > 1 $) są liczby $ 6 $, $ 12 $, $ 72 $, odpowiadające wartościom $ a = 2 $, $ a = 3 $, $ a = 8 $. Iloczyn $ b^2c $ powinien mieć - odpowiednio - wartość: $ 24 $, $ 12 $, $ 2 $. Pierwsza możliwość prowadzi do sprzeczności z warunkiem (1). Druga i trzecia możliwość daje (w połączeniu z warunkiem (1)) rozwiązania $ (a,b,c) = (3,2,3) $ oraz $ (a,b,c) = (8,1,2) $. W każdym przypadku $ x_7 = x_6(x_5 + x_4) = 144ab(c+1) = 144\cdot 24 = 3456 $.

XLVIII OM - III - Zadanie 2

Zawody matematyczne: 
XLVIII OM, 1996-1997
Etap: 
III

Znaleźć wszystkie trójki liczb rzeczywistych $ x $, $ y $, $ z $ spełniające układ równań

\[<br /> \left\{<br /> \begin{array}{c}<br /> 3(x^2+y^2+z^2)=1\\<br /> x^2y^2 + y^2z^2 + z^2x^2 = xyz(x + y + z)^3.<br /> \end{array}\right.<br /> \]

Rozwiązanie

Przypuśćmy, że liczby $ x $, $ y $, $ z $ spełniają dany układ; z drugiego równania wynika, że

\[<br /> (1)\qquad xyz(x + y + z) \geq 0.<br /> \]

Dalej mamy

\[<br /> (2)\qquad 0 \leq (x - y)^2 + (y - z)^2 + (z - x)^2 = 3(x^2 + y^2 + z^2) - (x + y + z)^2,<br /> \]

co na mocy pierwszego równania układu daje:

\[<br /> (3)\qquad (x + y + z)^2 \leq 1.<br /> \]

Zachodzi też nierówność

\[<br /> \begin{split}<br /> 0 &\leq (xy - yz)^2 + (yz - zx)^2 + (zx - xy)^2 =\\<br /> &= 2(x^2y^2 + y^2z^2 + z^2x^2) - 2xyz(x + y + z),<br /> \end{split}<br /> \]

czyli

\[<br /> (4)\qquad xyz(x + y + z) \leq x^2y^2 + y^2z^2 + z^2x^2.<br /> \]

Dzięki własności (1) możemy pomnożyć nierówności (3) i (4) stronami:

\[<br /> (5)\qquad xyz(x + y + z)^3 \leq x^2y^2 + y^2z^2 + z^2x^2.<br /> \]

Zgodnie z drugim równaniem układu, nierówność (5) ma być równością. To znaczy, że albo obie mnożone nierówności (3) i (4) są równościami, albo wyrażenia po obu stronach (4) są równe zeru. W pierwszym przypadku znak równości w związkach (2) i (3) prowadzi do wniosku, że $ x = y = z = \pm 1/3 $. W drugim przypadku iloczyny $ zy $, $ yz $, $ zx $ są równe zeru, czyli pewne dwie spośród liczb $ z $, $ y $, $ z $ są równe zeru; trzecia musi być równa $ \pm 1/\sqrt{3} $, zgodnie z pierwszym równaniem układu. Daje to osiem trójek $ (x, y, z) $ spełniających dany układ równań:

\[<br /> (\varepsilon \cdot \frac{1}{3},\varepsilon \cdot \frac{1}{3},\varepsilon \cdot \frac{1}{3}), \quad (\varepsilon \cdot \frac{1}{\sqrt{3}},0,0), \quad (0,\varepsilon \cdot \frac{1}{\sqrt{3}},0), \quad (0,0,\varepsilon \cdot \frac{1}{\sqrt{3}}),<br /> \]

gdzie $ \varepsilon = \pm 1 $.

XLVIII OM - III - Zadanie 3

Zawody matematyczne: 
XLVIII OM, 1996-1997
Etap: 
III

Środkowe ścian bocznych $ ABD $, $ ACD $, $ BCD $ ostrosłupa $ ABCD $ poprowadzone z wierzchołka $ D $ tworzą równe kąty z krawędziami, do których zostały poprowadzone. Wykazać, że pole każdej ściany bocznej jest mniejsze od sumy pól pozostałych dwóch ścian bocznych.

Rozwiązanie

Udowodnimy nierówność

\[<br /> (1)\qquad \mathrm{pole} (ABD) < \mathrm{pole} (BCD) + \mathrm{pole} (CAD)<br /> \]

(pozostałe dwie nierówności dostaniemy analogicznie). Oznaczmy przez $ K $, $ L $, $ M $ odpowiednio środki krawędzi $ BC $, $ CA $, $ AB $. Odcinki $ DK $, $ DL $, $ DM $ tworzą równe kąty odpowiednio z krawędziami $ BC $, $ CA $, $ AB $; oznaczmy ten wspólny kąt przez $ \alpha $. Niech $ DH $ będzie wysokością trójkąta $ ABD $. Mamy:

\[<br /> (2)\qquad \mathrm{pole} (ABD) = \frac{1}{2} AB \cdot DH = \frac{1}{2} AB \cdot DM \cdot \sin \alpha = KL \cdot DM \cdot \sin \alpha.<br /> \]

Analogicznie:

\[<br /> (3) \qquad \mathrm{pole} (BCD) = LM \cdot DK \cdot \sin \alpha \quad \textrm{oraz}\quad \mathrm{pole} (CAD) = MK \cdot DL \cdot \sin \alpha.<br /> \]

Ponieważ $ \sin\alpha \neq 0 $, więc wykorzystując równości (2) i (3) możemy zapisać nierówność (1) w następującej równoważnej postaci:

\[<br /> (4) \qquad KL \cdot DM < LM \cdot DK + MK \cdot DL.<br /> \]

Rozważmy czworościan $ KLMD $. Niech $ N $ będzie takim punktem płaszczyzny $ KLM $, że $ KN = KD $, $ LN = LD $ oraz punkty $ M $ i $ N $ leżą po przeciwnych stronach prostej $ KL $. Oznaczmy przez $ P $ punkt przecięcia prostej $ KL $ z odcinkiem $ MN $. Ponieważ trójkąty $ KLD $ i $ KLN $ są przystające, więc $ DP = NP $. Dla czworokąta $ MKNL $ zachodzi nierówność Ptolemeusza:

\[<br /> KL \cdot NM \leq LM \cdot NK + MK \cdot NL.<br /> \]

Stąd otrzymujemy

\[<br /> \begin{split}<br /> KL \cdot DM &< KL \cdot (DP + PM) = KL \cdot (NP + PM) = KL \cdot NM \leq\\<br /> &\leq LM \cdot NK + MK \cdot NL = LM \cdot DK + MK \cdot DL,<br /> \end{split}<br /> \]

czyli nierówność (4), która jest równoważna nierówności (1).

XLVIII OM - III - Zadanie 4

Zawody matematyczne: 
XLVIII OM, 1996-1997
Etap: 
III

Ciąg $ a_1, a_2, a_3,\ldots $ jest określony wzorami

\[<br /> a_1 = 0, \quad a_n = a_{[n/2]} + (-1)^{n(n+1)/2}\quad \textrm{dla}\ n > 1.<br /> \]

Dla każdej liczby całkowitej $ k \geq 0 $ wyznaczyć liczbę numerów $ n $ spełniających warunki

\[<br /> 2^k \leq n < 2^{k+1}, \qquad a_n = 0.<br /> \]

Uwaga: $ [n/2] $ jest największą liczbą całkowitą nie przekraczającą $ n/2 $.

Rozwiązanie

Każdej liczbie całkowitej $ n \geq 1 $ przyporządkowujemy skończony ciąg symboli dwóch rodzajów: kropek i przecinków. Zapisujemy liczbę $ n $ w systemie dwójkowym. Pomiędzy każde dwie kolejne cyfry wstawiamy kropkę, gdy te cyfry są jednakowe, a przecinek, gdy są różne. Jeżeli $ n $ spełnia nierówność $ 2^k\leq n < 2^{k+1} $, czyli jest (w systemie dwójkowym) liczbą $ (k+1) $-cyfrową, to wstawione w opisany sposób kropki i przecinki tworzą ciąg $ k $-wyrazowy. Będziemy go nazywali {\it kodem} liczby $ n $. Każdy taki ciąg kropek i przecinków jest kodem dokładnie jednej liczby $ n $: na początku ma ona jedynkę, a dalsze cyfry są wyznaczone przez kolejne symbole kodu. Kod $ k $-wyrazowy wyznacza liczbę $ (k+1) $-cyfrową.

Oznaczmy przez $ b_n $ liczbę kropek, a przez $ c_n $ liczbę przecinków w kodzie liczby $ n $ i przyjmijmy $ d_n = b_n - c_n $.

Niech $ n $ będzie dowolną liczbą $ (k+1) $-cyfrową ($ k \geq 1 $). Skreślając jej ostatnią cyfrę otrzymujemy zapis dwójkowy liczby $ [n/2] $. Jeśli ostatnie dwie cyfry liczby $ n $ są równe, to $ b_n = b_{[n/2]} + 1 $, $ c_n = c_{[n/2]} $. Jeśli ostatnie dwie cyfry liczby $ n $ są różne, to $ b_n = b_{[n/2]} $, $ c_n = c_{[n/2]} + 1 $. Pierwsza z tych sytuacji ma miejsce, gdy $ n \equiv 0 $ lub $ n \equiv 3\ (\mathrm{mod}\ 4) $, druga - gdy $ n \equiv 1 $ lub $ n \equiv 2\ (\mathrm{mod}\ 4) $. Różnica $ d_n - d_{[n/2]} $ wynosi $ 1 $ w pierwszym przypadku, zaś $ -1 $ w drugim przypadku.

Dokładnie takie same wartości przybiera różnica $ a_n - a_{[n/2]} $. Dla $ n = 1 $ mamy $ a_1 = b_1 = c_1 = d_1 = 0 $. Stąd wniosek, że $ a_n = d_n $, czyli $ a_n = b_n - c_n $, dla $ n = 1,2,3,\ldots $ . Zatem dla $ (k+1) $-cyfrowej liczby $ n $ równość $ a_n = 0 $ zachodzi wtedy i tylko wtedy, gdy w jej $ k $-wyrazowym kodzie jest tyle samo symboli każdego rodzaju. Liczba takich $ k $-wyrazowych ciągów wynosi $ {k \choose {k/2}} $, gdy $ k $ jest liczbą parzystą, oraz $ 0 $, gdy $ k $ jest liczbą nieparzystą. Tyle jest więc numerów $ n $ spełniających zadane warunki.

XLVIII OM - III - Zadanie 5

Zawody matematyczne: 
XLVIII OM, 1996-1997
Etap: 
III

Dany jest pięciokąt wypukły $ ABCDE $, w którym $ DC = DE $ oraz $ \measuredangle DCB =\measuredangle DEA = 90^\circ $. Niech $ F $ będzie punktem boku $ AB $ wyznaczonym przez warunek $ AF: BF = AE: BC $. Udowodnić, że $ \measuredangle FCE = \measuredangle ADE $ oraz $ \measuredangle FEC= \measuredangle BDC $.

Rozwiązanie

Na przedłużeniu odcinka $ BC $ odkładamy odcinek $ CP = AE $. Z warunków zadania wynika, że trójkąty prostokątne $ PCD $ i $ AED $ są przystające. Stąd $ AD = DP $ oraz

\[<br /> \measuredangle ADP = \measuredangle PDC + \measuredangle ADC = \measuredangle ADE + \measuredangle ADC = \measuredangle EDC.<br /> \]

Ponieważ również $ ED = DC $, więc trójkąty $ ADP $ i $ EDC $ są podobne. Oznaczając przez $ Q $ punkt przecięcia prostych $ AP $ i $ EC $ dostajemy równość

\[<br /> \measuredangle DEQ = \measuredangle DEC = \measuredangle DAP = \measuredangle DAQ,<br /> \]

która dowodzi, że punkty $ A $, $ Q $, $ D $, $ E $ leżą na jednym okręgu. Zatem

\[<br /> (1)\qquad \measuredangle ADE = \measuredangle AQE.<br /> \]

Ze związków

\[<br /> \frac{AF}{BF}=\frac{AE}{BC}=\frac{PC}{BC}<br /> \]

wynika, że proste $ AP $ i $ FC $ są równoległe. Stąd $ \measuredangle AQE = \measuredangle FCE $, co w połączeniu ze wzorem (1) daje pierwszą równość tezy. Druga jest analogiczna.

XLVIII OM - III - Zadanie 6

Zawody matematyczne: 
XLVIII OM, 1996-1997
Etap: 
III

Na okręgu o promieniu $ 1 $ leży $ n $ różnych punktów ($ n \geq 2 $). Niech $ q $ będzie liczbą odcinków o końcach w tych punktach i długości większej niż $ \sqrt{2} $. Dowieść, że $ 3q \leq n^2 $.

Rozwiązanie

Odcinek o końcach w rozważanym zbiorze będziemy nazywać długim, jeśli jego długość jest większa niż $ \sqrt{2} $, a krótkim w przeciwnym przypadku. Tak więc $ q $ jest liczbą długich odcinków. W dany okrąg wpisujemy kwadrat $ ABCD $ tak, by żaden z danych $ n $ punktów nie był jego wierzchołkiem. Przyjmijmy, że na łukach $ AB $, $ BC $, $ CD $, $ DA $ leży odpowiednio $ a $ punktów, $ b $ punktów, $ c $ punktów, $ d $ punktów. Weźmy pod uwagę zbiór wszystkich czworokątów mających wierzchołki w danych punktach, po jednym na każdym z czterech łuków. Jest $ abcd $ takich czworokątów. Każdy czworokąt wpisany w dany okrąg ma co najmniej jeden bok krótki.

Przyporządkujmy każdemu czworokątowi (z rozważanego zbioru) jeden z jego krótkich boków i pomalujmy ten wybrany bok na zielono. Ustalony zielony odcinek mający końce na łukach $ AB $ i $ BC $ mógł zostać przyporządkowany co najwyżej $ c \cdot d $ czworokątom, a więc co najwyżej $ m $ czworokątom, gdzie $ m $ jest największą z liczb $ ab $, $ bc $, $ cd $, $ da $. Tak samo da się oszacować liczbę czworokątów, którym został przyporządkowany dowolnie ustalony zielony odcinek (o końcach w którychkolwiek dwóch sąsiednich łukach). Stąd wniosek, że łączna liczba zielonych odcinków jest nie mniejsza niż $ (abcd)/m $.

Wszystkie zielone odcinki są krótkie. Oczywiście takie wszystkie odcinki mające oba końce w jednym łuku są krótkie. Zatem liczba krótkich odcinków, równa $ {n \choose 2} - q $, spełnia oszacowanie:

\[<br /> {n \choose 2}-q\geq \frac{abcd}{m}+{a \choose 2}+{b \choose 2}+{c \choose 2}+{d \choose 2}.<br /> \]

Można przyjąć (przesuwając w razie potrzeby oznaczenia), że $ m = ab $. Otrzymana nierówność przybiera po przekształceniu postać:

\[<br /> \begin{split}<br /> q &\leq \frac{1}{2}(n(n - 1) - a(a - 1) - b(b - 1) - c(c - 1) - d(d - 1)) - cd =\\<br /> & = \frac{1}{2}n^2-\frac{1}{2}(a^2+b^2+c^2+d^2)-cd<br /> \end{split}<br /> \]

(skorzystaliśmy z tego, że $ a + b + c + d = n $). A zatem

\[<br /> \begin{split}<br /> n^2 - 3q & \geq - \frac{1}{2} n^2 + \frac{3}{2}(a^2 +b^2 + c^2+ d^2) + 3cd =\\<br /> &= \left(\frac{1}{2}(a + b)-(c + d)\right)^2 + \frac{3}{4}(a-b)^2 \geq 0.<br /> \end{split}<br /> \]
© Prawa autorskie Polskie Towarzystwo Matematyczne | Serwis znajduje się na serwerze MIMUW | Projekt: Krystyna Jaworska | Realizacja: Paweł Witkowski INTools, Tomasz Filar
Adres źródła: https://archom.ptm.org.pl/?q=node/436

Odnośniki:
[1] https://archom.ptm.org.pl/sites/default/files/om48_1.pdf
[2] https://archom.ptm.org.pl/sites/default/files/om48_2.pdf
[3] https://archom.ptm.org.pl/sites/default/files/om48_2r.pdf
[4] https://archom.ptm.org.pl/sites/default/files/om48_3.pdf
[5] https://archom.ptm.org.pl/sites/default/files/om48_3r.pdf