XLII OM - III etap

III etap XLII Olimpiady Matematycznej

XLII OM - III - Zadanie 1

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

III

Zbadać, czy istnieją czworościany $T_1$ i $T_2$ o następujących dwóch własnościach:

(a) objętość czworościanu $T_1$ jest większa od objętości czworościanu $T_2$ ;

(b) pole każdej ściany czworościanu $T_1$ nie przekracza pola żadnej ściany czworościanu $T_2$ .

Rozwiązanie

Istnieją takie pary czworościanów. Więcej: dla dowolnego czworościanu $T_1$ można zbudować czworościan $T_2$ tak, by były spełnione warunki (a) i (b). Oto przykład metody:

Niech $T_1$ będzie dowolnym czworościanem: niech $V_1$ będzie jego objętością, a $S_1$ - polem największej ściany. Weźmy liczbę dodatnią $a$ spełniającą nierówność $a^2 > 2S_1$ oraz dobierzmy do niej liczbę dodatnią $b$ taką, by zachodziła nierówność $a^2b< V_1$ . Zbudujmy prostopadłościan $P$ , którego dwiema równoległymi ścianami są kwadraty $Q$ i $Q'$ o boku długości $a$ , położone w odległości $b$ jeden od drugiego. Niech $T_2$ będzie czworościanem, którego dwiema rozłącznymi (skośnymi) krawędziami są przekątne kwadratów $Q$ i $Q'$ . Objętość $V_2$ czworościanu $T_2$ jest mniejsza niż objętość prostopadłościanu $P$ , równa $a^2b$ . Zatem $V_2 < V_1$ .

Ścianami czworościanu $T_2$ są cztery przystające trójkąty, o równym polu $S_2$ . Rzut każdego z nich na płaszczyznę kwadratu $Q$ jest połówką tego kwadratu. A zatem $S_2 > \frac{1}{2}($ pole $Q)= \frac{1}{2}a^2 > S_1$ .

Czworościany $T_1$ i $T_2$ mają więc wymagane własności.

XLII OM - III - Zadanie 2

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

III

Niech $X$ będzie zbiorem punktów płaszczyzny $(x.y)$ o obydwu współrzędnych całkowitych. Drogą długości $n$ nazywamy każdy taki ciąg $(P_0, P_1,\ldots, P_n)$ punktów zbioru $X$ , że $|P_{i-1}P_{i}|=1$ dla $i \in \{1,2,\ldots,n\}$ . Niech $F(n)$ będzie liczbą różnych dróg $(P_0,P_1,\ldots,P_n)$ o początku $P_0 = (0,0)$ i końcu $P_n$ położonym na prostej o równaniu $y = 0$ . Udowodnić, że

$ F(n) = \binom{2n}{n}. $

Rozwiązanie

Dowolnej drodze długości $n$ , o początku $P_0 = (0,0)$ , przyporządkujemy ciąg $2n$ symboli, z których każdy jest zerem lub jedynką. Czynimy to w sposób następujący. Jeżeli droga ma postać $(P_0,P_1,\ldots,P_n)$ , to odpowiadający jej ciąg zero-jedynkowy

$ (c_1,c_2,\ldots,c_{2n-1} ,c_{2n}), $

zwany kodem tej drogi, określamy zespołem reguł:

$ \begin{array}{lcll} \textrm{jeśli} & \overrightarrow{P_{j-1}P_j} = [ 1,0], & \textrm{to} & c_{2j-1} = 1, c_{2j} = 0;\\ \textrm{jeśli} & \overrightarrow{P_{j-1}P_j} = [ 0,1], & \textrm{to} & c_{2j-1} = 1, c_{2j} = 1;\\ \textrm{jeśli} & \overrightarrow{P_{j-1}P_j} = [-1,0], & \textrm{to} & c_{2j-1} = 0, c_{2j} = 1;\\ \textrm{jeśli} & \overrightarrow{P_{j-1}P_j} = [0,-1], & \textrm{to} & c_{2j-1} = 0, c_{2j} = 0. \end{array} $

Mówiąc obrazowo: krok w prawo kodujemy przy pomocy pary $10$ ; krok w górę: $11$ ; krok w lewo: $01$ ; krok w dół: $00$ .

