XXXI OM - III etap

III etap XXXI Olimpiady Matematycznej

XXXI - III - Zadanie 1

Zawody matematyczne:

XXXI OM, 1979-1980

Etap:

III

Obliczyć pole ośmiokąta wpisanego w okrąg wiedząc, że każdy z czterech kolejnych boków tego ośmiokąta ma długość 1, a każdy z czterech pozostałych ma długość 2.

Rozwiązanie

Pole ośmiokąta danego jest sumą pól ośmiu trójkątów, których wspólnym wierzchołkiem jest środek danego okręgu, podstawami zaś cięciwy, z których cztery mają długość $1$ , cztery pozostałe - długość $2$ . Takie samo pole ma ośmiokąt wpisany w okrąg, w którym kolejne boki mają na przemian długości $1$ oraz $2$ .

Zauważmy, że symetralna każdego boku tego ośmiokąta jest osią symetrii ośmiokąta, skąd wynika, że każde dwa kolejne kąty wewnętrzne tego wielokąta są równe. Suma miar kątów wewnętrznych ośmiokąta wynosi $(8-2) \cdot 180^\circ = = 1080^\circ$ , zatem każdy z kątów ma miarę $\frac{1}{8} \cdot 1080^\circ = 135^\circ$ .

Przedłużając dłuższe boki ośmiokąta otrzymamy czworokąt $KLMN$ , którego pole jest sumą pola ośmiokąta $ABCDEFGH$ oraz czterech trójkątów, których podstawami są krótsze boki ośmiokąta. Rozważmy którykolwiek z tych trójkątów, np. $\triangle ABK$ . Kąt $ABK$ jest kątem przyległym do kąta $ABC$ mającego miarę $135^\circ$ , wobec tego $\measuredangle ABK$ ma miarę $45^\circ$ , analogicznie $\measuredangle KAB$ ma miarę $45^\circ$ i w konsekwencji $\measuredangle AKB$ jest prosty. Wynika stąd, że $AB = KB \sqrt{2}$ , więc $KB = KA = \frac{1}{\sqrt{2}}$ . Przeprowadzając analogiczne rozumowanie dla trójkątów $CDL$ , $EFM$ , $HGN$ stwierdzamy, że wszystkie kąty czworokąta $KLMN$ są proste, a wszystkie boki mają długość $2 + 2 \cdot \frac{1}{\sqrt{2}}$ . Jest to więc kwadrat o boku długości $2 + \sqrt{2}$ , jego pole wynosi $(2 + \sqrt{2})^2 = 4 + 4\sqrt{2} + 2 = 6 + 4\sqrt{2}$ . Pole rozważanego ośmiokąta jest mniejsze
od pola tego kwadratu o sumę pól czterech trójkątów prostokątnych równoramiennych o ramieniu długości $\frac{1}{\sqrt{2}}$ . Pole takiego trójkąta wynosi $\frac{1}{2} \cdot \frac{1}{\sqrt{2}} \cdot \frac{1}{\sqrt{2}} = \frac{1}{4}$ . Szukane pole ośmiokąta wynosi więc

$ 6 + 4\sqrt{2}-4 \cdot \frac{1}{4} = 5 + 4 \sqrt{2}. $

XXXI - III - Zadanie 2

Zawody matematyczne:

XXXI OM, 1979-1980

Etap:

III

Dowieść, że dla dowolnej liczby $n$ istnieje rozwiązanie równania

$ a^2 + b^2 + c^2 = 3abc $

w liczbach naturalnych $a, b, c$ większych od $n$ .

Rozwiązanie

Zauważmy najpierw, że istnieją rozwiązania danego równania w liczbach naturalnych, np. $(1, 1, 1)$ , $(2, 1, 1)$ , $(5, 2, 1)$ , itd.

Pokażemy, że jeśli trójka liczb naturalnych $(a, b, c)$ spełniających warunek $a > b > c$ stanowi rozwiązanie danego równania, to istnieje taka liczba naturalna $d$ , że $c + d > a$ oraz $(c + d, a, b)$ też jest rozwiązaniem danego równania. Szukana liczba $d$ musi spełniać równanie

