XII OM - III etap

III etap XII Olimpiady Matematycznej

XII OM - III - Zadanie 1

Zawody matematyczne:

XII OM, 1960-1961

Etap:

III

Dowieść, że każda liczba naturalna, która nie jest całkowitą potęgą liczby $2$ , jest sumą dwóch lub więcej kolejnych liczb naturalnych.

Rozwiązanie

Niech $N$ będzie liczbą naturalną, która nie jest całkowitą potęgą dwóch, wobec czego

$ N = 2^n (2m + 1), $

gdzie $m$ i $n$ są liczbami całkowitymi, przy czym $m \geq 1$ , $n \geq 0$ .

Mamy dowieść, że istnieją takie liczby całkowite $a$ i $k$ , że

$ (1) \qquad a \geq 1,\ k \geq 2 $

oraz

$ a + (a + 1) + \ldots (a + k- 1) = N, $

czyli

$ (2) \qquad (2a + k - 1) k = 2^{n+1}(2m + 1). $

Warunek (2) jest spełniony, jeżeli $2a + k - 1 = 2^{n+1}$ , $k = 2m + 1$ , tzn. jeżeli

$ (3) \qquad a = 2^n - m, \ k = 2m + 1. $

Rozwiązanie $(a, k)$ równania (2), określone wzorami (3), czyni zadość warunkowi (1) tylko wtedy, gdy $a > 0$ , tj. gdy

$ (4) \qquad 2^n > m. $

Warunek (2) jest spełniony również wtedy, gdy $2a + k - 1 = 2m + 1$ , $k = 2^{n+1}$ , tzn. gdy

$ (5) \qquad a = m + 1 - 2^n,\ k = 2^{n+1}. $

Liczby $a$ i $k$ określone wzorami (5) są całkowite; warunek (1) spełniają one tylko wtedy, gdy

$ (6) \qquad 2^n \leq m . $

Ponieważ jeden z warunków (4) i (6) zawsze jest spełniony, więc równanie (2) ma zawsze rozwiązanie całkowite $(a, k)$ czyniące zadość nierównościom (1).

Gdy na przykład $N = 30$ , to otrzymamy rozwiązanie $a = 6$ , $k= 4$ i $N = 6 + 7 + 8 + 9$ , gdy $N = 225$ , to $a = 112$ , $k = 2$ , $N = 112 + 113$ .

Uwaga. Zastanowimy się nad tym, czy wyżej znaleziony rozkład liczby naturalnej N na sumę kolejnych liczb naturalnych jest jedynym takim rozkładem.

Przypuśćmy, jak poprzednio, że liczby całkowite a i k spełniają warunki (1) i (2). Możliwe są tylko dwa następujące przypadki:

A) liczba $k$ jest parzysta, wobec czego liczba $2a + k - 1$ jest nieparzysta.

Z równania (2) wynika, że $k$ jest podzielne przez $2n+1$ , zatem

$ (7) \qquad k = 2^{n+1} (2p + 1) $

$ (8) \qquad 2a + k-l = 2q+1,\textrm{ zatem } a = q+1 - 2^n(2p + 1) $

oraz

$ (9) \qquad 2m + 1 = (2p + 1) (2q + 1) $

gdzie $p$ i $q$ są liczbami całkowitymi nieujemnymi. Ponieważ $a \geq 1$ , więc z równości (8) wynika, że

$ (10) \qquad q \geq 2^n (2p + 1) $

Odwrotnie, jeżeli liczba $2m + 1$ ma postać (9), gdzie $p$ i $q$ są liczbami całkowitymi, przy czym $p \geq 0$ , a $q$ spełnia warunek (10), to liczby $a$ i $k$ obliczone według wzorów (7) i (8) określają rozkład liczby $N$ na sumę kolejnych liczb naturalnych. Jeżeli przy tym $p = 0$ , jest to ten sam rozkład, który znaleźliśmy poprzednio [wzory (5)].

