XXII OM - I etap

I etap XXII Olimpiady Matematycznej

XXII OM - I - Zadanie 1

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

Udowodnić twierdzenie: Współczynnik dwumianowy $\binom{n}{k}$ ma przy każdym naturalnym $k < n$ ten sam czynnik wspólny z $n$ większy od jedności wtedy i tylko wtedy, gdy $n$ jest potęgą liczby pierwszej.

Rozwiązanie

Udowodnimy, że jeżeli liczba $n$ jest potęgą liczby pierwszej $p$ , $n = p^r$ , to każdy ze współczynników dwumianowych , gdzie $1 \leq k < n$ , jest podzielny przez $p$ .

Mamy

$ \begin{split} \binom{n}{k} &= \frac{n(n-1)(n-2)\ldots(n-k+1)}{k!} =\\ &=\frac{n}{k}\cdot \frac{(n-1)(n-2)\ldots((n-1)-(k-1)+1)}{(k-1)!} =\\ &=\binom{n-1}{k-1} \end{split} $

Stąd $k\binom{n}{k}=n \binom{n-1}{k-1}$ Zatem liczba $n$ jest dzielnikiem liczby $k\binom{n}{k}$ Ponieważ $k < n$ , więc $n$ nie jest dzielnikiem $k$ i wobec tego istnieje
wspólny dzielnik liczb $n$ i $\binom{n}{k}$ większy od jedności. Jeżeli $n = p^r$ , to każdy dzielnik liczby $n$ większy od jedności jest podzielny przez $p$ i wobec tego p jest wspólnym dzielnikiem liczb $n$ i $\binom{n}{k}$ .

Udowodnimy z kolei, że jeżeli liczba $n > 1$ nie jest potęgą liczby pierwszej, to żadna liczba pierwsza $p$ dzieląca $n$ nie jest wspólnym dzielnikiem liczb $\binom{n}{k}$ , gdzie $1 \leq k < n$ .

Niech $n = p^rm$ , gdzie liczba $m > 1$ nie jest podzielna przez $p$ . Udowodnimy, że liczba $\binom{n}{p^k}$ nie jest podzielna przez $p$ .
\spos{1} Mamy

$ \begin{split} \binom{n}{p^r}&=\binom{p^rm}{p^r}=\frac{p^rm(p^rm-1)(p^rm-2)\ldots(p^rm-p^r+1)}{p^r(p^r-1)(p^r-2)\ldots1}=\\ &=m \prod_{j=1}^{p^r-1}\frac{p^rm-j}{p^r-j}. \end{split} $

Niech $p^s$ będzie dzielnikiem liczby $p^rm - j$ , gdzie $1 \leq j \leq p^r - 1$ Gdyby $s \geq r$ , to również $p^r$ byłoby dzielnikiem liczby $p^rm - j$ , a więc i liczby $j$ . Jest to niemożliwe, ponieważ $j < p^r$ . Zatem $s < r$ .

Ponieważ $p^r-j = (p^rm-j)- (m-1)p^r$ i oba składniki po prawej stronie są podzielne przez $p^s$ , więc i liczba $p^r - j$ jest podzielna przez $p^s$ .

Udowodniliśmy więc, że jeżeli licznik ułamka $\frac{p^rm-j}{p^r-j}$ jest podzielny przez pewną potęgę liczby $p$ , to przez tę samą potęgę jest też podzielny jego mianownik. Zatem przedstawiając ten ułamek w postaci skróconej stwierdzamy, że jego licznik nie będzie podzielny przez $p$ . Ponieważ liczba $\binom{n}{p^r}$ jest iloczynem liczby $m$ i takich ułamków o licznikach nie podzielnych przez $p$ , więc nie jest ona podzielna przez $p$ .

XXII OM - I - Zadanie 2

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

Udowodnić, że dla każdych liczb dodatnich $p$ i $q$ spełniających warunek $p + q = 1$ zachodzi nierówność

$ p \log p + q \log q \geq - \log 2. $

Rozwiązanie

Z warunków zadania wynika, że $0 < p < 1$ oraz $q = 1 - p$ . Zatem zadanie sprowadza się do tego, by wykazać, że funkcja $f(p) = p \log p + (1 - p) \log (1 - p)$ w przedziale $(0; 1)$ przybiera wartości nie mniejsze od $-\log 2$ . Obliczamy pochodną tej funkcji:

$ f'(p) = \log p + 1 - log(1 - p) - 1 = log \frac{p}{1-p}. $

Rozwiązując równanie $f'(p) = 0$ , czyli $\log \frac{p}{1-p} = 0$ , otrzymujemy $p = \frac{1}{2}$ . Zatem funkcja $f(p)$ może mieć ekstremum tylko w punkcie $p = -\frac{1}{2}$ .

