XXXIV OM - III etap

III etap XXXIV Olimpiady Matematycznej

XXXIV - III - Zadanie 3

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

III

Rozważamy grę jednoosobową na nieskończonej szachownicy opartą na następującej regule. Jeżeli na dwóch polach mających wspólny bok stoją plony i następne pole jest puste (trzy omawiane pola leżą na jednej linii poziomej lub pionowej), to możemy te piony usunąć i postawić jeden pion na trzecim z tych pól (które było puste).
Udowodnić, że jeżeli w pozycji początkowej piony wypełniają prostokąt o liczbie pól podzielnej przez 3, to nie możemy otrzymać pozycji, w której na szachownicy jest tylko jeden pion.

Rozwiązanie

Wprowadzając na płaszczyźnie odpowiedni układ współrzędnych możemy każdemu polu szachownicy przyporządkować parę liczb całkowitych, przy czym dwóm polom sąsiednim leżącym w jednym wierszu pionowym odpowiadają liczby $(m, n)$ i $(m,n+1)$ , a dwóm sąsiednim polom leżącym w jednym wierszu poziomym - liczby $(m, n)$ i $(m+1, n)$ . Każdemu polu szachownicy możemy przyporządkować sumę $m+n$ jego współrzędnych, a następnie resztę z podzielenia $m+n$ przez $3$ . W ten sposób podzielimy wszystkie pola na trzy zbiory:

$ \begin{split} & A_0 = \{(m, n) \colon m+n \equiv 0 \pmod 3\},\\ & A_1 = \{(m, n) \colon m+n \equiv 0 \pmod 3\},\\ & A_2 = \{(m, n) \colon m+n \equiv 0 \pmod 3\}, \end{split} $

Piony ustawione w pozycji początkowej zajmują prostokąt o wymiarach $3k \times l$ lub $l \times 3k$ . W każdym wierszu równoległym do boku długości $3k$ co trzeci pion stoi na polu należącym do $A_0$ , co trzeci - na polu należącym do $A_1$ i co trzeci na polu należącym do $A_2$ (sumy współrzędnych kolejnych pól są kolejnymi liczbami całkowitymi). Wobec tego w pozycji początkowej liczby pionów zajmujących pola należące do $A_0$ , do $A_1$ i do $A_2$ są równe. Jeśli w pewnej pozycji dokładnie $a_0$ pionów zajmuje pola ze zbioru $A_0$ , $a_1$ pionów - pola ze zbioru $A_1$ , $a_2$ pionów - ze zbioru $A_2$ , że dokonując ruchu dozwolonego w grze zabieramy dwa piony, a dostawiamy trzeci, przy czym zmian tych dokonujemy na trzech polach występujących obok siebie w jednym rzędzie, więc każde z tych pól należy do innego ze zbiorów $A_0$ , $A_1$ , $A_2$ . Zatem dwie z liczb $a_0$ , $a_1$ , $a_2$ zmniejszają się o $1$ , pozostała liczba wzrasta o $1$ . Ponieważ w pozycji początkowej liczby pionów zajmujących pola ze zbiorów $A_0$ , $A_1$ , $A_2$ były równe, więc po każdej serii dozwolonych ruchów liczby pionów zajmujących pola ze zbiorów $A_0$ , $A_1$ , $A_2$ są liczbami tej samej parzystości. Jeśli na szachownicy jest tylko jeden pion, to należy on do jednego ze zbiorów $A_1$ np. do $A_0$ i wówczas sytuacji tej odpowiadają liczby $a_0 = 1$ , $a_1 = 0$ , $a_2 = 0$ , które nie są tej samej parzystości. Wynika stąd, że nie można doprowadzić do pozycji, w której na szachownicy pozostałby tylko jeden pion.

XXXIV OM - III - Zadanie 1

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

III

Na płaszczyźnie dany jest $n$ -kąt wypukły $P_1, \ldots, P_n$ oraz punkt $Q$ w jego wnętrzu nie należący do żadnej przekątnej. Dowieść, że jeśli $n$ jest liczbą parzystą, to liczba trójkątów $P_iP_jP_k$ ( $i,j,k= 1,2,\ldots,n$ ), które zawierają punkt $Q$ jest parzysta.

Rozwiązanie