B) Liczba $k$ jest nieparzysta, zatem $2a + k - 1$ jest podzielne przez $2n+1$ . Wówczas

$ (11) \qquad k = 2q + 1 $

$ (12) \qquad 2a + k - 1 = 2^{n+1} (2p + 1), \textrm{ zatem } a = 2^n (2p + 1)-q, $

skąd, jak poprzednio,

$ 2m + 1 = (2p + 1) (2q + 1), $

przy czym liczby całkowite $p$ i $q$ czynią zadość nierównościom

$ (13) \qquad q>0, \quad q>2n(2p+ 1), $

gdyż $k > 1$ , $a > 0$ .

Odwrotnie, jeżeli liczba $2m + 1$ ma postać (9), gdzie $p$ i $q$ są liczbami całkowitymi spełniającymi warunki (13), to liczby $a$ i $k$ obliczone według wzorów (11) i (12) określają żądany rozkład liczby $N$ . Jeżeli przy tym $p = 0$ , jest to rozkład znaleziony poprzednio [wzory (3)].

Uzyskaliśmy wynik następujący. Jeżeli liczba $2m + 1$ jest liczbą pierwszą, to istnieje tylko jeden rozkład liczby $N$ na sumę kolejnych liczb naturalnych. Jest to znaleziony poprzednio rozkład określony wzorami (3), bądź wzorami (5), zależnie od tego, czy zachodzi nierówność (4) czy też nierówność (6). Jeżeli zaś $2m + 1$ jest liczbą złożoną, to oprócz tego są jeszcze inne rozkłady. Mianowicie każdemu rozkładowi liczby $2m + 1$ na $2$ czynniki nierówne i większe od $1$ odpowiadają dwa rozkłady liczby $N$ . Łatwo wykazać (co proponujemy czytelnikowi), że albo jeden z tych rozkładów odpowiada przypadkowi A), a drugi - przypadkowi B), albo też oba należą do przypadku B). Wreszcie, gdy istnieje rozkład liczby $2m + 1$ na dwa czynniki równe, tzn. gdy jest ona kwadratem liczby całkowitej, to poza już wymienionymi rozkładami istnieje jeszcze jeden rozkład należący do przypadku B).
Na przykład:

$ 30=6 + 7 + 8 + 9 = 4+ 5+ 6 + 7 + 8 = 9 + 10 + 11, $

$ \begin{split} 225 &= 112 + 113 = 74 + 75 + 76 = 43 + 44 + 45 + 46 + 47 =\\ &= 35 + 36 + 37 + 38 + 39 + 40 =\\ &= 21 + 22 + + 23 + 24 + 25 + 26 + 27 + 28 + 29 =\\ &= 18 + 19 + \ldots + 26 + 27 = 8 + 9 + \ldots + 21 + 22. \end{split} $

XII OM - III - Zadanie 2

Zawody matematyczne:

XII OM, 1960-1961

Etap:

Dowieść, że jeżeli $a + b = 1$ , to

$ a^5 + b^5 \geq \frac{1}{16} $

Rozwiązanie

\spos{I} Jeżeli $a = \frac{1}{2} + d$ , to $b = \frac{1}{2} - d$

$ a^5 = \left(\frac{1}{2} + d \right)^2 = \frac{1}{2^5} + 5 \frac{d}{2^4} + 10 \frac{d^2}{2^3} + 10 \frac{d^3}{2^2} + 5 \frac{d^4}{2} + d^5, $

$ b^5 = \left(\frac{1}{2} - d \right)^2 = \frac{1}{2^5} - 5 \frac{d}{2^4} + 10 \frac{d^2}{2^3} - 10 \frac{d^3}{2^2} - 5 \frac{d^4}{2} + d^5 $

zatem

$ a^5+b^5 =\frac{2}{2^5} + 2 \cdot 10 \frac{d^2}{2^3} + 2 \cdot 5 \frac{d^4}{2}. $

Ponieważ $d^2 \geq 0$ i $d^4 \geq 0$ , otrzymamy stąd

