XXXV OM

XXXV Olimpiada Matematyczna

Opracowanie rozwiązań: Maciej Bryński

XXXV OM - I etap

I etap XXXV Olimpiady Matematycznej

XXXV OM - I - Zadanie 1

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

Rozstrzygnąć, czy sześciokąt foremny można pokryć sześcioma kołami o średnicy równej długości boku sześciokąta.

Rozwiązanie

Żądane pokrycie otrzymamy biorąc koła, których średnicami są odcinki łączące środek sześciokąta z poszczególnymi wierzchołkami. Koło mające średnicę $\overline{AO}$ , gdzie $A$ jest wierzchołkiem sześciokąta, zawiera połowy boków stykających się w wierzchołku $A$ . Wynika to stąd, że środek $M$ boku $\overline{AB}$ leży na symetralnej odcinka $\overline{AB}$ , więc $\measuredangle AMO = 90^\circ$ i wobec tego punkt $M$ leży na okręgu o średnicy $\overline{AO}$ . Zatem każdy punkt sześciokąta należy do co najmniej jednego z kół, których średnicami są kolejno odcinki $\overline{AO}$ , $\overline{BO}$ , $\overline{CO}$ , $\overline{DO}$ , $\overline{EO}$ , $\overline{FO}$ .

XXXV OM - I - Zadanie 2

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

Wyznaczyć wszystkie wartości parametru $a$ , dla których układ równań

$ \begin{split} x + y + z &= 2,\\ xy + yz +zx &= 1,\\ xyz &= a. \end{split} $

ma rozwiązania w liczbach rzeczywistych.

Rozwiązanie

Liczby rzeczywiste $x$ , $y$ , $z$ stanowią rozwiązanie danego układu równań wtedy i tylko wtedy, gdy liczby te są pierwiastkami wielomianu

$ f(f) = t^3-2t^2+t-a. $

Istotnie, liczby $x$ , $y$ , $z$ są pierwiastkami wielomianu $f$ wtedy i tylko wtedy, gdy

$ t^3-2t^2+t-a = (t-x)(t-y)(t-z) = t^3 - (x + y + z) t^2 +(xy + yz + zx) t - xyz, $

a więc wtedy i tylko wtedy, gdy

$ -2 = -(x+y + z) $

$ 1 = xy +yz +zx $

$ - a = -xyz. $

Wobec tego pytanie postawione w zadaniu sprowadza się do tego, dla jakich wartości $a$ wielomian $f$ ma trzy pierwiastki rzeczywiste. Oczywiście $\displaystyle \lim_{t \to - \infty} f(t) = - \infty$ , $\displaystyle \lim_{t \to + \infty} f(t) = + \infty$ . Wyznaczymy punkty, w których funkcja $f$ ma ekstrema. Pochodną tej funkcji jest

$ f'(t) = 3t^2-4r +1. $

Miejscami zerowymi pochodnej są $t_1 = \frac{1}{3}$ , $t_2 = 1$ . Przyjmuje ona między tymi miejscami zerowymi wartości ujemne, skąd wynika, że przechodząc przez $t_1$ zmienia wartości z dodatnich na ujemne. Wobec tego w punkcie $t_1$ funkcja $f$ przyjmuje maksimum, a w $t_2$ - minimum. Wynika stąd, że na to, by wielomian $f$ miał trzy pierwiastki rzeczywiste (licząc z krotnościami) potrzeba i wystarcza, by $f(t_1) \geq 0$ , $f(t_2) \leq 0$ , tj.

$ \left\{ \begin{array}{rcl} \left( \frac{1}{3} \right)^3 - 2 \cdot \left( \frac{1}{3} \right)^2 + \frac{1}{3} - a \geq 0\\ -a \leq 0 \end{array} \right. $

czyli

$ 0 \leq a \leq \frac{4}{27}. $

Dany układ równań ma więc rozwiązania w liczbach rzeczywistych wtedy i tylko wtedy, gdy $a \in \left[ 0;\ \frac{4}{27} \right]$ .

XXXV OM - I - Zadanie 3

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

Wyznaczyć wszystkie wartości $p, q$ , dla których nierówność

$ |\sqrt{1-x^2} - px - q| \leq \frac{1}{2}(\sqrt{2}-1) $

zachodzi dla każdego $x$ z przedziału $[0; 1]$ .

Rozwiązanie

Szukamy takich funkcji liniowych $f(x) = px + q$ , że dla każdego $x_0$ z przedziału $[0; 1]$ wartość $f(x_0)$ różni się od wartości funkcji $g(x) = \sqrt{1 - x^2}$ w punkcie $x_0$ nie więcej niż o $\frac{1}{2}(\sqrt{2}-1)$ . Pokażemy najpierw, że funkcja $f(x) = - x+\frac{1}{2}(\sqrt{2} +1)$ spełnia ten warunek.

Funkcja $h(x) = \sqrt{1-x^2} + x- \frac{1}{2}(\sqrt{2}+1)$ przyjmuje na końcach przedziału $[0; 1]$ wartości równe $g(0)-f(0) = g (1)-f(1) = -\frac{1}{2}(\sqrt{2}-1)$ . Funkcja ta jest różniczkowania w przedziale $(0;1)$ i jej pochodna jest równa $h'(x) = 1 - \frac{x}{\sqrt{1-x^2}}$ . Jedynym miejscem zerowym pochodnej w przedziale $(0; 1)$ jest $\frac{1}{\sqrt{2}}$ , w tym punkcie funkcja $h$ przyjmuje maksimum równe $\frac{1}{2}(\sqrt{2}-1)$ . Wynika stąd, że dla każdego $x \in [0; 1]$ jest spełniona nierówność

$ \left| \sqrt{1-x^2} + x -\frac{1}{2}(\sqrt{2}+1) \right| \leq \frac{1}{2}(\sqrt{2}-1). $

Pokażemy, że liczby $p = -1$ , $q = \frac{1}{2}(\sqrt{2}+1)$ stanowią jedyne rozwiązanie zadania.

Przypuśćmy, że para liczb $(p_1, q_1)$ różna od pary $(p, q)$ jest również rozwiązaniem zadania. Rozważmy prostą $l_1$ o równaniu $y = p_1 x + q_1$ . Z przeprowadzonych wyżej rachunków wynika, że punkt $(0, q_1)$ leży na osi $OY$ nie wyżej niż punkt $(0, q)$ , podobnie punkt $(1, p_1+q_1)$ leży na prostej o równaniu $x = 1$ nie wyżej niż punkt $(1,p + q)$ . Ponieważ proste o równaniach $y= px + q$ , $y = p_1 x + q_1$ nie mogą się pokrywać, więc punkt $\left( \frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}} p_1 + q_1 \right)$ leży poniżej punktu $\left( \frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}} p + q \right)$ . Ponieważ punkt $\left( \frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}} p + q \right)$ leży pod wykresem funkcji $g$ w odległości $\frac{1}{2}(\sqrt{2} -1)$ od punktu $\left( \frac{1}{\sqrt{2}}, g \left( \frac{1}{\sqrt{2}} \right) \right)$ , więc odległość punktu $\left( \frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}} p_1 + q_1 \right)$ od $\left( \frac{1}{\sqrt{2}}, g \left( \frac{1}{\sqrt{2}} \right) \right)$ przekracza $\frac{1}{2} (\sqrt{2}-1)$ .

Wynika stąd, że żadna para liczb $(p_1, q_1)$ różna od $(p, q)$ nie spełnia warunków zadania. Jedynym rozwiązaniem jest więc $p=-1$ , $q=\frac{1}{2}(\sqrt{2}-1)$ .

XXXV OM - I - Zadanie 4

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

Dane są dwa przecinające się okręgi $o(O_1, r_1)$ i $o(O_2, r_2)$ i prosta styczna do nich odpowiednio w punktach $A$ i $B$ . Punkt $C$ jest punktem wspólnym tych okręgów bliższym prostej $AB$ , $R$ jest długością promienia okręgu opisanego na trójkącie $ABC$ , $d = O_1O_2$ Udowodnić, że $\measuredangle ABC = \measuredangle O_1CO_2$ wtedy i tylko wtedy, gdy $d^2 = r_1^2 + r_2^2 + R^2$ .