$ (c + d)^2 + a^2 + b^2 = 3(c + d)ab, $

$ c^2 + 2cd + d^2 + a^2 + b^2 = 3abc + 3abd. $

Ponieważ $a^2 + b^2 + c^2 = 3abc$ , więc

$ 2cd + d^2 = 3abd, \ \textrm{to jest} $

$ 2c + d = 3ab, $

$ d = 3ab - 2c . $

Przeprowadzając powyższe rachunki w odwrotnej kolejności stwierdzamy, że istotnie trójka liczb $(3ab - c, a, b)$ stanowi rozwiązanie danego równania,, przy czym $3ab - c > 3a - c > a$ .

Wynika stąd, że dowolne rozwiązanie $(a, b, c)$ spełniające warunek $a> b > c$ (rozwiązaniem takim jest np. $(5, 2, 1)$ ) możemy zastąpić, przez rozwiązanie w liczbach naturalnych większych od $c$ . Iterując to postępowanie dostateczną ilość razy otrzymamy rozwiązanie w liczbach naturalnych większych od dowolnej liczby $n$ .

Uwaga. Korzystając z powyższego rozwiązania można nawet podać wzór na trójkę liczb spełniających dane równanie i większych od ustalonej liczby $n$ . Rozpatrzmy ciągi $\{ b_n \}$ i $\{ c_n \}$ określone w następujący sposób

$ b_1 = c_1 = 1, \ b_{k+1} = 3b_k - c_k,\ c_{k+1} = b_k. $

Modyfikując nieznacznie rozumowanie przeprowadzone w rozwiązaniu zadania stwierdzimy, że każda z trójek liczb $t_k= (1, b_k, c_k)$ spełnia dane równanie:

$ t_1 = (1, 2, 1) \ \textrm{jest rozwiązaniem}, $

Jeśli $t_k = (1, b_k, c_k)$ jest rozwiązaniem, to $t_{k+1} =(1, 3b_k - c_k, b_k)$ też jest rozwiązaniem.

Wynika stąd, że $b_1 = 1$ , $b_2 = 2$ , $b_{k+2} = 3b_{k+1} - b_k$ i trójki liczb $(1, b_{k+1}, b_k)$ spełniają równanie. Stosując jeszcze raz rozumowanie przeprowadzone w rozwiązaniu zadania stwierdzimy, że z faktu, że $(1, b_{k+1}, b_k)$ jest rozwiązaniem wynika, że $(b_{k+1}, b_k, 3b_k \cdot b_{k+1} - 1)$ też jest rozwiązaniem.

Z drugiej strony przez indukcję można wykazać, że

$ b_k = \frac{1}{\sqrt{2}} \left( \left( \frac{1+\sqrt{5}}{2} \right)^{2k-1} - \left( \frac{1-\sqrt{5}}{2} \right)^{2k-1} \right) $

oraz $b_k \geq k$ .

Reasumując otrzymujemy wzory na rozwiązanie $(b_{n+1}, b_n, 3b_n \cdot b_{n+1} - 1)$ w liczbach nie mniejszych od $n$ .

XXXI - III - Zadanie 3

Zawody matematyczne:

XXXI OM, 1979-1980

Etap:

III

Obieramy liczbę całkowitą $k$ z przedziału $[1, 99]$ . Następnie rzucamy 100 razy monetą (wyniki rzutów są niezależne). Niech

$ \varepsilon_j = \begin{cases} 1, & \mbox{ gdy w $j$-tym rzucie wypadnie orzeł,} \\ 2, & \mbox{ gdy w $j$-tym rzucie wypadnie reszka.} \end{cases} $

Oznaczmy przez $M_k$ zdarzenie polegające na tym, że istnieje taka liczba $i$ , że $k + \varepsilon_1 + \ldots + \varepsilon_i = 100$ . Jakie powinno być $k$ , aby prawdopodobieństwo zdarzenia $M_k$ było największe?

Rozwiązanie

Niech $P(M_k)$ będzie prawdopodobieństwem zdarzenia $M_k$ . Oczywiście $P(M_{99})=\frac{1}{2}$ , $p(M_{98})=\frac{1}{2} + \frac{1}{2} \cdot \frac{1}{2} = \frac{3}{4}$ . Pokażemy, że dla $k < 98$ jest $P(M_k) < \frac{3}{4}$ . Zauważmy najpierw, że