$ a^5+b^5 \geq \frac{2}{2^5}. $

Uwaga. Udowodnione wyżej twierdzenie jest przypadkiem szczególnym twierdzenia: Jeżeli $a + b = 1$ , to

$ (1) \qquad a^n+b^n \geq \frac{1}{2^{n-1}} (n \textrm{ - liczba naturalna}) $

Dowód tego twierdzenia łatwo poprowadzić powyższym sposobem I. Można go również poprowadzić wzorując się na sposobie II i stosując następujące rozumowanie indukcyjne. Gdy $n = 1$ , twierdzenie (1) jest prawdziwe. Przypuśćmy, że jest ono prawdziwe dla każdej wartości $n$ mniejszej, od pewnej liczby naturalnej $m$ . Dowiedziemy, że jest ono prawdziwe i wtedy, gdy $n$ równa się $m$ . Jeżeli $m$ jest parzyste, np. $m = 2k$ , to $k < m$ , zatem

$ \begin{split} a^m+b^m&=a^{2k}+b^{2k}=(a^k+b^k)^2- 2(ab)^k \geq \left( \frac{1}{2^{k-1}} \right)^2 - \frac{2}{2^{2k}}=\\ &=\frac{1}{2^{2k-1}}=\frac{1}{2^{m-1}} \end{split} $

Jeżeli zaś $m$ jest nieparzyste, np. $m = 2k + 1$ , to $m = k + (k + 1)$ , gdzie $k <m$ i $k+1<m$ , zatem

$ \begin{split} a^m + b^m &= a^{2k+1} + b^{2k+1} = (a^k + b^k) (a^{k-1}+b^{k+1}) - (ab)^k (a + b) \geq\\ &\geq \frac{1}{2^{k-1}} \cdot \frac{1}{2^k} -\frac{1}{2^{2k}}=\frac{1}{2^{2k}}=\frac{1}{2^{m-1}}. \end{split} $

XII OM - III - Zadanie 3

Zawody matematyczne:

XII OM, 1960-1961

Etap:

Dowieść, że jeżeli przekrój czworościanu płaszczyzną jest równoległobokiem, to połowa jego obwodu zawiera się między długością najmniejszej a długością największej krawędzi tego czworościanu.

Rozwiązanie

Niech równoległobok $MNPQ$ będzie przekrojem płaskim czworościanu $ABCD$ . Płaszczyzna $MNPQ$ jest oczywiście różna od płaszczyzn ścian czworościanu i każdy bok równoległoboku leży na innej ścianie. Przypuśćmy, że boki równolegle $MN$ i $QP$ leżą na ścianach $ABC$ i $BCD$ ; są one wtedy równoległe do krawędzi $BC$ , według której ściany te graniczą ze sobą, a boki $MQ$ i $NP$ są równoległe do krawędzi $AD$ (rys. 19).

Stosując twierdzenie Talesa do trójkątów $AMN$ i $ABC$ oraz do trójkątów $BMQ$ i $BAD$ otrzymujemy

$ \frac{MN}{BC} = \frac{AM}{AB} \textrm{ oraz } \frac{MQ}{AD} = \frac{MB}{AB}. $

Stąd

$ \frac{MN}{BC} + \frac{MQ}{AD} = \frac{AM + MB}{AB} = 1. $

Przypuśćmy, że $BC \leq AD$ ; w takim razie z powyższej równości wynika, że

$ \frac{MN}{AD} + \frac{MQ}{AD} \leq 1, \textrm{ a } \frac{MN}{BC} + \frac{MQ}{BC} \geq 1, $

zatem

$ BC \leq MN + MQ \leq AD. $

Jeżeli $a$ oznacza długość najmniejszej, a $b$ - długość największej przekątnej czworościanu, to $BC \geq a$ , a $AD \leq b$ i z nierówności powyższej wynika, że

$ a \leq MN + MQ \leq b, $

czego należało dowieść.

XII OM - III - Zadanie 4

