XXIX OM - III etap

III etap XXIX Olimpiady Matamatycznej

XXIX OM - III - Zadanie 1

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

III

W danym kącie wypukłym na płaszczyźnie biegnie promień światła odbijając się od ramion kąta zgodnie z zasadą, że kąt padania równa się kątowi odbicia. Promień, który trafi w wierzchołek kąta, zostaje pochłonięty. Udowodnić, że istnieje taka liczba naturalna $n$ , że każdy promień może odbić się od ramion kąta co najwyżej $n$ razy.

Rozwiązanie

Jeżeli promień światła wychodząc z punktu $C$ odbija się od jednego z ramion danego kąta w punkcie $P$ , a następnie od, drugiego ramienia w punkcie $Q$ , to dokonując symetrii $\varphi$ względem prostej $OP$ , gdzie $O$ jest wierzchołkiem danego kąta, stwierdzamy, że punkty $C$ , $P$ i $\varphi(Q)$ są współliniowe (rys. 15). Wynika to z równości kątów $\measuredangle CPA = \measuredangle QPO = \measuredangle \varphi(Q)PO$ .

Wobec tego zadanie sprowadza się do następującego: Z punktu $O$ prowadzimy półproste $m_1, m_2, \ldots, m_k, m_{k+1}, \ldots$ tak, że $\measuredangle (m_i, m_{i+1}) = \theta$ dla $i = 1, 2, \ldots$ (rys. 16). Należy udowodnić, że istnieje liczba naturalna $n$ o tej własności, że każda półprosta $m$ przechodząca przez pewien punkt położony wewnątrz kąta $\measuredangle (m_1, m_2)$ i przecinająca półprostą $m_2$ przecina kolejno nie więcej niż $n$ z narysowanych półprostych.

By to udowodnić, wystarczy tak obrać $k$ , by $(k - 2)\theta < \pi \leq (k - 1)\theta$ . Wtedy $\measuredangle (m_2, m_{k+1}) = (k - 1)\theta \geq \pi$ i półprosta $m$ przecinając półprostą $m_2$ nie przetnie już półprostej $m_{k+1}$ , ponieważ półproste $m_3$ i $m_{k+1}$ nie leżą w tej samej półpłaszczyźnie otwartej wyznaczonej przez prostą zawierającą półprostą $m_2$ . Tak więc półprosta $m$ przetnie co najwyżej $k - 1$ danych półprostych $m_2, m_3, \ldots ,m_k$ , gdzie $k - 2 < \frac{\pi}{\theta}$ , to znaczy $k - 1 < \frac{\pi}{\theta} + 1$ . Zatem promień światła odbije się od ramion danego kąta mniej niż $\frac{\pi}{\theta} + 1$ razy. Wystarczy więc przyjąć $n = \left[ \frac{\pi}{\theta} \right] + 1$ .

XXIX OM - III - Zadanie 2

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

III

Na płaszczyźnie dane są punkty o współrzędnych całkowitych, z których co najmniej jedna jest niepodzielna przez A. Dowieść, że punktów tych nie można tak połączyć w pary, aby odległość punktów każdej pary była równa 1; to znaczy nieskończonej szachownicy z wyciętymi polami o współrzędnych podzielnych przez 4 nie można pokryć kostkami domina.

Rozwiązanie

Rozważmy zbiór $A$ punktów na płaszczyźnie o współrzędnych całkowitych $(i, j)$ , gdzie $0 \leq i, j \leq 4k$ . Zauważmy, że jeżeli połączymy punkty w pary zgodnie z warunkami zadania, to suma współrzędnych jednego punktu każdej pary będzie liczbą nieparzystą, a drugiego parzystą.

Zbiór $A$ ma $(4k + 1)^2$ punktów, w tym $(k + 1)^2$ punktów ma obie współrzędne podzielne przez $4$ i na mocy warunków zadania punktów takich nie bierzemy pod uwagę. Liczba punktów zbioru $A$ , których suma współrzędnych jest parzysta, jest o $1$ większa od liczby punktów zbioru $A$ , których suma współrzędnych jest nieparzysta. Zatem liczba tych pierwszych punktów jest równa $8k^2 + 4k + 1$ , a drugich $8k^2 + 4k$ .

Na brzegu kwadratu wyznaczonego przez punkty zbioru $A$ jest $8k$ punktów o nieparzystej sumie współrzędnych (po $2k$ na każdym boku kwadratu).

Zgodnie z warunkami zadania $(8k^2 + 4k) - 8k = 8k^2 - 4k$ punktów zbioru $A$ o nieparzystej sumie współrzędnych, które leżą wewnątrz rozważanego kwadratu, należy połączyć w pary z pewnymi z $(8k^2 + 4k + 1) - (k + 1)^2 = 7k^2 + 2k$ punktów należących do zbioru $A$ o parzystej sumie współrzędnych, lecz nie o obu współrzędnych podzielnych przez $4$ .

