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}$ .