XXXIII OM - III etap

III etap XXXIII Olimpiady Matematycznej

XXXIII OM - III - Zadanie 1

Zawody matematyczne:

XXXIII OM, 1981-1982

Etap:

III

Wskazać taki sposób rozmieszczenia przy okrągłym stole $n$ dziewcząt i $n$ chłopców, aby liczba $d_n - c_n$ była największa, gdzie $d_n$ jest liczbą dziewcząt, siedzących między dwoma chłopcami, zaś $c_n$ - liczbą chłopców siedzących, między dwiema dziewczętami.

Rozwiązanie

Rozważmy dowolne rozsadzenie $n$ dziewcząt i $n$ chłopców. Nazwijmy grupą $k$ dziewcząt (dla $k > 1$ ) każdy ciąg $k$ dziewcząt siedzących obok sie*bie, jeśli pierwsza i $k$ -ta dziewczynka z tego ciągu sąsiaduje przy stole z chłopcem. Niech $D_n$ będzie liczbą grup dziewcząt w danym rozsadzeniu. Analogicznie definiujemy grupę $k$ chłopców. Niech $C_n$ będzie liczbą grup chłopców. Ponieważ każda grupa dziewcząt sąsiaduje z grupą chłopców lub z pojedynczym chłopcem i każda grupa chłopców sąsiaduje z grupą dziewcząt lub z pojedynczą dziewczynką, więc

$ d_n + D_n = c_n + C_n, $

skąd

$ (*) \qquad d_n - c_n = C_n - D_n. $

Jeśli $D_n = 0$ , to każda dziewczynka sąsiaduje z dwoma chłopcami, skąd wynika, że każdy chłopiec sąsiaduje z dwiema dziewczynkami, więc $C_n = 0$ i $d_n - c_n = 0$ . Jeśli natomiast $D_n \geq 1$ , to z równości (*) wynika, że

$ d_n - c_n \leq C_n - 1. $

Z drugiej strony $C_n$ jest liczbą grup chłopców, a każda grupa zawiera co
najmniej dwóch chłopców, więc $C_n \leq \frac{n}{2}$ . Ponadto $C_n$ jest liczbą całkowitą, więc $C_n \leq \left[ \frac{n}{2} \right]$ . ( $[k]$ jest największą liczbą całkowitą mniejszą lub równą $k$ ). Wobec tego

$ d_n - c_n \leq \left[ \frac{n}{2} \right] - 1 $

przy każdym rozsadzeniu $n$ dziewcząt i $n$ chłopców.

Pokażemy teraz takie rozsadzenie, przy którym $d_n - c_n = \left[ \frac{n}{2} \right] - 1$ . Jeśli $n = 2k$ , to sadzamy kolejno dwóch chłopców, jedną dziewczynkę, dwóch chłopców, jedną dziewczynkę itd., wreszcie ostatnich dwóch chłopców i dalej pozostałe dziewczęta. Przy tym rozsadzeniu $k - 1$ dziewcząt ma po obu stronach chłopców, natomiast żaden chłopiec nie ma dwóch sąsiadek.

Jeśli $n = 2k + 1$ , to sadzamy podobnie: dwóch chłopców, jedną dziewczynkę, dwóch chłopców, jedną dziewczynkę itd. wreszcie ostatnich trzech chłopców i resztę dziewcząt. W tej sytuacji również $k - 1$ dziewcząt siedzi między dwoma chłopcami, a żaden chłopiec nie ma dwóch sąsiadek.

Wobec tego maksymalna wartość $d_n - c_n$ wynosi $\left[ \frac{n}{2} \right]-1$ .

XXXIII OM - III - Zadanie 2

Zawody matematyczne:

XXXIII OM, 1981-1982

Etap:

III