Rozwiązanie

Z trójkąta równoramiennego $AC0_1$ wyznaczamy

$ \frac{AC}{2r_1} = \cos \measuredangle O_1AC. $

Ponieważ $\measuredangle O_1AB = 90^\circ$ , więc $\cos O_1AC = \sin (90^\circ -O_1AC) = \sin BAC$ . Stosując twierdzenie sinusów do trójkąta $ABC$ otrzymujemy

$ \sin \measuredangle BAC = \frac{|BC|}{2R}, $

więc

$ \frac{|AC|}{2r_1} = \frac{|BC|}{2R}. $

Podobnie

$ \frac{|BC|}{2r_2} = \frac{|AC|}{2R}. $

Z ostatnich dwóch równości wynika, że

$ r_1 r_2 = R^2. $

Obliczając sumę kątów o wierzchołku $C$ otrzymamy $360^\circ = \measuredangle O_1 CO_2 +\measuredangle ACB + (90^\circ - \measuredangle BAC) + (90^\circ- \measuredangle ABC) = \measuredangle O_1C0_2 + \measuredangle ACB+ (180^\circ -(\measuredangle BAC + \measuredangle ABC)) = \measuredangle O_1CO_2 + \measuredangle ACB + \measuredangle ACB$ . Stąd $\measuredangle ACB = 180^\circ -\frac{1}{2} \measuredangle O_1CO_2$ .

Wobec tego równość $\measuredangle ACB = \measuredangle O_1 CO_2$ jest spełniona wtedy i tylko wtedy, gdy $\measuredangle ACB = 120^\circ$ , a więc wtedy i tylko wtedy, gdy $\cos \measuredangle ACB = -\frac{1}{2}$ oraz
$0 \leq \measuredangle ACB \leq 180\circ$ . Z twierdzenia cosinusów otrzymujemy

$ \cos \measuredangle ACB = \frac{r_1^2 + r_2^2 - d^2}{2r_1r_2} = \frac{r_1^2+r_2^2-d^2}{2R^2}. $

Równość $\measuredangle ACB = \measuredangle O_1CO_2$ jest więc równoważna równości

$ \frac{r_1^2 + r_2^2 - d^2}{2R^2} = -\frac{1}{2},\ \textrm{tj.} \ d^2 = r_1^2 + r_2^2 + R^2. $

XXXV OM - I - Zadanie 5

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

Udowodnić, że istnieje taka wielokrotność liczby $5^n$ , której zapis w układzie dziesiętnym składa się $n$ cyfr różnych od zera.

Rozwiązanie

Liczba $5^n$ ma w zapisie dziesiętnym nie więcej niż $n$ cyfr: $5^n = c_0+c_1 \cdot 10 + c_2 \cdot 10^2+ \ldots +c_{n-1} \cdot 10^{n-1}$ , przy czym niektóre cyfry $c_i$ mogą być zerami. Przypuśćmy, że $k$ jest najmniejszą liczbą naturalną, dla której $c_k = 0$ . Rozważmy liczbę $5^{n} +10^{k} \cdot 5^{n-k}$ . Liczba ta ma w zapisie dziesiętnym postać $c_0+c_1 \cdot 10 + \ldots + c_{k-1} \cdot 10^{k-1} + 5 \cdot 10^{k} + \ldots$ , gdzie $c_i \ne 0$ dla $i \leq k$ . Jeśli któraś z dalszych cyfr tej liczby jest równa zeru, np. $c_r = 0$ przy pewnym $r > k$ , ale $c_j \ne 0$ dla $j < r$ , to rozważamy liczbę $5^{n} +10^{k} \cdot 5^{n-k} +10^{r} \cdot 5^{n-r}$ , która w zapisie dziesiętnym ma $r + 1$ kolejnych cyfr różnych od zera.

W wyniku takich operacji otrzymamy liczbę, w której zapisie dziesiętnym niezerowe są cyfry odpowiadające rzędom $1$ , $10$ , $10^2$ , $10^{n-1}$ . Ponadto liczba ta nie przekracza $5^{n} + 10 \cdot 5^{n-t} +10^2 \cdot 5^{n-2} + \ldots +10^{n-t} \cdot 5 =5^{n} + 2 \cdot 5^{n} + 2^2 \cdot 5^n+ \ldots +2^{n-1} \cdot 5^{n} = 5^n(1 +2 + 2^2+ \ldots + 2^{n-1}) = 5^{n}(2^{n}-1) < 10^{n}$ .

Jest to więc liczba mająca w zapisie dziesiętnym dokładnie $n$ cyfr różnych od zera. Jest ona przy tym wielokrotnością liczby $5^{n}$ , gdyż powstaje przez dodanie do $5^{n}$ składników postaci $10^{k} \cdot 5^{n-k} = 5^{n} \cdot 2^{k}$ , które są wielokrotnościami liczby $5^{n}$ .

XXXV OM - I - Zadanie 6

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

Rozwiązać układ równań

$ \begin{cases} \frac{x+y}{1+xy} &= \frac{2a}{1+a^2}, \\ \frac{x-y}{1-xy} &= \frac{2b}{1+b^2}. \end{cases} $

Rozwiązanie

Jeśli para liczb $(x,y)$ jest rozwiązaniem tego układu, to $xy \ne 1$ , $xy \ne -1$ . Rozpatrzmy kilka najprostszych przypadków.

Jeśli $x = 1$ , to równania przybierają postać

$ \frac{1+y}{1+y} = \frac{2a}{1+a^2}, \frac{1-y}{1-y}= \frac{2b}{1+b^2} $

są więc w przypadku, gdy $a = b = 1$ spełnione przez każdą liczbę $y$ różną od $1$ , $- 1$ , a dla innych $a$ , $b$ nie mają rozwiązań.

Podobnie stwierdzamy, że jeśli $y = 1$ , to musi być $a = 1$ , $b = - 1$ i wtedy $x$ może przybierać dowolną wartość różną od $1$ , $-1$ . Następnie $x = - 1$ jedynie dla $a = - 1$ , $b = - 1$ i wówczas $y$ może być dowolną liczbą $\ne 1$ , $- 1$ , natomiast $y = - 1$ dla $a = - 1$ , $b = 1$ i wtedy $x$ jest dowolne różne od $1$ , $- 1$ .

W przypadku $a = b \ne 1$ lub $ab = 1$ , $a \ne 1$ , $-1$ jest $x=\frac{2a}{1+a^2}$ , $y = 0$ , w przypadku $a = - b \ne 1$ , $- 1$ lub $ab = - 1$ , $a \ne 1$ , $- 1$ jest $x = 0$ , $y = \frac{2a}{1+a^2}$ .

Możemy teraz szukać rozwiązań w innych przypadkach zakładając, że $x \ne 1$ , $x \ne -1$ , $y \ne 1$ , $y \ne - 1$ , $xy \ne 1$ , $xy \ne - 1$ , $a \ne b$ , $a \ne - b$ , $ab \ne 1$ , $ab \ne -1$ .

Dany układ równań przekształćmy do równoważnej postaci

$ \begin{split} (1) \qquad x + y & = \frac{2a}{1+a^2} (1+xy)\\ x - y & = \frac{2b}{1+b^2} (1-xy) \end{split} $

Dodając do obu stron pierwszego równania wyrażenie $1 + xy$ otrzymamy

$ \begin{split} (2) \qquad x + y + 1 + xy & = \left( \frac{2a}{1+a^2} +1 \right) (1+xy)\\ (1+x)(1+y) & = \frac{(1+a)^2}{1+a^2} (1+xy). \end{split} $

Odejmując obie strony pierwszego równania układu (1) od $1 +xy$ otrzymamy

$ \begin{split} (3) \qquad 1 + xy -x -y & = (1+xy) \left( 1 - \frac{2a}{1+a^2} \right) \\ (1-x)(1-y) & = (1+xy) \frac{(1-a)^2}{1+a^2} . \end{split} $

