XXV OM - III etap

III etap XXV Olimpiady Matematycznej

XXV OM - III - Zadanie 1

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

III

W czworościanie $ABCD$ krawędź $\overline{AB}$ jest prostopadła do krawędzi $\overline{CD}$ i $\measuredangle ACB = \measuredangle ADB$ . Udowodnić, że płaszczyzna wyznaczona przez krawędź $\overline{AB}$ i środek krawędzi $\overline{CD}$ jest prostopadła do krawędzi $\overline{CD}$ .

Rozwiązanie

Udowodnimy najpierw
Lemat. Jeżeli proste $AB$ i $PQ$ przecinają się pod kątem prostym w punkcie $P$ , to liczba punktów półprostej $PQ^\to$ , z których widać odcinek $\overline{AB}$ pod kątem $\alpha$ , jest równa $0$ , $1$ lub $2$ .

Dowód. Jak wiadomo, zbiór punktów zawartych w półpłaszczyźnie o krawędzi $AB$ i zawierającej punkt $Q$ , z których widać odcinek $AB$ pod kątem $\alpha$ , jest łukiem pewnego okręgu. Ten łuk ma z półprostą $PQ^\to$ $0$ , $1$ lub $2$ punkty wspólne w zależności od położenia odcinka $AB$ względem punktu $P$ i od wielkości kąta $\alpha$ (rys. 19).

Wniosek. Niech prosta $AB$ będzie prostopadła do płaszczyzny $\pi$ . Zbiór punktów płaszczyzny $\pi$ , z których widać odcinek $\overline{AB}$ pod kątem
$\alpha(0 < \alpha < \pi)$ , jest pusty, jest okręgiem lub sumą dwóch okręgów współśrodkowych.

Dowód. Niech $P$ będzie punktem przecięcia prostej $AB$ z płaszczyzną $\pi$ , a $Q$ - dowolnym punktem płaszczyzny $\pi$ różnym od $P$ . Na mocy lematu półprosta $PQ^\to$ zawiera co najwyżej dwa punkty, z których widać odcinek $\overline{AB}$ pod kątem $\alpha$ . Przy obrocie dokoła prostej $AB$ punkty te utworzą co najwyżej dwa okręgi współśrodkowe i z każdego punktu tych okręgów widać odcinek $\overline{AB}$ pod kątem $\alpha$ . Na mocy lematu z każdego punktu płaszczyzny $\pi$ nie należącego do tych okręgów widać odcinek $\overline{AB}$ pod kątem różnym od $\alpha$ .

Przechodzimy do rozwiązania zadania. Niech $\pi$ będzie płaszczyzną prostopadłą do $AB$ i zawierającą odcinek $\overline{CD}$ i niech $P$ będzie punktem przecięcia prostej $AB$ z płaszczyzn $\pi$ . Na mocy warunków zadania z punktów $C$ i $D$ widać odcinek $\overline{AB}$ pod tym samym kątem. Z wniosku z lematu wynika więc, że albo

1) punkty $C$ i $D$ należą do jednego okręgu o środku w punkcie $P$ , albo,

2) punkty $C$ i $D$ należą do różnych okręgów o środku w punkcie $P$ .

W pierwszym przypadku symetralna odcinka $\overline{CD}$ zawiera punkt $P$
i wobec tego płaszczyzna wyznaczona przez krawędź $\overline{AB}$ i środek krawędzi $\overline{CD}$ jest prostopadła do krawędzi $\overline{CD}$ . W drugim przypadku symetralna odcinka $\overline{CD}$ nie zawiera punktu $P$ . Gdyby bowiem go zawierała, to punkt $P$ byłby równo odległy od punktów $C$ i $D$ . Punkty te należałyby więc do jednego okręgu o środku w punkcie $P$ , co nie ma miejsca. Wobec tego płaszczyzna wyznaczona przez krawędź $\overline{AB}$ i środek krawędzi $\overline{CD}$ nie zawiera symetralnej odcinka $\overline{CD}$ , a więc nie jest do niego prostopadła.