Rozważmy najpierw czworokąt wypukły $ABCD$ i punkt $K$ w jego wnętrzu nie należący do żadnej przekątnej. Punkt $K$ należy do jednej z dwóch półpłaszczyzn o krawędzi $AC$ . Wynika stąd, że punkt $K$ należy do dokładnie dwóch spośród trójkątów $ABC$ , $ABD$ , $ACD$ , $BCD$ (na rys. 11 punkt $K$ należy do trójkątów $ACD$ i $BCD$ ). Udowodniliśmy w ten sposób tezę twierdzenia dla $n = 4$ . Przypuśćmy, że $n$ jest liczbą parzystą większą od $4$ . Wybierając dowolne cztery wierzchołki $P_i$ , $P_j$ , $P_k$ , $P_l$ danego wielokąta otrzymamy czworokąt wypukły. Jeśli punkt $Q$ należy do tego czworokąta, to należy on do dwóch spośród trójkątów $P_iP_jP_k$ , $P_iP_jP_l$ , $P_iP_kP_l$ , $P_jP_kP_l$ ; jeśli punkt $Q$ nie należy do czworokąta, to nie należy również do żadnego z tych trójkątów. W każdym przypadku liczba trójkątów wyznaczonych przez wierzchołki $P_i$ , $P_j$ , $P_k$ , $P_l$ i zawierających punkt $Q$ jest parzysta. Dowolnie ustalony trójkąt $P_iP_jP_k$ jest zawarty w $n-3$ czworokątach o wierzchołkach będących wierzchołkami danego wielokąta. Wobec tego rozważając wszystkie czworokąty $P_iP_jP_kP_l$ i zawarte w nich trójkąty zawierające punkt $Q$ policzymy każdy trójkąt $(n-3)$ -krotnie. Dodając liczby trójkątów zawartych w czworokątach $P_iP_jP_kP_l$ i zawierających punkt $Q$ otrzymamy więc pewną liczbę parzystą równą $(n-3)t$ , gdzie $t$ jest liczbą trójkątów $P_iP_jP_k$ zawierających punkt $Q$ . Ponieważ $n-3$ jest liczbą nieparzystą (bo $n$ jest liczbą parzystą), więc liczba rozważanych trójkątów jest parzysta.

XXXIV OM - III - Zadanie 2

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

III

Dana jest liczba niewymierna $a$ należąca do przedziału $(0,1)$ i liczba naturalna $N$ . Udowodnić, że istnieją takie liczby naturalne $p, q, r, s$ , że

$ \frac{p}{q} < a < \frac{r}{s}, \; \frac{r}{s} - \frac{p}{q} < \frac{1}{N} \quad \text{oraz} \quad rq-ps=1. $

Rozwiązanie

Niech $k$ będzie największą liczbą naturalną spełniającą nierówność $\frac{1}{k} > a$ . Wobec tego

$ (1) \qquad \frac{1}{1+k} < a < \frac{1}{k}, $

a zatem przyjmując $p_0 = 1$ , $q_0= k+1$ , $r_0 = 1$ , $s_0=k$ mamy spełnioną nierówność

$ \frac{p_0}{q_0} < a < \frac{r_0}{s_0} $

oraz warunek $r_0q_0-p_0s_0 = 1$ , gdyż $1 \cdot (k+1)-1 \cdot k = 1$ . Jeżeli ponadto $\frac{1}{k} - \frac{1}{k+1} < \frac{1}{N}$ , to liczby $p_0$ , $q_0$ , $r_0$ , $s_0$ stanowią rozwiązanie zadania. Jeśli ostatnia nierówność nie jest spełniona to następujący lemat wskaże drogę do rozwiązania.

Lemat. Jeśli liczby naturalne $b$ , $c$ , $d$ , $e$ spełniają warunki

$ \frac{b}{c} < \frac{d}{e} \ \textrm{oraz} \ dc-be=1, $

$ \begin{split} & \frac{b}{c} < \frac{b+d}{c+e},\ (b+d)c - b(c+e) = 1,\ \frac{b+d}{c+e} - \frac{b}{c} = \frac{1}{(c+e)c}, \\ & \frac{b+d}{c+e} < \frac{d}{e},\ d(e+c)-(b+d)e=1,\ \frac{d}{e} - \frac{b+d}{c+e} = \frac{1}{e(c+e)}. \end{split} $

Dowód. $(b+d)c-b(c+e)= bc+dc-bc-be= dc-be = 1$ . Obliczamy różnicę

$ \frac{b+d}{c+e}- \frac{b}{c} = \frac{(b+d)c-b(c+e)}{(c+e)c} = \frac{1}{(c+e)c}, $

skąd oczywiście wynika, że $\displaystyle \frac{b}{c} < \frac{b+d}{c+e}$ . Pozostałe warunki otrzymujemy analogicznie.