Jeżeli więc można by było połączyć punkty płaszczyzny w pary zgodnie z warunkami zadania, to dla każdej liczby naturalnej $k$ zachodziłaby nierówność

$ 8k^2 -4k \leq 7k^2 + 2k, $

czyli $k^2 \leq 6k$ . Jednak już dla $k = 7$ nierówność ta nie zachodzi.

Wobec tego nie można połączyć danych punktów w pary zgodnie z warunkami zadania.

Uwaga. Jeżeli pola szachownicy są na przemian koloru białego i czarnego i jedno z wyciętych pól jest czarne, to wszystkie wycięte pola są czarne. Ponieważ kostka domina pokrywa jedno pole białe i jedno czarne, więc liczba pól każdego koloru pokrytych kostkami domina jest taka sama. Jeżeli więc rozpatrujemy odpowiednio dużą część skończoną szachownicy nieskończonej, to będzie tam zbyt dużo pól białych, by można było wszystkie pokryć kostkami domina. Na tej myśli jest oparte podane wyżej rozwiązanie.

XXIX OM - III - Zadanie 3

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

III

Dowieść, że jeżeli

$ x^{2m} \cdot P(x, y) + y^{2m} \cdot Q(x, y) = (x+y)^{2m} \cdot R(x, y), $

gdzie $m$ jest liczbą naturalną, $P, Q, R$ są wielomianami stopni mniejszych od $m$ , to każdy z tych wielomianów jest wielomianem zerowym.
Uwaga. Stopniem wielomianu niezerowego $W(x, y) = \sum a_{ij}x^iy_^j$ nazywamy maksymalną liczbę całkowitą $i + j$ , dla której $a_{ij}\neq 0$ . Za stopień wielomianu zerowego przyjmujemy liczbę 0.

Rozwiązanie

\spos{1} Jeżeli wielomian $P(x,y)$ nie jest zerowy, to istnieje taka liczba $a \ne 0$ , że wielomian jednej zmiennej $P(x, a)$ nie jest zerowy. Podstawiając w równości danej w zadaniu $y = a$ otrzymujemy

$ (1) \qquad x^{2m} \cdot P (x, a) + a^{2m} \cdot Q (x, a) = (x + a)^{2m} \cdot R (x, a). $

Wielomian $F(x)$ stojący po lewej stronie równości (1) nie jest zerowy i jest sumą co najwyżej $2m$ jednomianów, ponieważ z założenia stopień każdego z wielomianów $P(x, a)$ i $Q (x, a)$ jest mniejszy od $m$ .

Z drugiej strony z (1) wynika, że liczba $(-a)$ jest co najmniej $2m$ -krotnym pierwiastkiem wielomianu $F(x)$ .

Na mocy zadania 24(6) z XXVIII Olimpiady Matematycznej uzyskaliśmy sprzeczność.

Wobec tego wielomian $P(x, y)$ jest zerowy. Analogicznie dowodzimy, że wielomian $Q(x,y)$ jest zerowy, a wobec tego i,wielomian $R (x, y)$ jest zerowy.

XXIX OM - III - Zadanie 4

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

III

Niech $X$ będzie zbiorem $n$ -elementowym. Udowodnić, że suma liczb elementów zbiorów $A \cap B$ rozciągnięta na wszystkie pary uporządkowane $(A, B)$ podzbiorów zbioru $X$ równa jest $n\cdot 4^{n-1}$ .

Rozwiązanie

Niech $a$ będzie ustalonym elementem zbioru $X$ . Liczba podzbiorów zbioru $X$ zawierających element $a$ jest równa liczbie wszystkich podzbiorów zbioru $(n-1)$ -elementowego $X- \{a\}$ , to znaczy jest równa $2_{n-1}$ . Wobec tego liczba takich par $(A, B)$ podzbiorów zbioru $X$ , że $a \in A \cap B$ , jest równa $(2^{n-1})^2 =4^{n-1}$ .

Inaczej mówiąc, w sumie, o której jest mowa w zadaniu, element $a$ jest liczony $4^{n-1}$ razy. Ponieważ zbiór $X$ ma $n$ elementów, więc cała ta suma jest równa $n \cdot 4^{n-1}$ .

XXIX OM - III - Zadanie 5

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

III

Dana jest liczba rzeczywista $a$ . Definiujemy ciąg $(a_n)$ w sposób następujący

$ a_1 = a, $

$ a_{n+1} = \begin{cases} \frac{1}{2}\left(a_n-\frac{1}{a_n}\right), & \mathrm{ jeżeli }a_n \neq 0, \\ 0, &\mathrm{ jeżeli } a_n = 0. \end{cases} $