Na odwrót: każdy ciąg zero-jedynkowy długości $2n$ wyznacza drogę, której jest kodem.

Różnym drogom odpowiadają różne ciągi zero-jedynkowe; kodowanie jest wzajemnie jednoznaczne.

Zauważmy teraz, że jeżeli punkt $P_n$ , koniec drogi, leży na prostej o równaniu $y = k$ , to znaczy, że wykonaliśmy $g$ kroków w górę i $d$ kroków w dół, gdzie $g$ i $d$ są liczbami o różnicy $g - d = k$ . Pozostałe ruchy (w liczbie $n-g-d$ ) były poziome, i jest bez znaczenia, które z nich wykonaliśmy w prawo, a które w lewo.

Liczba jedynek w kodzie takiej drogi wynosi

$ 2g + (n-g-d) = n + g-d = n + k. $

A zatem kodami dróg kończących się na prostej $y = 0$ są ciągi złożone dokładnie z $n$ jedynek i $n$ zer. Numery miejsc, na których występują jedynki, mogą tworzyć dowolny $n$ -elementowy podzbiór zbioru $\{1,2,\ldots,2n\}$ . Liczba takich podzbiorów wynosi $\binom{2n}{n}$ . Tyle jest więc i dróg długości $n$ o końcu położonym na prostej $y = 0$ .

XLII OM - III - Zadanie 3

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

III

Niech $N$ będzie dowolną liczbą postaci

$ N= \sum_{k=1}^{60} \varepsilon_k\cdot k^{k^k}, $

gdzie każdy ze współczynników $\varepsilon_1,\ldots, \varepsilon_{60}$ równa się $1$ lub $-1$ . Udowodnić, że $N$ nie jest piątą potęgą żadnej liczby naturalnej.

Uwaga: $k^{k^k} = k^{(k^k)}$ .

Rozwiązanie

Zauważmy, że liczba $60^{60^{60}}$ jest piątą potęgą pewnej liczby naturalnej $M$ ; mianowicie

$ 60^{60^{60}} = M^5, \quad \textrm{gdzie} \ M=60^{12 \cdot 60^{59}}. $

Spośród składników sumy określającej liczbę $N$ , największym (co do wartości
bezwzględnej) jest oczywiście ten ostatni ( $60^{60^{60}}$ ). Wszystkie pozostałe składniki, wzięte łącznie, z dowolnymi znakami, stanowią tak znikomy ułamek liczby $M^5 = 60^{60^{60}}$ , że ich dodanie lub odjęcie nie pozwoli wyjść poza przedział $((M - 1)^5;( M + 1)^5)$ ; na tym nieprecyzyjnym spostrzeżeniu opiera się całe rozwiązanie.

Oznaczmy:

$ L = \sum_{k=1}^{59} \varepsilon_k \cdot k^{k^k}. $

Oszacujemy wartość bezwzględną tej sumy z góry i z dołu:

$ (1) \qquad |L| \leq \sum_{k=1}^{59} \varepsilon_k \cdot k^{k^k} < 59 \cdot 59^{59^{59}} = 59^{59^{59}+1} < 60^{59^{59}+1} < 60^{12 \cdot 60^{59}} = M; $

jednocześnie

$ \begin{split} (2) \qquad |L| \geq 59^{59^{59}} - \sum_{k=1}^{58} k^{k^k} & > 59^{59^{59}} - 58 \cdot 58^{58^{58}} = \\ & = 59^{59^{59}} - 58^{58^{58}+1} > 59^{59^{59}} - 59^{58^{58}+1} > 0; \end{split} $

skorzystaliśmy z banalnych nierówności $12 \cdot 60^{59} > 59^{59} + 1$ i $59^{59} > 58^{58} + 1$ .

Ponieważ

$ N = L + \varepsilon_{60} \cdot 60^{60^{60}} = L + \varepsilon_{60} \cdot M^5, $

z oszacowania (1) widać, że liczba $N$ ma znak taki, jak $\varepsilon_{60}$ . Jeśli więc $\varepsilon_{60}=- 1$ , to $N$ jest liczbą ujemną - nie może więc być piątą potęgą żadnej liczby naturalnej.

