XXXIV OM - II etap

II etap XXXIV Olimpiady Matematycznej

XXXIV OM - II - Zadanie 1

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Na płaszczyźnie z ustalonym układem współrzędnych dany jest wielokąt wypukły, którego wszystkie wierzchołki mają współrzędne całkowite. Dowieść, że podwojone pole tego wielokąta jest liczbą całkowitą.

Rozwiązanie

Obieramy dowolny wierzchołek wielokąta i prowadzimy z niego wszystkie przekątne. Podzielimy w ten sposób dany wielokąt na trójkąty, których wierzchołki mają współrzędne całkowite. Wystarczy więc udowodnić rozważane twierdzenie dla trójkąta.

Przez wierzchołki trójkąta prowadzimy proste równolegle do osi układu współrzędnych. Proste te przecinają się w punktach o współrzędnych całkowitych, wyznaczają więc prostokąt, którego pole jest liczbą całkowitą i na którego bokach leżą wierzchołki rozważanego trójkąta. Trójkąt nasz powstaje z tego prostokąta przez odcięcie jednego, dwóch albo trzech trójkątów prostokątnych o przyprostokątnych równoległych do osi układu współrzędnych i wierzchołkach w punktach o współrzędnych całkowitych. Długości przyprostokątnych tych trójkątów są liczbami całkowitymi, więc pole każdego trójkąta (równe połowie iloczynu długości przyprostokątnych) jest liczbą całkowitą albo połową liczby całkowitej. Wobec tego pole $S$ rozważanego trójkąta jest różnicą liczby całkowitej (pola prostokąta) i jednej, dwóch albo trzech liczb, z których każda jest całkowita albo jest połową liczby całkowitej. Zatem $2S$ jest liczbą całkowitą.

XXXIV OM - II - Zadanie 2

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Dane są takie trzy liczby nieujemne $a, b, c$ , że suma każdych dwóch jest nie mniejsza od pozostałej. Dowieść, że

$ \sqrt{a+b-c} + \sqrt{a-b+c} + \sqrt{-a+b+c} \leq \sqrt{a} + \sqrt{b} + \sqrt{c}. $

Rozwiązanie

Zastosujemy nierówność

$ (1) \qquad \sqrt{\frac{x+y}{2}} \geq \frac{1}{2} (\sqrt{x}+\sqrt{y}), \ \textrm{dla} \ x, y > 0, $

którą można wyprowadzić z własności funkcji pierwiastkowej, albo udowodnić bezpośrednio jak następuje. Podnosząc obustronnie do kwadratu otrzymujemy nierówność równoważną

$ \frac{x+y}{2} \geq \frac{1}{4} (x+y+2\sqrt{xy}), $

którą następnie przekształcamy do postaci

$ \begin{split} \frac{x+y}{4} \geq \frac{\sqrt{xy}}{2},\\ x+y-2\sqrt{xy} \geq 0,\\ (\sqrt{x} - \sqrt{y})^2 \geq 0 \end{split} $

Cztery powyższe nierówności są oczywiście równoważne, a ostatnia jest spełniona dla wszystkich nieujemnych $x$ , $y$ .

W nierówności (1) podstawiamy $x= a+b-c$ , $y = a-b+c$ i dostajemy

$ \sqrt{a} \geq \frac{1}{2}(\sqrt{a+b-c}+\sqrt{a-b+c}). $

Analogicznie

$ \sqrt{b} \geq \frac{1}{2}(\sqrt{a+b-c}+\sqrt{-a+b+c}) $

$ \sqrt{c} \geq \frac{1}{2}(\sqrt{a-b+c}+\sqrt{-a+b+c}). $

Po dodaniu tych nierówności otrzymujemy

$ \sqrt{a} + \sqrt{b} + \sqrt{c} \geq \sqrt{a+b-c}+\sqrt{a-b+c}+\sqrt{-a+b+c}. $

Uwaga. Jeśli liczby $a$ , $b$ , $c$ są różne, to każdą z powyższych nierówności można zastąpić przez nierówność ostrą.

XXXIV OM - II - Zadanie 3

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Punkt $P$ leży wewnątrz trójkąta $ABC$ , przy czym $\measuredangle PAC = \measuredangle PBC$ . Punkty $L$ i $M$ są odpowiednio rzutami $P$ na proste $BC$ i $CA$ , $D$ jest środkiem odcinka $AB$ . Dowieść, że $DL = DM$ .

Rozwiązanie

Niech $Q$ i $R$ będą odpowiednio środkami odcinków $AP$ i $BP$ . Punkty te są środkami kół opisanych odpowiednio na trójkątach $APM$ i $BPL$ , skąd wynika, że

$ \measuredangle MQP = 2 \measuredangle PAM \ \textrm{i} \ \measuredangle LRP = 2 \measuredangle PBL $

jako kąty środkowe oparte na tych samych łukach, co odpowiednie kąty wpisane. Kąty $PAM$ i $PBL$ są równe z założenia. Zatem