Rozważamy cztery ciągi liczb naturalnych $(p_n)$ , $(q_n)$ , $(r_n)$ , $(s_n)$ określone, jak następuje:

$ \begin{split} p_0 = 1,\ q_0 = k+1,\ r_0=1, s_0 = k,\\ p_{n+1} = p_n,\ q_{n + 1} = q_n, r_{n+1} = p_n+r_n,\ s_{n + 1} = q_n+s_n, \end{split} $

gdy

$ \frac{p_n}{q_n} < a < \frac{p_n+r_n}{q_n+s_n} $

oraz

$ p_{n+1} = p_n+r_n,\ q_{n + 1}= q_n+s_n,\ r_{n + 1}= r_n, s_{n + 1} = s_n, $

gdy

$ \frac{p_n+r_n}{q_n+s_n} < a < \frac{r_n}{s_n} $

Z powyższego określenia wynika, na podstawie nierówności (1) i lematu, że liczby $p_n$ , $q_n$ , $r_n$ , $s_n$ spełniają warunki

$ \frac{p_n}{q_n} < a < \frac{r_n}{s_n},\ r_nq_n - p_ns_n=1 \ \textrm{oraz} \ \frac{r_n}{s_n}-\frac{p_n}{q_n}=\frac{1}{s_nq_n}. $

Iloczyny $q_ns_n$ tworzą ciąg ściśle rosnący, bowiem przy przejściu od $n$ do $n+ 1$ jeden z czynników zwiększa się, drugi zaś pozostaje nie zmieniony. Wobec tego wystarczy przyjąć tak duże $n$ , żeby zachodziła nierówność $s_nq_n > N$ . Liczby $p_n$ , $q_n$ , $r_n$ , $s_n$ spełniają wówczas warunki zadania.

XXXIV OM - III - Zadanie 4

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

III

Udowodnić, że jeżeli liczby naturalne $a, b, c, d$ spełniają równość $ab = cd$ , to

$ \frac{\mathrm{NWD}(a, c)\cdot \mathrm{NWD}(a, d)}{\mathrm{NWD}(a, b, c, d)} = a. $

Rozwiązanie

Udowodnimy najpierw, że dla dowolnych liczb naturalnych $k$ , $j$ , $m$ , $n$

$ (1) \qquad \mathrm{NWD}(k,l) \cdot \mathrm{NWD} (m, n) = \mathrm{NWD} (km, kn, lm, ln). $

Jeśli liczba pierwsza $p$ spełnia relacje $p^\alpha | \mathrm{NWD} (k, l)$ oraz $p^\beta | \mathrm{NWD} (m,n)$ , to $p^\alpha | k$ , $p^\alpha | l$ , $p^\beta | m$ , $p^\beta | n$ , więc $p^{\alpha+\beta}$ dzieli każdą z liczb $km$ , $kn$ , $lm$ , $ln$ . Stąd $p^{\alpha+\beta} | \mathrm{NWD} (km, kn, lm, ln)$ . Wobec tego $\mathrm{NWD} (k, l) \cdot \mathrm{NWD} (m, n) | \mathrm{NWD} (km, kn, lm, ln)$ .

Jeśli $p^\gamma | \mathrm{NWD} (km, kn, lm, ln)$ oraz $p^\alpha | \mathrm{NWD} (k, l)$ , ale $p^{\alpha + 1} not \mid \mathrm{NWD} (k, l)$ , to jedna z liczb $k$ , $l$ nie dzieli się przez $p^{\alpha+1}$ , np. $k= p^\alpha \cdot k_1$ , $p \not \mid k_1$ . Ponieważ $p^\gamma | km$ , $p^\gamma | kn$ , więc $p^{\gamma \cdot \alpha} | \mathrm{NWD}(m, n)$ .

Wynika stąd, że $p^\gamma | \mathrm{NWD} (k, l) \cdot \mathrm{NWD} (m, n)$ , więc $\mathrm{NWD} (km, kn, lm, ln) | \mathrm{NWD} (k, l) \cdot \mathrm{NWD} (m, n)$ .

Tym samym równość (1) została udowodniona. Podstawiając w tej równości $k = a$ , $l = c$ , $m = a$ , $n= d$ otrzymamy

$ \mathrm{NWD}(a, c) \cdot \mathrm{NWD}(a,d)= \mathrm{NWD} (a^2, ad, ac, cd). $

Wobec założenia $cd = ab$ dostajemy stąd

