XXII OM

XXII Olimpiada Matematyczna

Opracowanie rozwiązań: Jerzy Browkin

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.

XXII OM - II etap

II etap XXII Olimpiady Matematycznej

XXII OM - II - Zadanie 1

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

Na ile sposobów można tak wybrać $k$ pól szachownicy $n \times n$ ( $k \leq n$ ), aby żadne dwa z wybranych pól nie leżały ani w jednym wierszu, ani w jednej kolumnie?

Rozwiązanie

Można najpierw wybrać $k$ wierszy, w których mają leżeć wybrane pola. Uczynić to można na $\displaystyle \binom{n}{k}$ sposobów. Następnie w każdym z tych wierszy należy kolejno wybrać jedno z $n$ pól, jedno z $n - 1$ pól leżących w pozostałych kolumnach, itd. - jedno z $n - k + 1$ pól. Zatem łączna liczba sposobów równa jest $\displaystyle \binom{n}{k} n(n - 1) \ldots (n - k + 1)$ .

XXII OM - II - Zadanie 2

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

Dowieść, że jeżeli $A, B, C$ są kątami trójkąta, to

$ 1 < \cos A + \cos B + \cos C \leq \frac{3}{2}. $

Rozwiązanie

Ponieważ $C = \pi - (A + B)$ , więc

$ \begin{split} \cos A + \cos B + \cos C &= 2 \cos \frac{A+B}{2} \cos \frac{A-B}{2} - \cos (A + B) =\\ &=2 \cos \frac{A+B}{2} \cos \frac{A-B}{2} - 2\cos^2 \frac{A + B}{2} +1. \end{split} $

Stąd

$ \begin{split} \cos A+\cos B+ \cos C &=1 + 2\cos \frac{A + B}{2} \left( \cos \frac{A-B}{2}- \cos \frac{A+B}{2} \right) =\\ &= 1 + 4 \cos \frac{A+B}{2} \sin \frac{A}{2}\sin \frac{B}{2}> 1. \end{split} $

Ponadto, biorąc pod uwagę, że $\left| \frac{A-B}{2} \right| \leq \frac{\pi}{2}$ , otrzymujemy

$ \begin{split} \cos A + \cos B + \cos C &= 2 \cos \frac{A+B}{2} \cos \frac{A-B}{2} - 2\cos^2 \frac{A + B}{2} +1 \leq\\ &\leq2 \cos \frac{A+B}{2} - 2\cos^2 \frac{A+B}{2} + 1 =\\ &= -2 \left( \cos \frac{A + B}{2} - \frac{1}{2} \right)^2 + \frac{3}{2} \leq \frac{3}{2}. \end{split} $

XXII OM - II - Zadanie 3

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

Danych jest 6 prostych w przestrzeni, z których żadne 3 nie są równoległe, żadne 3 nie przechodzą przez ten sam punkt i żadne 3 nie są zawarte w jednej płaszczyźnie. Udowodnić, że wśród tych 6 prostych istnieją 3 proste wzajemnie skośne.

Rozwiązanie

Z warunków zadania wynika, że w każdej trójce rozważanych prostych istnieje para prostych skośnych. Przyporządkujmy danym prostym w sposób wzajemnie jednoznaczny wierzchołki sześciokąta wypukłego oznaczone cyframi $1, 2, \ldots, 6$ (rys. 11). Jeżeli pewne dwie proste są skośne, to połączmy odpowiadające im wierzchołki sześciokąta linią ciągłą, a jeżeli nie są skośne - linią przerywaną.

Zadanie sprowadziliśmy więc do następującego: Danych jest sześć punktów. Każde dwa z nich połączone są linią ciągłą lub przerywaną. Przy tym każdy trójkąt o wierzchołkach należących do danego zbioru punktów ma co najmniej jeden bok będący linią ciągłą. Dowieść, że istnieje trójkąt, którego wszystkie boki są liniami ciągłymi.

Przypuśćmy, że nie ma trójkąta, którego wszystkie boki są. liniami ciągłymi. Istnieje więc para punktów połączona linią przerywaną. Niech to będzie na przykład para $1, 2$ . Ponieważ w każdym z trójkątów $1, 2, 3$ ; $1, 2, 4$ ; $1, 2, 5$ ; $1, 2, 6$ istnieje bok narysowany linią ciągłą i bokiem tym nie jest $1, 2$ , więc każdy z punktów $3, 4, 5, 6$ jest połączony linią ciągłą z co najmniej jednym z punktów $1, 2$ .

