XXI OM - III etap

III etap XXI Olimpiady Matematycznej

XXI OM - III -Zadanie 1

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

III

Średnica $\overline{AB}$ dzieli okrąg na dwa półokręgi. Na jednym półokręgu obrano n punktów $P_1 P_2, \ldots, P_n$ tak, że $P_1$ leży między $A$ i $P_2$ , $P_2$ leży między $P_1$ i $P_3$ , $\ldots$ , $P_n$ leży między $P_{n-1}$ i $B$ . Jak należy wybrać punkt $C$ na drugim półokręgu, aby suma pól trójkątów $CP_1P_2, CP_2P_3, CP_3P_4, \ldots, CP_{n-1}P_n$ była największa?

Rozwiązanie

Zauważmy, że suma pól trójkątów $CP_1P_2, CP_2P_3, CP_3P_4, \ldots, CP_{n-1}P_n$ jest równa sumie pól wielokąta $P_1P_2 \ldots P_n$ oraz trójkąta $CP_1P_n$ (rys. 13). Pierwsze pole nie zależy od wyboru punktu $C$ . Drugie pole będzie maksymalne, gdy odległość punktu $C$ od prostej $P_1P_n$ będzie możliwie duża. Punkt na okręgu najbardziej oddalony od danej cięciwy leży na symetralnej tej cięciwy. Zatem jako $C$ należy wziąć punkt przecięcia symetralnej odcinka $\overline{P_1P_n}$ z drugim półokręgiem.

XXI OM - III -Zadanie 2

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

III

Dane są trzy ciągi nieskończone, których elementami są liczby naturalne:

$ \begin{split} a_1, a_2, \ldots, \\ b_1, b_2, \ldots, \\ c_1, c_2, \ldots, \end{split} $

przy czym jeżeli $i \neq j$ , to $a_i \neq a_j$ , $b_i \neq b_j$ , $c_i \neq c_j$ .
Udowodnić, że istnieje para wskaźników $k, l$ taka, że $k < l$ i $a_k < a_l$ , $b_k < b_l$ , $c_k < c_l$ .

Rozwiązanie

Ponieważ wyrazy ciągu $a_1, a_2, \ldots$ są różnymi liczbami naturalnymi, a zbiór liczb naturalnych mniejszych od $a_1$ jest skończony, więc wszystkie dostatecznie dalekie wyrazy tego ciągu są większe od $a_1$ , tzn.

$ (1) \qquad a_n > a_1 \textrm{ dla } n > n_1. $

Podobnie stwierdzamy, że

$ (2) \qquad b_n > b_1 \textrm{ dla } n > n_2 \textrm{ i} $

$ (3) \qquad c_n > c_1 \textrm{ dla } n > n_3. $

Jeśli więc $n$ jest liczbą naturalną większą od każdej z liczb $n_1, n_2, n_3$ , to nierówności (1), (2), (3) będą prawdziwe dla tej liczby naturalnej.

XXI OM - III -Zadanie 3

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

III

Udowodnić, że $n > 1$ jest liczbą pierwszą wtedy i tylko wtedy, gdy dla każdego naturalnego $k$ , takiego że $1 \leq k \leq n - 1$ , współczynnik dwumianowy

$ \binom{n}{k} = \frac{n!}{k!(n-k)!} $

dzieli się przez $n$ .

Rozwiązanie

Jeśli $n$ jest liczbą pierwszą, to dla $1 \leq k \leq n - 1$ liczby $k$ i $n - k$ są mniejsze od $n$ i wobec tego liczby $k!$ i $(n - k)!$ nie są podzielne przez $n$ .

Ze wzoru $\displaystyle \binom{n}{k} = \binom{n!}{k!(n-k)!}$ otrzymujemy

$ (1) \qquad n! = \binom{n}{k} k!(n-k)!. $

Ponieważ lewa strona (1) jest podzielna przez liczbę pierwszą $n$ , a $k!$ i $(n - k)!$ nie są podzielne przez $n$ , więc liczba $\binom{n}{k}$ jest podzielna przez $n$ .

Przypuśćmy z kolei, że $n$ jest liczbą złożoną i oznaczmy przez $p$ pewien dzielnik pierwszy tej liczby. Gdyby liczba $\binom{n}{p}$ była podzielna przez $n$ , to dla pewnej liczby naturalnej $s$ mielibyśmy $\binom{n}{p}= ns$ . Wtedy ze wzoru

$ \binom{n}{p} = \frac{n(n-1)(n-2) \ldots (n -(p-1))}{p!} $

otrzymalibyśmy $s =\frac{(n-1)(n-2) \ldots (n -(p-1))}{p!}$ , czyli

$ (1) \qquad sp! = (n- 1)(n-2)\ldots(n- (p- 1)). $

Ponieważ $p \mid n$ , więc liczby $n - 1, n - 2, \ldots, n - (p - 1)$ nie są podzielne przez $p$ . Zatem prawa strona równości (1) nie jest podzielna przez $p$ , a lewa strona jest oczywiście podzielna przez $p$ .

Otrzymana sprzeczność dowodzi, że liczba $\binom{n}{p}$ nie jest podzielna przez $n$ .

XXI OM - III -Zadanie 4

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

III

Na płaszczyźnie danych jest $n$ prostokątów o bokach odpowiednio równoległych do dwóch danych prostych prostopadłych. Udowodnić, że jeżeli każde dwa z tych prostokątów mają co najmniej jeden punkt wspólny, to istnieje punkt należący do wszystkich prostokątów.