Teza zadania w drugim przypadku nie jest więc prawdziwa. Przypadek pierwszy ma miejsce na przykład wtedy, gdy punkt $P$ należy do odcinka $\overline{AB}$ , a więc na przykład, gdy kąt $\measuredangle ACB$ jest rozwarty.

XXV OM - III - Zadanie 2

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

III

Łososie płynąc w górę rzeki muszą pokonać dwa wodospady. Prawdopodobieństwo, że łosoś pokona pierwszy wodospad w danej próbie, wynosi $p > 0$ , a prawdopodobieństwo pokonania drugiego wodospadu w danej próbie wynosi $q > 0$ . Zakładamy, że kolejne próby forsowania wodospadów są niezależne. Obliczyć prawdopodobieństwo zdarzenia, ze łosoś nie przebędzie pierwszego wodospadu w $n$ próbach pod warunkiem, że w $n$ próbach nie pokona obu wodospadów.

Rozwiązanie

Niech $A_n$ będzie zdarzeniem polegającym na tym, że łosoś nie pokona pierwszego wodospadu w $n$ próbach, a $B_n$ - zdarzeniem, że łosoś nie pokona obu wodospadów w $n$ próbach. Ponieważ prawdopodobieństwo tego, że łosoś nie pokona pierwszego wodospadu w jednej próbie równe jest $1 - p$ , a próby są niezależne, więc

$ (1) \qquad p(A_n) = (1-p)^n. $

Zdarzenie $B_n$ zajdzie wtedy, gdy albo łosoś nie pokona w $n$ próbach pierwszego wodospadu, albo pokona w $k$ -tej próbie $(1 \leq k \leq n)$ pierwszy wodospad i nie pokona w pozostałych $n-k$ próbach drugiego wodospadu. Zatem

$ (2) \qquad p(B_n) = (1 -p)^n + \sum_{k=1}^n (1 -p)^{k-1} p(1 - q)^{n-k}. $

Jeżeli $p = q$ , to wzór (2) przybiera postać

$ (3) \qquad p(B_n) = (1 -p)^n + \sum_{k=1}^n (1 -p)^{n-1} p = (1-p)^n + np(l -p)^{n-1}. $

Jeżeli $q= 1$ , to

$ (4) \qquad p(B_n) = (1 - p)^n + (1 - p)^{n-1}p = (1 - p)^{n-1}. $

W tym przypadku bowiem łosoś pokonałby drugi wodospad już w pierwszej próbie. Zatem zdarzenie $B_n$ zajdzie wtedy, gdy łosoś nie pokona pierwszego wodospadu w $n$ próbach lub pokona go dopiero w $n$ -tej próbie.

Wzór (4) wynika zresztą ze wzoru (2), jeżeli przyjmiemy, że $0^0 = 1$ .

Wreszcie, jeżeli $p \ne q$ i $q < 1$ , to korzystając ze wzoru na sumę wyrazów ciągu geometrycznego przekształcamy (2) jak następuje:

$ \begin{split} p(B_n) & = (1-p)^n + p(1-q)^{n-1} \frac{1- \left( \frac{1-p}{1-q} \right)^n}{1-\frac{1-p}{1-q}} = (1-p)^n + \\ & + (1-q)^{n} \frac{p}{p-q} \left[ 1- \left( \frac{1-p}{1-q} \right)^n \right] = (1-p)^n + \frac{p}{p-q} ((1-q)^n - (1-p)^n)=\\ & = \frac{p(1-q)^n q(1-p)^n}{p-q}. \end{split} $

Mamy więc w tym przypadku

$ (5) \qquad p (B_n) = \frac{p(1-q)^n - q(1-p)^n}{p-q}. $

Jeżeli zajdzie zdarzenie $A_n$ , to tym bardziej zajdzie zdarzenie $B_n$ . Wobec tego $A_n \cap B_n = A_n$ . Ze wzoru na prawdopodobieństwo warunkowe otrzymujemy więc

$ (6) \qquad P(A_n \mid B_n) = \frac{A_n \cap B_n)}{p(B_n)} = \frac{P(A_n)}{P(B_n)}. $