Gdyby pewien z punktów $1, 2$ był połączony linią ciągłą z co najmniej trzema z punktów $3, 4, 5, 6$ , na przykład punkt $1$ z punktami $3, 4, 5$ , to rozważając trójkąty $1, 3, 4$ ; $1,4, 5$ ; $1, 3, 5$ , w których dwa boki narysowane są linią ciągłą, stwierdzamy, że boki $3, 4$ ; $4, 5$ oraz $3, 5$ są narysowane linią przerywaną (rys. 11). W trójkącie $3, 4, 5$ żaden z boków nie byłby więc narysowany linią ciągłą. Jest to sprzeczne z warunkami zadania.

Zatem każdy z punktów $1$ i $2$ jest połączony linią ciągłą z dokładnie dwoma z punktów $3, 4, 5, 6$ . Bez zmniejszenia ogólności rozważań możemy założyć, że punkt $1$ jest połączony linią ciągłą z punktami $3$ i $4$ , a punkt $2$ - z punktami $5$ i $6$ . Natomiast punkt $1$ jest połączony linią przerywaną z punktami $5$ i $6$ , a punkt $2$ - z punktami $3$ i $4$ (rys. 12). Rozważając trójkąt $2, 5, 6$ stwierdzamy, że punkty $5$ i $6$ są połączone linią przerywaną. Wtedy jednak trójkąt $1, 5, 6$ ma wszystkie boki narysowane linią przerywaną. Jest to sprzeczne z warunkami zadania. Uzyskana sprzeczność dowodzi, że istnieje trójkąt, którego wszystkie boki są narysowane liniami ciągłymi.

XXII OM - II - Zadanie 4

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

Na płaszczyźnie dany jest skończony zbiór punktów $Z$ o tej własności, że żadne dwie odległości punktów zbioru $Z$ nie są równe. Punkty $A, B$ należące do $Z$ łączymy wtedy i tylko wtedy, gdy $A$ jest punktem najbliższym $B$ lub $B$ jest punktem najbliższym $A$ . Udowodnić, że żaden punkt zbioru $Z$ nie będzie połączony z więcej niż pięcioma innymi.

Rozwiązanie

Przypuśćmy, że punkt $A \in Z$ jest połączony z pewnymi punktami $B$ i $C$ zbioru $Z$ i niech na przykład $AB < AC$ . Wtedy punkt $C$ nie jest najbliższy $A$ , a więc z warunków zadania wynika, że punkt $A$ jest najbliższy $C$ . W szczególności więc $AC < BC$ . Zatem w trójkącie $ABC$ bok $\overline{BC}$ jest najdłuższy, a więc kąt $\measuredangle BAC$ jest największy. Wynika stąd, że $\measuredangle BAC > \frac{\pi}{3}$ .

Udowodniliśmy w ten sposób, że jeżeli punkt $A \in Z$ jest połączony z pewnymi punktami $B$ i $C$ zbioru $Z$ , to $\measuredangle BAC > \frac{\pi}{3}$ .

Jeżeli więc punkt $A \in Z$ jest połączony (rys. 13) z punktami $B_1, B_2, \ldots, B_n$ zbioru $Z$ , to

$ \measuredangle B_1AB_2 > \frac{\pi}{3},\ \measuredangle B_2AB_3 > \frac{\pi}{3},\ \ldots, \measuredangle B_nAB_1 > \frac{\pi}{3}. $

Dodając te nierówności stronami otrzymujemy, że $2\pi > n \frac{\pi}{3}$ czyli $n < 6$ . Zatem liczba $n$ punktów zbioru $Z$ , z którymi jest połączony punkt $A$ jest nie większa od $5$ .

XXII OM - II - Zadanie 5

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

Dany jest zbiór liczb $\{1, 2, 3, \ldots, 100\}$ . Ze zbioru tego utworzyć 10 podzbiorów parami rozłącznych $N_i = \{a_{i,1}, a_{i,2}, \ldots a_{i,10}}$ ( $i = 1, 2, \ldots, 10$ ) tak, aby suma iloczynów

$ \sum_{i=10}^{10}\prod_{j=1}^{10} a_{i,j} $

była największa.

Rozwiązanie

Udowodnimy najpierw następujący

Lemat. Jeżeli $\{a_1, \ldots, a_r, b_1, \ldots, b_r \}$ jest zbiorem $2r$ różnych liczb dodatnich oraz $a_i < b_j$ dla $i,j = 1,2, \ldots,r$ , to dla każdego $k$ $(1 \leq k < r)$

$ (1) \qquad a_1 \ldots a_kb_{k+1} \ldots b_r + b_1 \ldots b_k a_{k+1} \ldots a_r < a_1 \ldots a_r + b_1 \ldots b_r. $