Udowodnić, że ciąg $(a_n)$ ma nieskończenie wiele wyrazów nieujemnych i nieskończenie wiele wyrazów niedodatnich.

Rozwiązanie

Jeżeli pewien wyraz ciągu $(a_n)$ jest równy zeru, to wszystkie następne wyrazy tego ciągu też są równe zeru i teza zadania jest spełniona. Załóżmy więc, że wszystkie wyrazy ciągu $(a_n)$ są różne od zera.

Niech $d_n = a_{n+1} - a_n$ . Obliczamy, że

$ d_n^2 = (a_{n+1} - a_n)^2 = a_{n+1}^2 - 2a_na_{n+1} + a_n^2 = a_{n+1}^2 + 1 > 1. $

Zatem $|d_n| > 1$ .

Jeżeli począwszy od pewnego miejsca wyrazy ciągu $(a_n)$ są dodatnie, to $a_{n+1} = \frac{1}{2} \left( a_n - \frac{1}{a_n} \right) < \frac{1}{2} a_n < a_n$ , to znaczy ciąg $(a_n)$ jest malejący. Jednak ciąg malejący, którego wyrazy kolejne różnią się więcej niż o $1$ , nie może zawierać tylko wyrazów dodatnich.

Jeżeli począwszy od pewnego miejsca wyrazy ciągu są ujemne, to $a_{n+1} = \frac{1}{2} \left( a_n - \frac{1}{a_n} \right) > \frac{1}{2} a_n > a_n$ , to znaczy ciąg $(a_n)$ jest rosnący.

Jednak ciąg rosnący, którego wyrazy, kolejne różnią się więcej niż o $1$ , nie może zawierać tylko wyrazów ujemnych.

Wobec tego ciąg $(a_n)$ zawiera nieskończenie wiele wyrazów dodatnich i nieskończenie wiele wyrazów ujemnych.

XXIX OM - III - Zadanie 6

Zawody matematyczne:

XXIX OM, 1977-1978

Etap:

III

Dowieść, że jeżeli w dowolnym czworościanie $h_1, h_2, h_3, h_4$ są długościami czterech wysokości, $d_1, d_2, d_3$ zaś odległościami trzech par prostych zawierających przeciwległe krawędzie, to

$ \frac{1}{h_1^2} + \frac{1}{h_2^2} + \frac{1}{h_3^2} + \frac{1}{h_4^2} = \frac{1}{d_1^2} + \frac{1}{d_2^2} + \frac{1}{d_3^2} $

Rozwiązanie

Niech dany będzie czworościan $ABCD$ . Rozpatrzmy graniastosłup $ABCDEF$ o podstawie $ABC$ i tworzącej $\overline{AD}$ . Objętość $V_S$ tego graniastosłupa jest trzy razy większa od objętości $V$ danego czworościanu. Poza tym $V = \frac{1}{3}h_1 \cdot S_{ABC}$ , gdzie $h_1$ jest długością wysokości czworościanu poprowadzonej z wierzchołka $D$ .

Rozważany graniastosłup jest sumą danego czworościanu i ostrosłupa $BCDEF$ (rys. 17). Wobec tego $V_S = V + \frac{1}{3} d_1 \cdot S_1$ , gdzie $d_1$ jest długością wysokości ostrosłupa poprowadzonej z wierzchołka $D$ , czyli odległością krawędzi przeciwległych $\overline{AD}$ i $\overline{BC}$ danego czworościanu, a $S_1$ - polem równoległoboku wyznaczonego przez parę wektorów $\overrightarrow{BC}$ i $\overrightarrow{BE} = \overrightarrow{AD}$ odpowiadających parze krawędzi przeciwległych $\overline{BC}$ i $\overline{AD}$ danego czworościanu.

Z powyższych zależności otrzymujemy

$ \frac{1}{h_1} = \frac{S_{ABC}}{3V} \ \textrm{i} \ \frac{1}{d_1} = \frac{S_1}{6v}. $

Analogicznie znajdujemy podobne wyrażenia dla $h_2$ , $h_3$ , $h_4$ , $d_2$ , $d_3$ . Podstawiając je do równości podanej w zadaniu dochodzimy do równości równoważnej:

$ (1) \qquad 4 (S^2_{ABC} + S2_{BCD} + S2_{ACD} + S2_{ABD}) = S_1^2 + S_2^2 + S_3^2, $

gdzie $S_1$ , $S_2$ , $S_3$ są polami równoległoboków wyznaczonych przez wektory odpowiadające parom krawędzi przeciwległych danego czworościanu.