Obie strony równania (3) są różne od zera, możemy więc podzielić stronami (2) przez (3)

$ \frac{(1+x)(1+y)}{(1-x)(1-y)} = \left( \frac{1+a}{1-a} \right)^2. $

Postępując analogicznie z drugim równaniem układu (1) otrzymamy

$ \frac{(1+x)(1+y)}{(1-x)(1-y)} = \left( \frac{1+b}{1-b} \right)^2. $

Pomnóżmy teraz dwa ostatnie równania stronami

$ \left( \frac{(1+x)}{(1-x)} \right)^2 = \left( \frac{(1+a)(1+b)}{(1-a)(1-b)} \right)^2. $

więc

$ \frac{1+x}{1-x} = \frac{(1+a)(1+b)}{(1-a)(1-b)} \ \textrm{lub} \ \frac{1+x}{1-x} = - \frac{(1+a)(1+b)}{(1-a)(1-b)} $

Z pierwszego z tych równań obliczamy

$ \begin{split} (1-a)(1-b)+(1-a)(1-b)x = (1 + a)(1+b)-(1 + a)(1+b)x,\\ (1-a-b+ab + 1+a+b+ab)x = 1+a+b+ab-1+a + b-ab,\\ (2 + 2ab)x = 2a + 2b,\\ x_1 = \frac{a+b}{1+ab}. \end{split} $

i podobnie z drugiego równania

$ x_2 = \frac{1+ab}{a+b}. $

Podstawiając $x_1$ do pierwszego z równań układu (1) otrzymamy

$ \begin{split} \frac{a+b}{1+ab} + y = \frac{2a}{1+a^2} \left( 1 + \frac{a+b}{1+ab}y \right),\\ \left( 1-\frac{2a}{1+a^2} \cdot \frac{a+b}{1+ab}y \right) = \frac{2a}{1+a^2} - \frac{a+b}{1+ab}\\ \frac{1 +a^2 +ab+a^3b-2a^2-2ab}{(1+a^2)(1+ab)}y = \frac{2a + 2a^2b-a-b-a^3-a^2b}{(1 +a^2)(1 +ab)} \\ \frac{(1-a^2)(1-ab)}{(1+a^2)(1+ab)} y = \frac{(a-b)(1-a^2)}{(1+a^2)(1+ab)} \\ y_1 = \frac{a-b}{1-ab} \end{split} $

Podobnie podstawiając $x_2$ do pierwszego równania układu (1) obliczamy

$ y_2 = \frac{1-ab}{a-b} $

XXXV OM - I - Zadanie 7

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

Udowodnić, że dla dowolnych liczb naturalnych $m, p$ większych od 1 spełniona jest nierówność

$ \sum_{k=1}^m \frac{1}{(k+1)\cdot\sqrt[p]{k}} < p. $

Rozwiązanie

Oszacujemy $k$ -ty składnik rozważanej sumy:

$ \begin{split} \frac{1}{(k+1) \cdot \sqrt[p]{k}} = \frac{1}{\sqrt[p]{k}} \left( \frac{k}{k} - \frac{k}{k+1}\right)=\\ = k^{1-\frac{1}{p}} \left( \frac{1}{k} - \frac{1}{k+1} \right) = k^{1-\frac{1}{p}} ((k^{-\frac{1}{p}})^p - ((k+1)^{-\frac{1}{p}})^p) =\\ k^{1-\frac{1}{p}} (k^{-\frac{1}{p}} - (k+1)^{-\frac{1}{p}}) \sum_{j=0}^{p-1} k^{-\frac{j}{p}} (k+1)^{-\frac{p-1-j}{p}} =\\ = (k^{-\frac{1}{p}} - (k+1)^-{-\frac{1}{p}}) \sum_{j=0}^{p-1} k^{\frac{p-1-j}{p}} (k+1)^{-\frac{p-1-j}{p}}=\\ (k^{-\frac{1}{p}} - (k+1)^{-\frac{1}{p}}) \sum_{j=0}^{p-1} \left( \frac{k}{k+1} \right)^{\frac{p-j-1}{p}} < (k^{-\frac{1}{p}} - (k+1)^{-\frac{1}{p}})p, \end{split} $

gdyż suma występująca przed znakiem nierówności ma $p$ składników, z których każdy jest mniejszy od $1$ . Wobec tego

$ \begin{split} \sum_{k=1}^m \frac{1}{(k+1) \sqrt[p]{k}} < \sum_{k=1}^m (k^{-\frac{1}{p}} - (k+1)^{-\frac{1}{p}}) p = p(1^{-\frac{1}{p}} - 2^{-\frac{1}{p}} + 2^{-\frac{1}{p}} -3^{-\frac{1}{p}} + \ldots \\ + m^{-\frac{1}{p}} - (m+1)^{-\frac{1}{p}}) = p(1^{-\frac{1}{p}} - (m+1)^{-\frac{1}{p}}) = p \left( 1 - \frac{1}{\sqrt[p]{m+1}}\right) < p \end{split} $

XXXV OM - I - Zadanie 8

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

Niech $n$ będzie liczbą naturalną parzystą. Udowodnić, że czworokąt można podzielić na $n$ trójkątów, których wierzchołki leżą w wierzchołkach czworokąta albo wewnątrz czworokąta, a bok każdego trójkąta jest albo bokiem czworokąta, albo bokiem innego trójkąta.

Rozwiązanie

Co najmniej jedna przekątna czworokąta jest zawarta w jego wnętrzu. Niech będzie to np. przekątna $\overline{AC}$ . Jeśli $n = 2$ , to podział czworokąta $ABCD$ na trójkąty $ABC$ i $ACD$ jest żądanym podziałem. Przypuśćmy, że $n = 2k$ jest liczbą parzystą. Obierzmy na przekątnej $AC$ dowolne punkty $A_1,\ldots,A_{k-1}$ leżące na niej w kolejności zgodnej z numeracją i różne od $A$ i $C$ . Przyjmijmy dodatkowo $A_0 = A$ , $A_k = C$ . Podział czworokąta $ABCD$ na trójkąty $A_{i-1}BA_i$ oraz $A_{i-1}DA_i$ , $i = 1,\ldots, k$ spełnia postawione warunki.

XXXV OM - I - Zadanie 9

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

Trzy zdarzenia spełniają warunki:
a) ich prawdopodobieństwa są równe,
b) każde dwa spośród nich są niezależne,
c) nie zachodzą równocześnie.
Wyznaczyć największą wartość prawdopodobieństwa każdego z tych zdarzeń.

Rozwiązanie

Przypuśćmy, że $A$ , $B$ , $C$ są tymi zdarzeniami, przy czym prawdopodobieństwo każdego z nich wynosi $p$ . Wobec założenia o niezależności każdych dwóch spośród rozważanych zdarzeń, prawdopodobieństwo każdej części wspólnej $A \cap B$ , $B \cap C$ , $C \cap A$ wynosi $p^2$ . Ponadto $A \cap B \cap C \ne 0$ . Wobec tego

$ P(A \cup B \cup C) = 3p-3p^2. $

Ponieważ oczywiście $P (A \cup B \cup C) \geq P (A \cap B) +P (B \cap C) +P (C \cap A) = 3p^2$ , więc $3p-3p^2 \geq 3p^2$ , skąd wynika, że $p \leq \frac{1}{2}$ .

Wartość $p = \frac{1}{2}$ jest przyjmowana np. przez następujące zdarzenia. Przy dwukrotnym rzucie monetą przyjmujemy jako $A$ zdarzenie polegające na tym, że w pierwszym rzucie wypadła reszka, $B$ - w drugim rzucie wypadł orzeł, $C$ - w obu rzutach wypadło to samo. Oczywiście $P(A) = P(B) = P (C) = \frac{1}{2}$ , zdarzenia $A$ , $B$ , $C$ są parami niezależne i nie mogą zachodzić jednocześnie.