Inaczej mówiąc lemat stwierdza, że jeżeli dany zbiór jest rozbity na dwa podzbiory $r$ -elementowe, to suma iloczynów elementów należących do każdego z podzbiorów będzie największa, gdy każda liczba należąca do jednego z podzbiorów będzie mniejsza od każdej liczby należącej do drugiego.

Dowód. Przekształcamy nierówność (1) w sposób równoważny

$ a_1 \ldots a_k (b_{k+1} \ldots b_r - a_{k+1} \ldots a_r) < b_1 \ldots b_k - a_{k+1} \ldots a_r. $

$ (2) \qquad (b_1 \ldots b_k - a_1 \ldots a_k) (b_{k+1} \ldots b_r - a_{k+1} \ldots a_r) > 0. $

Z założenia mamy $a_1 \ldots a_k < b_1 \ldots b_k$ oraz $a_{k+1} \ldots a-r <b_{k+1} \ldots b_r$ . Wynika stąd nierówność (2).

Przystępujemy teraz do rozwiązania zadania. Przypuśćmy, że podzbiory $N_i$ ( $i =1,2, \ldots, 10$ ) zbioru $\{ 1, 2, 3, \ldots, 100\}$ spełniają warunki zadania. Wynika stąd w szczególności, że dla $i \ne j$ zbiór $N_i \cup N_j$ ma następującą własność: Jeżeli rozbić w dowolny sposób zbiór $N_i \cup N_j$ na dwa podzbiory $10$ -elementowe, to suma iloczynów elementów należących do każdego z podzbiorów będzie największa wtedy, gdy tymi podzbiorami będą $N_i$ i $N_j$ .

Z lematu wynika więc, że każda liczba należąca do zbioru $N_i$ jest mniejsza od każdej liczby należącej do zbioru $N_j$ lub odwrotnie. Zatem (zamieniając ewentualnie kolejność zbiorów $N_i$ ) zbiory $N_i$ spełniające warunki zadania mają następującą własność: Każda liczba należąca do zbioru $N_i$ jest mniejsza od każdej liczby należącej do zbioru $N_{i+1}$ dla $i = 1,2, \ldots, 9$ . Wobec tego do $N_1$ należy $10$ najmniejszych liczb zbioru $\{1, 2, 3, \ldots, 100\}$ , do $N_2$ - $10$ następnych liczb naturalnych itd. Ogólnie $N_i = \{10(i - 1) + j \colon j = 1, 2, \ldots, 10\}$ dla $i = 1,2, \ldots, 10$ .

XXII OM - II - Zadanie 6

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

Dany jest ciąg nieskończony $\{a_n\}$ . Dowieść, że jeżeli

$ a_n + a_{n+2} > 2a_{n+1} \quad \tex{ dla } \quad n = 1, 2, \ldots, $

$ \frac{a_1+a_3+\ldots a_{2n+1}}{n+1} \geq \frac{a_2+a_4+\ldots a_{2n}}{n} $

dla $n = 1, 2, \ldots$ .

Rozwiązanie

Nierówność $a_n + a_{n+2} \geq 2a_{n+1}$ daną w założeniu przekształcamy do postaci równoważnej

$ (1) \qquad a_{n+2} - a_{n+1} \geq a_{n + 1} - a_n/ $

Oznaczając $b_{n+1} = a_{n+1} - a_n$ dla $n = 1, 2, \ldots$ nierówność (1) można zapisać w postaci $b_{n+2} > b_{n+1}$ . Zatem ciąg $\{b_n\}$ jest niemalejący.

Nierówność daną w tezie przekształcamy do postaci równoważnej

$ (2) \qquad n(a_1 + a_3+ \ldots + a_{2n+1}) \geq (n + 1)(a_2 + a_4 + \ldots + a_{2n}). $

Nierówność (2) udowodnimy przez indukcję ze względu na $n$ . Dla $n = 1$ przybiera ona postać $a_1 + a_3 \geq 2a_2$ . Jest to szczególny przypadek nierówności danej w założeniu.

Załóżmy z kolei, że nierówność (2) zachodzi dla pewnej liczby naturalnej $n$ , udowodnimy, że zachodzi ona dla liczby $n + 1$ , tzn. że

$ (3) \qquad (n +1)(a_1 + a_3+ \ldots + a_{2n+1} + a_{2n+3}) \geq (n + 2) (a_2 + a_4 + \ldots + a_{2n} + a_{2n+2}). $

Porównując (2) i (3) stwierdzamy, iż wystarczy dowieść, że

$ (4) \qquad (a_1 + a_3+ \ldots + a_{2n+1}) + (n + 1)a_{2n+3} \geq (a_2 + a_4 + \ldots + a_{2n}) + (n + 2)a_{2n+2}. $

Wtedy dodając stronami (2) i (4) otrzymamy (3).