$ \ (1) \qquad \measuredangle MQP= \measuredangle LRP. $

Odcinek $\overline{DQ}$ łączy środki boków $\overline{AB}$ i $\overline{AP}$ trójkąta $ABP$ . Wynika stąd, że $\overline{DQ} || \overline{BP}$ . Analogicznie $\overline{DR} || \overline{AP}$ . Wobec tego czworokąt $DRPQ$ jest równoległobokiem, skąd wynika, że

$ (2) \qquad \measuredangle PQD = \measuredangle PRD. $

Z równości (1) i (2) otrzymujemy, że $\measuredangle MQD = \measuredangle DRL$ . Ponadto $MQ= QP= DR$ oraz $LR= RP= DQ$ . Wynika stąd, że trójkąty $MQD$ i $DRL$ są przystające, a zatem $DM$ = $DL$ .

XXXIV OM - II - Zadanie 4

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Niech $a(k)$ będzie największą liczbą nieparzystą, przez którą dzieli się $k$ . Udowodnić, że

$ \sum_{k=1}^{2^n} a(k) = \frac{1}{3}(4^n+2). $

Rozwiązanie

Największy dzielnik nieparzysty $a(k)$ liczby $k$ możemy otrzymać w następujący sposób. Jeśli $k$ jest liczbą nieparzystą, to $a(k)= k$ , w przeciwnym razie rozważamy liczbę $k/2$ . Jeśli $k/2$ jest liczbą nieparzystą, to $a(k) = k/2$ , w przeciwnym razie rozważamy liczbę $k/4$ itd.

Wobec tego szukaną sumę otrzymamy odejmując od sumy kolejnych liczb naturalnych od $1$ do $2^n$ połówki co drugiego składnika, następnie czwarte części co czwartego składnika, dalej ósme części co ósmego składnika itd. Zatem

$ \begin{split} \sum_{k=1}^{2^n} a(k) &= \sum_{k=1}^{2^n} k - \sum_{k=1}^{2^{n-1}} k - \sum_{k=1}^{2^{n-2}}k - \ldots - \sum_{k=1}^{2} k -1 = \\&= \frac{2^n(2^n+1)}{2} - \frac{2^{n-1}(2^{n-1}+1)}{2} - \frac{2^{n-2}(2^{n-2}+1)}{2} - \ldots - \frac{2(2+1)}{2} -1=\\ &=\frac{1}{2} \cdot 2^n(2^n+1) - \sum_{m=0}^{n-1} \frac{1}{2} \cdot 2^m(2^m+1) =\\ &= \frac{1}{2} (4^n + 2^n) - \frac{1}{2} \sum_{m=0}^{n-1} 4^m - \frac{1}{2} \sum_{m=0}^{n-1} 2^m = \frac{1}{2} (4^n+2^n) - \frac{4^n-1}{4-1} - \frac{2^n-1}{2-1}=\\ &= \frac{1}{2} \left( 4^n+ 2^n - \frac{1}{3} \cdot 4^n + \frac{1}{3} - 2^n + 1 \right) = \frac{1}{3} (4^n+2). \end{split} $

XXXIV OM - II - Zadanie 5

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Dwusieczne kątów $CAB, ABC, BCA$ trójkąta $ABC$ przecinają okrąg opisany na tym trójkącie odpowiednio w punktach $K, L, M$ . Dowieść, że

$ AK+BL+CM > AB+BC+CA. $

Rozwiązanie

Oznaczmy krótko przez $A$ , $B$ , $C$ odpowiednie kąty trójkąta $ABC$ . Kąt $AKB$ jest oparty na tym samym łuku, co kąt $C$ , więc $\measuredangle AKB = C$ . W trójkącie $AKB$ suma miar kątów wynosi $180^\circ$ , więc $\measuredangle ABK = 180^\circ -\measuredangle AKB- \measuredangle BAK = 180^\circ - C- A/2$ . Stąd i z twierdzenia sinusów zastosowanego do trójkąta $ABK$ otrzymujemy $AK= 2R\sin \measuredangle ABK = 2R \sin (180^\circ -C-A/2) = 2R\sin \left( C+ \frac{A}{2} \right)$ . Analogicznie mamy

$ BL= 2R \sin \left(A+ \frac{B}{2} \right). $

$ CM = 2R \sin \left(B+ \frac{C}{2} \right), $

skąd wynika, że

$ AK+BL+CM = 2R \left( \sin \left(A + \frac{B}{2} \right) + \sin \left(B+\frac{C}{2} \right) +\sin \left(C+\frac{A}{2}\right) \right), $

natomiast

$ AB+BC+CA=2R(\sin A+\sin B+\sin C). $

Dana w zadaniu nierówność jest więc równoważna nierówności

$ \sin A+\sin B+\sin C < \sin \left(A + \frac{B}{2} \right) + \sin \left(B+\frac{C}{2} \right) +\sin \left(C+\frac{A}{2}\right), $

a ta ostatnia była treścią zadania 2 z zawodów stopnia pierwszego.