Wobec tego największą wartością rozważanego prawdopodobieństwa jest $\frac{1}{2}$ .

XXXV OM - I - Zadanie 10

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

Na płaszczyźnie dane jest $3n$ punktów, wśród których nie ma trzech punktów współliniowych. Dowieść, że istnieje $n$ rozłącznych trójkątów o wierzchołkach w danych punktach.

Rozwiązanie

Rozważmy wszystkie proste, z których każda przechodzi przez dwa punkty danego zbioru $3n$ punktów. Prostych tych jest skończenie wiele, więc istnieje prosta $l$ , która nie jest prostopadła do żadnej z nich. Zrzutujmy wszystkie dane punkty prostopadle na prostą $l$ , rzuty żadnych dwóch punktów nie pokrywają się. Ponumerujmy dane punkty $A_1, \ldots, A_{3n}$ zgodnie z kolejnością, w jakiej ich rzuty są usytuowane na prostej $l$ . Trójkąty $A_{3i-2} A_{3i-1} A_{3i}$ dla $i = 1,\ldots, n$ są rozłączne.

XXXV OM - I - Zadanie 11

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

Podać wzory wyraźne na $n$ -ty wyraz ciągów określonych wzorami rekurencyjnymi:

$ \begin{split} a_{n+1} &= 3a_n + b_n, \\ b_{n+1} &= -a_n + b_n, \\ a_1 = 14, &\; b_1 = -6. \end{split} $

Rozwiązanie

Rozważmy ciąg $(c_n)$ określony wzorem

$ c_n = a_n + b_n. $

Ponieważ $c_{n+1} = a_{n+1}+b_{n+1} = 3a_n + b_n - a_n +b_n = 2a_n + 2b_n = 2c_n$ , więc ciąg $(c_n)$ określony jest wzorem rekurencyjnym

$ c_{n + 1} = 2c_n,\ c_1 = 14-6 = 8 = 2^3 $

Przez indukcję stwierdzamy, że $c_n = 2^{n + 2}$ .

Ponieważ $b_n = c_n-a_n = 2^{n+2} -a_n$ , więc

$ a_{n+1} = 3a_n + b_n = 3a_n + 2^{n+2} - a_n = 2a_n + 2^{n + 2}. $

Z ostatniego wzoru wynika, że kolejne wyrazy ciągu $(a_n)$ dzielą się przez kolejne potęgi dwójki. Przyjmując

$ a_n = 2^nx_n. $

otrzymujemy $2^{n+1}x_{n+1} = 2^{n + 1}x_n + 2^{n+ 2}$ , więc $x_{n +1} =x_n + 2$ , $x_1 = 7$ . Stąd przez oczywistą indukcję wynika, że $x_n = 2n + 5$ . Wobec tego $a_n = 2^n(2n + 5)$ , $b_n = 2^{n + 2}-2^n(2n + 5) = 2^n(4-2n-5) = -2^n(2n + 1)$ .

XXXV OM - I - Zadanie 12

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

W kącie trójściennym $W$ zawarta jest półprosta $L$ przechodząca przez jego wierzchołek. Dowieść, że suma kątów utworzonych przez $L$ z krawędziami $W$ nie przekracza sumy kątów płaskich $W$ .

Rozwiązanie

Rozważmy kulę o promieniu 1 i środku w wierzchołku kąta trójściennego. Miara każdego kąta płaskiego, którego ramionami są półproste o początku w środku kuli, równa jest długości odpowiedniego łuku koła wielkiego (krótszego z dwóch łuków wyznaczonych przez punkty przecięcia danych półprostych z powierzchnią kuli). Wszystkie łuki na powierzchni kuli, o których będziemy mówić w trakcie tego rozwiązania, będą łukami odpowiednich kół wielkich.

Suma miar kątów płaskich kąta trójściennego równa jest sumie długości łuków $AB$ , $BC$ i $CA$ , których końce są punktami wspólnymi krawędzi kąta trójściennego i powierzchni kuli. Suma miar kątów utworzonych przez $L$ z krawędziami kąta trójściennego równa jest sumie długości łuków $AD$ , $BD$ i $CD$ , gdzie $D$ jest punktem wspólnym półprostej $L$ i powierzchni kuli.

Długość łuku (zgodnie z przyjętą umową - łuku koła wielkiego) łączącego dwa punkty na powierzchni kuli spełnia własności odległości (zob, np. R. Courant, H. Robbins, Co to jest matematyka, rozdział VII), w szczególności tzw. nierówność trójkąta

$ AB + BC \leq AC $

Na podstawie nierówności trójkąta długości odpowiednich łuków spełniają

$ AD + DC \leq (AE + ED) + DC = AE + EC \leq AE+(EB + BC) = AB + BC. $

Otrzymaliśmy więc, że

$ AD + DC \leq AB + BC, $

a przez analogiczne rozumowanie możemy stwierdzić, że

$ AD + DB \leq AC + BC $

oraz

$ BD + DC \leq AB+AC. $

Dodając stronami ostatnie trzy nierówności otrzymujemy

$ 2 (AD + BD + CD) \leq 2(AB + BC + CA), $

więc

$ AD + BD + CD \leq AB + BC + CA, $

stąd wynika, że suma miar kątów utworzonych przez $L$ z krawędziami kąta trójściennego $W$ nie przekracza sumy miar kątów płaskich $W$ .

XXXV OM - II etap

II etap XXXV Olimpiady Matematycznej

XXXV OM - II - Zadanie 1

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

Dla danej liczby naturalnej $n$ znaleźć liczbę rozwiązań równania $\sqrt{x} + \sqrt{y} = n$ w liczbach naturalnych $x, y$ .

Rozwiązanie

Dla $n = 1$ dane równanie nie ma rozwiązań w liczbach naturalnych. Dla $n > 1$ każda para liczb $x_1 = 1^2, y_1 = (n- 1)^2, x_2 = 2^2, y_2 = (n-2)^2, \ldots, x_{n-1} = (n - 1)^2, y_{n-1} = 1^2$ stanowi oczywiście rozwiązanie danego równania, gdyż $\sqrt{k^2} + \sqrt{(n - k)^2} = k+(n-k) = n$ dla $0 < k < n$ .

Wykażemy, że innych rozwiązań nie ma. Gdyby para liczb naturalnych $x$ , $y$ była rozwiązaniem danego równania, przy czym np. liczba $x$ nie byłaby kwadratem liczby naturalnej, to spełniona byłaby równość $y = (n -\sqrt{x})^2$ , skąd wynikałoby, że $y-n^2 - x = 2n\sqrt{x}$ . Po lewej stronie tej równości występuje liczba całkowita, zatem $2n \sqrt{x}$ również jest liczbą całkowitą. Zatem $\sqrt{x}$ jest liczbą wymierną, $\sqrt{x} = \frac{m}{n}$ . Wobec tego $x = \left( \frac{m}{n} \right)^2$ , $xn^2 = m^2$ . W rozkładzie liczb $n^2$ , $m^2$ na czynniki pierwsze każdy czynnik występuje w potędze o wykładniku parzystym. Wobec jednoznaczności rozkładu liczby naturalnej na czynniki pierwsze wynika stąd, że również w rozkładzie liczby $x$ każdy czynnik pierwszy występuje w potędze o wykładniku parzystym,

$ x = p_1^{2k_1} p_2^{2k_2} \ldots p_s^{2k_s} $

Zatem $x$ jest kwadratem liczby naturalnej wbrew założeniu. Podobnie stwierdzamy,że żadna para liczb naturalnych $(x, y)$ , w której $y$ nie jest kwadratem liczby naturalnej, nie jest rozwiązaniem danego równania.

Wobec tego dane równanie ma $n - 1$ rozwiązań w liczbach naturalnych.

XXXV OM - II - Zadanie 2

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