Przekształcamy nierówność (4) w sposób równoważny

$ \begin{split} (n + 1)(a_{2n+3} - a_{2n+2}) \geq (a_2 - a_1) + (a_4 - a_3) + \ldots + \\ +(a_{2n} - a_{2n} - 1) + (a_{2n+2} - a_{2n+1}), \end{split} $

$ (5) \qquad (n + 1) b_{2n+3} \geq b_2 + b_4+ \ldots +b_{2n} + b_{2n+2}. $

Ponieważ, jak stwierdziliśmy na początku, ciąg $\{b_n\}$ jest niemalejący, więc w szczególności

$b_{2n + 3} \geq b_2,$

$b_{2n + 3} \geq b_4,$

$\ldots$

$b_{2n + 3} \geq b_{2n},$

$b_{2n + 3} \geq b_{2n+2}.$

Dodając te nierówności stronami otrzymujemy (5). Zatem prawdziwe są nierówności (4) i (3). Wobec tego na mocy zasady indukcji nierówność (2) zachodzi dla każdej liczby naturalnej $n$ .

XXII OM - III etap

II etap XXII Olimpiady Matematycznej

XXII OM - III - Zadanie 1

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

III

Dowieść, że jeżeli $a_n$ jest ciągiem różnych liczb naturalnych, których rozwinięcia dziesiętne nie zawierają, cyfry O, to

$ \sum_{n=1}^{\infty} \frac{1}{a_n} < 29. $

Rozwiązanie

Oznaczmy przez $b_n$ liczbę powstającą z liczby $a_n$ przez zastąpienie wszystkich jej cyfr prócz pierwszej zerami. Mamy oczywiście $b_n \leq a_n$ i wobec tego $\frac{1}{a_n} \leq \frac{1}{b_n}$ . W ciągu $\{a_n\}$ jest $9$ liczb jednocyfrowych, $9^2$ liczb dwucyfrowych i ogólnie $9^k$ liczb $k$ -cyfrowych, ponieważ każda cyfra takiej liczby może przybierać jedną z dziewięciu wartości $1, 2, \ldots, 9$ .

Wśród $9^k$ liczb $k$ -cyfrowych ciągu $\{a_n\}$ jest $9^{k-1}$ takich, których pierwszą cyfrą jest $1$ , $9^{k-1}$ takich, których pierwszą cyfrą jest $2$ itd. Wobec tego w ciągu $\{b_n\}$ liczba $k$ -cyfrowa $c 00 \ldots 0$ , gdzie $c$ jest ustaloną cyfrą różną od zera, powtarza się $9^{k-1}$ razy.

Stąd

$ \sum_{\substack{n \\ b_n \textrm{ ma } k \textrm{cyfr}}} \frac{1}{b_n} = 9^{k-1} \sum_{c=1}^9 \frac{1}{c00 \ldots 0} = 9^{k-1} \sum_{c=1}^9 \frac{1}{c \cdot 10^{k-1}} = \left( \frac{9}{10} \right)^{k-1} \sum_{c=1}^9 \frac{1}{c}. $

Obliczamy bezpośrednio, że

$ s_9 = \sum_{c=1}^9 \frac{1}{c} = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \ldots + \frac{1}{9} = 2,8289\ldots < 2,9. $

Wobec tego

$ \begin{split} \sum_{\substack{n \\ b_n \textrm{ ma } \leq r \textrm{cyfr}}} \frac{1}{b_n}&= \sum_{k=1}^r \sum_{\substack{n \\ b_n \textrm{ ma } k \textrm{cyfr}}} \frac{1}{b_n} = \sum_{k=1}^r s_9 \left( \frac{9}{10} \right)^{k-1} =\\ &=s_9 \sum_{k=1}^r \left( \frac{9}{10} \right)^{k-1} = s_9 \frac{1 - 0,9r}{1 - 0,9} < s_9 \frac{1}{1-0,9} = 10s_9. \end{split} $

Ponieważ nierówność $\displaystyle \sum_{\substack{n \\ b_n \textrm{ ma } \leq r \textrm{cyfr}}} \frac{1}{b_n} < 10 s_9$ ma miejsce dla każdej liczby
naturalnej $r$ , więc $\displaystyle \sum_{n=1}^\infty \frac{1}{b_n} \leq 10 s_9 < 29$ . Tym bardziej $\displaystyle \sum_{n=1}^\infty \frac{1}{a_n} < 29$ .

XXII OM - III - Zadanie 2

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

III

Na stole bilardowym w kształcie trójkąta, którego miary kątów są współmierne, pchnięto kulę z pewnego punktu wewnętrznego. Kula odbija się od ścian zgodnie z prawem "kąt padania równy kątowi odbicia". Udowodnić, że liczba kierunków, w jakich może się poruszać kula, jest skończona. (Zakładamy, że kula nie trafia w wierzchołek trójkąta).