$ \mathrm{NWD} (a, c) \cdot \mathrm{NWD} (a, d) = \mathrm{NWD} (a^2, ad, ac, ab) = a \cdot \mathrm{NWD} (a, d, c, b) = a \cdot \mathrm{NWD} (a, b, c, d). $

XXXIV OM - III - Zadanie 5

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

III

Na płaszczyźnie dane są wektory $\overrightarrow{a_1}, \overrightarrow{a_2}, \overrightarrow{a_3}$ o długości 1. Dowieść, że można tak wybrać liczby $\varepsilon_1, \varepsilon_2, \varepsilon_3$ równe 1 lub 2, że długość wektora $\varepsilon_1\overrightarrow{a_1} + \varepsilon_2\overrightarrow{a_2} + \varepsilon_3\overrightarrow{a_3}$ jest nie mniejsza od 2.

Rozwiązanie

Zaczepmy w dowolnym punkcie $0$ wektory $\overrightarrow{a_1}$ , $\overrightarrow{a_2}$ , $\overrightarrow{a_3}$ . Wyznaczają one trzy proste przecinające się w punkcie $0$ . Wśród kątów wyznaczonych przez pary tych prostych istnieje kąt o mierze $\alpha$ nie większej od $\frac{\pi}{3}$ . Przypuśćmy, że jest to kąt między prostymi wyznaczonymi przez wektory $\overrightarrow{a_1}$ i $\overrightarrow{a_2}$ (w innym przypadku wystarczy zmienić numerację wektorów). Wobec tego jeden z kątów $\measuredangle (\overrightarrow{a_1}, \overrightarrow{a_2})$ , $\measuredangle (\overrightarrow{a_1}, -\overrightarrow{a_2})$ ma miarę $\alpha \in \left[0, \frac{\pi}{3} \right]$ .

Przyjmujemy $\varepsilon_2$ tak, by kąt $\measuredangle (\overrightarrow{a_1}\varepsilon_2 \overrightarrow{a_2})$ miał miarę $\alpha$ . Obliczmy iloczyn skalarny wektora $\overrightarrow{b}=\overrightarrow{a_1}+\varepsilon_2 \overrightarrow{a_2}$ przez siebie:

$ \begin{split} \overrightarrow{b_2}^2 = (\overrightarrow{a_1}+\varepsilon_2 \overrightarrow{a_2})^2 = |\overrightarrow{a_1}|^2 + |\overrightarrow{a_2}|^2 + 2 \overrightarrow{a_1} |\varepsilon_2 \overrightarrow{a_2} |=\\ 2 + 2 |\overrightarrow{a_1}| \cdot |\varepsilon_2 \overrightarrow{a_2}| \cdot \cos \alpha \geq 2 + 2 \cdot \frac{1}{2} = 3. \end{split} $

Wobec tego $|\overrightarrow{b}| \geq \sqrt{3}$ .

Zauważmy następnie, że

$ (\overrightarrow{b}+\overrightarrow{a_3})^2+ (b-\overrightarrow{a_3})^2 = \overrightarrow{b}^2 + 2\overrightarrow{b} \cdot \overrightarrow{a_3} + \overrightarrow{a_3}^2 +\overrightarrow{b}^2-2\overrightarrow{b} \cdot \overrightarrow{a_3} +\overrightarrow{a_3}^2 = 2|b|^2+2 \geq 2 \cdot 3+2= 8. $

Wobec tego jedna z liczb $(\overrightarrow{a_1}+ \varepsilon_2 \overrightarrow{a_2} +\overrightarrow{a_3})^2$ , $(\overrightarrow{a_1}+ \varepsilon_2 \overrightarrow{a_2} -\overrightarrow{a_3})^2$ nie jest mniejsza od $4$ . Przyjmujemy $\varepsilon_3$ tak, by $(a_1+ \varepsilon_2 a_2 +\varepsilon_3 a_3)^2 \geq 4$ . Wówczas $|a_1 + \varepsilon_2 a_2+\varepsilon_3a_3| \geq 2$ .

XXXIV OM - III - Zadanie 6

Zawody matematyczne:

XXXIV OM, 1982-1983

Etap:

III

Wykazać, że jeśli wszystkie kąty dwuścienne czworościanu są ostre, to wszystkie jego ściany są trójkątami ostrokątnymi.

Rozwiązanie