$ (1) \qquad P(M_{k-2}) = \frac{1}{2} P(M_{k-1}) + \frac{1}{2} P(M_k)\ \textrm{dla}\ 2 < k < 100. $

Istotnie, jeśli w pierwszym rzucie wypadnie orzeł (prawdopodobieństwo tego wynosi $\frac{1}{2}$ , to zdarzenie sprzyjające zdarzeniu $M_{k-2}$ polega na tym, że $(k - 2) + 1 + \varepsilon_2 + \ldots + \varepsilon_i = 100$ , więc $k - 1 + \varepsilon_2 +\ldots + \varepsilon_i = 100$ .

Jeśli zaś w pierwszym rzucie wypadnie reszka, to zdarzenie sprzyjające polega na tym, że $k + \varepsilon_2 + \ldots + \varepsilon_i = 100$ .

Stosując (1) możemy udowodnić przez indukcję, że

$ P(M_{98-n}) < \frac{3}{4} \ \textrm{dla}\ n= 1, 2, \ldots,97. $

Dla $n = 1$ jest na mocy (1)

$ P(M_{97}) = \frac{1}{2} P(M_{98}) + \frac{1}{2} P(M_{99}) = \frac{1}{2} \cdot \frac{3}{4} + \frac{1}{2} \cdot \frac{1}{2} = \frac{5}{8} < \frac{3}{4}. $

Załóżmy, że dla pewnego $n$ $(1 < n < 97)$ i dla $k = 1, 2, \ldots, n$ jest $P(M_{98-k}) < \frac{3}{4}$ .

$ P(M_{98-(n+1)}) = \frac{1}{2} P(M_{98-n}) + \frac{1}{2} P(M_{98-n+1}) < \frac{1}{2} \cdot \frac{3}{4} + \frac{1}{2} \cdot \frac{3}{4} = \frac{3}{4}. $

Wynika stąd na mocy zasady indukcji, że $P(M_k) < \frac{3}{4}$ dla $1 \leq k < 98$ .

Ponieważ ponadto $P(M_{99}) < \frac{3}{4}$ , więc prawdopodobieństwo zdarzenia $M_k$ jest największe dla $k = 98$ .

XXXI - III - Zadanie 4

Zawody matematyczne:

XXXI OM, 1979-1980

Etap:

III

Udowodnić, że dla każdego wielomianu $W$ trzech zmiennych istnieją takie wielomiany $U$ i $V$ , że tożsamościowo zachodzą równości

$ \begin{split} W(x, y,z) = U (x, y, z) + V (x, y, z), U (x, y, z) = U (y, x, z), V(x, y,z) = -V(x, z, y). \end{split} $

Rozwiązanie

Przypuśćmy, że wielomiany $U$ i $V$ spełniają warunki zadania. Wobec tego

$ (*) \qquad\begin{split} W(x, y, z) &= U(x, y, z) + V(x, y, z) \\ W(y, x, z) &= U(x, y, z) + V(y, x, z) \\ W(x, z, y) &= U(x, z, y) - V(x, y, z) \\ W(y, z, x) &= U(y, z, x) - V(y, x, z) \\ W(z, x, y) &= U(x, z, y) + V(z, x, y) \\ W(z, y, x) &= U(y, z, x) - V(z, x, y). \end{split} $

Z dwóch pierwszych równań wyliczamy

$ U (x, y,z) = \frac{1}{2} W(x, y,z) + \frac{1}{2} W(y, x, z) - \frac{1}{2} V(x, y,z) - \frac{1}{2} V(y, x, z). $

Z dwóch kolejnych równań układu (*) otrzymujemy

$ V(x,y, z) = - W (x, z,y) + U(x,z,y), $

$ V(y, x, z) = - W(y, z, x) + U (y, z, x), $

więc

$ \begin{split} U(x,y,z) = \frac{1}{2} W(x,y,z) + \frac{1}{2} W(y,x,z) + \frac{1}{2} W(x,z,y)- \frac{1}{2} U(x,z,y)+\\ + \frac{1}{2} W(y,z,x)-\frac{1}{2} U(y,z,x). \end{split} $

Wreszcie z ostatnich dwóch równań układu (*) wynika

$ U(x,z,y) = W (z,x,y) - V(z,x,y) $

$ U(y, z, x) = W(z,y, x) + V(z, x,y), $

więc

$ \begin{split} U(x, y,z)&=\frac{1}{2} W(x, y, z) + \frac{1}{2} W(y, x, z) + \frac{1}{2} W(x, z,y)+ \frac{1}{2} W(y, x, z) + \\ & \quad- \frac{1}{2} W(z,x,y)+ \frac{1}{2} V(z, x ,y) - \frac{1}{2} W (z, y, x) - \frac{1}{2} V (z, x, y)\\ U(x, y, z) &= \frac{1}{2} (W(x, y, z) + W(y, x, z) + W(x, z, y)+ W(y, z, x)+\\ &\quad - W(z,x,y) - W(z,y,x)). \end{split} $

Wobec tego

$ \begin{split} V(x,y,z) &= W(x,y,z) - U(x,y,z) = \\ &=\frac{1}{2} (W(x,y,z)-W(y,x,z)-W(x,z,y)+\\ &\quad- W(y, z, x) + W (z, x, y) + W(z,y, x)) \end{split} $

Z określenia $V$ wynika, że wielomiany $U$ i $V$ zdefiniowane wyżej spełniają związek

$ W(x, y,z) = U(x, y, z) + V(x, y, z). $

Sprawdzamy bezpośrednio, że

$ \begin{split} U(y, x, z) &= \frac{1}{2} (W(y, x, z) + W(x, y, z) + W(y, z, x) + W(x, z, y) +\\ &\quad - W(z,y, x) - W (z, x,y)) = U(x,y, z),\\ V(x, z,y) &= \frac{1}{2} (W(x, z,y) - W(z, x,y) - W(x,y, z) - W(z,y,x)+ W(y, x, z) +\\ &\quad + W(y, z,x)) = \frac{1}{2}(- W(x, y, z) + W(y, x, z) + W(x, z, y) +\\ &\quad + W(y, z, x) - W (z, x,y) - W(z,y, x)) = -V(x,y, z). \end{split} $

Wykazaliśmy więc, że wielomiany

$ \begin{split} U(x,y,z)=& \frac{1}{2} (W(x,y, z) + W(y, x, z) + W(x, z,y) + W(y, z,x)+\\ & -W(z,x,y)- W(z,y,x)),\\ V(x, y, z) =& \frac{1}{2} (W(x,y, z) - W(y, x, z) - W(x, z,y) - W(y, z, x) + \\ & + W(z,x,y) + W(z,y,x)) \end{split} $

spełniają wymagania zadania, przy czym są to jedyne wielomiany spełniające te wymagania.

XXXI - III - Zadanie 5

Zawody matematyczne:

XXXI OM, 1979-1980

Etap:

III

W czworościanie pola sześciu trójkątów, których bokami są krawędzie, a wierzchołkami środki przeciwległych krawędzi czworościanu, są równe. Udowodnić, że czworościan ten jest foremny.

Rozwiązanie

Założenie zadania gwarantuje równość pól sześciu trójkątów, z których każdy ma podstawę będącą krawędzią czworościanu, a wierzchołek przeciwległy jest środkiem przeciwległej krawędzi. Na czworościanie $ABCD$ opisujemy równoległościan $A_1CB_1DAC_1BD_1$ , którego każda ściana zawiera pewną krawędź czworościanu i jest równoległa do przeciwległej krawędzi czworościanu. Z założenia o równości pól sześciu trójkątów, których bokami są krawędzie a wierzchołkami środki przeciwległych krawędzi czworościanu wynika, że przekroje równoległościanu płaszczyznami zawierającymi przeciwległe krawędzie mają równe pola, bo np. pole $A_1B_1BA$ jest równe $2 \cdot$ pole $\triangle ABK_1$ , pole $CDD_1C_1$ równe jest $2 \cdot$ pole $\triangle CDK$ itp. dla pozostałych czterech przekrojów.

Poprowadźmy teraz płaszczyznę prostopadłą do pewnej krawędzi rozważanego równoległościanu, np. do $\overline{AA_1}$ . Przecina ona proste $AA_1$ , $BB_1$ , $CC_1$ , $DD_1$ odpowiednio w punktach $A_2$ , $B_2$ , $C_2$ , $D_2$ , przy czym $A_2C_2B_2D_2$ jest równoległobokiem. Ponieważ pole $ABB_1A_1$ jest równe $AA_1 \cdot A_2B_2$ oraz pole $CDD_1C_1$ jest równe $CC_1 \cdot C_2D_2$ , przy czym pola te są równe i $AA_1 = CC_1$ , więc $A_2B_2 = C_2D_2$ . Wobec tego równoległobok $A_2C_2B_2D_2$ ma przekątne równej długości, jest więc prostokątem. Wynika stąd, że ściany $AC_1CA_1$ i $CB_1BC_1$ ; $CB_1BC_1$ i $B_1DD_1B$ ; $B_1DD_1B$ i $A_1DD_1A$ są do siebie prostopadłe.

Prowadząc płaszczyznę prostopadłą do krawędzi $AC_1$ a następnie płaszczyznę prostopadłą do krawędzi $AD_1$ stwierdzimy w analogiczny sposóbj że każde dwie ściany równoległościanu mające wspólną krawędź są prostopadłe, a więc równoległościan jest prostopadłościanem. Jeśli $x$ , $y$ , $z$ są długościami krawędzi tego prostopadłościanu, to ponieważ (jak stwierdziliśmy wyżej) przekroje poprowadzone przez przeciwległe krawędzie mają równe pola, więc

$ x \sqrt{y^2 + z^2} = y\sqrt{x^2 + z^2} = z\sqrt{x^2 + y^2}. $

Wynika stąd

$ x^2y^2 + x^2z^2 = y^2x^2 + y^2z^2 = z^2x^2 + z^2y^2. $

Pierwsza z tych równości pociąga za sobą $x^2z^2 = y^2z^2$ , więc $x = y$ , podobnie z drugiej równości wynika $y = z$ .

Wobec tego równoległościan opisany na danym czworościanie jest czworościanem, a stąd wynika, że dany czworościan jest foremny.

XXXI - III - Zadanie 6

Zawody matematyczne:

XXXI OM, 1979-1980

Etap:

III

Dowieść, że dla każdej liczby naturalnej $n$ zachodzi równość

$ \sum_{s=n}^{2n} 2^{2n-s} \binom{s}{n} = 2^{2n} $

Rozwiązanie

\spos{I} Przeprowadzimy dowód indukcyjny równości otrzymanej z danej równości przez podzielenie obu stron przez $2^{2^n}$ :

$ (1) \qquad \sum_{s=n}^{2n} 2^{-s} \binom{s}{n} =1. $

W dowodzie wykorzystamy następującą własność współczynników dwumianowych.

Lemat. Dla każdych liczb całkowitych $r$ , $s$ spełniających nierówności $0 \leq s \leq r$ jest

$ (2) \qquad \binom{r}{s+1} = \binom{r+1}{s+1} - \binom{r}{s} $

(gdy $s = r$ przyjmujemy $\binom{r}{s+1} = 0$ ).

Dowód lematu. Jeśli $s = r$ , to $\binom{r}{s} =1$ , $\binom{r+1}{s+1} = 1$ , $\binom{r}{s+1}=0$ , więc równość (2) jest oczywiście spełniona. Załóżmy, że $s < r$ .

$ \begin{split} \binom{r+1}{s+1} - \binom{r}{s} &= \frac{(r+1)!}{(s+1)! [(r+1) - (s+1)]!}- \frac{r!}{s! (r-s)!} = \\ & = \frac{(r+1)!}{(s+1)! (r - s)!}- \frac{r!}{s! (r-s)!} = \frac{(r+1)! - r!(s+1)}{(s+1)! (r - s)!} =\\ & = \frac{r! [(r+1) - (s+1)]}{(s+1)! (r - s)!} = \frac{r! (r-s)}{(s+1)! (r - s)!} = \\ & = \frac{r!}{(s+1)! (r - s-1)!} = \binom{r}{s+1}. \end{split} $

Dowód lematu został więc zakończony. Powróćmy do dowodu równości (1).
Dla $n = 1$

$ \sum_{s=1}^2 2^{-s} \binom{s}{1} = 2^{-1} \cdot \binom{1}{1} + 2^{-2} \cdot \binom{2}{1} = \frac{1}{2} \cdot 1 + \frac{1}{4} \cdot 2 = \frac{1}{2} + \frac{1}{2} = 1. $

Załóżmy, że równość (1) jest spełniona dla pewnej liczby naturalnej $n$ i rozważmy sumę

$ (3) \qquad S= \sum_{s=n+1}^{2(n+1)} 2^{-s} \binom{s}{n+1}. $

Na mocy lematu zastosowanego do współczynnika $\binom{s}{n+1}$ jest

$ \begin{split} S & = \sum_{s=n+1}^{2n+2} 2^{-s} \binom{s}{n+1}= \sum_{s=n+1}^{2n+2} 2^{-s} \binom{s+1}{n+1} - \sum_{s=n+1}^{2n+2} 2^{-s} \binom{s}{n}=\\ &= 2 \cdot \sum_{s=n+1}^{2n+2} 2^{-s-1} \binom{s+1}{n+1} - \sum_{s=n+1}^{2n+2} 2^{-s} \binom{s}{n} = 2 \cdot \sum_{s=n+2}^{2n+3} 2^{-s} \binom{s}{n+1} +\\ &\quad - \sum_{s=n}^{2n} 2^{-s} \binom{s}{n}+ 2^{-n} \binom{n}{n} - 2^{-2n-1} \binom{2n+1}{n} - 2^{-2n-2} \binom{2n+2}{n}. \end{split} $

Ponieważ na mocy założenia indukcyjnego $\sum_{s=n}^{2n} 2^{-s} \binom{s}{n}=1$ , ponadto $\binom{n}{n}=1$ , więc

$ \begin{split} S & = 2 \cdot \sum_{s=n+2}^{2n+3} 2^{-s} \binom{s}{n+1} - 1 + 2^{-n} - 2^{-2n-2} \left[ 2 \binom{2n+1}{n} + \binom{2n+2}{n} \right]=\\ & = 2 \cdot \sum_{s=n+1}^{2n+2} 2^{-s} \binom{s}{n+1} - 2 \cdot 2^{-n-1} \binom{n+1}{n+1} + 2 \cdot 2^{-2n-3} \binom{2n+3}{n+1} +\\ &\quad- 1 + 2^{-n} - 2^{-2n-2} \left[ \binom{2n+2}{n} + 2 \binom{2n+1}{n} \right] = 2S - 2^{-n} + \\ &\quad + 2^{-2n-2} \left[ \binom{2n+3}{n+1} - \binom{2n+2}{n} - 2\cdot \binom{2n+1}{n} \right] -1 + 2^{-n}. \end{split} $

Wobec tego

$ S = 2S - 1 + 2^{-2n-2} \left[ \binom{2n+3}{n+1} - \binom{2n+2}{n} - 2\cdot \binom{2n+1}{n} \right], $

a więc

$ S = 1 - 2^{-2n-2} \left[ \binom{2n+3}{n+1} - \binom{2n+2}{n} - 2\cdot \binom{2n+1}{n} \right]. $

Na mocy lematu $\binom{2n+3}{n+1} - \binom{2n+2}{n} = \binom{2n+2}{n+1}$ , $\binom{2n+2}{n+1} - \binom{2n+1}{n} = \binom{2n+1}{n+1}$ , ponadto
$\binom{2n+1}{n+1} = \binom{2n+1}{n} = \frac{(2n+1)!}{n!(n+1)!}$ , więc wyrażenie występujące w nawiasie kwadratowym w równości (4) jest równe $0$ . Ostatecznie więc $S=1$ . Z założenia indukcyjnego wynikła prawdziwość równości (3). Na mocy zasady indukcji równość (1) jest spełniona dla każdej liczby naturalnej $n$ .