Jeżeli $n = 1$ , to z warunków zadania wynika, że $p(A_n) = 1 - p$ oraz $p(B_n) = 1$ . Zatem z (6) otrzymujemy, że $p(A_n \mid B_n)= 1 -p$ . W dalszym ciągu będziemy więc zakładali, że $n \geq 2$ .

Zauważmy, że jeżeli $p \ne q$ , to $p(B_n) \ne 0$ . Istotnie, gdyby $p(B_n) = 0$ , to ze wzoru (5) otrzymalibyśmy $p(1 - q)^n = q(1 -p)^n$ . Stąd

$ (7) \qquad \frac{p}{q} = \left( \frac{1-p}{1-q} \right)^n. $

Jeżeli na przykład $p < q$ , to $1 - p > 1 - q$ i równość (7) nie może mieć miejsca. Podobnie dowodzimy, że (7) nie zachodzi, gdy $p> q$ .

Jeżeli $p = q$ i p $(B_n) = 0$ , to ze wzoru (3) wynika, ze $p = 1$ . Zatem w przypadku, gdy $p = q = 1$ (i tylko w tym przypadku) prawdopodobieństwo warunkowe $p(A_n \mid B_n)$ nie istnieje. Obliczamy je w pozostałych przypadkach.

Jeżeli $p = q < 1$ , to z (1), (3) i (6) otrzymujemy

$ (8) \qquad p(A_n \mid B_n) = \frac{1 - p}{1-p+np} = \frac{1-p}{1+(n-1)p}. $

Jeżeli $p < q = 1$ , to z (1), (4-) i (6) otrzymujemy

$ (9) \qquad p(A_n \mid B_n) = 1-p. $

Jeżeli $p \ne q < 1$ , to z (1), (5) i (6) otrzymujemy

$ (10) \qquad p(A_n \mid B_n) =\frac{(1-p)^n(p-q)}{p(1-q)^n - q(1-p)^n}= \frac{(p-q) \left( \frac{1-p}{1-q} \right)^n}{p-g} \left( \frac{1-p}{1-q} \right)^n. $

Uwaga.

Zbadamy w każdym z przypadków liczbę $g= \lim_{n \to \infty} p(A_n \mid B_n)$ .

Jeżeli $p = q < 1$ , to ze wzoru (8) wynika, że $g = 0$ .

Jeżeli $p < q = 1$ , to ze wzoru (9) wynika, że $g = 1 - p = 1 -\displaystyle \frac{p}{1}$ .

Jeżeli $p < q < 1$ , to $1 - p > 1 - q$ i $\displaystyle \lim_{n \to \infty} \left( \frac{1-p}{1-q} \right)^n = \infty$ . Zatem z (10) wynika, że $\displaystyle g = \frac{p-q}{-q} = 1- \frac{p}{q}$ .

Jeżeli $q < p \leq 1$ , to $1 - p < l - q$ i $\displaystyle \lim_{n \to \infty} \left( \frac{1-p}{1-q} \right)^n = 0$ . Wobec tego z (10) otrzymujemy, że $g = 0$ .

Zawsze więc $g = \max \left(0, 1 - \frac{p}{q} \right)$ .

XXV OM - III - Zadanie 3

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

III

Niech $r$ będzie liczbą naturalną. Dowieść, że trójmian $x^2 - rx - 1$ nie jest dzielnikiem żadnego wielomianu $p(x) \neq 0$ o współczynnikach całkowitych, mniejszych co do wartości bezwzględnej od $r$ .

Rozwiązanie

\spos{1} Przypuśćmy, że wielomian

$ p(x) = a_0 + a_1x + \ldots + a_nx^n $

gdzie $a_n \ne 0$ , ma współczynniki całkowite, co do wartości bezwzględnej mniejsze od $r$ i jest podzielny przez trójmian $f(x) = x^2 - rx - 1$ . Mamy więc

$ (1) \qquad p = f \cdot h, $

gdzie wielomian $h(x) = b_0 + b_1x + \ldots + b_{n-2}x^{n-2}$ ma współczynniki całkowite, co wynika z algorytmu dzielenia wielomianów.