Dla $p \in \left(0; \frac{1}{2} \right)$ mamy $\frac{p}{1-p} < 1$ , czyli $f'(p) < 0$ . Zatem w przedziale $\left( 0; \frac{1}{2} \right)$ funkcja $f(p)$ jest malejąca. Dla $p \in \left( \frac{1}{2}; 1 \right)$ mamy $\frac{p}{1-p}> 1$ czyli $f'(p) >0$ . Zatem w przedziale $\left( \frac{1}{2}; 1 \right)$ funkcja $f(p)$ jest rosnąca. Wobec tego w punkcie $p=\frac{1}{2}$ funkcja $f(p)$ ma minimum równe $f \left(\frac{1}{2} \right) = -\log 2$ i jest to najmniejsza wartość przybierana przez tę funkcję w przedziale $(0; 1)$ . Inaczej mówiąc $f(p) =p\log p +(1 -p) \log (1 - p) \geq -\log 2$ dla każdego $p \in (0; 1)$ .

XXII OM - I - Zadanie 3

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

Przez punkt $P$ , należący do płaszczyzny trójkąta $ABC$ , poprowadzono trzy proste prostopadłe odpowiednio do prostych $BC$ , $AC$ i prostej zawierającej środkową $\overline{CE}$ . Udowodnić, że przetną one prostą zawierającą wysokość $CD$ odpowiednio w takich punktach $K, L, M$ , że $KM = LM$ .

Rozwiązanie

Udowodnimy najpierw kilka pomocniczych faktów.

Lemat. Jeżeli odpowiednie boki dwóch trójkątów są równoległe, to trójkąty te są podobne.

Dowód. Niech $AB\parallel A'B'$ , $BC \parallel B'C$ , $CA \parallel C'A'$ . Wtedy odpowiednie kąty trójkątów $ABC$ i $A'B'C'$ mają ramiona równoległe. Zatem miary tych kątów są równe lub w sumie dają miarę kąta półpełnego. Mamy więc

$ \measuredangle A= \measuredangle A' \quad \textrm{lub} \quad \measuredangle A +\measuredangle A' =180^\circ, $

$ \measuredangle B= \measuredangle B' \quad \textrm{lub} \quad \measuredangle B +\measuredangle B' =180^\circ, $

$ \measuredangle C= \measuredangle C' \quad \textrm{lub} \quad \measuredangle C +\measuredangle C' =180^\circ, $

Gdyby w co najmniej dwóch przypadkach spełniony był drugi człon alternatywy, np. $\measuredangle A +\measuredangle A' =180^\circ$ , $\measuredangle B +\measuredangle B' =180^\circ$ to wobec tego, że suma miar kątów trójkąta równa jest $180^\circ$ , mielibyśmy, że

$ \measuredangle A +\measuredangle A' +\measuredangle B +\measuredangle B' =360^\circ $

$ \measuredangle A + \measuredangle B + \measuredangle C +\measuredangle A' +\measuredangle B' + \measuredangle C'=360^\circ $

Stąd $\measuredangle C + \measuredangle C' = 0^\circ$ , co nie jest możliwe.

Wobec tego w co najmniej dwóch przypadkach spełniony jest pierwszy człon alternatywy, np. $\measuredangle A = \measuredangle A'$ i $\measuredangle B =\measuredangle B'$ Wynika stąd, że trójkąty $ABC$ i $A'B'C'$ są podobne.

Wniosek. Jeżeli odpowiednie boki dwóch trójkątów są prostopadłe, to trójkąty te są podobne:

Dowód. Niech

$ (1) \qquad AB \bot A_1B_1,\quad BC \bot B_1C_1,\quad CA \bot C_1A_1. $

Obróćmy trójkąt $A_1B_1C_1$ wokół dowolnego punktu o kąt prosty. Otrzymamy wtedy trójkąt $A'B'C'$ o bokach prostopadłych do odpowiednich boków trójkąta $A_1B_1C_1$ , tzn.

$ (2) \qquad A_1B_1 \bot A'B', \quad B_1C_1 \bot B'C', \quad C_1A_1 \bot C'A'. $

Z (1) i (2) wynika, że $AB \parallel A'B'$ , $BC \parallel B'C'$ , $CA \parallel C'A'$ . Zatem na mocy lematu trójkąty $ABC$ i $A'B'C'$ są podobne. Ponieważ trójkąty $A'B'C'$ i $A_1B_1C_1$ są przystające, więc wynika stąd, że również trójkąty $ABC$ i $A_1 B_1 C_1$ są podobne.

Przystąpimy teraz do rozwiązania zadania.

Jeżeli punkt $P$ należy do prostej zawierającej odcinek $CD$ , to $P = K = L = M$ i wobec tego $KM = LM = 0$ .

Jeżeli punkt $P$ nie należy do prostej zawierającej odcinek $CD$ , to z warunków zadania wynika, że odpowiednie boki trójkątów $PKM$ i $CBE$ są prostopadłe, a także odpowiednie boki trójkątów $PLM$ i $CAE$ są prostopadłe (rys. 6). Zatem na mocy udowodnionego wyżej wniosku trójkąty $PKM$ i $CBE$ oraz trójkąty $PLM$ i $CAE$ są podobne.

Oznaczając odpowiednio stosunki tych podobieństw przez $\lambda$ i $\mu$ otrzymamy, że $PM = \lambda CE$ , $KM = \lambda BE$ , $PM = \mu CE$ , $LM = \mu AE$ . Z pierwszej i trzeciej równości wynika, że $\lambda =\mu$ . Punkt $E$ jest środkiem odcinka $AB$ , tzn. $AE = BE$ . Zatem z drugiej i czwartej równości wynika, że $KM = LM$ .