Na bokach trójkąta $ABC$ budujemy podobne trójkąty równoramienne: trójkąt $APB$ na zewnątrz trójkąta $ABC$ ( $AP = PB$ ), trójkąt $CQA$ na zewnątrz trójkąta $ABC$ ( $CQ = QA$ ), trójkąt $CRB$ do wewnątrz trójkąta $ABC$ ( $CR = RB$ ). Dowieść, że $APRQ$ jest równoległobokiem lub punkty $A, P, R, Q$ leżą na prostej.

Rozwiązanie

Rozważmy podobieństwo mające punkt stały $C$ i przekształcające $B$ na $R$ (jest to złożenie obrotu wokół $C$ o kąt $BCR$ z jednokładnością o środku $C$ i skali równej stosunkowi długości podstawy do długości ramienia w każdym ze zbudowanych trójkątów równoramiennych). Podobieństwo to przekształca $A$ na $Q$ . Wynika stąd, że trójkąty $ABC$ i $QRC$ są podobne.

Analogicznie stwierdzamy, że podobieństwo o punkcie stałym $B$ przekształcające $C$ na $R$ przekształca $A$ na $P$ , więc trójkąty $ABC$ i $PBR$ są podobne. Wobec tego trójkąty $QRC$ i $PBR$ są podobne. Ponieważ $BR = CR$ , więc trójkąty te są przystające, a zatem $QC = PR$ i $QR = PB$ . Ale $QC = AQ$ i $PB = AP$ , więc $AQ = PR$ i $AP = QR$ . Ponadto kąt między wektorami $\overrightarrow{BP}$ i $\overrightarrow{RQ}$ ma miarę równą $\measuredangle PBA + \measuredangle BCR = 2 \measuredangle PBA$ , kąt zaś między wektorami $\overrightarrow{AP}$ i $\overrightarrow{BP}$ ma miarę równą $180^\circ - 2 \measuredangle PBA$ , skąd wynika, że wektory $\overrightarrow{RQ}$ i $\overrightarrow{AP}$ są równoległe. Wobec tego punkty $A$ , $P$ , $R$ , $Q$ leżą na jednej prostej albo są kolejnymi wierzchołkami równoległoboku.

XXXV OM - II - Zadanie 3

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

Dane są ciągi $(x_1, x_2, \ldots, x_n)$ , $(y_1, y_2, \ldots, y_n)$ o wyrazach dodatnich. Udowodnić, że istnieje taka permutacja $p$ zbioru $\{1, 2, \ldots, n\}$ , że dla każdego rzeczywistego $t$ ciąg

$ (x_{p(1)}+ty_{p(1)}, x_{p(2)}+ty_{p(2)}, \ldots, x_{p(n)}+ty_{p(n)}) $

ma następującą własność: istnieje taka liczba $k$ , że $1 \leq k \leq n$ oraz wszystkie niezerowe wyrazy ciągu o wskaźnikach mniejszych od $k$ są jednakowego znaku i wszystkie niezerowe wyrazy ciągu o wskaźnikach nie mniejszych od $k$ są jednakowego znaku.

Rozwiązanie

Obliczamy ilorazy $\frac{x_1}{y_1}, \frac{x_2}{y_2}, ldots, \frac{x_n}{y_n}$ , znajdujemy takie $j$ , że $\frac{x_j}{y_j}$ jest nie większe od wszystkich pozostałych ilorazów i przyjmujemy $p(1) = j$ . Następnie znajdujemy takie $k$ , że $\frac{x_k}{y_k}$ jest nie większe od wszystkich ilorazów $\frac{x_i}{y_i}$ różnych od $\frac{x_j}{y_j}$ i przyjmujemy $p(2) = k$ itd.

Wobec tego

$ \frac{x_{p(1)}}{y_{p(1)}} \leq \frac{x_{p(2)}}{y_{p(2)}} \leq \ldots \leq \frac{x_{p(n)}}{y_{p(n)}}. $

Rozważamy dowolną liczbę rzeczywistą $t$ i porównujemy liczbę $- t$ z liczbami $\frac{x_{p(j)}}{y_{p(j)}}$ . Istnieje liczba naturalna $k$ , dla której

$ (*) \qquad \frac{x_{p(1)}}{y_{p(1)}} \leq \ldots \leq \frac{x_{p(k-1)}}{y_{p(k-1)}} \leq-t \leq \frac{x_{p(k)}}{y_{p(k)}} \leq \ldots \leq \frac{x_{p(n)}}{y_{p(n)}} $

przy czym może być $k = 1$ , tj.

$ -t \leq \frac{x_{p(1)}}{y_{p(1)}} \leq \ldots \leq \frac{x_{p(n)}}{y_{p(n)}}, $

albo $k = n +1$ , tj.

$ \frac{x_{p(1)}}{y_{p(1)}} \leq \ldots \leq \frac{x_{p(n)}}{y_{p(n)}} \leq -t, $

Z nierówności (*) wynika, że

$ \frac{x_{p(1)}}{y_{p(1)}} +t \leq 0, \ldots, \frac{x_{p(k-1)}}{y_{p(k-1)}} +t\leq 0, \frac{x_{p(k)}}{y_{p(k)}}+t \geq 0,\ldots, \frac{x_{p(n)}}{y_{p(n)}}+t \geq 0, $

a ponieważ $y_{p(i)} > 0$ dla $i = 1,\ldots,n$ , więc

$ x_{p(1)}+ty_{p(1)} \leq 0, \ldots, x_{p(k-1)} + ty_{p(k-1)} \leq 0, x_{p(k)}+ty_{p(k)} \geq 0, \ldots, x_{p(n)} +ty_{p(n)} \geq 0 $

co kończy dowód.

Uwaga. W dowodzie wykorzystaliśmy jedynie dodatniość wyrazów ciągu $(y_i)$ .

XXXV OM - II - Zadanie 4

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

W zawodach Olimpiady Matematycznej bierze udział $3n$ uczestników. Mają oni wyznaczone miejsca w trzech rzędach, po $n$ miejsc w każdym i są wpuszczani na salę pojedynczo, po czym natychmiast zajmują swoje miejsca. Obliczyć prawdopodobieństwo tego, że aż do momentu zajęcia miejsca przez ostatniego zawodnika, w każdej chwili dla każdych dwóch rzędów różnica liczb siedzących w nich zawodników jest nie większa od 1.

Rozwiązanie

Zdarzeniami elementarnymi są permutacje zbioru $3n$ -elementowego. Liczba ich wynosi $(3n)!$ . Obliczymy liczbę zdarzeń sprzyjających zdarzeniu wymienionemu w treści zadania. Jako pierwszy może wyjść na salę dowolny zawodnik (jest więc $3n$ możliwości). Następna osoba może być jedną z $2n$ tych, których miejsca nie są wyznaczone w rzędzie, w którym siedzi pierwszy zawodnik. Trzecim wchodzącym na salę uczestnikiem powinien być ktoś mający miejsce w rzędzie, w którym nie siedzi żaden z poprzednio wpuszczonych zawodników (jest $n$ takich możliwości). Następną osobą może być ktokolwiek z pozostałych $3(n -1)$ osób. Kolejna osoba nie może usiąść w rzędzie, w którym siedzą już dwie osoby, jest więc $2(n- 1)$ możliwości wyboru tego zawodnika. Szósta osoba wpuszczana na salę powinna być jedną z $n - 1$ osób, których miejsce jest w rzędzie zajętym tylko przez jednego zawodnika. Następnie sytuacja znów się powtarza: we wszystkich rzędach siedzą po dwie osoby, przed wejściem czeka $3 (n - 2)$ zawodników. Teraz może wejść którykolwiek z nich, po nim ktoś z $2(n - 2)$ tych, których miejsca są w innych rzędach niż miejsce ostatnio wpuszczonego itd. Liczba zdarzeń sprzyjających wynosi więc

$ \begin{split} 3n \cdot 2n \cdot n \cdot 3 (n - 1) \cdot 2 (n - 1) \cdot (n - 1) \cdot 3 (n - 2) \cdot 2 (n - 2) \cdot (n - 2) \ldots 3 \cdot 2 \cdot 1 =\\ = 3n \cdot 3(n-1) \cdot 3(n-2) \cdot \ldots \cdot 3 \cdot 2n \cdot 2(n-1) \cdot 2(n-2) \cdot \ldots \cdot 2 \cdot n \cdot (n-1) \cdot (n-2) \cdot \ldots 1 =\\ = 3^n \cdot n! \cdot 2^n \cdot n! \cdot n! = 6^n \cdot (n!)^3 \end{split} $

