XLIX OM - III etap

III etap XLIX Olimpiady Matematycznej

Załącznik	Wielkość
XLIX OM III etap - Zadania [1]	59.37 KB
XLIX OM III etap - Rozwiązania [2]	81.47 KB

XLIX OM - III - Zadanie 1

Zawody matematyczne:

XLIX OM, 1997-1998

Etap:

III

Znaleźć wszystkie układy liczb całkowitych $(a, b, c, x, y, z)$ spełniające układ równań

$ \left\{\begin{array}{l} a + b + c = xyz\\ x + y + z = abc \end{array}\right. $

oraz warunki $a\geq b \geq c \geq 1$ , $x\geq y\geq z \geq 1$ .

Rozwiązanie

Dodając równania danego układu stronami i przekształcając otrzymujemy równość $A + B + X + Y = 4$ , gdzie

$ \begin{array}{ll} A = (ab - 1)(c - 1), & B = (a- 1)(b- 1),\\ X = (xy-1)(z-1), & Y = (x-1)(y-1). \end{array} $

Liczby $A$ , $B$ , $X$ , $Y$ są liczbami całkowitymi nieujemnymi. Jeśli $c \geq 2$ , to $A \geq 3$ , $B \geq 1$ i w konsekwencji $A = 3$ , $B = 1$ , $X = 0$ , $Y = 0$ , co daje rozwiązanie

$ (a,b,c,x,y,z) = (2,2,2,6,1,1). $

Analogicznie, założenie $z \geq 2$ prowadzi do rozwiązania

$ (a,b,c,x,y,z) = (6,1,1,2,2,2). $

Pozostaje możliwość $c = z = 1$ . Wówczas $A = X = 0$ , więc $B + Y = 4$ . W wyniku prostego rozumowania otrzymujemy dalszych pięć układów $(a,b,c,x,y,z)$ spełniających zadane równania:

$ (3,2,1,3,2,1),\ (3,3,1,7,1,1),\ (5,2,1,8,1,1),\ (7,1,1,3,1,1),\ (8,1,1,5,2,1). $

XLIX OM - III - Zadanie 2

Zawody matematyczne:

XLIX OM, 1997-1998

Etap:

III

Ciąg Fibonacciego $(F_n)$ jest dany wzorami:

$ F_0 = F_1 = 1,\ F_{n+2} = F_n + F_{n+1} \ \textrm{dla}\ n = 0,1, 2,\ldots . $

Wyznaczyć wszystkie pary $(k, m)$ liczb całkowitych $m > k \geq 0$ , dla których w ciągu $(x_n)$ określonym wzorami

$ x_0=\frac{F_k}{F_m}, \quad x_{n+1}= \left\{\begin{array}{cll} \frac{2x_n-1}{1-x_n}&\textrm{gdy}&x_n \neq 1\\ 1&\textrm{gdy}&x_n = 1 \end{array}\right. \quad (n=0,1,2,3,\ldots) $

występuje liczba $1$ .

Rozwiązanie

Załóżmy, że dla pewnej liczby całkowitej $r \geq 0$ zachodzi równość: $x_r = 1$ , przy czym $r$ jest najmniejszym numerem o tej własności. Jeśli $r = 0$ , to $F_k = F_m$ , skąd $k = 0$ , $m = 1$ . Dalej zakładamy, że $r \geq 1$ . W podanym wzorze rekurencyjnym podstawiamy $n = r - 1$ i wyznaczamy $x_{r-1} = 2/3$ . Zgadujemy, że $x_{r-j} = F_{2j}/F_{2j+1}$ dla $j = 0,1,\ldots, r$ i dowodzimy słuszności tego przypuszczenia przez łatwą indukcję. Dla $j = r$ otrzymujemy

$ (1)\qquad x_0=\frac{F_{2r}}{F_{2r+1}}=\frac{F_k}{F_m}. $

Wykażemy teraz, że $m = k + 1$ oraz że $k$ jest liczbą parzystą. (Nietrudno wykazać, że nawet $k = 2r$ .) Gdyby zachodziła nierówność $m \geq k + 2$ , mielibyśmy

$ \frac{F_m}{F_k}-1\geq \frac{F_{k+2}}{F_k}-1=\frac{F_{k+1}}{F_k}\geq 1 >\frac{F_{2r-1}}{F_{2r}}=\frac{F_{2r+1}}{F_{2r}}-1, $

wbrew równości (1). Zatem $m = k + 1$ , czyli $x_0 = F_k/F_{k+1}$ . Gdy wyraz początkowy $x_0$ ma tę postać, z rekurencyjnej definicji ciągu $(x_n)$ , otrzymujemy przez łatwą indukcję wzór

$ (2)\qquad x_n=\frac{F_{k-2n}}{F_{k+1-2n}}\ \textrm{dla}\ n\leq\frac{k}{2}. $

Przypuśćmy, że $k$ jest liczbą nieparzystą i przyjmijmy $\ell = (k-1)/2$ . Wówczas, na mocy wzoru (2), $x_n < 1$ dla $n < \ell$ oraz $x_\ell= F_1/F_2 = 1/2$ , skąd $x_{\ell+1} = 0$ , $x_{\ell+2} = -1$ i wszystkie dalsze wyrazy są ujemne. W ciągu $(x_n)$ nie występuje więc liczba $1$ , wbrew temu, że $x_r = 1$ . Liczba $k$ musi więc być parzysta.

Wykazaliśmy zatem, że jeśli w rozważanym ciągu występuje liczba $1$ , to para $(k,m)$ jest postaci $(2r, 2r + 1)$ dla pewnej liczby całkowitej $r \geq 0$ .

Na odwrót: jeśli $k = 2r$ , $m = 2r + 1$ , gdzie $r$ jest dowolną liczbą całkowitą nieujemną, to $x_0 = F_k/F_{k+1}$ , skąd na mocy wzoru (2) widzimy, że ciąg $(x_n)$ zawiera wyraz $x_r = F_0/F_1 = 1$ .

XLIX OM - III - Zadanie 3

Zawody matematyczne:

XLIX OM, 1997-1998

Etap:

III

Pięciokąt wypukły $ABCDE$ jest podstawą ostrosłupa $ABCDES$ . Płaszczyzna przecina krawędzie $SA$ , $SB$ , $SC$ , $SD$ , $SE$ odpowiednio w punktach $A'$ , $B'$ , $C'$ , $D'$ , $E'$ (różnych od wierzchołków ostrosłupa). Udowodnić, że punkty przecięcia przekątnych czworokątów $ABB'A'$ , $BCC'B'$ , $CDD'C'$ , $DEE'D'$ , $EAA'E'$ leżą na jednej płaszczyźnie.

Rozwiązanie

Oznaczmy przez $\pi$ i $\pi'$ płaszczyzny zawierające odpowiednio punkty $A$ , $B$ , $C$ , $D$ , $E$ oraz $A'$ , $B'$ , $C'$ , $D$ ', $E'$ . Ponadto niech $K$ , $L$ , $M$ , $N$ , $O$ będą punktami przecięcia przekątnych czworokątów $ABB'A'$ , $BCC'B'$ , $CDD'C'$ , $DEE'D'$ , $EAA'E'$ (odpowiednio).

Załóżmy najpierw, że płaszczyzny $\pi$ i $\pi'$ są równoległe. Wówczas stosunek odległości tych płaszczyzn od każdego z punktów $K$ , $L$ , $M$ , $N$ , $O$ jest taki sam. Punkty te leżą więc na jednej płaszczyźnie, równoległej do płaszczyzn $\pi$ i $\pi'$ .

Załóżmy teraz, że płaszczyzny $\pi$ i $\pi'$ nie są równoległe. Oznaczmy przez $\ell$ ich wspólną prostą. Niech $\sigma$ będzie płaszczyzną zawierającą prostą $\ell$ i przechodzącą przez punkt $K$ . Ponieważ punkty $A$ , $C$ , $A'$ , $C'$ są współpłaszczyznowe, więc proste $AC$ i $A'C'$ są albo równoległe, albo przecinają się w punkcie $X$ należącym do prostej $\ell$ .

W pierwszym przypadku, zarówno prosta $KL$ (część wspólna płaszczyzn $AB'C$ , $A'BC'$ ) jak i prosta $\ell$ (część wspólna płaszczyzn $ABC$ , $A'B'C'$ ) są równoległe do prostych $AC$ i $A'C'$ . Proste $KL$ i $\ell$ są więc równoległe.

W drugim przypadku, punkty $K$ , $L$ , $X$ należą do obu płaszczyzn $AB'C$ i $A'BC'$ . Stąd wnioskujemy, że punkty te leżą na jednej prostej, czyli proste $KL$ i $\ell$ mają punkt wspólny. Zatem w obu przypadkach punkt $L$ należy do płaszczyzny $\sigma$ .

Rozważając płaszczyzny $BC'D$ , $B'CD'$ oraz korzystając z tego, że $L \in \sigma$ , poprzez rozumowanie analogiczne do powyższego dowodzimy, że punkt $M$ leży na płaszczyźnie $\sigma$ . Wnioskując tak jak wyżej jeszcze dwukrotnie dostajemy, że punkty $N$ , $O$ również leżą na płaszczyźnie $\sigma$ . Zatem punkty $K$ , $L$ , $M$ , $N$ , $O$ leżą na płaszczyźnie $\sigma$ , co kończy dowód.

XLIX OM - III - Zadanie 4

Zawody matematyczne:

XLIX OM, 1997-1998

Etap:

III

Dowieść, że w ciągu $(a_n)$ określonym wzorami

$ a_1 = 1, \quad a_n = a_{n-1} + a_{[n/2]}\ \textrm{dla}\ n = 2,3,4,\ldots $

występuje nieskończenie wiele liczb podzielnych przez $7$ .

Uwaga: $[n/2]$ jest największą liczbą całkowitą nie przekraczającą $n/2$ .

Rozwiązanie

W ciągu $(a_n)$ są wyrazy podzielne przez $7$ (na przykład $a_5 = 7$ ). Przypuśćmy, że jest ich skończenie wiele; niech $a_k$ będzie ostatnim z tych wyrazów. Oznaczmy: $a_k = x$ , $a_{2k-1} = y$ , $a_{4k-3} = z$ ; liczba $x$ dzieli się przez $7$ , a liczby $y$ i $z$ - nie.

Zachodzą równości:

$ \begin{array}{llllll} a_{2k}&=a_{2k-1}+a_{k}&=x+y,&a_{2k+1}&=a_{2k}+a_{k}&=2x+y,\\ a_{4k-2}&=a_{4k-3}+a_{2k-1}&=y+z,&a_{4k-1}&=a_{4k-2}+a_{2k-1}&=2y+z,\\ a_{4k}&=a_{4k-1}+a_{2k}&=x+3y+z,&a_{4k+1}&=a_{4k}+a_{2k}&=2x+4y+z,\\ a_{4k+2}&=a_{4k+1}+a_{2k+1}&=4x+5y+z,&a_{4k+3}&=a_{4k+2}+a_{2k+1}&=6x+6y+z,\\ \end{array} $

Przy dzieleniu przez $7$ liczby $a_{4k-3},a_{4k-2},\ldots,a_{4k+3}$ dają więc takie same reszty jak liczby $z, z + y, \ldots , z + 6y$ . Ponieważ $y$ nie dzieli się przez $7$ , wszystkie te reszty są różne. Zatem jedna z tych siedmiu liczb jest podzielna przez $7$ , wbrew przypuszczeniu, że $a_k$ jest ostatnim takim wyrazem. Sprzeczność kończy dowód.

XLIX OM - III - Zadanie 5

Zawody matematyczne:

XLIX OM, 1997-1998

Etap:

III

Punkty $D$ i $E$ leżą na boku $AB$ trójkąta $ABC$ i spełniają warunek

$ \frac{AD}{DB}\cdot\frac{AE}{EB}=\left(\frac{AC}{CB}\right)^2. $

Udowodnić, że $\measuredangle ACD =\measuredangle BCE$ .

Rozwiązanie

Oznaczmy przez $\ell$ prostą przechodzącą przez punkt $A$ i równoległą do $BC$ . Proste $CD$ i $CE$ przecinają prostą $\ell$ odpowiednio w punktach $P$ i $Q$ .

Z warunków danych w zadaniu otrzymujemy

$ \left( \frac{AC}{CB} \right)^2 = \frac{AD}{DB}\cdot\frac{AE}{EB}=\frac{AP}{CB}\cdot\frac{AQ}{CB}, $

skąd

$ \frac{AP}{AC}=\frac{AC}{AQ}. $

Ponieważ $\measuredangle CAP = \measuredangle QAC$ , więc z powyższej równości wynika, że trójkąty $CAP$ i $QAC$ są podobne. Zatem

$ \measuredangle ACD = \measuredangle ACP = \measuredangle AQC = \measuredangle BCE . $

XLIX OM - III - Zadanie 6

Zawody matematyczne:

XLIX OM, 1997-1998

Etap:

III

Rozważamy na płaszczyźnie kwadraty jednostkowe, których wierzchołki mają obie współrzędne całkowite. Niech $S$ będzie szachownicą, której polami są wszystkie kwadraty jednostkowe zawarte w kole określonym nierównością $x^2+y^2 \leq 1998^2$ . Na wszystkich polach szachownicy piszemy liczbę $+1$ . Wykonujemy ciąg operacji. Każda z nich polega na wybraniu dowolnego rzędu poziomego, pionowego lub ukośnego i zmianie znaków wszystkich liczb napisanych na polach wybranego rzędu. (Rząd ukośny tworzą wszystkie pola szachownicy $S$ , których środki leżą na pewnej prostej przecinającej osie układu współrzędnych pod kątem $45^\circ$ .)

Rozstrzygnąć, czy w ten sposób można doprowadzić do sytuacji, w której na jednym polu będzie napisana liczba $-1$ , a na pozostałych $+1$ .

Rozwiązanie

Odpowiedź: nie można.

Przypuśćmy, że da się uzyskać konfigurację z dokładnie jednym polem $P_1$ , na którym jest napisana liczba $-1$ . Z uwagi na standardowe symetrie szachownicy $S$ można założyć, że pole $P_1$ ma środek $(a-\frac{1}{2},b-\frac{1}{2})$ , gdzie $a \geq b \geq 1$ ( $a$ , $b$ - liczby całkowite). Punkt ( $a$ , $b$ ) jest wierzchołkiem pola $P_1$ , więc $a^2 + b^2 < 1998^2$ .

Wykażemy, że kwadrat jednostkowy $P_2$ o środku $(a-\frac{3}{2},b+\frac{1}{2})$ także jest polem szachownicy $S$ .

Jeżeli $a > b$ , to $(a-1)^2 + (b+1)^2 \leq a^2 + b^2 \leq 1998^2$ . Jeśli zaś $a = b$ , to nierówność $a^2 + b^2 = 2a^2 \leq 1998^2$ na pewno nie jest równością; stąd wynika, że

$ (a - 1)^2 + (b + 1)^2 = 2a^2 + 2 \leq 1998^2. $

Zatem punkt $(a-1,b+1)$ , czyli prawy górny wierzchołek kwadratu $P_2$ , należy do koła, o którym mowa w zadaniu. W konsekwencji cały kwadrat $P_2$ zawiera się w tym kole, czyli jest polem szachownicy $S$ .

Rozważmy teraz osiem kwadratów jednostkowych, z których dwa są polami $P_1$ i $P_2$ , ułożonych tak jak na rysunku obok. Ponieważ kwadraty $P_1$ i $P_2$ są polami szachownicy $S$ , więc pozostałe sześć kwadratów również.

Zauważmy, że każdy rząd pionowy, poziomy lub ukośny zawiera albo dokładnie dwa spośród ośmiu danych pól, albo nie zawiera żadnego z nich. Iloczyn liczb napisanych na tych ośmiu polach nie ulega wobec tego zmianie w wyniku wykonywanych operacji i stale jest równy $1$ . Nie jest więc możliwe, by w pewnym momencie na polu $P_1$ znalazła się liczba $-1$ , a na pozostałych $+1$ .