W dalszym ciągu przyjmujemy, że $\varepsilon_{60} = +1$ . Zatem $N = M^5 + L$ .

Przypuśćmy, że $N$ jest piątą potęgą pewnej liczby naturalnej $K$ :

$ N = K^5. $

Liczba $K$ nie może być równa $M$ ; znaczyłoby to bowiem, że $L = 0$ , wbrew nierówności (2). Wobec tego $K \geq M +1$ lub $K \leq M - 1$ i w konsekwencji

$ L = K^5 - M^5 \geq (M +1)^5- M^5 \quad \textrm{lub} \quad L \leq (M - 1)^5 - M^5. $

Stąd

$ \begin{split} |L| & \geq \min \{(M + 1)^5 - M^5, M^5 - (M - 1)^5\} = M^5 - (M - 1 )^5 =\\ & = 5 M^4 - 10M^3 +10M^2 - 5M +1 > 5M^4 - 10 M^3 > M^4. \end{split} $

To się jednak nie da pogodzić z oszacowaniem (1). Sprzeczność dowodzi niesłuszności przypuszczenia, że $N = K^5$ dla pewnego $K$ naturalnego; dowód jest zakończony.

XLII OM - III - Zadanie 4

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

III

Na płaszczyźnie z kartezjańskim układem współrzędnych rozważamy zbiór $V$ wszystkich wektorów swobodnych, których obie współrzędne są liczbami całkowitymi. Wyznaczyć wszystkie funkcje $f$ , określone na zbiorze $V$ , o wartościach rzeczywistych, spełniające warunki:

(a) $f(v) = 1$ dla każdego z czterech wektorów $v\in V$ o długości $1$ ;

(b) $f(v+w) = f(v) + f(w)$ dla każdej pary wektorów prostopadłych $v, w \in V$ .

Uwaga: Wektor zerowy jest prostopadły do każdego wektora.

Rozwiązanie

Przypuśćmy, że funkcja $f$ spełnia postawione warunki. Korzystając z tych
warunków, wypiszmy wartości $f(\overrightarrow{\mathbf{v}})$ dla kilku wektorów o niewielkich współrzędnych całkowitych:

$ \begin{array}{cccc} \overrightarrow{\mathbf{v}} & f(\overrightarrow{\mathbf{v}}) & \overrightarrow{\mathbf{v}} & f(\overrightarrow{\mathbf{v}}) \\ {[} 1, 0{]} & 1 & {[} 2, 0{]} = {[} 1,1 {]} + {[}1,-1{]} & 2 + 2 = 4 \\ {[} 0, 1{]} & 1 & {[} 0, 2{]} = {[} 1,1 {]} + {[}-1,1{]} & 2 + 2 = 4 \\ {[}-1, 0{]} & 1 & {[}-2, 0{]} = {[}-1,1 {]} + {[}-1,-1{]} & 2 + 2 = 4 \\ {[} 0,-1{]} & 1 & {[} 0,-2{]} = {[}-1,-1{]} + {[} 1,-1{]} & 2 + 2 = 4 \\ {[} 1, 1{]} = {[} 1,0{]} + {[}0,1 {]} & 1 + 1=2 & {[}1,2{]} = {[}1,0{]} + {[}0,2 {]} & 1+4 = 5 \\ {[}-1, 1{]} = {[}-1,0{]} + {[}0,1{]} & 1 + 1 = 2 & {[}2,-1{]} = {[}2,0{]} + {[}0,-1{]} & 4+1 = 5 \\ {[}-1,-1{]} = {[}-1,0{]} + {[}0,-1{]} & 1 + 1=2 & {[}3,1{]} = {[}1,2{]} + {[}2,-1{]} & 5 + 5=10 \\ {[} 1,-1{]} = {[}0,-1{]} + {[}1,0{]} & 1+1 = 2 & {[}3,0{]} = {[}3,1{]} - {[}0,1 {]} & 10-1 = 9 \end{array} $

(Przy obliczaniu ostatniej ze znalezionych wartości wykorzystaliśmy prostopadłość wektorów $[3,0]$ i $[0,1]$ i wynikającą z niej na mocy warunku (b) równość $f([3,0]) = f([3,1])-f([0,1])$ .)