XXII OM - I - Zadanie 4

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

Wyznaczyć kąty, jakie tworzy płaszczyzna przechodząca przez środki trzech skośnych krawędzi sześcianu ze ścianami sześcianu.

Rozwiązanie

Oznaczmy przez $P$ , $Q$ , $R$ środki trzech skośnych krawędzi sześcianu o krawędzi długości a (rys. 7), Oznaczmy przez n płaszczyznę. trójkąta $PQR$ , a przez $\pi'$ - płaszczyznę podstawy $ABCD$ .

Trójkąt $PQR$ jest równoboczny, ponieważ obracając sześcian o $90^\circ$ wokół osi pionowej (przechodzącej przez środki ścian $ABCD$ i $A'B'C'D'$ ), a następnie wokół osi poziomej (przechodzącej przez środki ścian $ADD'A'$ i $BCC'B'$ ) punkty $P$ , $O$ , $R$ przejdą odpowiednio na $Q$ , $R$ , $P$ . Zatem $PQ = QR = RP$ .

Niech $E$ będzie środkiem odcinka $RQ$ . Wtedy punkt $E$ jest równoodległy od ścian $ABCD$ i $A'B'C'D'$ i wobec tego prosta $PE$ jest równoległa do płaszczyzny $\pi'$ , a więc i do wspólnej krawędzi płaszczyzn
$\pi$ $\pi'$ .

Prosta $PE$ jest prostopadła do prostej $QR$ , ponieważ środkowa w trójkącie równobocznym jest też wysokością. Zatem prosta $QR$ jest prostopadła do wspólnej krawędzi płaszczyzn $\pi$ i $\pi'$ . Wobec tego kąt $\alpha$ między płaszczyznami $\pi$ i $\pi'$ równy jest kątowi między prostą $QR$ i jej rzutem $QR'$ na płaszczyznę $\pi'$ . Zatem $\alpha = \measuredangle RQR'$ .

Za pomocą twierdzenia Pitagorasa obliczamy, że $QR'^2 = QC^2 +CR'^2 = \frac{1}{2} a^2$ , czyli $QR' = \frac{\sqrt{2}}{2} a$ . Zatem $\tg \alpha = \frac{RR'}{QR} = \sqrt{2}$ . Z tablic odczytujemy, że $a = 54^\circ45'$ .

Analogicznie dowodzimy, że kąt między płaszczyzną $xpi$ i dowolną ścianą sześcianu też jest równy $\alpha$ .

XXII OM - I - Zadanie 5

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

Dana jest liczba naturalna $N$ . Obliczyć liczbę takich ciągów $(x_1, \ldots, x_N)$ , że $x_i = 7$ albo $x_i = —13$ ( $i = 1, \ldots, N$ ) oraz

$ \sum_{i=1}^N x_i = 0. $

Rozwiązanie

Przypuśćmy, że dla pewnej liczby naturalnej $N$ istnieje ciąg $(x_1, \ldots, x_N)$ spełniający warunki zadania. Oznaczmy przez $t$ liczbę wyrazów tego ciągu równych $7$ . Wtedy z warunków zadania wynika, że $7t = 13(N - t)$ , czyli $20r = 13N$ . Wynika stąd, że liczba $N$ jest podzielna przez $20$ .

Na odwrót, jeżeli $N = 20r$ , gdzie $r$ jest pewną liczbą naturalną to, aby otrzymać ciąg $(x_1, \ldots, x_N)$ spełniający warunki zadania, w którym t wyrazów równych jest 7, musimy tak obrać liczbę t, by $20t = 13N$ , czyli $t = 13r$ . Każdy taki ciąg otrzymamy więc pisząc dowolnie na $13r$ miejscach liczbę $7$ , a na pozostałych $-13$ . Liczba takich ciągów jest więc równa $\binom{20r}{13r}$ .

Zatem liczba, o którą chodzi w zadaniu, równa jest $0$ , gdy $N$ nie jest podzielna przez $20$ , i równa jest $\binom{20r}{13r}$ gdy $N = 20r$ .

XXII OM - I - Zadanie 6

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

Niech $f(x,y,z) = \max(x^2 — yz, y^2 — xz, z^2 — xy)$ . Znaleźć zbiór wartości funkcji $f(x,y,z)$ rozpatrywanej dla liczb $x,y,z$ spełniających warunki:

$ (1) \qquad x^2 + y^2 + z^2 = 5, \; yz + zx + xy = 2, \; x \geq 0, y \geq 0, z \geq 0. $

Uwaga: $\max (a, b, c)$ jest to największa z liczb $a, b, c$ .

Rozwiązanie

Z (1) wynika, że

$ (x + y + z)^2 = x^2 + y^2 + z^2 + 2(xy + yz + zx) = 9, $

a więc $x + y + z = 3$ . Wynika stąd, że warunki (1) dodane w zadaniu są równoważne warunkom:

$ (2) \qquad x^2 + y^2 +z^2 = 5, \quad x+y+z = 3, \quad x\geq 0, \quad y \geq 0, \quad z \geq 0. $