Rozwiązanie

Udowodnimy najpierw następujący
Lemat. Po dwukrotnym odbiciu kuli kolejno od boków $\overline{CA}$ i $\overline{AB}$ trójkąta $ABC$ (rys. 14) kierunek ruchu kuli zmienia się o kąt $2 \measuredangle BAC$ .

Dowód. Rozpatrzmy obraz $AB'C$ trójkąta $ABC$ w symetrii względem prostej $AC$ oraz obraz $AB'C'$ trójkąta $AB'C$ w symetrii względem prostej $AB'$ . Oznaczmy przez $k$ , $l$ , $m$ kolejne wektory obrazujące ruch kuli, przez $l'$ , $m'$ - obrazy wektorów $l$ , $m$ w pierwszej symetrii, a przez $m''$ - obraz wektora $m'$ w drugiej symetrii (rys. 14).

Z prawa ,,kąt padania równy jest kątowi odbicia'' wynika, że wektory $k$ , $l'$ , $m''$ mają ten sam kierunek. Ponieważ złożenie rozważanych symetrii jest obrotem wokół punktu $A$ o kąt $2\measuredangle BAC$ , więc trójkąt $AB'C'$ jest obrazem trójkąta $ABC$ przy tym obrocie, a wektor $m''$ - obrazem wektora $m$ . Wynika stąd, że kierunki wektorów $k$ i $m$ różnią się o kąt $2 \measuredangle BAC$ .

Przystąpimy teraz do rozwiązania zadania. Ponieważ miary kątów trójkąta $ABC$ są współmierne, więc istnieje taka liczba $\lambda$ i liczby naturalne $r$ , $s$ , $t$ , że $\measuredangle BAC = r\lambda$ , $\measuredangle ABC = s\lambda$ , $\measuredangle ACB = t\lambda$ . Stąd $\lambda (r + s + t) = \pi$ . Oznaczając $n = r + s + t$ otrzymujemy, że $\lambda = \frac{\pi}{n}$ .

Zatem na mocy lematu po parzystej liczbie odbić kierunek ruchu kuli zmienia się o kąt, którego miara jest parzystą wielokrotnością liczby $\lambda = \frac{\pi}{n}$ , a więc jedną z liczb $2\lambda, 4\lambda, 6\lambda, \ldots, 2n\lambda = 2\pi$ . Zatem po parzystej liczbie odbić ruch kuli może się odbywać po jednym z $n$ kierunków. Podobnie po nieparzystej liczbie odbić ruch kuli może się odbywać po jednym z $n$ kierunków. Łączna liczba kierunków, po których porusza się kula, jest więc nie większa od $2n$ .

Uwaga. Analogicznie można udowodnić, że jeżeli w zadaniu trójkąt zastąpić dowolnym wielokątem, którego miary kątów są współmierne, to również liczba kierunków, po jakich może się poruszać kula w takim wielokącie, jest skończona.

XXII OM - III - Zadanie 3

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

III

Ile co najmniej zamków trzeba założyć do skarbca, aby przy pewnym rozkładzie kluczy z 11-osobowej komisji upoważnionej do otwierania skarbca każdych 6 członków mogło go otworzyć, ale żadnych 5 nie mogło? Określić rozdział kluczy między członków komisji przy minimalnej liczbie zamków.

Rozwiązanie

Przypuśćmy, że dla pewnej liczby naturalnej $n$ istnieje taki rozkład kluczy do $n$ zamków wśród $11$ -osobowej komisji, że warunki zadania są spełnione. Oznaczmy przez $A_i$ zbiór zamków, które może otworzyć $i$ -ty członek komisji, gdzie $i = 1, 2, \ldots, 11$ , i oznaczmy przez $A$ zbiór wszystkich zamków. Wtedy z warunków zadania wynika, że

$ (1) \qquad A_{i_1} \cup \ldots \cup A_{i_5} \ne A $

dla dowolnego pięcioelementowego podzbioru $\{ i_1, \ldots, i_5\}$ zbioru $\{1, 2, \ldots, 11\}$ oraz

$ (2) \qquad A_{j_1} \cup \ldots \cup A_{j_6} = A $

dla dowolnego sześcioelementowego podzbioru $\{j_1, \ldots, j_6\}$ zbioru $\{1,2,\ldots, 11\}$ .