(Podany tu opis można oczywiście zastąpić dowodem indukcyjnym). Wobec tego szukane prawdopodobieństwo wynosi

$ \frac{6^n \cdot (n!)^3}{(3n)!} $

XXXV OM - II - Zadanie 5

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

Obliczyć kres dolny pól sześciokątów wypukłych, których wszystkie wierzchołki mają współrzędne całkowite.

Rozwiązanie

W rozwiązaniu zastosujemy następujący lemat, który był treścią zadania konkursowego w poprzedniej Olimpiadzie Matematycznej

Lemat. Podwojone pole trójkąta, którego wszystkie wierzchołki mają współrzędne całkowite jest liczbą całkowitą.

Dowód. Pole trójkąta $ABC$ jest równe połowie wartości bezwzględnej
wyznacznika utworzonego ze współrzędnych wektorów $\overrightarrow{AB}$ i $\overrightarrow{AC}$ . Jeśli współrzędne wierzchołków $A$ , $B$ , $C$ są liczbami całkowitymi, to współrzędne wektorów $\overrightarrow{AB}$ i
$\overrightarrow{AC}$ też są liczbami całkowitymi, wyznacznik utworzony z tych współrzędnych również jest liczbą całkowitą, a w konsekwencji podwojone pole trójkąta $ABC$ jest liczbą całkowitą.

Każdy punkt na płaszczyźnie mający współrzędne całkowite należy do dokładnie jednego z następujących czterech zbiorów

$A$ - zbiór punktów, których obie współrzędne są parzyste,
$B$ - zbiór punktów, których obie współrzędne są nieparzyste,
$C$ - zbiór punktów, których pierwsza współrzędna jest parzysta, druga nieparzysta,
$D$ - zbiór punktów, których pierwsza współrzędna jest nieparzysta, druga parzysta.

Gdy dwa punkty płaszczyzny należą do jednego z tych zbiorów, to mówimy, że mają ten sam typ parzystości. Jeżeli punkty $P = (p_1,p_2)$ i $Q = (q_1, q_2)$ mają ten sam typ parzystości, to środek odcinka $\overline{PQ}$ ma współrzędne
$\left( \displaystyle \frac{1}{2} (p_1+q_1), \frac{1}{2} (p_2+q_2) \right)$ będące liczbami całkowitymi (suma liczb tej samej parzystości jest liczbą parzystą).

Powróćmy do sześciokątów wypukłych, których każdy wierzchołek ma współrzędne całkowite. Wśród sześciu wierzchołków sześciokąta można znaleźć dwa mające ten sam typ parzystości.

Jeśli dwa kolejne wierzchołki (np. $K$ i $L$ ) sześciokąta $KLMNOP$ mają ten sam typ parzystości, to łącząc środek $S$ odcinka $\overline{KL}$ z punktem $M$ otrzymamy sześciokąt $KSMNOP$ mający pole mniejsze od sześciokąta $KLMNOP$ . Przy wyznaczaniu kresu dolnego pól sześciokątów możemy więc ograniczyć się do takich sześciokątów, w których kolejne wierzchołki nie mają tego samego typu parzystości. Wobec tego istnieją pewne dwa niekolejne wierzchołki mające ten sam typ parzystości. Środek odcinka łączącego te wierzchołki ma współrzędne całkowite i leży wewnątrz sześciokąta. Łącząc ten środek z wszystkimi wierzchołkami sześciokąta otrzymamy sześć trójkątów, których suma pól równa jest polu sześciokąta. Wobec tego na mocy lematu pole sześciokąta jest nie mniejsze od $6 \cdot \frac{1}{2} = 3$ . Przykładem sześciokąta wypukłego mającego wierzchołki o współrzędnych całkowitych, którego pole wynosi $3$ , jest sześciokąt o wierzchołkach $K = (- 1, - 1)$ , $L = (0, - 1)$ , $M = (1, 0)$ , $N = (1,1)$ , $O = (0,1)$ , $P = (- 1, 0)$ .

Szukany kres dolny wynosi więc $3$ .

XXXV OM - II - Zadanie 6

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

Ciąg $(x_n)$ określony jest wzorami

$ x_1=c,\; x_{n+1} = cx_n + \sqrt{(c^2-1)(x_n^2-1)} \quad\text{ dla }\quad n=1,2,\ldots $

Dowieść, że jeśli $c$ jest liczbą naturalną, to wszystkie liczby $x_n$ są naturalne.

Rozwiązanie

Wyrazy $x_1 = c$ , $x_2 = 2c^2 - 1$ są liczbami naturalnymi.

Załóżmy dla pewnego $n$ , że wszystkie wyrazy $x_k$ przy $k \leq n$ są naturalne. Udowodnimy, że $x_{n+1}$ jest liczbą naturalną. Z danego wzoru wynika, że

$ x_{n+1} -cx_n = \sqrt{(c^2-1)(x_n^2-1)}, $

więc

$ (*) \qquad(x_{n+1}-cx_n^2) =(c^2-1)(x_n^2-1) $

i podobnie

$ (x_n-cx_{n-1})^2 =(c^2-1)(x^2_{n-1}-1). $

Z ostatniej równości otrzymujemy

$ \begin{split} x_n^2 - 2cx_n x_{n-1} + c^2 x^2_{n-1} =c^2 x^2_{n-1} - c^2 - x^2_{n-1}+1,\\ x_n^2 + c^2 - 1 = 2cx_n x_{n-1} - x^2_{n-1}, \end{split} $

a po odjęciu obu stron od $c^2x^2_n$

$ c^2 x_n^2 -x_n^2 - c^2 + 1 = c^2x_n^2 - 2cx_n x_{n-1} + x_{n-1}^2, $

czyli

$ (**)\qquad (c^2-1)(x_n^2-1) = (cx_n - x_{n-1})^2. $

Porównując (*) i (**) stwierdzamy, że

$ (x_{n+1}-cx_n)^2 = (cx_n - x_{n-1})^2. $

Ponieważ ze wzoru określającego ciąg wynika, że $x_{n+1} \geq cx_n$ oraz $cx_n \geq x_{n-1}$ , więc

$ x_{n + 1} - cx_n = cx_n - x_{n-1}, $

a zatem

$ x_{n+1} = 2cx_n - x_{n-1}. $

Na mocy przyjętego założenia indukcyjnego liczby $x_n$ i $x_{n-1}$ są naturalne, więc liczba $2cx_n - x_{n-1}$ jest całkowita. Jest to ponadto liczba dodatnia, a więc $x_{n+ 1}$ jest liczbą naturalną.

Na mocy zasady indukcji wszystkie wyrazy ciągu $(x_n)$ są liczbami naturalnymi.

XXXV OM - III etap

III etap XXXV Olimpiady Matematycznej

XXXV OM - III - Zadanie 1

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

III

Wyznaczyć liczbę takich funkcji $f$ odwzorowujących zbiór $n$ -elementowy w ten sam zbiór, że $f^{n-1}$ jest funkcją stałą, zaś $f^{n-2}$ nie jest funkcją stałą, gdzie $f^k = f\circ f \circ \ldots \circ f$ , $n$ jest ustaloną liczbą naturalną większą od 2.

Rozwiązanie