Zawody matematyczne:

XII OM, 1960-1961

Etap:

III

Dowieść, że jeżeli każdy bok trójkąta jest mniejszy niż $1$ , to jego pole jest mniejsze niż $\frac{\sqrt{3}}{4}$ .

Rozwiązanie

W każdym trójkącie przynajmniej jeden kąt nie przewyższa $60^\circ$ . Przypuśćmy, że w trójkącie $ABC$ o bokach mniejszych od jedności jest $\measuredangle C \leq 60^\circ$ . Wówczas

$ \textrm{pole }ABC = \frac{1}{2} AC \cdot BC \sin \measuredangle C < \frac{1}{2} \sin 60^\circ = \frac{\sqrt{3}}{4}. $

XII OM - III - Zadanie 5

Zawody matematyczne:

XII OM, 1960-1961

Etap:

Cztery proste przecinające się w sześciu punktach tworzą cztery trójkąty. Dowieść, że okręgi opisane na tych trójkątach mają punkt wspólny.

Rozwiązanie

Cztery proste przecinające się w $6$ punktach tworzą figurę zwaną czworobokiem zupełnym (por. Zadania z Olimpiad Matematycznych, tom I, Warszawa 1960. Zadanie 79). Oznaczmy te punkty literami $A$ , $B$ , $C$ , $D$ , $E$ , $F$ (rys. 21) w taki sposób, że na danych prostych leżą odpowiednio trójki punktów $(A, B, C)$ , $(A, D, E)$ , $(C, F, D)$ , $(B, F, E)$ , przy czym punkt $B$ leży wewnątrz odcinka $AC$ , punkt $D$ - wewnątrz odcinka $AE$ , a punkt $F$ jest wspólnym punktem wewnętrznym odcinków $CD$ i $BE$ .

Na tej figurze są trójkąty: $ABE$ , $BCF$ , $ACD$ i $DEF$ ; niech $K_1$ , $K_2$ , $K_3$ , $K_4$ oznaczają odpowiednio okręgi opisane na tych trójkątach. Okrąg $K_2$ przechodzi przez punkt $F$ leżący wewnątrz okręgu $K_1$ i przez punkt $C$ leżący na zewnątrz tego okręgu. Zatem okręgi $K_1$ i $K_2$ przecinają się w $2$ punktach; jednym z nich jest punkt $B$ , więc drugi punkt przecięcia $M$ leży po przeciwnej stronie cięciwy $FC$ . Według twierdzenia o kącie wpisanym

$ \measuredangle AMB = \measuredangle AEB,\ \measuredangle BMC = \measuredangle BFC, $

zatem

$ \measuredangle AMC = \measuredangle AMB + \measuredangle MBC = \measuredangle AEB + \measuredangle BFC = \measuredangle AEB + \measuredangle DFE = \measuredangle ADC. $

Ponieważ punkty $D$ i $M$ leżą po tej samej stronie prostej $AC$ , więc z równości $\measuredangle AMC = \measuredangle ADC$ wynika, że punkt $M$ leży na okręgu $K_3$ , okręgi $K_1$ , $K_2$ , $K_3$ mają zatem punkt, wspólny $M$ .

W taki sam sposób udowodnimy, że okręgi $K_1$ , $K_3$ , $K_4$ mają punkt wspólny $N$ . Punkty $M$ i $N$ są punktami wspólnymi okręgów $K_1$ i $K_3$ ; żaden z nich nie może pokrywać się z punktem wspólnym $A$ tychże okręgów, gdyż punkt $A$ leży na zewnątrz okręgów $K_2$ i $K_4$ , więc $M$ i $N$ pokrywają się, tzn. okręgi $K_1$ , $K_2$ , $K_3$ , $K_4$ mają punkt wspólny.