Jeśli dokonamy dowolnej permutacji liter $x$ , $y$ , $z$ , to warunki jadania nie ulegną zmianie. Zatem bez zmniejszenia ogólności możemy ograniczyć się do rozpatrywania tylko takich liczb $x$ , $y$ , $z$ , że $0 < x < y < z$ . Wtedy oczywiście $x^2 - yz \leq y^2 - xz < z^2 - xy$ , i więc $f(x, y, z) = z^2 - xy$ . Za pomocą (1) i (2) obliczamy, że $z^2 - xy = z^2 + yz + zx - 2 = z^2 + z (3 - z) - 2 = 3z - 2$ .

Zadanie nasze sprowadziliśmy więc do następującego: Znaleźć zbiór wartości funkcji $g(z) = 3z - 2$ rozpatrywanej dla liczb $z$ spełniających warunek: istnieją takie liczby $x$ , $y$ , że

$ (3) \qquad x^2 + y^2 + z^2 = 5, \quad x + y + z = 3, \quad 0 \leq x \leq y \leq z. $

Równanie $x + y + z = 3$ określa płaszczyznę $P$ odległą o $\sqrt{3}$ od początku układu, a równanie $x^2 + y^2 + z^2 = 5$ - sferę $S$ o środku w punkcie $(0, 0, 0)$ i promieniu $\sqrt{5}$ . Ponieważ $\sqrt{3} < \sqrt{5}$ , więc układ równań (3) określa okrąg $K$ będący częścią wspólną płaszczyzny $P$ i sfery $S$ . Interesują nas tylko takie punkty $(x, y, z)$ okręgu $K$ , które spełniają warunek $0 \leq x \leq y \leq z$ . Aby je wyznaczyć, przecinamy okrąg $K$ płaszczyznami $x = 0$ , $x = y$ , $y = z$ . Wyznaczamy punkty przecięcia (rys. 8) rozwiązując następujące układy równań:

$ \left\{ \begin{array}{l} y^2 +z^2=5\\ y + z =3 \end{array} \right. $

Rozwiązania: $A = (0, 1, 2)$ i $B = (0, 2, 1)$ .

$ \left\{ \begin{array}{l} y^2 +z^2=5\\ y + z =3 \end{array} \right. $

Rozwiązania:

$ C= \left( 1 + \frac{\sqrt{3}}{3}, 1 + \frac{\sqrt{3}}{3}, 1 - \frac{2}{3} \sqrt{3} \right) $

$ D= \left( 1 - \frac{\sqrt{3}}{3}, 1 - \frac{\sqrt{3}}{3}, 1 + \frac{2}{3} \sqrt{3} \right). $

$ \left\{ \begin{array}{l} x^2 +2z^2=5\\ x + 2z =3 \end{array} \right. $

Rozwiązania:

$ E= \left(1 - \frac{2}{3} \sqrt{3}, 1 + \frac{\sqrt{3}}{3}, 1 + \frac{\sqrt{3}}{3} \right), $

$ F= \left(1 + \frac{2}{3} \sqrt{3}, 1 - \frac{\sqrt{3}}{3}, 1 - \frac{\sqrt{3}}{3} \right). $

Zatem warunek $x \geq 0$ spełniają punkty należące do łuku $\widehat{AFB}$ , warunek $x \leq y$ - punkty należące do łuku $\widehat{CED}$ , a warunek $y \leq z$ - punkty należące do łuku $\widehat{EDF}$ (rys. 8). Wobec tego warunek $0 \leq x \leq y \leq z$ spełniają punkty należące do części wspólnej tych łuków, tzn. punkty należące do łuku $\widehat{AD}$ .

Rzut łuku $\widehat{AD}$ na oś z jest odcinkiem, którego końcami są rzuty punktów $A$ i $D$ , tzn. punkty $(0, 0, 2)$ i $\left( 0, 1 + \frac{2}{3} \sqrt{3} \right)$ j. Ponieważ funkcja $g(z) = 3z - 2$ jest rosnąca, więc zbiór wartości tej funkcji rozpatrywanej dla punktów łuku $\widehat{AD}$ jest odcinkiem o końcach $g(2) = 4$ i $g \left(1 + \frac{2}{3} \sqrt{3} \right) = 1 + 2 \sqrt{3}$ .

XXII OM - I - Zadanie 7

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

Na płaszczyźnie danych jest pięć punktów kratowych (tzn. punktów o współrzędnych całkowitych). Udowodnić, że środek jednego z odcinków łączących te punkty jest również punktem kratowym.

Rozwiązanie

Niech dane będą punkty kratowe $P_i = (x_i, y_i)$ , gdzie $i = 1, 2, 3, 4, 5$ . Wśród liczb $x_1$ , $x_2$ , $x_3$ , $x_4$ , $x_5$ , są co najmniej trzy jednakowej parzystości (tzn. trzy parzyste lub trzy nieparzyste), bo jeśli na przykład co najwyżej dwie są parzyste, to pozostałe są nieparzyste. Niech na przykład liczby $x_1$ , $x_2$ , $x_3$ będą jednakowej parzystości.

Rozumując podobnie jak poprzednio stwierdzamy, że wśród liczb $y_1$ , $y_2$ , $y_3$ co najmniej dwie jednakowej parzystości. Niech na przykład liczby $y_1$ $y_2$ będą jednakowej parzystości. Wtedy liczby $x_1 + x_2$ i $y_1 + y_2$ będą parzyste, a więc środek odcinka $P_1P_2$ będzie miał współrzędne całkowite $\left(\frac{1}{2}(x_1+x_2), \frac{1}{2}(y_1+y_2) \right)$ czyli będzie punktem kratowym.

Uwaga 1. Prawdziwe jest analogiczne twierdzenie w przestrzeni n-wymiarowej: Jeżeli danych jest w przestrzeni $n$ --wymiarowej $2^n + 1$ punktów o współrzędnych całkowitych, to środek jednego z odcinków łączących te punkty ma współrzędne całkowite.

Uwaga 2. Można też uogólnić zadanie w inny sposób. Jeżeli na płaszczyźnie danych jest $n$ punktów kratowych, to środki co najmniej $\displaystyle \binom{\left< \frac{n}{4} \right>}{2}$ odcinków łączących te punkty są punktami kratowymi.
Tu $\left<x\right>$ oznacza najmniejszą liczbę całkowitą nie mniejszą od $x$ .

Dowód uwagi 2. Podzielmy dane punkty na klasy w zależności od parzystości ich współrzędnych. Są cztery klasy $(n, n)$ , $(n, p)$ , $(p, n)$ i $(p, p)$ , gdzie $n$ oznacza, że odpowiednia współrzędna jest nieparzysta, a $p$ -- że parzysta. W jednej z klas będzie więc co najmniej $\frac{n}{4}$ punktów, a ponieważ liczba punktów w klasie jest całkowita, więc w jednej z klas będzie co najmniej $\left< \frac{n}{4} \right>$ punktów.

Ponieważ środek odcinka, którego końce są punktami jednej klasy jest punktem kratowym, a dla $r$ punktów jest $\binom{r}{2}$ odcinków je łączących, więc liczba odcinków, których środki są punktami kratowymi jest równa co najmniej $\displaystyle \binom{\left< \frac{n}{4} \right>}{2}$ .

Zauważmy jeszcze, że

$ \left< \frac{n}{4} \right>= \left\{ \begin{array}{lll} k,&\textrm{gdy}& n=4k,\\ k+1,&\textrm{gdy}& n=4k+1,\ 4k+2, \ \textrm{lub}\ 4k+3 \end{array}\right. $

XXII OM - I - Zadanie 8

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

Dany jest sześcian o krawędzi długości 1; niech $S$ oznacza powierzchnię tego sześcianu. Udowodnić, że istnieje taki punkt $A \in S$ , że
1) dla każdego punktu $B \in S$ istnieje łamana łącząca $A$ i $B$ o długości nie większej niż 2 zawarta w $S$ ;
2) istnieje taki punkt $B \in S$ , że nie istnieje łamana łącząca $A$ i $B$ zawarta w $S$ o długości mniejszej niż 2.

Rozwiązanie

Oznaczmy przez $A$ środek jednej ze ścian sześcianu, a przez $B$ - środek ściany przeciwległej (rys. 9). Udowodnimy, że punkt $A$ spełnia warunek 1) zadania, a punkty $A$ i $B$ spełniają warunek 2).