Przypuśćmy, że $A = \{a_1, a_2,\ldots, a_n \}$ jest danym zbiorem $n$ -efementowym, $f$ - funkcją spełniającą warunki zadania. Rozważmy zbiory $A, f(A), f^2(A), \ldots, f^{n-1}(A)$ . Z założenia wynika, że zbiór $f^{n-1}(A)$ jest jednoelementowy, natomiast zbiór $f^{n-2}(A)$ ma więcej niż jeden element. Ponadto $f^{k-1}(A) \supset f^k(A)$ dla $k = 1,2,\ldots,n - 1$ , gdyż każdy element postaci $f^k(x)$ jest postaci $f^{k-1}(y)$ , gdzie $y =f(x)$ , a przy tym $f^{k-1}(A) \ne f^k(A)$ . Gdyby bowiem $f^{k-1}(A) = f^k(A) = \{a_{i_1}, a_{i_2}, \ldots, a_{i_r}\}$ , to funkcja $f$ przekształcałaby podzbiór $\{a_{i_1}, a_{i_2}, \ldots, a_{i_r}\}$ na ten sam podzbiór i byłaby na tym podzbiorze różnowartościowa. Każda iteracja funkcji $f$ byłaby więc różnowartościowa na tym podzbiorze, wbrew temu, że $f^{n-1}$ jest funkcją stałą.

Wobec tego mają miejsce zawierania

$ (*) \qquad A \supset f(A) \supset f^2(A) \supset \ldots \supset f^{n-2}(A) \supset f^{n-1}(A), $

z których żadne nie jest równością. Zbiór $A$ ma $n$ elementów, zbiór $f^{n-1}(A)$ ma jeden element. Wynika stąd, że każdy zbiór w ciągu (*) ma o jeden element mniej od zbioru poprzedniego.

Wykazaliśmy, że każda funkcja $f$ spełniająca warunki zadania wyznacza ciąg podzbiorów zbioru $A$ , w którym każdy następny podzbiór powstaje z poprzedniego przez odrzucenie jednego elementu, a zatem jednoznacznie wyznacza pewną permutację zbioru $A$ .

Z drugiej strony każdy taki ciąg podzbiorów zbioru $A$ jednoznacznie wyznacza funkcję $f$ bo jeśli

$ f^{n-1}(A) = \{a_1\},\ f^{n-2}(A) = \{a_1, a_2\},\ f^{n-3}(A) = \{a_1, a_2, a_3\},\ \ldots, $

$ \ldots, f(A) = \{a_1, a_2, \ldots, a_{n-1}\}, $

$ f(a_1)=a_1, f(a_2)=a_1, f(a_3)=a_2, \ldots, f(a_n)=a_{n-1}. $

Funkcje spełniające warunki zadania są wobec tego wyznaczone jednoznacznie przes permutacje zbioru $A$ . Ich liczba wynosi zatem $n!$ .

XXXV OM - III - Zadanie 2

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

III

Dla ustalonej liczby naturalnej $n$ oraz każdego $i = 1, 2, \ldots, n$ , $j = 1, 2, \ldots$ określamy

$ a_{j,i} = \begin{cases} 1 &\text{ dla }j=i \\ 0 &\text{ dla }j\neq i \end{cases} $

natomiast dla $i = n + 1,\ldots, 2n$ $j = 1,2,\ldots, n$

$ a_{j,i} = -\frac{1}{n}. $

Udowodnić, że dla każdej permutacji $p$ zbioru $\{1, 2,\ldots, 2n\}$ spełniona jest nierówność

$ \sum_{j=1}^n \left| \sum_{k=1}^n a_{j, p(k)}\right| \geq \frac{n}{2}. $

Rozwiązanie

Jeśli permutacja $p$ liczbom $1,2,\ldots,n$ przyporządkowuje $s$ wartości nie
większych od $n$ oraz $n-s$ wartości większych od $n$ , to suma $\displaystyle \sum_{k-1}^n a_{j,p(k)}$ równa jest $1+(n - s) \cdot \frac{-1}{n} = \frac{s}{n}$ albo $(n-s) \cdot \frac{-1}{n}$ w zależności od tego, czy istnieje $k \leq \{1,2, \ldots,n \}$ , dla którego $j= p(k)$ , czy też nie. Dla dokładnie $s$ wartości $j$ takie $k$ istnieje, dla $n-s$ wartości nie istnieje. Wobec tego

$ \begin{split} \sum_{j=1}^n \left| \sum_{k-1}^n a_{j,p(k)} \right| = s \cdot \left| \frac{s}{n} \right| + (n-s) \cdot \left| (n-s) \frac{-1}{n} \right|=\\ \frac{s^2}{n} + \frac{(n-s)^2}{n} = \frac{(2s-n)^2+n^2}{2n} \geq \frac{n^2}{2n} = \frac{n}{2}. \end{split} $

XXXV OM - III - Zadanie 3

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

III

Dany jest ośmiościan foremny $W$ o środku $O$ . W płaszczyźnie $P$ przechodzącej przez punkt $O$ wybrano koła $K(O, r_1)$ i $K (O, r_2)$ o środku $O$ i promieniach $r_1$ i $r_2$ , odpowiednio. Wykazać, że jeżeli

$ K(O, r_1) \subset P\cap W \subset K(O, r_2), $

$ \frac{r_1}{r_2} \leq \frac{\sqrt{3}}{2}. $

Rozwiązanie

Rozważmy przekrój ośmiościanu płaszczyzną $P$ . Punkt $O$ jest środkiem symetrii tego przekroju, skąd wynika, że przekrój jest wielokątem o parzystej liczbie boków oraz że przeciwległe boki są równoległe i równej długości. W zależności od tego, czy płaszczyzna $P$ przechodzi przez wierzchołek ośmiościanu, czy nie przechodzi, przekrój jest czworokątem lub sześciokątem. Rozważmy te przypadki kolejno.

Jeśli płaszczyzna $P$ przechodzi przez wierzchołek ośmiościanu, to przechodzi też przez wierzchołek przeciwległy, skąd wynika, że sąsiednie boki przekroju mają równe długości, zatem przekrój jest rombem. Wobec tego średnica mniejszego z rozważanych kół nie przekracza odległości przeciwległych boków rombu, zaś średnica większego nie jest krótsza od dłuższej przekątnej rombu. Jeśli długość boku rombu wynosi $d$ , to $2r_1 \leq d$ , $2r_2 \geq d \sqrt{2}$ , a zatem

$ \frac{r_1}{r_2} \leq \frac{1}{\sqrt{2}} < \frac{\sqrt{3}}{2}. $

W drugim przypadku przekrojem jest sześciokąt, którego przeciwległe boki są równoległe i mają równe długości, a przekątne sześciokąta przecinają się w punkcie $O$ , który jest ich wspólnym środkiem.

Przypuśćmy, że $K$ , $L$ , $M$ , $N$ , $P$ , $Q$ są kolejnymi wierzchołkami tego sześciokąta, przy czym kąt $KOL$ jest nie mniejszy od każdego z kątów mających wierzchołek $O$ i ramiona przechodzące przez sąsiednie wierzchołki sześciokąta. Wobec tego $\measuredangle KOL \geq 60^\circ$ . Oczywiście promień $r_1$ jest nie większy od odległości punktu $O$ od odcinka $\overline{KL}$ , promień $r_2$ jest nie mniejszy od $OK$ . Ponieważ punkt $O$ jest środkiem symetrii całej figury, więc trójkąt $KOL$ jest równoramienny, odległość punktu $O$ od $\overline{KL}$ równa jest długości wysokości opuszczonej na $\overline{KL}$ , tj. wynosi

$ OK \cdot \cos \left( \frac{1}{2} \measuredangle KOL \right) \leq OK \cdot \cos 30^\circ = OK \cdot \frac{\sqrt{3}}{2}. $

Wobec tego

$ \frac{r_1}{r_2} \leq \frac{\sqrt{3}}{2}. $

XXXV OM - III - Zadanie 4

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

III

Rzucamy $n$ -krotnie monetą i wynik zapisujemy w postaci ciągu $(a_1, a_2, \ldots, a_n)$ , gdzie $a_i = 1$ lub $a_i = 2$ w zależności od tego, czy w $i$ -tym rzucie wypadł orzeł, czy reszka. Przyjmujemy $b_j = a_1 + a_2 + \ldots + a_j$ dla $j = 1, 2,\ldots, n$ , $p(n)$ jest prawdopodobieństwem tego, że w ciągu $(b_1, b_2, \ldots, b_n)$ wystąpi liczba $n$ . Wyznaczyć $p(n)$ w zależności od $p(n-1)$ i $p(n-2)$ .