Uwaga. Dowód powyższy wymaga uzupełnienia. Przyjęliśmy bowiem bez uzasadnienia, że punkty przecięcia $4$ prostych można zawsze oznaczyć w ten sposób, że na danych prostych leżą odpowiednio trójki $(A, B, C)$ , $(A, D, E)$ , $(C, F, D)$ , $(B, F, E)$ , przy czym punktami wewnętrznymi tych $4$ trójek są punkty $B$ , $D$ , $F$ i $F$ . Fakt ten wysnuliśmy z obserwacji rysunku, co nie jest ścisłym dowodem matematycznym. Przeprowadzimy obecnie jego dowód nie posługując się rysunkiem.

Wśród danych $6$ punktów są $4$ trójki punktów współliniowych tzn. leżących na jednej prostej), a w każdej trójce jeden z punktów leży między dwoma innymi. Zatem któryś z danych $6$ punktów nie jest punktem wewnętrznym żadnej trójki, nazwijmy go $P_1$ . Przez $P_1$ przechodzą $2$ spośród danych prostych; na jednej leżą dalsze $2$ z danych punktów, które możemy oznaczyć literami $P_2$ i $P_3$ w ten sposób, żeby punkt $P_2$ leżał pomiędzy punktami $P_1$ i $P_3$ ; podobnie na drugiej prostej leżą $2$ inne punkty, które tak oznaczymy literami $P_4$ i $P_5$ , że $P_4$ leży między $P_1$ i $P_5$ . Szósty punkt oznaczymy literą $P_6$ , przy czym mogą zajść $2$ przypadki, które kolejno rozpatrzymy: 1) $P_6$ jest punktem przecięcia prostych $P_3P_4$ i $P_2P_5$ ; wówczas $P_6$ leży między punktami $P_3$ i $P_4$ , gdyż prosta $P_2P_5$ przecina bok $P_1P_3$ trójkąta $P_1P_3P_4$ w punkcie $P_2$ , więc musi przeciąć bok $P_3P_4$ (Twierdzenie: Jeżeli prosta ma punkt wspólny z bokiem trójkąta, a nie przechodzi przez żaden wierzchołek trójkąta, to ma punkt wspólny z którymś z pozostałych boków trójkąta, jest podstawowym faktem geometrii przyjmowanym zwykle za pewnik zwany pewnikiem Pascha. Sformułował go w r. 1882 Moritz Pasch (1843-1930), matematyk niemiecki, profesor uniwersytetu w Giessen.); analogicznie punkt $P_6$ leży między punktami $P_2$ i $P_5$ . Jeżeli punkty $P_1$ , $P_2$ , $P_3$ , $P_4$ , $P_5$ , $P_6$ nazwiemy odpowiednio $A$ , $B$ , $C$ , $D$ , $E$ , $F$ , otrzymamy żądane oznaczenia punktów. 2) $P_6$ jest punktem przecięcia prostych $P_2P_4$ i $P_3P_5$ . Wówczas może zajść jeden z dwóch przypadków : a) Punkt $P_2$ leży między punktami $P_4$ i $P_6$ ; wówczas punkt $P_3$ leży między punktami $P_5$ i $P_6$ , gdyż prosta $P_1P_3$ przechodzi przez punkt $P_2$ boku $P_4P_6$ trójkąta $P_4P_5P_6$ , więc musi przeciąć bok $P_5P_6$ . Poszukiwane oznaczenie otrzymamy wówczas nazywając punkty $P_1$ , $P_2$ , $P_3$ , $P_4$ , $P_5$ , $P_6$ odpowiednio $C$ , $F$ , $D$ , $B$ , $A$ , $E$ ; b) punkt $P_4$ leży między punktem $P_2$ i $P_6$ ; wówczas punkt $P_5$ leży między $P_3$ i $P_6$ , gdyż prosta $P_1P_5$ przechodząc przez punkt $P_4$ boku $P_2P_6$ trójkąta $P_2P_3P_6$ musi przejść przez jakiś punkt boku $P_3P_6$ . W tym przypadku punkty $P_1$ , $P_2$ , $P_3$ , $P_4$ , $P_5$ , $P_6$ nazywamy odpowiednio $C$ , $B$ , $A$ , $F$ , $D$ , $E$ i otrzymujemy żądane oznaczenia.