Porównując odpowiednie współczynniki wielomianów po obu stronach równości (1) otrzymujemy

$(2.0) \qquad a_0 = -b_0,$

$(2.1) \qquad a_1 = -b_1-rb_0,$

$(2.2) \qquad a_2 = -b_2 - rb_1 + b_0,$

$\vdots$

$(2.k) \qquad a_k = -b_k - rb_{k-1} + b_{k-2} \ \textrm{dla} \ k = 2, 3, \ldots,n- 2,$

$\vdots$

$(2.n-2) \qquad a_{n-2} = - b_{n-2} - rb_{n-3} + b_{n-4},$

$(2.n-1) \qquad a_{n-1} = - rb_{n-2} + b_{n-3},$

$(2.n) \qquad a_n = b_{n-2}$

Z równości (2.n) wynika, że $b_{n-2} \ne 0$ . Następnie z (2.n - 1) wynika, że $b_{n-3} \ne 0$ i liczby $b_{n-2}$ i $b_{n-3}$ mają ten sam znak. W przeciwnym razie bowiem mielibyśmy $|a_{n-1}| = |-rb_{n-2} + b_{n-3}| = |-rb_{n-2}| + |b_{n-3}| \geq r |b_{n-2}| \geq r$ , co przeczy założeniu, że $|a_{n-1} < r$ . Analogicznie z (2.n - 2) otrzymujemy, że $b_{n-4} \ne 0$ i liczby $b_{n-3}$ i $b_{n-4}$ mają ten sam znak. W przeciwnym razie bowiem mielibyśmy $|a_{n-2}| = |-b_{n-2} - rb_{n-3} + b_{n-4}| = |-b_{n-2}| + |-rb_{n-3}| + |b_{n-4}| \geq r |b_{n-3}| \geq r|$ , co przeczy założeniu, że $|a_{n-2}| < r$ .

Ogólnie, jeżeli dla pewnej liczby $k \in \{2, 3, \ldots, n - 2\}$ liczby $b_k$ i $b_{k-1}$ mają ten sam znak, to $b_{k-2} \ne 0$ i liczby $b_{k-1}$ i $b_{k-2}$ mają ten sam znak. W przeciwnym razie bowiem z równości (2.k) otrzymalibyśmy, że $|a_k| = |-b_k| + |-rb_{k-1}|+ |b_{k-2}| \geq r$ , co przeczy założeniu.

Na mocy zasady indukcji wynika stąd, że liczby $b_{n-2}, b_{n-3}, \ldots, b_1, b_0$ są różne od zera i mają jednakowe znaki. Wobec tego z równości (2.1) otrzymujemy $|a_1| = |-b_1 -rb_0| = |b_1| + |rb_0| \geq r$ , co przeczy założeniu.

Uzyskana sprzeczność dowodzi, że taki wielomian $p$ nie istnieje.

Uwaga 1. W powyższym rozwiązaniu nie korzystaliśmy w sposób istotny z założenia, że wielomian $p$ ma współczynniki całkowite. Wystarczyłoby zakładać, że $|p_n| \geq 1$ oraz $|p_i| \leq r - 1$ dla $r = 0, 1,\ldots, n-1$ .

Uwaga 2. Niech $H(f)$ będzie największą wartością bezwzględną współczynników wielomianu $f$ . Dla wielomianów o współczynnikach całkowitych na ogół nie jest prawdą, że jeżeli $f \mid g$ , to $H(f) \leq H(g)$ . Na przykład

$ (1 - x + x^2)(1 + 2x + x^2) = 1 + x + x^3 + x^4. $

XXV OM - III - Zadanie 4

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

III

Dowieść, że dla każdej liczby naturalnej $n$ i ciągu liczb rzeczywistych $a_1, a_2, \ldots, a_n$ istnieje liczba naturalna $k \leq n$ taka, że

$ \left| \sum_{i=1}^k a_i - \sum_{i=k+1}^n a_i \right| \leq \max_{1\leq i \leq n} |a_i| $