Widzimy z tej tabelki, że $f([k,0])=k^2$ dla $k = 1,2,3$ . Prowadzi to do przypuszczenia, że dla wszystkich $k$ naturalnych powinna zachodzić równość $f([k,0]) = k^2$ , oraz także - przez symetrię - $f([0,k]) = k^2$ , $f([-k,0]) = k^2$ , $f([0,-k]) = k^2$ , a jeśli tak - to

$ (1) \qquad f([x,y]) = x^2 + y^2 \quad \textrm{dla wszystkich całkowitych} \ x,y, $

bowiem wektor $[x,y]$ jest sumą wektorów prostopadłych $[x,0]$ i $[0,y]$ .

Udowodnimy teraz słuszność hipotezy (1).

Wektor zerowy $\overrightarrow{\mathbf{0}} = [0,0]$ jest prostopadły do każdego wektora, więc i do siebie samego. Stąd $f(\overrightarrow{\mathbf{0}}) = f(\overrightarrow{\mathbf{0}}+\overrightarrow{\mathbf{0}}) = f(\overrightarrow{\mathbf{0}}) + f(\overrightarrow{\mathbf{0}})$ , czyli $f(\overrightarrow{\mathbf{0}}) = 0$ . Zatem równość (1) zachodzi dla $x = y = 0$ .

Wykażemy przez indukcję względem $n$ , że