W czworokącie $ABCD$ wpisanym w koło prosta przechodząca przez środek boku $\overline{AB}$ i punkt przecięcia przekątnych jest prostopadła do boku $\overline{CD}$ . Udowodnić, że boki $\overline{AB}$ i $\overline{CD}$ są równoległe lub przekątne czworokąta są prostopadłe.

Rozwiązanie

Niech $O$ będzie punktem przecięcia przekątnych, $E$ - środkiem boku $\overline{AB}$ , $F$ - punktem przecięcia boku $\overline{CD}$ i prostej $EC$ . Ponieważ czworokąt $ABCD$ jest wpisany w koło, więc

$ | \measuredangle BAC| = | \measuredangle BDC| = \alpha, $

$ | \measuredangle ABD| = | \measuredangle ACD| = \beta. $

Wobec tego

$ | \measuredangle BOE| = | \measuredangle DOF| = 90^\circ - \alpha, $

$ | \measuredangle AOE| = | \measuredangle COF| = 90^\circ - \beta. $

Z twierdzenia sinusów zastosowanego kolejno do trójkątów $AOE$ i $BOF$ otrzymujemy

$ \frac{\sin \alpha}{OE} = \frac{\sin (90^\circ - \beta)}{AE},\ \frac{\sin \beta}{OE} = \frac{\sin (90^\circ - \alpha)}{BE} $

Ponieważ $EA = BE$ , więc dzieląc ostatnie równania stronami otrzymamy

$ \frac{\sin \alpha}{\sin \beta} = \frac{\sin(90^\circ - \beta)}{\sin (90^\circ - \alpha)} $

stąd na podstawie odpowiedniego wzoru redukcyjnego

$ \frac{\sin \alpha}{\sin \beta}=\frac{\cos \beta}{\cos \alpha} $

$ \sin \alpha \cos \alpha = \sin \beta cos \beta, $

$ \sin 2 \alpha = \sin 2 \beta. $

Ponieważ $0 < \alpha < 90^\circ$ , $0 < \beta < 90^\circ$ , więc albo a) $2 \alpha = 2 \beta$ , albo b) $2 \gamma = 180^\circ - 2\beta$ . W przypadku a) zachodzi równość $\alpha = \beta$ , a więc proste $AB$ i $CD$ przecięte prostą $AC$ wyznaczają przystające kąty naprzemianległe;

$ |\measuredangle BAC| = |\measuredangle ACD|. $

Wynika stąd, że $AB || CD$ .

W przypadku b) otrzymujemy $\alpha =90^\circ - \beta$ , tj. $\alpha + \beta = 90^\circ$ i w trójkącie $ABO$ jest $|\measuredangle BAC| + |\measuredangle ABO| = 90^\circ$ . Wynika stąd, że $|\measuredangle AOB|= 90^\circ$ , to jest przekątne $\overline{AC}$ i $\overline{BD}$ są prostopadłe.

XXXIII OM - III - Zadanie 3

Zawody matematyczne:

XXXIII OM, 1981-1982

Etap:

III

Wyznaczyć wszystkie pary liczb dodatnich $x, y$ spełniające układ równań

$ \begin{split} x^2 + y^2 &= a^2 + b^2 \\ x^3 + y^3 &= a^3 + b^3 \end{split} $

gdzie $a, b$ są danymi liczbami dodatnimi.

Rozwiązanie

Jeżeli para liczb dodatnich $(x,y)$ spełnia dany układ równań, to $y = \sqrt{a^2 + b^2 - x^2}$ ,

$ x^3 + \sqrt{(a^2 + b^2 - x^2)}^3 - a^3 - b^3 = 0. $