Udowodnimy wzór (1) za pomocą rachunku wektorowego. Kwadrat pola równoległoboku wyznaczonego przez wektory $\overrightarrow{u}$ i $\overrightarrow{v}$ jest
równy $(\overrightarrow{u} \times \overrightarrow{v} )^2$ . Oznaczając $\overrightarrow{a} = \overrightarrow{AB}$ , $\overrightarrow{b} = \overrightarrow{AC}$ , $\overrightarrow{c} = \overrightarrow{AD}$ otrzymamy $\overrightarrow{BC} = \overrightarrow{b} - \overrightarrow{a}$ , $\overrightarrow{CD} = \overrightarrow{c} - \overrightarrow{b}$ , $\overrightarrow{BD} = \overrightarrow{c} - \overrightarrow{a}$ . Wobec tego równość (1) przyjmuje postać

$ \begin{split} (2) \qquad & (\overrightarrow{a} \times \overrightarrow{b})^2 + ((\overrightarrow{b} - \overrightarrow{a}) \times (\overrightarrow{c} -\overrightarrow{a}))^2 + (\overrightarrow{b} \times \overrightarrow{c})^2 + (\overrightarrow{a} \times \overrightarrow{c})^2 =\\ &\quad = ((\overrightarrow{b} - \overrightarrow{a}) \times \overrightarrow{c})^2 + ((\overrightarrow{c} - \overrightarrow{b}) \times \overrightarrow{a})^2 + ((\overrightarrow{c} - \overrightarrow{a}) \times \overrightarrow{b})^2. \end{split} $

Przekształcamy stronę prawą $P$ równości (2) korzystając z następujących praw działań na wektorach:

$ \begin{split} (\overrightarrow{u} + \overrightarrow{v}) \times \overrightarrow{w} &= \overrightarrow{u} \times \overrightarrow{w} + \overrightarrow{v} \times \overrightarrow{w},\ (\overrightarrow{u} + \overrightarrow{v} ) \cdot \overrightarrow{w} = \overrightarrow{u} \cdot \overrightarrow{w} + \overrightarrow{v} \cdot \overrightarrow{w},\\ \overrightarrow{u} \times \overrightarrow{v} &= -(\overrightarrow{v} \times \overrightarrow{u}), \ \textrm{stąd} \ \overrightarrow{u} \times \overrightarrow{u} = 0, \overrightarrow{u} \cdot \overrightarrow{v} = \overrightarrow{v} \cdot \overrightarrow{u}.\\ P &= (\overrightarrow{b} \times \overrightarrow{c})^2 - 2(\overrightarrow{b} \times \overrightarrow{c})(\overrightarrow{a} \times \overrightarrow{c}) + (\overrightarrow{a} \times \overrightarrow{c})^2+\\ & \quad + (\overrightarrow{c} \times \overrightarrow{a})^2 - 2(\overrightarrow{c} \times \overrightarrow{a})(\overrightarrow{b} \times \overrightarrow{a}) + (\overrightarrow{b} \times \overrightarrow{a})^2+\\ & \quad + (\overrightarrow{c} \times \overrightarrow{b})^2 - 2(\overrightarrow{c} \times \overrightarrow{b})(\overrightarrow{a} \times \overrightarrow{b}) + (\overrightarrow{a} \times \overrightarrow{b})^2. \end{split} $

Ponieważ

$ \begin{split} ((\overrightarrow{b} - \overrightarrow{a}) \times (\overrightarrow{c} - \overrightarrow{a}))^2 &= (\overrightarrow{b} \times \overrightarrow{c} - \overrightarrow{b} \times \overrightarrow{a} - \overrightarrow{a} \times \overrightarrow{c})^2 =\\ &= (\overrightarrow{b} \times \overrightarrow{c})^2 + (\overrightarrow{b} \times \overrightarrow{a})^2 + (\overrightarrow{a} \times \overrightarrow{c})^2+\\ &\quad - 2(\overrightarrow{b} \times \overrightarrow{c})(\overrightarrow{b} \times \overrightarrow{a}) - 2 (\overrightarrow{b} \times \overrightarrow{c}) (\overrightarrow{a} \times \overrightarrow{c})+\\ &\quad - 2 (\overrightarrow{b} \times \overrightarrow{a}) (\overrightarrow{c} \times \overrightarrow{a}), \end{split} $

więc strona lewa $L$ równości (2) jest równa

$ \begin{split} L = & 2(\overrightarrow{a} \times \overrightarrow{b})^2 + 2(\overrightarrow{b} \times \overrightarrow{c})^2 + 2(\overrightarrow{a} \times \overrightarrow{c})^2 - 2(\overrightarrow{b} \times \overrightarrow{c})(\overrightarrow{b} \times \overrightarrow{a}) +\\ & - 2(\overrightarrow{b} \times \overrightarrow{c})(\overrightarrow{a} \times \overrightarrow{c}) - 2(\overrightarrow{b} \times \overrightarrow{a})(\overrightarrow{c} \times \overrightarrow{a}). \end{split} $

Wobec tego widzimy, że $L = P$ , to znaczy równość (2) jest prawdziwa.