Każdej ścianie przyporządkowujemy wektor jednostkowy prostopadły do niej i skierowany na zewnątrz czworościanu. Rozważmy dwie ściany tworzące kąt $\alpha$ . Wektory przyporządkowane tym ścianom tworzą kąt $\pi - \alpha$ (rys. 12). Wobec tego na to, by wszystkie kąty dwuścienne czworościanu były ostre, potrzeba i wystarcza, by kąty między każdą parą spośród wektorów $\overrightarrow{a}$ , $\overrightarrow{b}$ , $\overrightarrow{c}$ , $\overrightarrow{d}$ przyporządkowanych poszczególnym ścianom były rozwarte, a więc by

$ \overrightarrow{a} \cdot \overrightarrow{b} < 0, \overrightarrow{a} \cdot \overrightarrow{c} < 0, \overrightarrow{a} \cdot \overrightarrow{d} < 0, \overrightarrow{b} \cdot \overrightarrow{c} < 0, \overrightarrow{b} \cdot \overrightarrow{d} < 0, \overrightarrow{c} \cdot \overrightarrow{d} < 0. $

Załóżmy, że spełnione są powyższe nierówności. Udowodnimy, że każdy kąt płaski czworościanu jest ostry. Rozważmy kąt $ABC$ . Wektor $\overrightarrow{a}$ przyporządkowany ścianie $BCD$ jest prostopadły do prostej $BC$ . Wobec tego rzut $\overrightarrow{a}_{ABC}$ wektora $\overrightarrow{a}$ na płaszczyznę $ABC$ też jest prostopadły do prostej $BC$ . Podobnie wektor $\overrightarrow{c}$ przyporządkowany ścianie $ABD$ jest prostopadły do prostej $AB$ , więc jego rzut $\overrightarrow{c}_{ABC}$ na płaszczyznę $ABC$ jest prostopadły do $AB$ . Wynika stąd, że

$ \measuredangle (\overrightarrow{a}_{ABC} \cdot \overrightarrow{c}_{ABC} )= \pi - \measuredangle ABC. $

Wobec tego kąt $ABC$ jest ostry wtedy i tylko wtedy, gdy $\overrightarrow{a}_{ABC} \cdot \overrightarrow{c}_{ABC} < 0$ .

Wektory $\overrightarrow{a}$ , $\overrightarrow{b}$ , $\overrightarrow{c}$ , $\overrightarrow{d}$ mają długość $1$ , wobec tego (rys. 14)

$ \overrightarrow{a}_{ABC} = \overrightarrow{a} - (\overrightarrow{a} \cdot \overrightarrow{d} ) \cdot \overrightarrow{d},\ \overrightarrow{c}_{ABC} = \overrightarrow{c} - (\overrightarrow{c} \cdot \overrightarrow{d} ) \cdot \overrightarrow{d}. $

Stąd

$ \begin{split} &\overrightarrow{a}_{ABC} \cdot \overrightarrow{c}_{ABC} = (\overrightarrow{a} - (\overrightarrow{a} \cdot \overrightarrow{d} ) \cdot \overrightarrow{d}) \cdot (\overrightarrow{c} - (\overrightarrow{c} \cdot \overrightarrow{d} ) \cdot \overrightarrow{d}) =\\ &\qquad =\overrightarrow{a} \cdot \overrightarrow{c} - (\overrightarrow{c} \cdot \overrightarrow{d})(\overrightarrow{a} \cdot \overrightarrow{d}) - (\overrightarrow{a} \cdot \overrightarrow{d})(\overrightarrow{c} \cdot \overrightarrow{d}) - +(\overrightarrow{a} \cdot \overrightarrow{d})(\overrightarrow{c} \cdot \overrightarrow{d})(\overrightarrow{d} \cdot \overrightarrow{d})=\\ &\qquad =\overrightarrow{a} \cdot \overrightarrow{c} - (\overrightarrow{c} \cdot \overrightarrow{d})(\overrightarrow{a} \cdot \overrightarrow{d}) - (\overrightarrow{a} \cdot \overrightarrow{d})(\overrightarrow{c} \cdot \overrightarrow{d}) +(\overrightarrow{a} \cdot \overrightarrow{d})(\overrightarrow{c} \cdot \overrightarrow{d}) \cdot 1=\\ &\qquad =\overrightarrow{a} \cdot \overrightarrow{c} - (\overrightarrow{c} \cdot \overrightarrow{d})(\overrightarrow{a} \cdot \overrightarrow{d}) < 0, \end{split} $

bo każdy z występujących tu iloczynów skalarnych jest ujemny. Wykazaliśmy więc, że kąt $ABC$ jest ostry. Dla pozostałych kątów płaskich dowód jest analogiczny.