Rozważmy funkcję $f$ określoną w przedziale $(0, \sqrt{a^2 + b^2}$ wzorem

$ f(x) = x^3 + (\sqrt{a^2 + b^2 - x^2})^3 - a^3 - b^3. $

Funkcja ta przyjmuje wartość $0$ dla $x = a$ oraz $x = b$ . Pokażemy, że nie ma ona innych miejsc zerowych. Funkcja $f$ ma pochodną

$ f'(x) = 3x^2 + \frac{3}{2} (a^2 + b^2+ x^2)^{\frac{1}{2}} \cdot (- 2x) = 3x^2 - 3x\sqrt{a^2 + b^2 - x^2}. $

Funkcja $f'$ w przedziale $(0, a^2 + b^2)$ ma tylko jedno miejsce zerowe $x = \sqrt{\frac{a^2+b^2}{2}}$ ( $3x^2 - 3x \sqrt{a^2 + b^2-x^2}=0$ , $2x^2 = a^2 + b^2$ , $x =\sqrt{\frac{a^2+b^2}{2}}$ , gdyż $x > 0$ ). Funkcja $F$ ma tylko miejsca zerowe $x = a$ i $x= b$ , gdyż pomiędzy tymi pierwiastkami jest tylko jedno miejsce zerowe pochodnej $x = \sqrt{\frac{a^2+b^2}{2}}$ . Wobec tego jedynymi rozwiązaniami danego układu równań są pary $(a, b)$ i $(b, a)$ .

XXXIII OM - III - Zadanie 4

Zawody matematyczne:

XXXIII OM, 1981-1982

Etap:

III

Na płaszczyźnie dany jest skończony zbiór punktów. Dowieść, że zbiór ten można pokryć otwartymi kwadratami rozłącznymi $Q_1, Q_2, \ldots, Q_n$ , tak, że

$ 1\leq \frac{N_j}{S_j} \leq 4 $

( $j = 1, 2,\ldots, n$ ) gdzie $N_j$ jest liczbą punktów zbioru leżących w kwadracie $Q_j$ , zaś $S_j$ jest polem kwadratu $Q_j$ .

Rozwiązanie

Obieramy na płaszczyźnie taki układ współrzędnych, aby zbiór punktów, których liczbę oznaczymy literą $N$ , leżał wewnątrz pierwszej ćwiartki i dodatkowo jeszcze żadna ze współrzędnych jego punktów nie dała się przedstawić w postaci $\frac{k}{2n}$ , gdzie $k$ , $n$ są liczbami naturalnymi. Niech $d$ będzie taką liczbą naturalną, że kwadrat $Q$ o wierzchołkach $(0,0)$ , $(d, 0)$ , $(d, d)$ , $(0, d)$ zawiera w swym wnętrzu wszystkie dane punkty. Niech $N$ będzie liczbą danych punktów. Rozważmy następujące przypadki

$ a) 1 \leq \frac{N}{d^2} \leq 4,\ b) \frac{N}{d^2} > 4,\ c) \frac{N}{d^2} < 1. $

W przypadku a) kwadrat $Q$ spełnia wymagane warunki. W przypadku b) przyjmujemy $d_1 = \frac{\sqrt{N}}{2}$ $(d_1> d)$ i kwadrat $Q_1$ o wierzchołkach $(0, 0)$ ,
$(d_1, 0)$ , $(d_1, d_1)$ , $(0, d_1)$ spełnia warunki zadania.

W przypadku c) dzielimy kwadrat $Q$ na cztery przystające kwadraty. Ze sposobu wyboru układu współrzędnych wynika, że każdy z danych punktów należy do wnętrza jednego z tych kwadratów. Dla każdego z tych kwadratów jest $S_i = \frac{d^2}{4}$ oraz $N_i \leq N$ , więc

$ \frac{N_i}{S_i} \leq \frac{N}{\frac{d^2}{4}} < 4. $

Te kwadraty, dla których $0 < \frac{N_i}{S_i} < 1$ dzielimy ponownie na cztery przystające kwadraty, przy czym żaden z danych punktów nie leży na brzegu nowego kwadratu. Postępowanie to kontynuujemy. Po $m$ -tym podziale jest albo $N_i = 0$ albo $\frac{N_i}{S_i} \geq \frac{1}{S_i}$ . Jeżeli $\frac{N_i}{S_i} \geq \frac{1}{S_i}$ , to $\frac{N_i}{S_i} \geq \frac{2^{2m}}{d^2}$ , gdyż $S_i = \left( \frac{d}{2^m} \right)^2$ .