Z (1) wynika, że zbiór $A - (A_{i_1} \cup \ldots \cup A_{i_5})$ jest niepusty. Oznaczmy przez $x_{i_1}, \ldots, x_{i_5}$ jeden z jego elementów, tzn. pewien zamek, którego nie może otworzyć grupa członków komisji o numerach $i_1, \ldots, i_5$ . Z (2) wynika, że dla każdego $j \not \in \{i_1, \ldots, i_5 \}$ mamy $x_{i_1 , \ldots, i_5} \in A_j$ .

Przypuśćmy, że $x_{i_1,\ldots,i_5} = x_{k_1, \ldots, k_5}$ dla pewnych podzbiorów $\{i_1, \ldots, i_5\}$ i $\{k_1, \ldots, k_5\}$ . Gdyby podzbiory te były różne, to na przykład $i_t \not \in \{ k_1, \ldots, k_5 \}$ . Wobec tego $x_{k_1, \ldots, k_5} \in A_{i_t}$ ; ale z drugiej strony $x_{1_i,\ldots, i_5} \not \in A_{i_t}$ . Uzyskana sprzeczność dowodzi, że $\{i_1, \ldots,i_5\} = \{ k_1, \ldots, k_5 \}$ .

Inaczej mówiąc różnym zbiorom pięcioelementowym $\{i_1, \ldots, i_5\}$ odpowiadają różne zamki. Zatem liczba zamków jest nie mniejsza od liczby podzbiorów pięcioelementowych zbioru $11$ -elementowego, cżyli $n \geq \binom{11}{15} = 462$ .

Udowodnimy z kolei, że jeżeli do skarbca założymy $\binom{11}{5}$ zamków, to można tak rozdzielić klucze do nich wśród członków $11$ -osobowej komisji, aby były spełnione warunki zadania.

Przyporządkujmy każdemu z $\binom{11}{5}$ zamków w sposób wzajemnie jednoznaczny podzbiór pięcioelementowy zbioru $\{1, 2, \ldots, 11\}$ . Jeżeli zamkowi odpowiada podzbiór $\{i_1, \ldots, i_5\}$ , to klucze do niego otrzymują wszyscy członkowie komisji o numerach różnych od $i_1, \ldots, i_5$ .

Wykażemy, że żadnych pięciu członków komisji nie otworzy pewnego zamka, a więc i skarbca. Istotnie, członkowie komisji o numerach $i_1, \ldots, i_5$ nie mają klucza do zamku, któremu odpowiada podzbiór $\{i_1, \ldots, i_5\}$ .

Wykażemy, że każdych sześciu członków komisji otworzy dowolny zamek, a więc i skarbiec. Jeżeli członkowie komisji mają numery $j_1, \ldots, j_6$ i chcą otworzyć zamek, któremu odpowiada podzbiór $\{i_1, \ldots, i_5\}$ , to jedna z sześciu liczb $j_1, \ldots, j_6$ nie należy do tego pięcioelementowego podzbioru, np. $j_t \not \in \{i_1, \ldots, i_5 \}$ . Wobec tego członek komisji o numerze $j_t$ , ma klucz do zamka odpowiadającego podzbiorowi $\{i_1, \ldots, i_5\}$ .

Zatem najmniejszą liczbą spełniającą warunki zadania jest $\binom{11}{5} = 462$ .

XXII OM - III - Zadanie 4

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

III

Udowodnić, że jeżeli liczby naturalne $x, y, z, n$ spełniają równanie

$ (1) \qquad x^n+y^n = z^n, $

to $\min (x, y) > n$ .

Rozwiązanie

Przypuśćmy, że liczby naturalne $x$ , $y$ , $z$ , $n$ spełniają równanie
(1). Bez zmniejszenia ogólności rozważań możemy przyjąć, że $x \leq y$ . Ponieważ $z^n = x^n + y^n > y^n$ , więc $z>y$ i stąd $z \geq y + 1$ . Wobec tego na mocy wzoru Newtona mamy

$ (2) \qquad z^n \geq (y + 1)^n = y^n + \binom{n}{1} y^{n-1} + \ldots \geq y^n + ny^{n-1}. $

Z (1) i (2) otrzymujemy, że $x^n \geq ny^{n-1}$ . Stąd wobec $x \leq y$ mamy $x^n \geq nx^{n-1}$ , czyli $x \geq n$ . Zatem $\min(x, y) = x \geq n$ .

XXII OM - III - Zadanie 5

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

III

Znaleźć największą liczbą całkowitą $A$ taką, że dla każdej permutacji zbioru liczb naturalnych nie większych od 100 suma pewnych 10 kolejnych wyrazów jest co najmniej równa $A$ .

Rozwiązanie