XII OM - III - Zadanie 6

Zawody matematyczne:

XII OM, 1960-1961

Etap:

III

Ktoś napisał sześć listów do sześciu osób i zaadresował do nich sześć kopert. Iloma sposobami można listy tak włożyć do kopert, żeby żaden list nie trafił do właściwej koperty?

Rozwiązanie

Niech $F (n)$ oznacza ilość wszystkich sposobów takiego włożenia $n$ listów $L_1, L_2, \ldots, L_n$ do $n$ kopert $K_1, K_2, \ldots, K_n$ , żeby żaden list $L_i$ nie trafił do właściwej koperty $K_i$ , czyli krócej, żeby nie było żadnego ,,trafienia''. Mamy obliczyć $F (6)$ .

Przypuśćmy, że wkładamy fałszywie wszystkie listy umieszczając list $L_1$ w kopercie $K_i$ ( $i \ne 1$ ). Możliwe są $2$ przypadki :

a) List $L_i$ trafił do koperty $K_1$ . Pozostałe $4$ listy należy wówczas włożyć fałszywie do pozostałych $4$ kopert, na co jest $F (4)$ sposobów. Ponieważ $K_i$ może być każdą z $5$ kopert $K_2$ , $K_3$ , $K_4$ , $K_5$ , $K_6$ , więc przypadek a) może się zdarzyć $5 \cdot F (4)$ razy.

b) List $L_i$ nie trafia do koperty $K_1$ . Przypisując listowi $L_i$ kopertę $K_1$ jako ,,niby-właściwą'' możemy powiedzieć, że wtedy żaden z listów $L_2$ , $L_3$ , $L_4$ , $L_5$ , $L_6$ nie trafia do właściwej koperty, na co jest $F (5)$ sposobów. A ponieważ $K_i$ może być - jak poprzednio - każdą z $5$ kopert, więc przypadek b) może się zdarzyć $5 \cdot F (5)$ razy.

Ponieważ przypadki a) i b) obejmują wszystkie możliwości, więc

$ F (6) = 5P (5) + 5P (4) $

Analogicznie

$F (5) = 4F (4) + 4F (3)$

$F (4) = 3F (3) + 3F (2)$

$F (3) = 2F (2) + 2F (1).$

Lecz oczywiście

$ F(1)=0, \ F(2) = 1, $

wobec czego z równań poprzednich otrzymujemy kolejno,

$ F (3) = 2,\ F (4) = 9,\ F (5) = 44, \ F (6) = 265. $

Uwaga. W rozumowaniach powyższych rozwiązań I i II liczba $6$ nie odgrywa żadnej istotnej roli. Można je równie dobrze zastosować do $n$ listów i $n$ kopert. Sposób I prowadzi wówczas do wzoru

$ (1) \qquad F (n) = (n - 1) F (n - 1) + (n - 1) F (n - 2). $

Jest to tzw. wzór zwrotny, albo redukcyjny, z którego można obliczyć $F (n)$ , gdy znane są wartości $F (n - 1)$ i $F (n - 2)$ . Podobnie sposób II prowadzi do wzoru redukcyjnego

$ (2) \qquad F(n) = n!- \binom{n}{1} F(n - 1) - \binom{n}{2} F(n - 2) - \ldots - \binom{n}{n-2} F (2) - 1. $

Wzór (1) pozwala w następujący sposób obliczyć $F (n)$ w zależności od $n$ . Napiszemy ten wzór w postaci

$ (3) \qquad F (n) - n F (n - 1 )= - [F (n - 1) - (n - 1) F(n-2)]. $

Ze wzoru (3) widzimy, że funkcja $F (k) - kF (k - 1)$ ma dla każdego naturalnego $k > 1$ tę samą wartość bezwzględną, ale zmienia znak przy przejściu od $k$ do $k + 1$ . A ponieważ