Rozwiązanie

Obierzmy dane proste za osie układu współrzędnych (rys. 14). Wtedy wierzchołki $i$ -tego prostokąta $P_i$ będą miały współrzędne $(x_i,y_i)$ , $(x_i,y'_i)$ , $(x'_i,y'_i)$ , $(x'_i,y_i)$ , gdzie $x_i < x'_i$ , $y_i <y'_i$ . Punkt $(x, y)$ należy więc do prostokąta $P_i$ wtedy i tylko wtedy, gdy $x_i \leq x \leq x'_i$ oraz $y_i \leq y \leq y'_i$ .

Z założenia każde dwa prostokąty $P_i$ i $P_j$ mają punkt wspólny. Zatem istnieją liczby $x$ , $y$ takie, że

$ x_i \leq x \leq x'_i \textrm{ i } x_j \leq x \leq x'_j $

oraz

$ y_i \leq y \leq y'_i \textrm{ i } y_j \leq y \leq y'_j. $

Stąd

$ (1) \qquad x_i \leq x'_j \textrm{ oraz } y_i \leq y'_j \textrm{ dla } i, j = 1,2, \ldots, n. $

Oznaczmy przez $a$ największą z liczb $x_i$ , a przez $b$ - największą z liczb $y_i$ . Wtedy z określenia

$ (2) \qquad x_j \leq a \textrm{ oraz } y_j \leq b \textrm{ dla } j = 1,2, \ldots, n, $

$ (3) \qquad a \leq x'_j \textrm{ oraz } b \leq y'_j \textrm{ dla } j = 1,2, \ldots, n. $

Nierówności (2) i (3) dowodzą, że punkt $(a, b)$ należy do każdego z prostokątów $P_j$ .

Uwaga 1. W przytoczonym rozwiązaniu nie korzystaliśmy w sposób istotny z tego, że liczba danych prostokątów jest skończona. Gdyby dana była pewna nieskończona rodzina prostokątów o analogicznych własnościach, to rozwiązanie przebiegałoby podobnie, z tym, że liczby $a$ i $b$ należałoby określać jako kresy górne zbioru liczb $x_j$ i odpowiednio $y_j$ .

Uwaga 2. Podobne twierdzenie jest prawdziwe, jeśli zamiast prostokątów rozpatrywać dowolne figury wypukłe. Mianowicie zachodzi następujące

Twierdzenie Helly'ego. Jeśli na płaszczyźnie dana jest pewna niepusta rodzina zbiorów wypukłych taka, że każde trzy zbiory tej rodziny mają punkt wspólny, to istnieje punkt należący do wszystkich zbiorów tej rodziny.

XXI OM - III -Zadanie 5

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

III

Na ile sposobów zbiór złożony z dwunastu elementów można podzielić na sześć rozłączonych zbiorów dwuelementowych?

Rozwiązanie

Oznaczmy jeden z elementów zbioru $12$ -elementowego przez $a_1$ . Podzbiór dwuelementowy zawierający element $a_1$ można utworzyć na $11$ sposobów. Mianowicie należy do $a_1$ dołączyć jeden z pozostałych jedenastu elementów.

Oznaczmy przez $a_2$ jeden z elementów zbioru $10$ -elementowego, który pozostał po utworzeniu zbioru dwuelementowego zawierającego element $a_1$ . Podzbiór dwuelementowy zawierający element $a_2$ można teraz utworzyć na $9$ sposobów. Mianowicie należy do $a_2$ dołączyć jeden z pozostałych dziewięciu elementów.

Postępując dalej analogicznie stwierdzamy, że szukana liczba równa jest $11 \cdot 9 \cdot 7 \cdot 5 \cdot 3$ .

XXI OM - III -Zadanie 6

Zawody matematyczne:

XXI OM, 1969-1970

Etap:

III

Znaleźć najmniejszą liczbę rzeczywistą $A$ taką, że dla każdego trójmianu kwadratowego $f(x)$ spełniającego warunek

$ (1) \qquad |f(x)| \leq 1 \quad \text{dla}\quad 0 \leq x \leq 1 $

zachodzi nierówność $f'(0) \leq A$ .

Rozwiązanie

Niech trójmian kwadratowy $f(x) = ax^2 + bx + c$ spełnia warunek (1). Wtedy w szczególności $|f(0)| \leq 1$ , $| f \left( \frac{1}{2} \right)| \leq 1$ i $|f(1)| \leq 1$ .

Ponieważ

$ f(0) = c,\ f(\frac{1}{2}) = \frac{a}{4} + \frac{b}{2} + c,\ f(1) = a+b+c $

oraz

$ f'(0) = b = 4 (\frac{a}{4} + \frac{b}{2} + c) - (a+b+c) - 3c, $

więc

$ | f'(0)| \leq 4 + \left( \frac{1}{2} \right)| + |f(1)| + 3|f(0)| \leq 4 + 1 + 3 = 8. $

Zatem $A \leq 8$ .

Z drugiej strony trójmian $f(x) = -8x^2 + 8x - 1$ spełnia warunek (1), co łatwo odczytać z jego wykresu (rys. 15). Ponadto $f'(0) = 8$ . Zatem $A \geq 8$ .

Poszukiwana liczba $A$ jest więc równa $8$ .