Zatem po nie więcej niż $[\log_2d] + 1$ podziałach dla każdego kwadratu będzie spełniona nierówność

$ 1 \leq \frac{N_i}{S_i} \leq 4. $

XXXIII OM - III - Zadanie 5

Zawody matematyczne:

XXXIII OM, 1981-1982

Etap:

III

Liczby całkowite $x_0, x_1, x_2, \ldots, x_n = x_0, x_{n+1} = x_1$ spełniają dla $k = 1, 2, \ldots, n$ nierówność

$ (-1)^{x_k} \cdot x_{k-1} \cdot x_{k+1} > 0. $

Dowieść, że różnica

$ \sum_{k=0}^{n-1} x_k - \sum_{k=0}^{n-1} |x_k| $

dzieli się przez 4.

Rozwiązanie

Z warunku

$ (-1)^{x_k} \cdot x_{k-1} \cdot x_{k+1} > 0 $

wynika, że $x_k \ne 0$ dla $k = 1, 2, \ldots, n$ . Przyjmując $\varepsilon_k = \frac{x_k}{|x_k|}$ otrzymamy nierówność

$ (-1)^{x_k} \varepsilon_{k-1} \varepsilon_{k+1} |x_{k-1} \cdot x_{k+1}| > 0. $

Stąd dostajemy

$ (*) \qquad (-1)^{x_k} \varepsilon_{k-1} \varepsilon_{k+1} > 0. $

Ponieważ mamy $\varepsilon_k = \pm 1$ więc zachodzi równość $\varepsilon_k = (-1)^{\frac{x_k-1}{2}}$ .

Podstawiamy $\lambda_k = \frac{\varepsilon_k-1}{2}$ . Z nierówności (*) otrzymamy

$ (-1)^{x_k} (-1)^{\lambda_{k+1}} (-1)^{\lambda_{k-1}} > 0, $

$ (-1)^{x_k+\lambda_{k+1}+\lambda_{k-1}} > 0, $

a więc

$ \nr{**} x_k + \lambda_{k+1} + \lambda_{k-1} \equiv 0 \pmod 2. $

Podstawiając $S_n = \sum_{k=0}^{n-1} x_k - \sum_{k=0}^{n-1} |x_k|$ otrzymamy

$ S_n = \sum_{k=0}^{n-1} x_k - |x_k| = \sum_{k=0}^{n-1} |x_k| (\varepsilon_k-1)=\sum_{k=0}^{n-1} 2\lambda_k |x_k|. $

Ponieważ $x_n = x_0$ , $x_{n+1} = x_1$ , więc $\varepsilon_n = \varepsilon_0$ , $\varepsilon_{n+1} = \varepsilon_1$ i $\lambda_n = \lambda_0$ , $\lambda_{n+1} = \lambda_1$ , Ponadto w oparciu o (**) i warunek

$ |x_k| \equiv x_k \pmod 2, $

otrzymamy

$ \begin{split} \frac{S_n}{2} = \sum_{k=0}^{n-1} \lambda_k |x_k| \equiv \sum_{k=1}^{n} \lambda_k x_k \equiv \sum_{k=1}^{n}- \lambda_k (\lambda_{k+1} + \lambda_{k-1})=\\ = - \sum_{k=1}^n \lambda_k \lambda_{k+1} - \sum_{k=1}^n \lambda_k \lambda_{k-1} (mod 2). \end{split} $

Warunek $S_n = 0 (mod 4)$ jest spełniony, gdyż