Rozwiązanie

Bezpośrednio stwierdzamy, że $p(1) = \frac{1}{2}$ , $p(2) = \frac{1}{4}$ . Przypuśćmy, że $n \geq 3$ . Zauważmy, że $b_j \geq j$ dla każdego $j$ . Liczba $n$ może wystąpić w ciągu $(b_1, b_2, \ldots, b_n)$ w następujących dwóch przypadkach:

1. Pewien wyraz tego ciągu równy jest $n-1$ , np. $b_k = n-1$ ( $k \leq n-1$ ) i ponadto $a_{k+1} = 1$ ,
2. Pewien wyraz tego ciągu równy jest $n - 2$ , np. $b_r = n - 2$ ( $r \leq n - 2$ ) i ponadto $a_{r + 1} = 2$ .

Prawdopodobieństwo dla wymienionych tu przypadków wynosi odpowiednio $p(n-1)\cdot \frac{1}{2}$ oraz $p(n-2)\cdot \frac{1}{2}$ , przy czym przypadki te nie mogą wystąpić jednocześnie. Wobec tego

$ p(n) = p(n-1) \cdot \frac{1}{2} + p(n-2)\cdot \frac{1}{2}. $

XXXV OM - III - Zadanie 5

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

III

Sześciokąt foremny o boku 1 zawarty jest w sumie mnogościowej sześciu kół mających średnicę 1. Wykazać, że żaden z wierzchołków sześciokąta nie należy do dwóch z tych kół.

Rozwiązanie

Przypuśćmy, że pewien wierzchołek sześciokąta należy do dwóch kół. Gdyby żadne z tych dwóch kół nie zawierało innego wierzchołka sześciokąta, to każdy z pozostałych pięciu wierzchołków należałby do jednego z pozostałych czterech kół. Wynika stąd, że istnieje koło $k_1$ zawierające dwa wierzchołki sześciokąta. Średnicą tego koła jest bok sześciokąta (powiedzmy $\overline{AB}$ ). W dowolnym otoczeniu każdego z punktów $A$ i $B$ znajdują się punkty nie należące do koła $k_1$ ale należące do sześciokąta. Zatem punkt $A$ jest punktem pewnego koła różnego od $k_1$ , podobnie punkt $B$ jest punktem jeszcze innego koła. Wobec tego sześć wierzchołków sześciokąta należy do pięciu kół różnych od $k_1$ . Istnieją więc dwa wierzchołki należące do koła $k_2$ będącego jednym z pięciu kół. Koła $k_1$ i $k_2$ pokrywają dwa boki sześciokąta, przy czym nie więcej niż jeden wierzchołek ma tę własność, że pewne jego otoczenie jest pokryte przez sumę kół $k_1$ i $k_2$ . Pozostałe pięć wierzchołków należy do pozostałych czterech kół. Zatem wśród tych kół jest koło zawierające dwa wierzchołki. Rozumowanie to kontynuujemy stwierdzając, że każde koło zawiera dwa wierzchołki sześciokąta i w związku z tym jego średnicą jest bok sześciokąta. Ale wobec tego środek sześciokąta nie należy do żadnego z tych sześciu kół, bo jego odległość od środka boku wynosi $\frac{\sqrt{3}}{2}$ i jest większa od długości promienia każdego z kół.

Wynika stąd, że jeśli rozważane koła pokrywają sześciokąt, to żaden z wierzchołków nie należy do dwóch kół.

XXXV OM - III - Zadanie 6

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

III

Miejscowości $P_1,\ldots, P_{1025}$ są obsługiwane przez linie lotnicze $A_1, \ldots, A_{10}$ , przy czym dla każdych miejscowości $P_k$ i $P_m$ ( $k \neq m$ ) istnieje taka linia, której samoloty latają bezpośrednio z $P_k$ do $P_m$ oraz bezpośrednio z $P_m$ do $P_k$ . Udowodnić, że któraś z tych linii może oferować podróż z nieparzystą liczbą lądowań rozpoczynającą i kończącą się w tej samej miejscowości.

Rozwiązanie

Przypuśćmy, że żadna z linii $A_1, \ldots, A_{10}$ nie może oferować podróży z nieparzystą liczbą lądowań, która zaczynałaby i kończyła się w tej samej miejscowości. Wynika stąd, że jeśli z miejscowości $P_k$ do miejscowości $P_m$ istnieje połączenie samolotami pewnej linii, przy którym jest parzysta liczba lądowań, to przy każdym innym połączeniu z $P_k$ do $P_m$ samolotami tej samej linii również jest parzysta liczba lądowań.

Dla każdej linii $A_j$ możemy zbiór miast podzielić w następujący sposób na dwa podzbiory $M_j$ i $N_j$ . Ustalamy dowolne miasto, np. $P_1$ i zaliczamy je do podzbioru $M_j$ . Następnie każde miasto, do którego można dolecieć z $P_1$ samolotami linii $A_j$ z parzystą liczbą lądowań zaliczamy do $M_j$ , natomiast każde miasto, do którego można dolecieć z $P_1$ samolotami linii $A_j$ z nieparzystą liczbą lądowań zaliczamy do $N_j$ . Jeśli po tym podziale pozostaną jeszcze pewne miasta, to dowolnie wybrane z nich, np. $P_k$ zaliczamy do $M_j$ wraz z tymi wszystkimi miastami, do których samoloty linii $A_j$ docierają z $P_k$ po parzystej liczbie lądowań. Te miasta, do których samoloty linii $A_j$ lecą z $P_k$ z nieparzystą liczbą lądowań zaliczamy do $N_j$ . Postępowanie to kontynuujemy, aż do wyczerpania wszystkich miast. Jeden ze zbiorów $M_1$ lub $N_1$ ma nie mniej niż $513$ elementów. Są to miasta nie mające między sobą bezpośrednich połączeń samolotami linii $A_1$ (dwa miasta, między którymi istnieje połączenie samolotami linii $A_1$ z nieparzystą liczbą lądowań, a więc w szczególności z jednym lądowaniem, należą do różnych zbiorów). Spośród tych $513$ miast nie mniej niż $257$ należy do jednego ze zbiorów $M_2$ albo $N_2$ . Żadne dwa spośród tych $257$ miast nie mają bezpośredniego połączenia samolotami linii $A_1$ oraz $A_2$ . Nie mniej niż połowa spośród nich,tj. $129$ miast należy do jednego ze zbiorów $M_3$ albo $N_3$ . Między żadnymi dwoma spośród tych $129$ miast nie ma bezpośredniego połączenia samolotami linii $A_1$ , $A_2$ , $A_3$ . Rozumując tak dalej stwierdzamy, że istnieje $65$ miast, między którymi nie ma żadnego bezpośredniego połączenia samolotami linii $A_1$ , $A_2$ , $A_3$ i $A_4$ , dalej - $33$ miasta bez bezpośredniego połączenia samolotami linii $A_1, \ldots, A_5$ , następnie $17$ miast nie mających bezpośredniego połączenia samolotami linii $A_1,\ldots, A_6$ . 9 spośród tych miast nie ma bezpośredniego połączenia samolotami linii $A_1, \ldots, A_7$ , $5$ z nich nie ma bezpośredniego połączenia samolotami $A_1, \ldots, A_8$ , $3$ miasta nie mają żadnego bezpośredniego rejsu żadnym samolotem linii $A_1, \ldots, A_9$ , wreszcie dwa miasta nie mają żadnego połączenia bezpośredniego samolotem żadnej z rozważanych dziesięciu linii. Ostatnie zdanie pozostaje jednak w sprzeczności z założeniem. Do sprzeczności tej doprowadziło przypuszczenie, że żadna linia nie może oferować podróży z nieparzystą liczbą lądowań zaczynającej i kończącej się w tej samej miejscowości. Zatem pewna linia może oferować taką podróż.