Rozwiązanie

Udowodnimy najpierw
Lemat. Jeżeli $\varepsilon \geq 0$ i liczby rzeczywiste $s_1, s_2, \ldots, s_n$ spełniają warunki

$ (1) \qquad |s_1| \leq \varepsilon, | s_{i+1} - s_i | \leq \varepsilon \ \textrm{dla}\ i = 1, 2, \ldots, n - 1,\ \textrm{to istnieje taka liczba naturalna}\ k \leq n,\ \textrm{że} $

$ (2) \qquad \left| s_k - \frac{1}{2}s_n \right| \leq \frac{1}{2}\varepsilon. $

Dowód. Jeżeli $\varepsilon = 0$ , to z (1) wynika, że $s_1 = s_2 = \ldots = s_n = 0$ , i teza lematu oczywiście zachodzi. Załóżmy więc, że $\varepsilon > 0$ .

Niech $a$ będzie najmniejszą, a $b$ - największą z liczb $s_1, s_2, \ldots, s_n$ . Liczby $s_1, s_2, \ldots, s_n$ dzielą więc przedział $\langle a;\ b \rangle$ na odcinki o długości nie przekraczającej $\varepsilon$ . Każda liczba tego przedziału jest więc odległa od jednej z liczb $s_1, s_2, \ldots, s_n$ nie więcej niż o $\displaystyle \frac{1}{2} \varepsilon$ . W szczególności, jeżeli $\displaystyle \frac{1}{2} s_n \in \langle a;\ b \rangle$ , to spełniony jest warunek (2). Załóżmy więc, że $\displaystyle \frac{1}{2} s_n \ne \langle a;\ b \rangle$ .

Z określenia liczb $a$ i $b$ wynika, że $s_n \in \langle a ;\ b \rangle$ . Jeżeli $0 \in \langle a ;\ b \rangle$ , to otrzymujemy, że $\displaystyle \frac{1}{2} s_n \in \langle a ;\ b \rangle$ , co przeczy przyjętemu założeniu.

Niech więc $0 \not \in \langle a ;\ b \rangle$ . Wtedy liczby $s_1, s_2, \ldots, s_n$ mają jednakowy znak. Ponieważ zmiana znaku wszystkich tych liczb nie zmienia warunków lematu, więc możemy założyć, że liczby $s_1, s_2, \ldots, s_n$ są dodatnie. Mamy więc

$ (3) \qquad 0 < a \leq s_n \leq b $

oraz

$ (4) \qquad 0 < a \leq s_1 \leq \varepsilon. $

Ponieważ $\displaystyle \frac{1}{2} s_n \not \in \langle a ;\ b \rangle$ , więc z (3) wynika, że $\displaystyle 0 < \frac{1}{2}a \leq \frac{1}{2} s_n < a$ . Zatem na mocy (4) mamy $\displaystyle | a - \frac{1}{2} s_n | < \frac{1}{2} a \leq \frac{1}{2} \varepsilon$ . Liczba $a$ jest jedną z liczb $s_1, s_2, \ldots, s_n$ . Otrzymaliśmy więc warunek (2).

Z lematu wynika natychmiast teza zadania. Wystarczy mianowicie przyjąć $\varepsilon = \max_{1 \leq i \leq n} | a_i |$ , $s_i = a_1 + a_2 + \ldots + a_i$ dla $i = 1, 2, \ldots, n$ . Wtedy $|s_1| = |a_1| \leq \varepsilon$ i $|s_{i+1} - s_i| = | a_{i+1} | \leq \varepsilon$ dla $i = 1, 2, \ldots, n - 1$ . Spełnione są więc założenia lematu. Z lematu wynika, że dla pewnej liczby naturalnej $k \leq n$ zachodzi $|2s_k -s_n | \leq \varepsilon$ , czyli

$ \left| \sum_{i=1}^k a_i - \sum_{i=k+1}^n a_i \right| \leq \max_{1 \leq i \leq n} |a_i|. $

XXV OM - III - Zadanie 5

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

III