XXXIV OM - II - Zadanie 6

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

Dla danej liczby $n$ oznaczmy przez $p_n$ prawdopodobieństwo tego, że przy losowym wyborze pary liczb całkowitych $k, m$ spełniających warunki $0 \leq k \leq m \leq 2^n$ (wybór każdej pary jest jednakowo prawdopodobny) liczba $\binom{m}{k}$ będzie parzysta. Obliczyć $\lim_{n\to \infty} p_n$ .

Rozwiązanie

Diagram na rysunku 10 przedstawia trójkąt Pascala napisany modulo $2$ , to znaczy mający zera i jedynki odpowiednio w tych miejscach, gdzie w zwykłym trójkącie Pascala występują liczby parzyste i nieparzyste. Jak w zwykłym trójkącie Pascala, tak i tu każdy element jest sumą elementów stojących bezpośrednio nad nim zgodnie z tabliczką dodawania modulo 2: $0+0=0$ , $0+1=1$ , $1+0=1$ , $1+1 = 0$ . Narysowane linie poziome dzielą ten trójkąt na warstwy:

warstwa $W_0$ złożona z wiersza nr $0$ ,
warstwa $W_1$ złożona z wiersza nr $1$ ,
warstwa $W_2$ złożona z wierszy nr $2$ i $3$ ,
warstwa $W_3$ złożona z wierszy nr $4$ , $5$ , $6$ , $7$ ,
$\ldots$
warstwa $W_j$ złożona z wierszy o numerach od $2^{j-1}$ do $2^j- 1$
$\ldots$

Udowodnimy indukcyjnie, że w dowolnej warstwie $W_j$ znajdują się dwa rozłączne trójkąty, z których każdy jest identyczny z trójkątem utworzonym przez warstwy $W_0, W_1, \ldots, W_{j-1}$ , oraz, że te dwa trójkąty są rozdzielone odwróconym trójkątem złożonym z samych zer; górny wiersz warstwy składa się ze skrajnych jedynek i samych zer, dolny zaś wiersz warstwy składa się z samych jedynek.

Dla $j= 1, 2, 3$ jest to widoczne z rysunków (linie ukośne wyznaczają podział na trójkąty, o których mowa). Załóżmy prawdziwość powyższych zależności dla pewnego $j$ i weźmy pod uwagę warstwę $W_{j + 1}$ .Z założenia indukcyjnego, ostatni wiersz warstwy $W_j$ ma postać $111\ldots 111$ , a zatem zgodnie z podaną wyżej regułą dodawania, pierwszy wiersz warstwy $W_{j + 1}$ ma postać $100\ldots 001$ . Skrajne jedynki tego wiersza dają początek dwóm nowym kopiom trójkąta Pascala, a pomiędzy nimi znajdują się zera. Warstwa $W_{j + 1}$ ma tyle samo wierszy, co warstwy $W_0, W_1, \ldots, W_j$ razem wzięte, więc w podstawie każdego z tych dwóch trójkątów na dole warstwy $W_{j + 1}$ znajdzie się ten sam układ cyfr, co i w ostatnim wierszu warstwy $W_j$ , czyli rząd jedynek. Wypełnią one ostatni rząd warstwy $W_{j + 1}$ . Kończy to dowód tezy indukcyjnej.

Liczba $p_n$ określona w zadaniu równa się stosunkowi liczby zer w wierszach o numerach od $0$ do $2^n$ do liczby wszystkich elementów tych wierszy. Wiersze te obejmują warstwy $W_0, W_1, \ldots, W_n$ oraz pierwszy wiersz warstwy $W_{n+1}$ . Z wyżej udowodnionego związku wynika, że w sumie warstw $W_0, \ldots, W_j$ jest trzykrotnie więcej jedynek, niż w sumie warstw $W_0, \ldots, W_{j-1}\ (j = 1, 2, 3,\ldots)$ , a ponieważ w warstwie $W_0$ jest jedna jedynka, więc w sumie warstw $W_0, \ldots, W_n$ jest $3^n$ jedynek. Doliczając do tego dwie skrajne jedynki następnego wiersza widzimy, że w rozważanym fragmencie trójkąta Pascala jest $a_n = 3^n+ 2$ jedynek. Wszystkich elementów jest w tym fragmencie $b_n= 1 + 2 + 3 + \ldots+ (2^n+ 1) = (2^n+ 1) (2^n+ 2) /2$ , a więc jest tam $b_n- a_n$ zer. Badane prawdopodobieństwo równa się

$ p_n = \frac{b_n-a_n}{b_n} = 1 - \frac{a_n}{b_n} = 1 - \frac{2(3^n+2)}{4^n+3 \cdot 2^n + 2} = 1 - \frac{2 \left( \left( \frac{3}{4}\right)^n + 2\left( \frac{1}{4} \right)^n \right)}{1 + 3 \left( \frac{2}{4}\right)^n + 2 \left( \frac{1}{4}^n \right)}. $

Stąd $\displaystyle \lim_{n \to \infty} p_n = 1$ .