XXXV OM - III etap

III etap XXXV Olimpiady Matematycznej

XXXV OM - III - Zadanie 1

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

III

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

Rozwiązanie

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

Wobec tego mają miejsce zawierania

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

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

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

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

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

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

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

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

XXXV OM - III - Zadanie 2

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

III

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

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

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

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

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

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

Rozwiązanie

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

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

XXXV OM - III - Zadanie 3

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

III

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

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

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

Rozwiązanie

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

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

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

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

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

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

Wobec tego

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

XXXV OM - III - Zadanie 4

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

III

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

Rozwiązanie

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

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

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

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

XXXV OM - III - Zadanie 5

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

III

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

Rozwiązanie

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

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

XXXV OM - III - Zadanie 6

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

III

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

Rozwiązanie

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

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