Udowodnić, że jeżeli liczby naturalne $n$ , $r$ spełniają nierówność $r + 3 \leq n$ ,to liczby $\binom{n}{r}$ , $\binom{n}{r+1}$ , $\binom{n}{r+2}$ , $\binom{n}{r+3}$ nie są kolejnymi wyrazami żadnego ciągu arytmetycznego.

Rozwiązanie

Udowodnimy najpierw dwa lematy.

Lemat 1. Dla ustalonej liczby naturalnej $n$ istnieją co najwyżej dwie takie liczby naturalne $k \leq n - 2$ , że liczby $\binom{n}{k}$ , $\binom{n}{k+1}$ , $\binom{n}{k+2}$ są kolejnymi wyrazami ciągu arytmetycznego.

Dowód. Jeżeli liczby $\displaystyle \binom{n}{k}, \binom{n}{k+1}, \binom{n}{k+2}$ są kolejnymi wyrazami ciągu arytmetycznego, to

$ \binom{n}{k} + \binom{n}{k+2} = 2\binom{n}{k+1}. $

Mnożąc tę równość stronami przez $\displaystyle \frac{(k+2)!(n-k)!}{n!}$ otrzymamy

$ (k + 2) (k +1) + (n - k) (n - k - 1) = 2 (k + 2) (n - k). $

Jest to równanie kwadratowe ze względu na $k$ . Ma więc ono co najwyżej dwa rozwiązania.

Lemat 2. Dla ustalonej liczby naturalnej $n$ istnieje co najwyżej jedna taka liczba naturalna $k \leq n - 1$ , że $\displaystyle \binom{n}{k} = \binom{n}{k+1}$ .

Dowód. Mnożąc powyższą równość obustronnie przez $\displaystyle \frac{(k+1)!(n-k)!}{n!}$ otrzymujemy $k + 1 = n - k$ . Jest to równanie stopnia pierwszego ze względu na $k$ . Ma więc ono co najwyżej jedno rozwiązanie w zbiorze liczb naturalnych mniejszych od $n$ .

Przystępujemy teraz do rozwiązania zadania. Dla uproszczenia zapisu przyjmijmy, że $a_j = \displaystyle \binom{n}{j}$ dla $j = 1, 2, \ldots, n$ . Przypuśćmy, ze
liczby

$ (1) \qquad a_r, a_{r+1}, a_{r+2}, a_{r+3} $

są kolejnymi wyrazami ciągu arytmetycznego. Na mocy wzoru $\displaystyle \binom{n}{k} = \binom{n}{n-k}$ , czyli $a_k = a_{n-k}$ , również liczby $a_{n-r-3}, a_{n-r-2}, a_{n-r-1}, a_{n-r}$ są kolejnymi wyrazami ciągu arytmetycznego. Mamy więc następujące ciągi arytmetyczne trójwyrazowe

$ a_{r}, a_{r+1}, a_{r + 2}, $

$ a_{r+1}, a_{r+2}, a_{r + 3}, $

$ a_{n-r-3}, a_{n-r-2}, a_{n-r-1} $

$ a_{n-r-2}, a_{n-r-1}, a_{n-r}, $

Z lematu 1 wynika, że zbiór $\{r, r + 1, n - r - 3, n - r - 2\}$ zawiera co najwyżej dwie różne liczby. Ponieważ $r$ i $r + 1$ oraz $n - r - 3$ i $n - r - 2$ są kolejnymi liczbami naturalnymi, więc $r =n - r - 3$ i $r + 1 = n - r - 2$ .

Zatem $a_{r+1} = a_{n-r-2} = a_{r+2}$ czyli ciąg arytmetyczny (1) jest stały. Z lematu 2 wynika, że jest to niemożliwe.

Uzyskana sprzeczność dowodzi, że liczby (1) nie są kolejnymi wyrazami ciągu arytmetycznego.