$ \frac{S_n}{2} = - \sum_{k=1}^n \lambda_k \lambda_{k+1} - \sum_{k=1}^n \lambda_k \lambda_{k-1}= -2 \sum_{k=1}^n \lambda_k \lambda_{k-1} \equiv (mod 2). $

XXXIII OM - III - Zadanie 6

Zawody matematyczne:

XXXIII OM, 1981-1982

Etap:

III

Udowodnić, że w dowolnym czworościanie suma wszystkich kątów dwuściennych jest większa od $2\pi$ .

Rozwiązanie

Udowodnimy najpierw następujący lemat.

Lemat. Suma miar kątów płaskich przy wierzchołkach kąta trójściennego jest mniejsza od $2\pi$ .

Dowód. Niech $O$ będzie wierzchołkiem kąta trójściennego, $A$ , $B$ , $C$ - punktami leżącymi na poszczególnych krawędziach w równej odległości od $O$ .

Niech $O'$ będzie rzutem prostokątnym punktu $O$ na płaszczyznę $ABC$ . Ponieważ trójkąty równoramienne $AOB$ i $AO'B$ mają wspólną podstawą $AB$ , a pierwszy z nich ma dłuższe ramiona, więc

$ |\measuredangle AOB| < |\measuredangle AO'B|. $

Mamy więc nierówności

$ |\measuredangle BOC| < |\measuredangle BO'C|, $

$ |\measuredangle COA| < |\measuredangle CO'A|, $

więc

$ |\measuredangle AOB| + |\measuredangle BOC| + |\measuredangle COA| < |\measuredangle AO'B| + |\measuredangle BO'C| + |\measuredangle CO'A|. $

Jeżeli punkt $O'$ należy do trójkąta $ABC$ , to oczywiście

$ |\measuredangle AO'B| + |\measuredangle BO'C| + |\measuredangle CO'A| = 2\pi, $

jeżeli natomiast punkt $O'$ leży na zewnątrz trójkąta $ABC$ i na przykład punkt $C$ należy do kąta $AO'B$ (pozostałe przypadki rozważa się analogicznie), to

$ |\measuredangle AO'B| + |\measuredangle BO'C| + |\measuredangle CO'A| = 2|\measuredangle AO'B| < 2\pi . $

Zatem w każdym przypadku otrzymujemy

$ |\measuredangle AOB| + |\measuredangle BOC| + |\measuredangle COA| < 2\pi $

Niech teraz $\alpha$ , $\beta$ , $\gamma$ , $\delta$ , $\varepsilon$ , $\zeta$ będą kątami dwuściennymi rozważanego czworościanu. W każdym wierzchołku czworościaniu narysujemy wektory normalne (tzn. prostopadłe) do ścian schodzących się w tym wierzchołku. Kąt o mierze $\pi - \varphi$ jest wyznaczony przez wektory normalne do ścian tworzących kąt o mierze $\varphi$ . Suma miar kątów płaskich wyznaczonych przez trójkę wektorów wyprowadzonych z wierzchołka jest na mocy lematu mniejsza od $2\pi$ , suma miar kątów płaskich wyznaczonych przez wektory narysowane we wszystkich wierzchołkach jest więc mniejsza od $8\pi$ . Wśród tych kątów dwukrotnie występuje każdy z kątów o miarach $\pi - |\alpha|, \pi - |\beta|, \ldots, \pi - |\zeta|$ . Wobec tego $2(\pi - |\alpha| + \pi - |beta| + \pi - |\gamma| + \pi - |\delta| + \pi - |\varepsilon| + \pi - |\zeta|) < 8 \pi$ , $|12\pi - 2(|\alpha| + |\beta| + |\gamma| + |\delta| + |\varepsilon| + |\zeta| < 8\pi$ , $2(|\alpha| + |\beta| + |\gamma| + |\delta| + |\varepsilon| + |\zeta|> 4\pi$ , $|\alpha| + |\beta| + |\gamma| + |\delta| + |\varepsilon| + |\zeta| > 2\pi$ .