Suma wszystkich liczb naturalnych nie większych od $100$ jest równa $1 + 2 + \ldots + 100 = \frac{1 +100}{2} 100 = 5050$ . Jeżeli $a_1, a_2, \ldots, a_{100}$ jest pewną permutacją zbioru liczb naturalnych nie większych od $100$ i suma każdych $10$ wyrazów tej permutacji jest mniejsza od pewnej liczby $B$ , to w szczególności

$ \begin{array}{cc} a_1 + a_2 + \ldots + a_{10} < B,\\ a_{11} + a_{12} + \ldots + a_{20} < B,\\ \ldots\\ a_{91} + a_{92} + \ldots + a_{100} < B. \end{array} $

Dodając te nierówności stronami otrzymujemy, że $a_1 + a_2 + \ldots + a_{100} = 1 + 2 + \ldots + 100 < 10B$ , czyli $505 < B$ .

Zatem określona w zadaniu liczba $A$ spełnia nierówność.

$ (1) \qquad A \geq 505. $

Z drugiej strony rozważmy następującą permutację $a_1, a_2,\ldots, a_{100}$ zbioru liczb naturalnych nie większych od $100$

$ 100, 1, 99, 2, 98, 3, 97,4, \ldots, 51, 50. $

Permutację tę można określić wzorami:

$ a_{2n+1} = 100 - n\ \textrm{dla}\ 0 \leq n \leq 49, $

$ a_{2n} = n\ \textrm{dla}\ 1 \leq n \leq 50. $

Udowodnimy, że suma dowolnych kolejnych $10$ wyrazów tej permutacji jest nie większa od $505$ .

Istotnie, jeżeli pierwszy z rozważanych $10$ wyrazów ma numer parzysty $2k$ , to

$ \begin{split} s &= a_{2k} + a_{2k+1} + \ldots + a_{2k+9} =\\ &= (a_{2k} + a_{2k+2} +\ldots+ a_{2k+8}) + (a_{2k+1} + a_{2k+3} + \ldots + a_{2k+9}) =\\ &= [k + (k + 1) + \ldots + (k + 4)] + \{(100 - k) +\\ &\quad+ [100 - (k + 1)] + \ldots + [100 - (k + 4)]\} = 500. \end{split} $

Jeżeli zaś pierwszy z rozważanych wyrazów ma numer nieparzysty $2k + 1$ , to

$ \begin{split} s &= a_{2k+1} + a_{2k+2} + \ldots + a_{2k+10} =\\ &= (a_{2k} + a_{2k+1} +\ldots+ a_{2k+9}) + a_{2k+10} - a_{2k} =\\ &=s + (k + 5) - k = s + 5 = 505. \end{split} $

Tak więc suma dowolnych $10$ kolejnych wyrazów tej permutacji jest nie większa od $505$ . Wobec tego liczba $A$ określona w zadaniu spełnia nierówność

$ (2) \qquad A \leq 505. $

Z (1) i (2) wynika, że $A = 505$ .

Uwaga 1. Zadanie można uogólnić następująco: Znaleźć największą liczbę całkowitą $A$ taką, że dla każdej permutacji zbioru liczb naturalnych nie większych od liczby parzystej $n = 2t$ suma pewnych $m = 2r$ (gdzie $r$ jest dzielnikiem $t$ ) kolejnych wyrazów jest co najmniej równa $A$ .

Dokonując drobnych zmian w podanym wyżej rozwiązaniu polegających na zamianie liczby $100$ przez $2t$ , a liczby $10$ przez $2r$ , można dowieść, że $A = \frac{1}{2} m(n + 1)$ .

Uwaga 2. W przypadku gdy $m \leq n$ są dowolnymi liczbami naturalnymi na ogół nie jest prawdą, że każda permutacją zbioru liczb naturalnych nie większych od $n$ zawiera $m$ kolejnych wyrazów o sumie nie mniejszej od $\frac{1}{2} m(n + 1)$ . Na przykład przy $n = 6$ , $m = 4$ permutacja $6, 4, 1, 2, 3, 5$ nie zawiera czterech kolejnych wyrazów o sumie nie mniejszej od $14$ .

XXII OM - III - Zadanie 6

Zawody matematyczne:

XXII OM, 1970-1971

Etap:

III

Dany jest czworościan foremny o krawędzi długości 1. Udowodnić, że:
1) Na powierzchni $S$ czworościanu istnieją takie cztery punkty, że odległość każdego punktu powierzchni $S$ od jednego z tych czterech punktów nie przekracza $\frac{1}{2}$ .
2) Na powierzchni $S$ nie istnieją trzy punkty o podobnej własności.
Przez odległość punktów należących do $S$ rozumiemy kres dolny długości łamanych zawartych w $S$ łączących te punkty.

Rozwiązanie