Uwaga. Można dowieść, że jeżeli dla pewnych liczb naturalnych $n$ i $r$ , gdzie $r \leq n - 2$ , liczby $\displaystyle \binom{n}{r}, \binom{n}{r+1}, \binom{n}{r+2}$ są kolejnymi wyrazami ciągu arytmetycznego, to istnieje taka liczba naturalna $m \geq 3$ , że $n = m^2 - 2$ i $r = \displaystyle \frac{1}{2} (m^2 - m) - 2$ lub $r = \displaystyle \frac{1}{2} (m^2 + m) - 2$ .

Na odwrót, jeżeli liczby $n$ i $r$ są określone powyższymi wzorami, to liczby $\displaystyle \binom{n}{k}, \binom{n}{k+1}, \binom{n}{k+2}$ są kolejnymi wyrazami ciągu arytmetycznego.

Na przykład biorąc $m = 3$ otrzymujemy, że liczby $\displaystyle \binom{7}{1}, \binom{7}{2}, \binom{7}{3}$ tworzą ciąg arytmetyczny.

XXV OM - III - Zadanie 6

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

III

Podzielono $n$ -kąt wypukły przekątnymi na trójkąty w ten sposób, że
1° z każdego wierzchołka wychodzi parzysta liczba przekątnych,
2° żadne dwie przekątne nie mają wspólnych punktów wewnętrznych.
Udowodnić, że $n$ jest podzielne przez 3.

Rozwiązanie

Udowodnimy najpierw

Lemat. Jeżeli $F$ jest figurą na płaszczyźnie i za pomocą $r$ prostych podzielono ją na części, to można te części tak pomalować dwoma kolorami, by każde dwie części mające odcinek wspólny miały różne kolory.

Dowód. Zastosujemy indukcję ze względu na $r$ . W przypadku $r = 1$ teza jest oczywista, ponieważ prosta dzieli płaszczyznę na dwie półpłaszczyzny. Części figury $F$ zawarte w jednej półpłaszczyźnie malujemy jednym kolorem, a części zawarte w drugiej - drugim.

Niech $r$ będzie liczbą naturalną. Zakładamy, że w przypadku $r$ prostych można otrzymane części figury $F$ tak pomalować dwoma kolorami, by był spełniony warunek lematu. Prowadząc $(r + 1)$ -szą prostą dzielimy płaszczyznę na dwie półpłaszczyzny. Części figury $F$ zawarte w jednej z tych półpłaszczyzn zostawiamy tak pomalowane, jak dotychczas, a części zawarte w drugiej - malujemy odwrotnie niż dotychczas (zmieniamy kolor każdej części). Wtedy oczywiście będzie spełniony warunek lematu.

Przystępujemy do rozwiązania zadania. Ponieważ dany $n$ -kąt został podzielony za pomocą pewnej liczby prostych (przekątnych), więc części otrzymane z podziału (trójkąty) można na mocy lematu tak pomalować dwoma kolorami, by trójkąty mające wspólny bok różniły się kolorem.

Ponieważ liczba rozpatrywanych przekątnych wychodzących z dowolnego wierzchołka $A$ danego $n$ -kąta jest parzysta, więc liczba trójkątów, dla których punkt $A$ jest wierzchołkiem, jest nieparzysta. Wobec tego, że trójkąty te mają kolejno różne kolory, więc skrajne trójkąty mają ten sam kolor. Wynika stąd, że trójkąty, których jednym z boków jest bok danego wielokąta, są wszystkie pomalowane na ten sam kolor.

Zatem suma liczby boków $n$ -kąta i liczby wszystkich rozważanych przekątnych jest równa liczbie boków trójkątów pomalowanych tym kolorem. Liczba ta jest więc podzielna przez $3$ . Z drugiej strony liczba rozważanych przekątnych jest równa liczbie boków trójkątów pomalowanych drugim kolorem. Liczba ta jest więc też podzielna przez $3$ . Zatem różnica tych liczb, czyli liczba $n$ , tez jest podzielna przez $3$ .

Uwaga. Jeżeli w treści zadania trójkąty zastąpić przez $k$ -kąty, gdzie $k > 3$ , to zastępując w powyższym rozwiązaniu trójkąty przez $k$ -kąty otrzymamy, że liczba $n$ jest podzielna przez $k$ .