$ (2) \qquad \left\{ \begin{array}{c} f([x,y]) = x^2 + y^2 \quad \textrm{dla każdego wektora} \ [x,y]\\ \textrm{o współrzędnych całkowitych} \ x,y\ \textrm{takich, że} \ |x| \leq n, |y| \leq n. \end{array} \right. $

Dla $n = 1$ jest to prawda; widać to z tabelki.

Przyjmijmy słuszność stwierdzenia (2) dla pewnej liczby naturalnej $n \geq 1$ . W szczególności mamy więc

$ f([n,-1]) = f([1,n]) = f([-n,1]) = f([-1,-n]) = n^2 + 1. $

Cztery występujące w tych równościach wektory są kolejno parami prostopadłe. Zatem, zgodnie z warunkiem (b),

$ (3) \qquad \begin{split} f([n+1, n-1]) & = f([n,-1]) + f([ 1,n]) =2n^2 + 2,\\ f([1-n, n+1]) & = f([1,n]) + f([-n,1]) =2n^2 + 2,\\ f([-n-1,1-n]) & = f([-n,1]) + f([-1 ,-n]) = 2n^2+2,\\ f([n-1,-n-1]) & = f([-1,-n]) + f([n,-1]) = 2n^2+2. \end{split} $

Jednocześnie mamy równość

$ f([n + 1,n- 1]) = f([n+ 1,0]) + f([0,n - 1]). $

Stąd wobec pierwszego z wzorów (3) oraz założenia indukcyjnego dostajemy:

$ f([n + 1,0]) = f([n + 1,n-1])-f([0,n-1]) = (2n^2+2)-(n-1)^2 = (n+1)^2. $

Podobnie, korzystając z pozostałych trzech wzorów (3), dostajemy równości

$ \begin{split} f([0,n+1]) = (n + 1)^2,& \\ f([-n-1,0]) = (n+1)^2, & \\ f([0,-n-1]) = (n+1)^2. & \end{split} $

Wykazaliśmy w ten sposób, że

$ f([k,0]) = f([0,k]) = k^2 $

dla dowolnej liczby całkowitej $k$ o module nie przekraczającym $n + 1$ . (Dla $|k| = n+1$ są to otrzymane przed chwilą wzory; a dla $|k| \leq n$ jest to konsekwencja założenia indukcyjnego.) Jeśli więc $[x,y]$ jest dowolnym wektorem o współrzędnych całkowitych, których moduły nie przekraczają $n+1$ , to

$ f([x,y]) = f([x,0]) + f([0,y]) = x^2 + y^2. $

To dowodzi stwierdzenia (2) z $n$ zastąpionym przez $n+1$ .

Na mocy zasady indukcji, (2) zachodzi dla każdej liczby naturalnej $n \geq 1$ .

Wobec tego jedyną funkcją spełniającą podane warunki jest funkcja $f$ określona wzorem (1).

XLII OM - III - Zadanie 5

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

III

Nieprzystające okręgi $k_1$ i $k_2$ leżą jeden na zewnątrz drugiego. Wspólne styczne do tych okręgów przecinają prostą wyznaczoną przez ich środki w punktach $A$ i $B$ . Niech $P$ będzie dowolnym punktem okręgu $k_1$ . Dowieść, że istnieje średnica okręgu $k_2$ , której jeden koniec leży na prostej $PA$ , a drugi — na prostej $PB$ .

Rozwiązanie

Oznaczmy środki okręgów $k_1$ i $k_2$ odpowiednio przez $O_1$ i $O_2$ , a ich promienie - przez $r_1$ i $r_2$ . Punkty $A$ i $B$ leżą na prostej $O_1O_2$ , przy czym jest obojętne, która litera oznacza który punkt. Umówmy się, dla ustalenia uwagi, że punkt $B$ leży na odcinku $O_1O_2$ , a punkt $A$ - poza tym odcinkiem.

Weźmy pod uwagę jedną z wspólnych stycznych do okręgów $k_1$ i $k_2$ , przechodzącą przez punkt $A$ oraz jedną z wspólnych stycznych, przechodzącą przez punkt $B$ . Punkty styczności tej pierwszej prostej z okręgami $k_1$ i $k_2$ oznaczmy przez $U_1$ i $U_2$ , a tej drugiej - przez $V_1$ i $V_2$ (rysunek 9 przedstawia sytuację, gdy $r_1 < r_2$ ; ale całe dalsze rozumowanie nie zmienia się, gdy $r_1 > r_2$ - proponujemy Czytelnikowi wykonanie odpowiedniego rysunku).

Z podobieństwa trójkątów prostokątnych $AU_1O_1$ i $AU_2O_2$ oraz z podobieństwa trójkątów $BV_1O_1$ i $BV_2O_2$ wynikają proporcje

$ \frac{|AO_2|}{|AO_1|} = \frac{r_2}{r_1} = \frac{|BO_2|}{|BO_1|}. $

Niech $j_A$ będzie jednokładnością o środku $A$ i stosunku $r_2/r_1$ ; symbolem $j_B$ oznaczmy jednokładność o środku $B$ i stosunku $-r_2/r_1$ . Z uzyskanych przed chwilą proporcji wynika, że

$ j_A(O_1) = O_2 = j_B(O_1). $

Widzimy więc, że obrazom okręgu $k_1$ w każdej z tych jednokładności jest okrąg $k_2$ .

Weźmy pod uwagę punkty

$ Q = j_A(P), \quad R = j_B(P); $

leżą one na okręgu $k_2$ . Punkt $R$ jest obrazem punktu $Q$ w przekształceniu

$ f = j_B \circ j_A^{-1}. $

Przekształcenie $j_A^{-1}$ (odwrotne do $j_A$ ) jest jednokładnością o stosunku $r_1/r_2$ . Zatem $f$ jest izometrią, i to izometrią parzystą (jako złożenie dwóch jednokładności).

Okrąg $k_2$ przechodzi w przekształceniu $j_A^{-1}$ na okrąg $k_1$ : okrąg $k_1$ przechodzi w przekształceniu $j_B$ na okrąg $k_2$ . Tak więc obrazem okręgu $k_2$ w przekształceniu $f$ jest ten sam okrąg $k_2$ . Wobec tego $f$ , jako izometria parzysta, jest obrotem o pewien kąt wokół punktu $O_2$ .

Aby wyznaczyć ten kąt, oznaczmy przez $C_1$ i $D_1$ punkty przecięcia prostej $O_1O_2$ z okręgiem $k_1$ , a przez $C_2$ i $D_2$ punkty przecięcia tej prostej z okręgiem $k_2$ . Ustalmy oznaczenia tak, by rozważane punkty leżały na prostej $O_1O_2$ w porządku: $C_1$ , $O_1$ , $D_1$ , $B$ , $D_2$ , $O_2$ , $C_2$ . Wówczas $j_A(D_1) = C_2$ , $j_B(D_1) = D_2$ , a więc $f(C_2) = D_2$ .

Odcinek $C_2D_2$ jest średnicą okręgu $k_2$ ; obrót $f$ przeprowadza jeden jej koniec na drugi. W takim razie $f$ jest obrotem o $180^\circ$ .

Wcześniej zauważyliśmy, że $f$ przeprowadza punkt $Q$ na $R$ . To znaczy, że także odcinek $QR$ jest średnicą okręgu $k_2$ . Punkt $Q$ leży na prostej $PA$ , a punkt $R$ na prostej $PB$ . Odcinek $QR$ jest więc średnicą, której istnienie należało wykazać.

XLII OM - III - Zadanie 6

Zawody matematyczne:

XLII OM, 1990-1991

Etap:

III

Dowieść, że dla każdej trójki liczb rzeczywistych $x,y,z$ takich, że $x^2+y^2+z^2 = 2$ spełniona jest nierówność $x+y+z\leq 2+xyz$ oraz ustalić, kiedy zachodzi równość.

Rozwiązanie

Przyjmijmy oznaczenia

$ u = yz, \ v = zx, \ w = xy, \ s = x + y + z, \ q = xyz. $

Z założenia, że $x^2 + y^2 + z^2 = 2$ , wynikają równości

$ \begin{split} x^2 + (y-z)^2 & = 2-2u,\\ y^2 + (z-x)^2 & = 2-2v,\\ z^2 + (x-y)^2 & = 2-2w. \end{split} $

Lewe strony są liczbami nieujemnymi. Stąd $u,v,w \leq 1$ . Mamy więc nierówność

$ (1) \qquad (1-u)(1-v)(1-w) \geq 0. $

Z przyjętych oznaczeń wynika, że

$ s^2 = (x + y + z)^2 = x^2 + y^2 + z^2+ 2(yz + zx + xy) = 2 + 2(u + v + w), $

czyli

$ u+v+w = \frac{1}{2}s^2 - 1. $

Ponadto

$ vw+ wu + uv = x^2yz + y^2zx + z^2xy = sq $

oraz

$ uvw = (yz)(zx)(xy) = q^2. $

Mamy zaś udowodnić, że

$ (2) \qquad s-q \leq 2. $

Przekształcamy lewą stronę nierówności (1), korzystając ze związków uzyskanych powyżej:

$ \begin{split} (1 - u)(1 - v)( 1 - w) & = 1-(u+v + w) + (vw + wu+uv)-uvw =\\ & = 1-(\tfrac{1}{2}s^2-1) + sq - q^2=\\ & = 2-\tfrac{1}{2}(s-q)^2-\tfrac{1}{2}q^2. \end{split} $

Zgodnie z (1), jest to liczba nieujemna. Zatem

$ \tfrac{1}{2}(s-q)^2 \leq 2-\tfrac{1}{2} q^2. $

Ponieważ zaś

$ (3) \qquad q^2 \geq 0, $

wnosimy stąd, że $(s-q)^2 \leq 4$ , czyli

$ |s-q| \leq 2. $

Dowodzona nierówność (2) wynika stąd natychmiast.

Aby stała się ona równością, konieczne są znaki równości w szacowaniach (1) i (3). Równość w (3) oznacza, że jedna z liczb $x$ , $y$ , $z$ jest zerem. Niech na przykład $z = 0$ . Wtedy $u = v = 0$ i równość w (1) oznacza, że $w= 1$ , czyli $xy= 1$ . Wreszcie, skoro $q = 0$ , zatem postulowana równość w (2) przybiera postać $s = 2$ , czyli $x+y = 2$ .

Jedynym rozwiązaniem układu równań: $x+ y = 2$ , $xy = 1$ jest $x = y= 1$ .

Przyjęliśmy przykładowo, że $z = 0$ . Oczywiście jeśli $x = 0$ lub $y = 0$ , to - odpowiednio - uzyskujemy związek $y = z = 1$ lub $z = x = 1$ jako konieczny warunek zachodzenia równości w (2).

I na odwrót: jeśli dwie spośród liczb $x$ , $y$ , $z$ są jedynkami, a jedna zerem, to udowodniona nierówność staje się równością. Jest to więc warunek konieczny i dostateczny.