1) Rozetnijmy powierzchnię $S$ sześcianu wzdłuż łamanych $BPC$ , $BQD$ , $BRE$ , $BTF$ i rozwińmy ją na płaszczyźnie. Otrzymamy wtedy figurę $S'$ przedstawioną na rysunku 10. Ponieważ odległości punktu $A$ od $B, B', B'', B'''$ są równe $2$ , więc cała figura $S'$ jest zawarta w kole o środku w punkcie $A$ i długości promienia $2$ . Wynika stąd, że każdy punkt figury $S'$ można połączyć z punktem $A$ odcinkiem o długości nie większej niż $2$ . Odcinek taki będzie oczywiście zawarty w $S'$ . Przechodząc od rozwinięcia $S'$ powierzchni sześcianu do powierzchni sześcianu $S$ każdy taki odcinek wyznaczy łamaną o długości nie większej niż $2$ zawartą w $S$ łączącą punkt $A$ z dowolnym punktem należącym do $S$ .

2) Każda łamana $\mathcal{L}$ łącząca punkty $A$ i $B$ przecina czworokąt $CDEF$ i czworokąt $PQRT$ , ponieważ każdy z tych czworokątów dzieli powierzchnię sześcianu na dwie części, a punkty $A$ i $B$ znajdują się w różnych częściach. Oznaczmy przez $K$ pierwszy punkt przecięcia łamanej $\mathcal{L}$ z czworokątem $CDEF$ , a przez $L$ - ostatni jej punkt przecięcia z czworokątem $PQRT$ . Długość łamanej $\mathcal{L}$ jest nie mniejsza od sumy długości odcinków $\overline{AK}$ , $\overline{KL}$ , i $\overline{LB}$ , ponieważ długość odcinka łączącego dwa punkty jest nie większa od długości każdej łamanej łączącej te punkty. Najmniejsza odległość środka kwadratu od punktu na jego boku jest równa połowie długości boku. Zatem $AK \geq \frac{1}{2}$ i $LB \geq \frac{1}{2}$ . Punkty $K$ i $L$ należą do płaszczyzn równoległych $CDEF$ i $PQRT$ odległych o $1$ . Zatem odległość tych punktów jest nie mniejsza od odległości płaszczyzn, tzn. $KL \geq 1$ . Stąd długość łamanej $\mathcal{L} \geq AK + KL + LB \geq \frac{1}{2} + 1 + \frac{1}{2} = 2$ .

XXII OM - I - Zadanie 9

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

Znaleźć cyfry $a, b, c$ , dla których przy każdym $n$ naturalnym zachodzi równość

$ \overline{\underbrace{aa\ldots a}_n\underbrace{bb\ldots b}_n} + 1 = (\overline{\underbrace{cc\ldots c}_n} + 1)^2 $

Uwaga: Symbol $\overline{a_1a_2\ldots a_k}$ oznacza liczbę, której kolejnymi cyframi w układzie dziesiętnym są $a_1, a_2, \ldots, a_k$ .

Rozwiązanie

Oznaczmy $p_n = \overline{\underbrace{11 \ldots 1}_n}$ . Wtedy $p_n = 10^{n-1} + 10^{n-2} + \ldots + 10 + 1 = \frac{10^n -1}{9}$ i stąd $10^n = 9p_n + 1$ .

Mamy

$ \overline{\underbrace{aa \ldots a}_n \underbrace{bb \ldots b}_n} = \overline{\underbrace{aa \ldots a}_n} \cdot 10^n + \overline{\underbrace{bb \ldots b}_n} = ap_n 10^n + bp_n = ap_n (9p_n + 1) + bp_n $

oraz $(\overline{\underbrace{cc \ldots c}_n} + 1 )^2 = (cp_n + 1)^2 = c^2p^2_n + 2cp_n + 1$ .

Równość dana w zadaniu przybiera więc postać

$ 9ap_n^2 + (a + b)p_n + 1 = c^2p_n^2 + 2cp_n + 1, $

czyli

$ (1) \qquad 9ap_n + (a + b) = c^2p_n + 2c. $

Wykorzystamy twierdzenie: Jeżeli dwa wielomiany $f(x)$ i $g(x)$ dla nieskończenie wielu argumentów $x$ przybierają równe wartości, to mają one odpowiednie współczynniki równe.

W naszym przypadku wielomiany $f(x) = 9ax + (a + b)$ i $g(x) = c^2x + 2c$ przybierają równe wartości dla $x = p_n$ , gdzie $n = 1, 2, \ldots$ . Zatem na mocy przytoczonego twierdzenia odpowiednie współczynniki wielomianów $f(x)$ i $g(x)$ są równe, tzn.

$ (2) \qquad 9a = c^2 \textrm{ i } a + b = 2c. $

Na odwrót, jeżeli liczby $a$ , $b$ , $c$ spełniają (2), to oczywiście dla każdej liczby naturalnej $n$ zachodzi równość (1). Wystarczy więc wyznaczyć wszystkie takie cyfry $a$ , $b$ , $c$ , które spełniają układ (2). Z pierwszego równania wynika, że cyfra $c$ jest podzielna przez $3$ , tzn. $c = 0, 3, 6$ lub $9$ . W każdym z tych przypadków łatwo wyznaczyć odpowiednie wartości cyfr $a$ i $b$ . Otrzymujemy następujące rozwiązania układu (2): $(a, b, c) = (0, 0, 0)$ , $(1, 5, 3)$ , $(4, 8, 6)$ i $(9, 9, 9)$ .

Uwaga 1. Z założenia, że dla każdej liczby naturalnej $n$ zachodzi (1), można inaczej wyprowadzić układ równań (2). Mianowicie dzieląc stronami równość (1) przez $p_n$ i przechodząc do granicy, gdy $n \to \infty$ otrzymujemy, że $\displaystyle \lim_{n \to \infty} p_n = \infty$ i wobec tego ${\displaystyle \lim_{n \to \infty} }\left( 9a + \frac{a+b}{p_n} \right) = 9a + 0 = 9a$ oraz ${\displaystyle \lim_{n \to \infty} }\left( c^2 + \frac{2c}{p_n} \right)= c^2 + 0 = c^2$ . Zatem $9a = c^2$ . Z tej równości i z (1) wynika, że $a + b = 2c$ .

Uwaga 2. Analogiczne zadanie można rozwiązać w przypadku dowolnej podstawy numeracji $g \geq 2$ . Dokonując podobnych przekształceń, jak w podanym wyżej rozwiązaniu, dochodzimy do równości

$ \nr{1'} (g - 1 )ap_n + (a + b) = c^2p_n + 2c, $

która zachodzi dla dowolnej liczby naturalnej $n$ . Podobnie, jak poprzednio stwierdzamy, że (1') jest równoważna następującemu układowi

$ \nr{2'} (g-1)a = c^2 \textrm{ i } a + b = 2c. $

Znajdziemy wszystkie cyfry $a$ , $b$ , $c$ w układzie numeracji o podstawie $g$ , które spełniają układ równań (2'). Oznaczmy przez $t^2$ największy kwadrat liczby naturalnej $t$ , który jest dzielnikiem liczby $g-1$ . Wtedy $g-1 = t^2s$ , gdzie $s$ jest liczbą bezkwadratową, tzn. $s$ nie jest podzielne przez kwadrat liczby naturalnej większej od jedności. Z pierwszego równania (2') wynika, że liczba $c$ jest podzielna przez $ts$ , tzn. $c = tsu$ , gdzie $u$ jest pewną liczbą całkowitą. Z tego samego równania otrzymujemy, że $a = su^2$ . Wreszcie z drugiego równania układu (2') otrzymujemy, że $b = su(2t - u)$ .

Zatem wszystkie rozwiązania układu (2') w liczbach całkowitych dane są wzorami:

$ \nr{3'} \begin{array}{l} a = su^2,\\ b = su(2t - u),\\ c = tsu, \end{array} $

gdzie $u$ jest dowolną liczbą całkowitą.

Jednak w naszym zadaniu liczby $a$ , $b$ , $c$ są cyframi przy podstawie numeracji $g$ , tzn. spełniają nierówności $0 \leq a, b, c \leq g - 1 = t^2s$ . Nierówność $0 \leq c \leq g - 1$ można zapisać w postaci $0 \leq tsu < t^2s$ , co jest równoważne z $0 \leq u \leq t$ . Na odwrót, jeżeli $0 \leq u \leq t$ , to mamy $0 \leq a = su^2 \leq st^2 = g - 1$ oraz $0 \leq b = su (2t - u)=s (2tu - u^2) = s (t^2 -(t - u)^2) \leq st^2 = g - 1$ . Zatem wszystkie rozwiązania zadania dane są wzorami (3'), gdzie $0 \leq u \leq t$ .

W szczególności przy $u = 0$ otrzymujemy rozwiązanie $a = b = c = 0$ , a przy $u = t$ - rozwiązanie $a = b = c = g - 1$ .

XXII OM - I - Zadanie 10

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

Dana jest tablica o $n$ wierszach i $n$ kolumnach. Liczba znajdująca się w $m$ -tej kolumnie i $k$ -tym wierszu równa jest $n(k - 1) + m$ . Jak należy wybrać $n$ liczb, po jednej z każdego wiersza i każdej kolumny, aby iloczyn tych liczb był największy ?

Rozwiązanie

Oznaczmy $a_{k,m} = n (k - 1) + m$ , gdzie $1 \leq k, m \leq n$ . Przypuśćmy, że z $i$ -tego wiersza wybieramy liczbę stojącą w kolumnie o numerze $m_i$ , gdzie $i = 1, 2, \ldots, n$ . Z warunków zadania wynika, że ciąg $m_1, m_2, \ldots, m_n$ ma różne wyrazy. Każdemu takiemu ciągowi odpowiada iloczyn $a_{1m_1} \cdot a_{2m_2} \cdot \ldots \cdot a_{nm_n}$ .

Udowodnimy, że jeżeli ciąg $m_1, m_2, \ldots, m_n$ nie jest malejący, to odpowiadający mu iloczyn nie jest największy.

Niech na przykład $m_i < m_{i+1}$ dla pewnego $i$ . Rozważmy iloczyny $A$ i $B$ odpowiadające ciągom:

$ m_1, \ldots, mi, m_{i + 1}, \ldots, m_n $

oraz

$ m_1, \ldots,m_{i+1}, m_i, \ldots,m_n $

(ciągi te różnią się tylko wyrazami o numerach $i$ oraz $i + 1$ ). Zatem

$ A = a_{1m_1} \ldots a_{im_i} a_{i+1m_{i+1}} \ldots a_{n m_n}= \prod_{k \ne i, i+1} a_{km_k} \cdot a_{im_i} a_{i+1 m_{i+1}} $

oraz

$ B = a_{1m_1} \ldots a_{im_{i+1}} a_{i+1m_i} \ldots a_{n m_n}= \prod_{k \ne i, i+1} a_{km_k} \cdot a_{im_{i+1}} a_{i+1 m_i}. $

Oznaczając $\displaystyle C= \prod_{k \ne i, i+1} a_{km_k}$ i wykorzystując określenie liczb $a_{km}$ otrzymujemy:

$ \begin{split} B - A &= C (a_{im_{i+1}} a_{i+1m_i} - a_{im_i} a_{i+1m_{i+1}}=\\ &=C [ (n (i - 1) + m_{i+1}) (ni + m_i) -(n(i- 1) + m_i)(ni + m_{i+1}] =\\ &= C (m_{i+1} - m_i) > 0. \end{split} $

Zatem $B > A$ , tzn. iloczyn odpowiadający drugiemu ciągowi jest większy niż iloczyn odpowiadający pierwszemu. Dowiedliśmy więc, że jeżeli ciąg $m_1, m_2, \ldots, m_n$ nie jest malejący, to odpowiadający mu iloczyn nie jest największy. Wobec tego największy iloczyn odpowiada ciągowi malejącemu. Ponieważ z liczb $1, 2, \ldots, n$ można tylko na jeden sposób utworzyć $n$ -wyrazowy ciąg malejący, mianowicie ciąg $n, n - 1, \ldots, 2, 1$ , więc największy iloczyn jest równy $a_{1n}a_{2n-1} \ldots a_{n1} = n(2n - 1) (3n - 2) (4n - 3) \ldots (n^2 - (n -1))$ .

XXII OM - I - Zadanie 11

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

Rzucamy $2n$ razy monetą. Niech $p_n$ oznacza prawdopodobieństwo, że otrzymamy serię o długości $r > n$ . Udowodnić, że $\lim p_n = 0$ .

Rozwiązanie

Zdarzeniami elementarnymi są wszystkie ciągi $2n$ -wyrazowe o wyrazach orzeł lub reszka; wszystkie one są jednakowo prawdopodobne i jest ich $2^{2n}$ . Niech $A_n$ będzie zdarzeniem polegającym na tym, że otrzymamy serię o długości co najmniej $n$ .

Rozważmy następujące trzyetapowe postępowanie:

1) Wybór pewnych $n$ kolejnych miejsc spośród $2n$ ;

2) Umieszczenie na wybranych miejscach samych orłów lub samych reszek;

3) Zapełnienie pozostałych miejsc dowolnie orłami i reszkami. W wyniku każdego takiego postępowania otrzymujemy ciąg będący zdarzeniem elementarnym sprzyjającym zdarzeniu $A_n$ , ponieważ ciąg taki zawiera serię długości $\geq n$ . Na odwrót każdy ciąg zawierający serię długości $\geq n$ można otrzymać w wyniku takiego postępowania. Oczywiście ten sam ciąg możemy otrzymać kilkakrotnie. Zatem liczba opisanych wyżej sposobów postępowania jest większa od liczby zdarzeń elementarnych sprzyjających zdarzeniu $A_n$ .

Wyznaczymy teraz liczbę opisanych wyżej sposobów postępowania. Czynność 1) można wykonać na $n + 1$ sposobów, ponieważ pierwszym z wybranych $n$ kolejnych miejsc może być tylko miejsce o numerze $1, 2, \ldots, n$ lub $n + 1$ . Czynność 2) można wykonać na dwa sposoby: albo umieszczając orły, albo umieszczając reszki. Wreszcie czynność 3) można wykonać na $2^n$ sposobów, ponieważ mamy $n$ pozostałych miejsc zapełnić orłami lub reszkami.

Tak więc liczba wszystkich opisanych wyżej sposobów postępowania jest równa $2(n + 1) 2^n$ .

Ze wzoru Newtona otrzymujemy, że dla $n \geq 2$

$ 2^n = (1 + 1)^n = \binom{n}{0} + \binom{n}{1} + \binom{n}{2} + \ldots + \binom{n}{n} > \binom{n}{2} = \frac{n(n-1)}{2}. $

Zatem

$ 0 < p(A_n) < \frac{2(n+1)}{\frac{n(n-1)}{2}} = \frac{4(n+1)}{n(n-1)} = \frac{4}{n} \left( 1 + \frac{2}{n-1} \right). $

Ponieważ ${\displaystyle \lim_{n \to \infty}} \frac{4}{n} = 0$ i ${\displaystyle \lim_{n \to \infty}} \frac{2}{n-1} = 0$ , więc wynika stąd, że
$\displaystyle \lim_{n \to \infty} p(A_n) = 0$ .

XXII OM - I - Zadanie 12

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

Dowieść, że każdy wielościan wypukły ma ścianę trójkątną lub kąt trójścienny.

Rozwiązanie

Załóżmy, że istnieje wielościan wypukły $W$ nie mający ani ściany trójkątnej, ani kąta trójściennego. Niech $w$ będzie liczbą wierzchołków, $k$ - liczbą krawędzi, a $s$ - liczbą ścian tego wielościanu i niech $\varphi$ będzie sumą miar wszystkich kątów płaskich przy wierzchołkach wielościanu $W$ . Ponieważ z każdego wierzchołka wychodzą co najmniej cztery krawędzie, a każda krawędź łączy dwa wierzchołki, więc $k \geq \frac{1}{2} \cdot 4w = 2w$ . Ponieważ każda ściana ma co najmniej cztery krawędzie, a dla $n \geq 4$ suma miar kątów wewnętrznych $n$ -kąta jest $\geq 2\pi$ , więc $\varphi \geq 2\pi s$ . Wewnątrz każdej ściany $S_i$ wybierzmy punkt $O_i$ i połączmy go ze wszystkimi wierzchołkami tej ściany. W wyniku otrzymujemy podział powierzchni wielościanu na $2k$ trójkątów, ponieważ każda krawędź jest bokiem dokładnie dwóch trójkątów. Niech $\Psi$ będzie sumą miar kątów we wszystkich trójkątach. Wtedy $4\pi w \leq 2k\pi = \Psi = \varphi + 2\pi s \leq 2\varphi$ , a więc $\varphi < 2\pi w$ . Z drugiej strony, ponieważ wielościan $W$ jest wypukły, więc $\varphi < 2\pi w$ . Otrzymana sprzeczność dowodzi, że nie istnieje wielościan o założonych własnościach.