1) Zauważmy najpierw, że w trójkącie równobocznym o boku długości $1$ środki dwóch boków mają tę własność, że każdy punkt należący do trójkąta jest odległy od jednego z nich nie więcej niż o $\frac{1}{2}$ . Istotnie, zakreślając koła o środkach w tych punktach (rys. 15) i promieniach długości $\frac{1}{2}$ stwierdzamy, że trójkąt jest zawarty w sumie tych kół.

W czworościanie foremnym $ABCS$ obierzmy punkty $P$ , $Q$ , $R$ , $T$ będące środkami krawędzi $\overline{AS}$ , $\overline{BS}$ , $\overline{AC}$ , $\overline{BC}$ (rys. 16). W ten sposób do każdej ze ścian czworościanu należą dwa z punktów $P$ , $Q$ , $R$ , $T$ i są one środkami dwóch krawędzi tej ściany. Z uwagi zrobionej na początku wynika więc, że każdy punkt dowolnej ściany czworościanu jest odległy od jednego z punktów $P$ , $Q$ , $R$ , $T$ nie więcej niż o $\frac{1}{2}$ .

2) Przypuśćmy, że istnieją trzy punkty $P$ , $Q$ , $R$ należące do powierzchni czworościanu takie, że dowolny punkt powierzchni czworościanu jest odległy od jednego z nich nie więcej niż o $\frac{1}{2}$ . Ponieważ czworościan ma cztery wierzchołki, więc co najmniej dwa wierzchołki są odległe od tego samego punktu z $P$ , $Q$ , $R$ nie więcej niż o $\frac{1}{2}$ . Niech na przykład punkty $A$ i $S$ będą odległe od $P$ nie więcej niż o $\frac{1}{2}$ . Ponieważ odległość punktów $A$ i $S$ równa jest $1$ , więc wynika stąd, że punkt $P$ jest środkiem krawędzi $\overline{AS}$ .

Zauważmy, że każdy punkt należący do wysokości $\overline{SD}$ ściany $SBC$ (za wyjątkiem punktu $S$ ) jest odległy od punktu $P$ więcej niż o $\frac{1}{2}$ . Istotnie, rozważmy rozwinięcie powierzchni czworościanu foremnego $ABCS$ (rys. 17). Zakreskowany obszar składa się z punktów odległych od $P$ nie więcej niż o $\frac{1}{2}$ . Wysokość $\overline{SD}$ ma tylko punkt $S$ wspólny z tym obszarem.

Gdyby więc punkt $S$ był odległy więcej niż o $\frac{1}{2}$ od każdego z punktów $Q$ i $R$ , to i każdy punkt pewnego otoczenia punktu $S$ miałby podobną własność. Wobec tego punkty odcinka $\overline{SD}$ dostatecznie bliskie punktu $S$ byłyby odległe od każdego z punktów $P$ , $Q$ , $R$ więcej niż o $\frac{1}{2}$ . Jest to jednak sprzeczne z naszym pierwotnym przypuszczeniem. Zatem punkt $S$ jest odległy od jednego z punktów $Q$ i $R$ nie więcej niż o $\frac{1}{2}$ i podobnie stwierdzamy, że punkt $A$ jest odległy od jednego z punktów $Q$ i $R$ nie więcej niż o $\frac{1}{2}$ . Ponieważ wierzchołki $B$ i $C$ są odległe od punktu $P$ więcej niż o $\frac{1}{2}$ , więc również każdy z punktów $B$ i $C$ jest odległy od jednego z punktów $Q$ i $R$ nie więcej niż o $\frac{1}{2}$ . Wynika stąd, że co najmniej dwa z punktów $A$ , $B$ , $C$ , $S$ są odległe od jednego z punktów $Q$ i $R$ nie więcej niż o $\frac{1}{2}$ .

Niech na przykład punkty $B$ i $S$ będą odległe od $Q$ nie więcej niż o $\frac{1}{2}$ (pozostałe przypadki rozpatruje się podobnie). Wtedy punkt $Q$ jest środkiem krawędzi $\overline{BS}$ , a punkt $R$ - środkiem krawędzi $\overline{AC}$ .

Wówczas jednak rozumując podobnie, jak poprzednio, stwierdzamy, że punkty należące do wysokości $\overline{BE}$ ściany $ABC$ położone dostatecznie blisko punktu $B$ są odległe od każdego z punktów $P$ , $Q$ , $R$ więcej niż o $\frac{1}{2}$ . Uzyskana sprzeczność dowodzi, że nie istnieją trzy punkty $P$ , $Q$ , $R$ należące do powierzchni czworościanu $ABCS$ takie, że każdy punkt powierzchni czworościanu jest odległy od jednego z nich nie więcej niż o $\frac{1}{2}$ .