Środkowo-Europejska Olimpiada Matematyczna

MEMO to Środkowo-Europejska Olimpiada Matematyczna (Middle European Mathematical Olympiad) dla szkół średnich. Pierwsze zawody pod nazwą MEMO odbyły się w 2007r., ale historia Olimpiady jest dłuższa: Od 1978 do 2006 odbywały się co roku Austriacko-Polskie Zawody Matematyczne [1]. W 2007 roku do Austrii i Polski dołączyły inne kraje i po raz pierwszy odbyła się Środkowo-Europejska Olimpiada Matematyczna. Jej gospodarzem była Austria (Eisenstadt). Druga edycja MEMO miała miejsce w 2008 roku w Ołomuńcu w Czechach i startowały w nich reprezentacje 9 państw: Austrii, Chorwacji, Czech, , Niemiec, Polski, Słowacji, Słowenii, Szwajcarii i Węgier. W 2009 r. gospodarzem MEMO była Polska i do udziału w zawodach zaprosiła 10 reprezentacji: oprócz wymienionych wcześniej wystąpiła również drużyna Litwy.

Drużyna składa się z 6 zawodników. Zawodnicy nie mogą być członkami delegacji na Międzynarodową Olimpiadę Matematyczną [2] (IMO) w danym roku. Muszą też być uczniami w czasie trwania zawodów, które odbywają się we wrześniu lub w październiku. Olimpiada jest dwudniowa: pierwszego dnia odbywają się zawody indywidualne, a następnego - drużynowe. W zawodach indywidualnych rozwiązywane są 4 zadania, na co uczestnicy mają 5 godzin, zaś na drużynowych - 8 zadań. W latach 2007 i 2008 drużyny miały do rozwiązania 4 zadania, ale w Ołomuńcu postanowiono zwiększyć tę liczbę. Za zadanie można uzyskać od 0 do 8 pkt. Sposób oceniania jest podobny do stosowanego na IMO.

I MEMO

Zawody matematyczne:

I MEMO, 2007

Zadania z I Środkowo-Europejskiej Olimpiady Matematycznej

Załącznik	Wielkość
I MEMO - Zadania z rozwiązaniami [3]	147.6 KB

I MEMO - Zadanie 1

Zawody matematyczne:

I MEMO, 2007

Dodatnie liczby rzeczywiste $a$ , $b$ , $c$ , $d$ spełniają warunek

$ a+b+c+d=4. $

Wykazać, że

$ a^2bc+b^2cd+c^2da+d^2ab\le 4. $

Rozwiązanie

Obie strony nierówności nie zmienią się, jeżeli dokonamy cyklicznej permutacji zmiennych $a$ , $b$ , $c$ , $d$ . Możemy zatem przyjąć, że $a\ge c$ , gdyż w przeciwnym razie dokonamy cyklicznej permutacji $(a,b,c,d)\to(c,d,a,b)$ . Dalej, jeżeli $a\ge c$ oraz $b<d$ , to przeprowadzamy permutację $(a,b,c,d)\to(b,c,d,a)$ i otrzymujemy układ, w którym $a\ge c$ i $b\ge d$ .

Będziemy więc dalej zakładać, że $a\ge c$ oraz $b\ge d$ . Wynika stąd w szczególności nierówność

$ (a-c)(b-d)\ge 0, \quad\hbox{czyli równoważnie}\quad ab+cd\ge bc+ad. $

Wobec tego korzystając dwukrotnie z nierówności $xy\le({x+y\over 2})^2$ uzyskujemy

$ \begin{split}a^2bc+b^2cd+c^2da+d^2ab& =ac(ab+cd)+bd(bc+ad)\le \cr &\le ac(ab+cd)+bd(ab+cd)= \cr &=(ac+bd)(ab+cd)\le\Bigl({ac+bd+ab+cd\over 2}\Bigr)^2= \cr &=\Bigl({(a+d)(b+c)\over 2}\Bigl)^2\le \Bigl({({a+d+b+c\over 2})^2\over 2}\Bigr)^2=4, \end{split} $

co kończy rozwiązanie zadania.

I MEMO - Zadanie 2

Zawody matematyczne:

I MEMO, 2007

Rozważamy zbiór $n$ kul ponumerowanych liczbami $1, 2, 3, \ldots, n$ . Danych jest $k>1$ takich zbiorów kul. Chcemy pokolorować wszystkie kule dwoma kolorami, białym i czarnym, tak aby

kule oznaczone tym samym numerem były tego samego koloru;
dowolny podzbiór $k+1$ kul z (niekoniecznie różnymi)
numerami $a_1$ , $a_2$ , $\ldots$ , $a_{k+1}$ spełniającymi
warunek

$ a_1+a_2+\ldots+a_k=a_{k+1} $

musiał zawierać co najmniej jedną kulę każdego koloru.

Dla każdego $k$ znaleźć największe możliwe $n$ , dla którego istnieje pokolorowanie spełniające powyższe warunki.

Rozwiązanie

Dla ustalenia uwagi przyjmijmy, że kule oznaczone numerem 1 są białe. Rozpatrzymy dwa przypadki:

1. Kule z numerem 2 są czarne.

Na mocy warunku b) kule z numerem $1+1+\ldots+1=k$ są czarne oraz kule z numerem $2+2+\ldots+2=2k$ są białe. Skoro kule z numerami 1 i $2k$ są białe, zależność

$ (k+1)+\underbrace{1+\ldots+1}_{k-1}=2k $

wskazuje, że kule z numerami $k+1$ są czarne.

Jednakże kule z numerami $2k$ i 1 są wówczas białe, zaś kule z numerami $k+1$ i 2 są czarne. Wobec równości

$ 2k+\underbrace{1+\ldots+1}_{k-1}=(k+1)+\underbrace{2+\ldots+2}_{k-1}=3k-1 $

niezależnie od koloru kul z numerem $3k-1$ dochodzimy do sprzeczności z warunkiem b), jeżeli $n\ge 3k-1$ . Zatem w tym przypadku mamy $n\le 3k-2$ .

2. Kule z numerem 2 są białe.

Dowolna liczba całkowita z przedziału $\langle k; 2k\rangle$ może być przedstawiona w postaci sumy $k$ liczb, z których każda jest równa 1 lub 2. Skoro kule z numerami 1 i 2 są białe, na podstawie warunku b) kule z numerami $k$ , $k+1$ , $\ldots$ , $2k$ są czarne. W takim razie kule z numerem $k+k+\ldots+k=k^2$ są białe. Kule z numerami $k$ i $k+1$ są czarne, zaś kule z numerami 1 i $k^2$ - białe. Wobec tego równości

$ k+\underbrace{(k+1)+(k+1)+\ldots+(k+1)}_{k-1}= k^2+\underbrace{1+1+\ldots+1}_{k-1}=k^2+k-1 $

dowodzą, że dla obu możliwych kolorów kul z numerem $k^2+k-1$ otrzymujemy sprzeczność z warunkiem b), o ile $n\ge k^2+k-1$ . Musi więc zachodzić nierówność $n\le k^2+k-2$ .

Zatem liczba $n$ nie przekracza większej z liczb $3k-2$ i $k^2+k-2$ . Jednakże dla $k\ge 2$ mamy $k^2+k-2\ge 3k-2$ i w efekcie $n\le k^2+k-2$ .

Wykażemy, że dla $n=k^2+k-2$ istnieje pokolorowanie kul spełniające żądane warunki. Weźmy mianowicie pod uwagę następujące pokolorowanie:

$ \begin{split} \hbox{numery kul białych:}\quad & 1,\,2,\,\ldots,\,k-2,\,k-1,\,k^2,\,k^2+1,\,\ldots,\,k^2+k-2, \\ \hbox{numery kul czarnych:}\quad & k,\,k+1,\,k+2,\ldots,\,k^2-2,\,k^2-1. \\ \end{split} $

Pokolorowanie to spełnia warunek b) dany w treści zadania. Rzeczywiście, jeżeli rozpatrzymy $k$ kul czarnych, to numer każdej z nich jest nie mniejszy niż $k$ i wobec tego suma tych numerów jest nie mniejsza niż $k^2$ , zaś kula o takim numerze jest biała. Niech z kolei $a_1$ , $a_2$ , $\ldots$ , $a_k$ będą numerami białych kul. Mamy udowodnić, że jeżeli $s=a_1+a_2+\ldots+a_k\le k^2+k-2$ , to kule o numerze $s$ są czarne. Jeśli liczby $a_1$ , $a_2$ , $\ldots$ , $a_k$ są mniejsze niż $k$ , to liczba $s$ leży w przedziale $\langle k; k^2-k\rangle$ , jeśli natomiast jedna z liczb $a_1$ , $a_2$ , $\ldots$ , $a_k$ jest nie mniejsza niż $k^2$ , to $s\ge k^2+k-1$ . To kończy dowód faktu, że rozpatrywane pokolorowanie ma żądane własności.

Odpowiedź: Szukana największa wartość wynosi $n=k^2+k-2$ .

I MEMO - Zadanie 3

Zawody matematyczne:

I MEMO, 2007

Dany jest okrąg $k$ oraz okręgi $k_1$ , $k_2$ , $k_3$ , $k_4$ o środkach odpowiednio $O_1$ , $O_2$ , $O_3$ , $O_4$ leżących na okręgu $k$ . Dla $i=1,2,3,4$ okręgi $k_i$ oraz $k_{i+1}$ (gdzie $k_5=k_1$ ) przecinają się w punktach $A_i$ i $B_i$ w taki sposób, że $A_i$ leży na okręgu $k$ . Zakładamy, że punkty $O_1$ , $A_1$ , $O_2$ , $A_2$ , $O_3$ , $A_3$ , $O_4$ , $A_4$ leżą w takiej kolejności na okręgu $k$ i są parami różne. Wykazać, że czworokąt $B_1B_2B_3B_4$ jest prostokątem.

Rozwiązanie

Punkty $A_2$ i $B_2$ , jako punkty przecięcia okręgów $k_2$ i $k_3$ , są symet\-ryczne względem prostej $O_2O_3$ łączącej środki tych okręgów (rys. 1). Uzyskujemy stąd równość

$ \measuredangle A_2O_2O_3=\measuredangle B_2O_2O_3. (1) \qquad $

Ponadto łuki $A_2O_3$ i $O_3A_3$ okręgu $k$ mają jednakowe długości, więc oparte na nich kąty mają równe miary. Innymi słowy,

$ \measuredangle A_2O_2O_3=\measuredangle A_3O_2O_3. (2) \qquad $

Z równości (1) i (2) wnioskujemy, że punkty $O_2$ , $B_2$ , $A_3$ leżą na jednej prostej. Podobnie dowodzimy, że punkty $O_1$ , $B_4$ , $A_3$ leżą na jednej prostej. Rozpatrując teraz czworokąt $A_1O_2A_3O_1$ wpisany w okrąg $k$ stwierdzamy, że

$ (3) \qquad \measuredangle B_2O_2A_1+\measuredangle B_4O_1A_1= \measuredangle A_3O_2A_1+\measuredangle A_3O_1A_1=180^\circ. $

Na mocy zależności pomiędzy kątami środkowymi i wpisanymi otrzymujemy

$ \begin{split} \measuredangle B_2B_1A_1+\measuredangle B_4B_1A_1 &=(180^\circ-\measuredangle B_2A_2A_1)+(180^\circ-\measuredangle B_4A_4A_1)= \\ &=(180^\circ-\xfrac{1}{2}\measuredangle B_2O_2A_1)+ (180^\circ-\xfrac{1}{2}\measuredangle B_4O_1A_1)= \\ &=360^\circ-\xfrac{1}{2} (\measuredangle B_2O_2A_1+\measuredangle B_4O_1A_1). \end{split} $

W połączeniu z równością (3) prowadzi to do wniosku, że

$ \measuredangle B_2B_1A_1+\measuredangle B_4B_1A_1=270^\circ, $

a to oznacza, że $\measuredangle B_4B_1B_2=90^\circ$ . Rozumując analogicznie wykazujemy, że kąty $\measuredangle B_1B_2B_3$ , $\measuredangle B_2B_3B_4$ i $\measuredangle B_3B_4B_1$ są proste. Wynika stąd teza zadania.

I MEMO - Zadanie 4

Znaleźć wszystkie pary $(x,y)$ liczb całkowitych dodatnich spełniających równanie

$ x!+y!=x^y\,. $

Rozwiązanie

Rozwiązanie podzielimy na dwa przypadki: $x\le y$ oraz $x>y$ .

1. $x\le y$ .

Ponieważ $x!+y!\ge 1+1=2$ , więc liczba $x$ nie może być równa 1. Ponadto liczby $x!$ i $y!$ są podzielne przez $x-1$ , co oznacza, że

$ (1) \qquad x-1\,|\,x!+y!=x^y\,. $

Jednakże liczby $x-1$ i $x$ nie mają wspólnych czynników pierwszych; to samo można wobec tego powiedzieć o liczbach $x-1$ i $x^y$ . Podzielność (1) jest więc możliwa jedynie w przypadku $x-1=1$ , czyli $x=2$ .

Pozostaje zbadać równanie $2+y!=2^y$ . Równanie to nie ma rozwiązań dla $y\ge 4$ , gdyż wówczas liczby $y!$ oraz $2^y$ są podzielne przez 4, nie mogą zatem różnić się o 2. Obliczamy jeszcze, że

$ 2+1!=3\ne 2=2^1, \qquad 2+2!=4=2^2, \qquad 2+3!=8=2^3. $

Widzimy, że liczby $y=2$ i $y=3$ mają żądaną własność, a liczba $y=1$ - nie.

2. $x>y$ .

W tej sytuacji otrzymujemy równanie

$ x^y=x!+y!=y!\cdot[(y+1)(y+2)\ldots(x-1)x+1]. $

Oznaczmy $L=(y+1)(y+2)\ldots(x-1)x+1$ ; liczba $L$ jest więc dzielnikiem liczby $x^y$ . Z nierówności $L>1$ wynika, że liczby $L$ i $x$ mają wspólny dzielnik pierwszy $p$ . Z drugiej strony liczba $L-1$ jest podzielna przez $x$ i tym bardziej jest podzielna przez $p$ . Stąd wniosek, że liczby $L-1$ i $L$ są podzielne przez $p$ , co nie może mieć miejsca.

Otrzymana sprzeczność wskazuje, że w tym przypadku nie ma rozwiązań.

Odpowiedź: Rozwiązaniami zadania są pary $(x,y)=(2,2)$ i $(x,y)=(2,3)$ .

I MEMO - Zadanie 5

Zawody matematyczne:

I MEMO, 2007

Dodatnie liczby rzeczywiste $a$ , $b$ , $c$ , $d$ spełniają warunki

$ {1\over 2}\le a,b,c,d\le 2\qquad\hbox{oraz}\qquad abcd=1. $

Znaleźć największą możliwą wartość wyrażenia

$ \Bigl(a+{1\over b}\Bigr)\Bigl(b+{1\over c}\Bigr) \Bigl(c+{1\over d}\Bigr)\Bigl(d+{1\over a}\Bigr). $

Rozwiązanie

Korzystając z równości $abcd=1$ obliczamy, że

$ \begin{split}\Bigl(a+{1\over b}\Bigl)\Bigr(c+{1\over d}\Bigr)&= ac+{a\over d}+{c\over b}+{1\over bd}= ac+a^2bc+ac^2d+ac=ac(ab+2+cd), \cr \Bigl(b+{1\over c}\Bigl)\Bigr(d+{1\over a}\Bigr)&= bd+{b\over a}+{d\over c}+{1\over ac}= bd+b^2cd+abd^2+bd=bd(bc+2+ad), \end{split} $

skąd otrzymujemy

$ \Bigl(a+{1\over b}\Bigr)\Bigl(b+{1\over c}\Bigr) \Bigl(c+{1\over d}\Bigr)\Bigl(d+{1\over a}\Bigr) =(ab+2+cd)(bc+2+ad). $

Ponadto

$ \begin{split}ab+2+cd&= ab+2+{1\over ab}=\Bigl(\sqrt{ab}+{1\over\sqrt{ab}}\Bigr)^2, \cr bc+2+ad&= bc+2+{1\over bc}=\Bigl(\sqrt{bc}+{1\over\sqrt{bc}}\Bigr)^2, \end{split} $

co implikuje równość

$ \begin{split}\Bigl(a&+{1\over b}\Bigr)\Bigl(b+{1\over c}\Bigr) \Bigl(c+{1\over d}\Bigr)\Bigl(d+{1\over a}\Bigr) =\Bigl[\Bigl(\sqrt{ab}+{1\over\sqrt{ab}}\Bigr) \Bigl(\sqrt{bc}+{1\over\sqrt{bc}}\Bigr)\Bigr]^2= \cr &=\Bigl(\sqrt{ab^2c}+\sqrt{{a\over c}}+ \sqrt{{c\over a}}+{1\over\sqrt{ab^2c}}\Bigl)^2= \Bigl(\sqrt{{b\over d}}+\sqrt{{d\over b}}+ \sqrt{{a\over c}}+\sqrt{{c\over a}}\Bigr)^2. \end{split} $

Doszliśmy w ten sposób do przedstawienia

$ (1) \qquad \Bigl(a+{1\over b}\Bigr)\Bigl(b+{1\over c}\Bigr) \Bigl(c+{1\over d}\Bigr)\Bigl(d+{1\over a}\Bigr)= \Bigl[f\Bigl(\sqrt{{b\over d}}\Bigr)+ f\Bigl(\sqrt{{a\over c}}\Bigr)\Bigr]^2, $

gdzie oznaczyliśmy $f(t)=t+1/t$ .

Na mocy warunku ${1\over 2}\le a,b,c,d \le 2$ liczby $\sqrt{{b\over d}}$ i $\sqrt{{a\over c}}$ należą do przedziału $\langle {1\over 2};2 \rangle$ . Dla dowolnych liczb dodatnich $t_1$ , $t_2$ mamy

$ f(t_1)-f(t_2)=t_1-t_2+{1\over t_1}-{1\over t_2}= (t_1-t_2)+{t_2-t_1\over t_1t_2}= (t_1-t_2)\Bigl(1-{1\over t_1t_2}\Bigr). $

Z powyższej zależności wynika, że funkcja $f$ jest malejąca w przedziale $(0;1 \rangle$ oraz rosnąca w przedziale $\langle 1;\infty)$ . Stąd wniosek, że

$ f(t)\le\max\{f(\frac{1}{2}),f(2)\} =\frac{5}{2} $

dla dowolnej liczby $t\in\langle \frac{1}{2};2 \rangle$ . Zatem z równości (1) wynika, że

$ (2) \qquad \Bigl(a+{1\over b}\Bigr)\Bigl(b+{1\over c}\Bigr) \Bigl(c+{1\over d}\Bigr)\Bigl(d+{1\over a}\Bigr) \le (\frac{5}{2}+\frac{5}{2})^2=25. $

Na koniec pozostaje zauważyć, że dla $a=b=2$ , $c=d=\frac{1}{2}$ nierówność (2) staje się równością (czynniki lewej strony są odpowiednio równe $\frac{5}{2}$ , 4, $\frac{5}{2}$ , 1).

Odpowiedź: Największą możliwą wartością badanego wyrażenia jest 25.

I MEMO - Zadanie 6

Zawody matematyczne:

I MEMO, 2007

Niech $P$ będzie dowolnym zbiorem pięciu różnych punktów płaszczyzny, z których żadne trzy nie leżą na jednej prostej. Oznaczmy przez $a(P)$ liczbę trójkątów ostrokątnych, których wierzchołki należą do zbioru $P$ . Wyznaczyć największą możliwą wartość $a(P)$ .

Rozwiązanie

Rozpoczniemy od wykazania nierówności $a(P)\le 7$ .

Liczba wszystkich trójkątów o wierzchołkach należących do 5-elementowego zbioru $P$ wynosi ${5\choose 3}=10$ , wystarczy zatem udowodnić, że istnieją co najmniej 3 trójkąty nieostrokątne o wierzchołkach należących do tego zbioru.

Jeżeli $P$ jest zbiorem pięciu punktów płaszczyzny, z których żadne trzy nie leżą na jednej prostej, to możliwe są następujące trzy sytuacje:

Punkty zbioru $P$ są wierzchołkami pięciokąta wypukłego.
Jeden punkt zbioru $P$ leży wewnątrz czworokąta wypukłego wyznaczonego przez pozostałe cztery punkty zbioru $P$ .
Dwa punkty zbioru $P$ leżą wewnątrz trójkąta wyznaczonego przez trzy pozostałe punkty zbioru $P$ .

Rozpatrzymy po kolei trzy powyższe przypadki.

Niech $ABCDE$ będzie rozpatrywanym pięciokątem wypukłym. Jeżeli co najmniej trzy jego kąty wewnętrzne są nieostre, to każdy z trójkątów, którego wierzchołkami są trzy kolejne wierzchołki pięciokąta wyznaczające nieostry kąt wewnętrzny tego pięciokąta, jest trójkątem nieostrokątnym - są więc co najmniej trzy takie trójkąty.

Z drugiej strony, rozważany pięciokąt wypukły musi mieć przynajmniej dwa nieostre kąty wewnętrzne. Gdyby bowiem miał on cztery ostre kąty wewnętrzne, np. $\measuredangle A,\,\measuredangle B,\,\measuredangle C,\,\measuredangle D<90^\circ$ , to otrzymalibyśmy

$ \measuredangle A+\measuredangle B+\measuredangle C+\measuredangle D+\measuredangle E< 4\cdot 90^\circ+180^\circ=540^\circ, $

co nie jest możliwe, gdyż suma kątów wewnętrznych pięciokąta wynosi $540^\circ$ .

Przyjmujemy więc dalej, że pięciokąt $ABCDE$ ma dokładnie dwa nieostre kąty wewnętrzne. Są to albo dwa sąsiednie kąty, na przykład $\measuredangle A$ i $\measuredangle B$ (rys. 2), albo dwa niesąsiednie kąty, powiedzmy $\measuredangle A$ i $\measuredangle C$ (rys. 3).

W pierwszym przypadku trójkąty $EAB$ i $ABC$ są nieostrokątne oraz co najmniej jeden z trójkątów $EBC$ , $BCD$ , $CDE$ , $DEB$ jest nieostrokątny (w przeciwnym razie wszystkie kąty wewnętrzne czworokąta $BCDE$ byłyby ostre, i w efekcie ich suma byłaby mniejsza od $360^\circ$ , co daje sprzeczność).

Natomiast w drugim przypadku trójkąty $EAB$ i $BCD$ są nieostrokątne oraz - tak jak poprzednio - przynajmniej jeden z trójkątów $EAC$ , $ACD$ , $CDE$ , $DEA$ jest nieostrokątny.

To kończy rozpatrywanie przypadku 1.
Niech punkt $E$ leży wewnątrz czworokąta wypukłego $ABCD$ . Nie ograniczając ogólności rozumowania możemy przyjąć, że punkt $E$ leży wewnątrz trójkąta $ABC$ (rys. 4). Wtedy suma kątów $\measuredangle AEB$ , $\measuredangle BEC$ i $\measuredangle CEA$ jest równa $360^\circ$ . Kąty te są mniejsze od $180^\circ$ , zatem co najmniej dwa z tych kątów są nieostre. To oznacza, że co najmniej dwa z trójkątów $AEB$ , $BEC$ , $CEA$ są nieostrokątne. Ponadto co najmniej jeden z kątów wewnętrznych czworokąta wypukłego $ABCD$ jest nieostry, czyli jeden z trójkątów $DAB$ , $ABC$ , $BCD$ , $CDA$ jest nieostrokątny.

Zatem istnieją co najmniej trzy trójkąty nieostrokątne o wierzchołkach należących do zbioru $\{A,B,C,D,E\}$ .
Niech punkty $D$ i $E$ leżą wewnątrz trójkąta $ABC$ (rys. 5). Wówczas rozumując tak jak w przypadku 2. dochodzimy do wniosku, że co najmniej dwa z trójkątów $ADB$ , $BDC$ , $CDA$ są nieostrokątne oraz co najmniej dwa z trójkątów $AEB$ , $BEC$ , $CEA$ są nieostrokątne. Łącznie więc istnieją przynajmniej cztery trójkąty nieostrokątne o wierzchołkach należących do zbioru $\{A,B,C,D,E\}$ .

To kończy dowód nierówności $a(P)\le 7$ . Pozostaje wskazać taki zbiór $P$ złożony z 5 punktów płaszczyzny, z których żadne trzy nie leżą na jednej prostej, że $a(P)=7$ .

Rozpatrzmy w tym celu okrąg $k$ o środku $O$ oraz trzy różne punkty $A$ , $B$ , $C$ leżące na tym okręgu i spełniające równości

$ \measuredangle AOB=\measuredangle BOC=\alpha, $

gdzie $\alpha$ jest kątem mniejszym od $45^\circ$ . Następnie niech odcinki $AX$ , $BY$ , $CZ$ będą średnicami okręgu $k$ . Wybierzmy dowolny punkt $D$ wewnątrz trójkąta ograniczonego prostymi $BY$ , $CY$ , $AX$ oraz niech $E$ będzie punktem symetrycznym do punktu $D$ względem średnicy $BY$ (rys. 6).

Wykażemy, że dla zbioru $P=\{A,B,C,D,E\}$ zachodzi równość $a(P)=7$ .

Trójkąt $ACD$ jest ostrokątny, gdyż

$ \begin{split} \measuredangle ADC & <\measuredangle AOC=2\alpha<90^\circ, \\ \measuredangle ACD & <\measuredangle ACY<\measuredangle ACX=90^\circ, \\ \measuredangle CAD & <\measuredangle CAY<\measuredangle CAZ=90^\circ. \end{split} $

Analogicznie trójkąt $ACE$ jest ostrokątny. Dalej, trójkąt $ABE$ jest ostrokątny, mamy bowiem

$ \begin{split} \measuredangle BAE & <\measuredangle BAY=90^\circ , \\ \measuredangle ABE & <\measuredangle ABY<\measuredangle ABX=90^\circ, \\ \measuredangle AEB & <\measuredangle AEC<\measuredangle AOC=2\alpha<90^\circ. \end{split} $

Podobnie stwierdzamy, że trójkąt $BCD$ jest ostrokątny. Następnie trójkąt $ABD$ jest ostrokątny:

$ \begin{split} \measuredangle ABD & <\measuredangle ABX=90^\circ, \\ \measuredangle BAD & <\measuredangle BAY=90^\circ, \\ \measuredangle ADB & <\measuredangle ADC<\measuredangle AOC=2\alpha<90^\circ. \end{split} $

Tak samo dowodzimy, że trójkąt $BCE$ jest ostrokątny. Wreszcie trójkąt $BDE$ jest równoramienny oraz kąt pomiędzy jego ramionami spełnia nierówność $\measuredangle DBE< \measuredangle XBZ=\alpha<45^\circ$ , zatem trójkąt ten jest ostrokątny.

Wskazaliśmy tym samym 7 trójkątów ostrokątnych ( $ACD$ , $ACE$ , $ABD$ , $ABE$ , $BCD$ , $BCE$ i $BDE$ ) o wierzchołkach należących do zbioru $P$ . To w połączeniu z pierwszą częścią kończy rozwiązanie zadania.

Odpowiedź: Największa możliwa wartość $a(P)$ wynosi 7.

I MEMO - Zadanie 7

Zawody matematyczne:

I MEMO, 2007

Czworościan $T$ nazwiemy dobrym, jeżeli wszystkie długości jego krawędzi są różnymi dodatnimi liczbami całkowitymi, z których jedna jest równa 2, a jedna 3. Oznaczmy przez $s(T)$ sumę długości krawędzi dobrego czworościanu $T$ .

Znaleźć wszystkie takie dodatnie liczby całkowite $n$ , dla których istnieje dobry czworościan $T$ spełniający warunek $s(T)=n$ .

Ile istnieje nieprzystających dobrych czworościanów $T$ , dla których $s(T)=2007$ ?

Uwaga: Nie jest konieczne dowodzenie, że rozważane czworościany są niezdegenerowane, tzn. posiadają dodatnią objętość.

Rozwiązanie

Dobre czworościany dzielimy na dwie kategorie:

Krawędzie o długościach 2 i 3 nie należą do jednej ściany.

Oznaczmy wierzchołki danego czworościanu przez $A$ , $B$ , $C$ , $D$ tak, by $AB=2$ , $CD=3$ oraz by krawędź $AC$ była najkrótszą wśród czterech pozostałych krawędzi (rys. 7). Wszystkie krawędzie rozpatrywanego czworościanu mają różne długości całkowite, więc w szczególności $AC\ge 4$ .

(Równość $AC=1$ jest wykluczona, gdyż wraz z nierównością trójkąta prowadziłaby ona do wniosku, że $|AB-CB|<AC=1$ , wbrew temu, że $AB$ i $CB$ są różnymi liczbami całkowitymi.)

Z nierówności trójkąta otrzymujemy $BC<AB+AC=AC+2$ . Ponadto krawędź $AC$ jest krótsza od krawędzi $BC$ , skąd wynika, że $BC=AC+1$ .

Następnie raz jeszcze korzystając z nierówności trójkąta uzyskujemy $AD<AC+CD=AC+3$ . Ponadto $AD>AC$ oraz liczba $AC+1$ jest długością krawędzi $BC$ . Zatem $AD=AC+2$ . Wreszcie

$ |BD-(AC+2)|=|BD-AD|<AB=2, $

czyli długość $BD$ jest jedną z liczb $AC+1$ , $AC+2$ , $AC+3$ . Dwie pierwsze liczby są długościami odpowiednio krawędzi $BC$ i $AD$ , więc $BD=AC+3$ .

Udowodniliśmy w ten sposób, że

$ AB=2, \quad CD=3, \quad AC=k, \quad BC=k+1, \quad AD=k+2, \quad BD=k+3 $

dla pewnej liczby całkowitej $k\ge 4$ . Suma długości krawędzi czworościanu $ABCD$ wynosi w tym przypadku

$ 2+3+k+(k+1)+(k+2)+(k+3)=4k+11. $

Suma ta może być równa dowolnej liczbie całkowitej nie mniejszej od 27 oraz dającej resztę 3 z dzielenia przez 4, i każdej takiej liczbie odpowiada dokładnie jeden czworościan należący do kategorii 1.
Krawędzie o długościach 2 i 3 należą do jednej ściany.

Oznaczmy dany czworościan przez $ABCD$ i przyjmijmy, że $BC=2$ oraz $AB=3$ . Wówczas z nierówności trójkąta oraz z założenia, że długości wszystkich krawędzi są różnymi liczbami całkowitymi, dostajemy $AC=4$ .

Ponadto $|BD-CD|<BC=2$ , więc długości krawędzi $BD$ i $CD$ są dwiema kolejnymi liczbami całkowitymi.

Jeżeli $BD=k$ i $CD=k+1$ (rys. 8), to otrzymujemy

$ |AD-k|=|AD-BD|<AB=3 \quad\hbox{oraz}\quad |AD-(k+1)|=|AD-CD|<AC=4. $

Stąd wynika, że $AD$ może przyjąć jedną z następujących trzech wartości: $k-2$ , $k-1$ , $k+2$ . Odpowiadające im zakresy zmienności $k$ to $k\ge 7$ , $k\ge 6$ , $k\ge 5$ , a odpowiadające sumy długości krawędzi wynoszą $3k+8$ , $3k+9$ , $3k+12$ . W ten sposób możemy uzyskać dowolną liczbę całkowitą nie mniejszą od 27 podzielną przez 3 oraz dowolną liczbę całkowitą nie mniejszą od 29 dającą resztę 2 z dzielenia przez 3.

Przypuśćmy z kolei, że $BD=k+1$ i $CD=k$ . Wtedy

$ |AD-(k+1)|=|AD-BD|<AB=3 \quad\hbox{oraz}\quad |AD-k|=|AD-CD|<AC=4. $

Zatem $AD$ może przyjąć jedną z następujących trzech wartości: $k-1$ , $k+2$ , $k+3$ . Odpowiadające im zakresy zmienności $k$ to $k\ge 6$ , $k\ge 5$ , $k\ge 5$ , a odpowiadające sumy długości krawędzi wynoszą $3k+9$ , $3k+12$ , $3k+13$ . W ten sposób możemy otrzymać dowolną liczbę całkowitą nie mniejszą od 27 podzielną przez 3 oraz dowolną liczbę całkowitą nie mniejszą od 28 dającą resztę 1 z dzielenia przez 3.

Ponieważ $2007\equiv 3\,\,\mod{4}$ i $3\,|\,2007$ , więc istnieje jeden dobry czworościan o sumie długości krawędzi równej 2007 należący do kategorii 1. - jego krawędzie mają długości 2, 3, 499, 500, 501, 502, oraz co najwyżej cztery nieprzystające dobre czworościany o sumie długości krawędzi równej 2007 należące do kategorii 2. - ich krawędzie mają długości 2, 3, 4, 665, 666, 667. Otrzymujemy następujących pięć czworościanów (rys. 9).

Nietrudno sprawdzić, że żadne dwa z powyższych czworościanów nie są przystające. Rzeczywiście, pierwszy ma inne długości krawędzi niż pozostałe cztery. Badając cztery pozostałe widzimy, że z wierzchołka, w którym schodzą się krawędzie o długościach 2 i 3 w drugim i trzecim czworościanie wychodzi krawędź o długości 666, w czwartym - o długości 667, w piątym - o długości 665. Ponadto czworościan drugi nie jest przystający do trzeciego, gdyż tylko jeden z nich zawiera ścianę o krawędziach długości 3, 665, 666.

Odpowiedź:

Taki czworościan istnieje wtedy i tylko wtedy, gdy $n\ge 27$ .
5 czworościanów.

I MEMO - Zadanie 8

Zawody matematyczne:

I MEMO, 2007

Wyznaczyć wszystkie dodatnie liczby całkowite $k$ , dla których istnieje taka liczba całkowita $a$ , że liczba $(a+k)^3-a^3$ jest podzielna przez 2007.

Rozwiązanie

Jeżeli liczba $(a+k)^3-a^3=3(a^2k+ak^2)+k^3$ dzieli się przez $2007=3\cdot 669$ , to tym bardziej dzieli się przez 3, co może mieć miejsce jedynie wtedy, gdy spełniona jest podzielność $3\,|\,k^3$ . Zatem warunkiem koniecznym na to, by dodatnia liczba całkowita $k$ spełniała warunki zadania, jest podzielność $3\,|\,k$ .

Wykażemy, iż jest to również warunek dostateczny.

Jeżeli mianowicie $3\,|\,k$ , to $k=3m$ dla pewnej liczby całkowitej $m>0$ ; wówczas dla wartości $a=38m$ liczba

$\begin{split}(a+k)^3-a^3&=(38m+3m)^3-(38m)^3=\cr &=(41^3-38^3)m^3=14049m^3=2007\cdot 7m^3}$

jest podzielna przez 2007.

Odpowiedź: Liczba całkowita dodatnia $k$ spełnia warunki zadania wtedy i tylko wtedy, gdy jest podzielna przez 3.

Uwaga: Jak dojść do tego, że gdy $k=3m$ , to należy podstawić $a=38m$ , by liczba $(a+k)^3-a^3$ była podzielna przez 2007 ?

Rozpatrzmy szczególny przypadek $m=1$ . Chcemy, aby liczba

$ (a+3)^3-a^3=9(a^2+3a+3) $

była podzielna przez $2007=9\cdot 223$ , co jest oczywiście równoważne podzielności $223\,|\,a^2+3a+3$ , czyli równości

$ (1) \qquad a^2+3a+3=223n $

dla pewnej liczby całkowitej $n$ . Potraktujmy tę równość jako równanie kwadratowe ze względu na zmienną $a$ przy danej wartości $n$ . Jeżeli rozwiązanie równania jest liczbą całkowitą, to wyróżnik tego równania, który wynosi $3^2-4(3-223n)=892n-3$ , powinien być kwadratem liczby całkowitej. Przy tym liczba $n$ musi być nieparzysta, gdyż lewa strona równości (1) jest liczbą nieparzystą dla dowolnej liczby całkowitej $a$ .

Obliczając wielkość $892n-3$ kolejno dla liczb $n=1,3,5,\ldots$ stwierdzamy, że dla $n=7$ otrzymujemy kwadrat: $892\cdot 7-3=6241=79^2$ . Równanie (1) przybiera wówczas postać $a^2+3a+3=1561$ i jego rozwiązaniami są liczby $a=38$ oraz $a=-41$ .

Zatem do liczby $m=1$ możemy dobrać wartość $a=38$ . Mnożąc teraz liczbę $(38+3)^3-38^3$ (która jest podzielna przez 2007) przez $m^3$ widzimy, że do dowolnej wartości $m$ można dobrać liczbę $a=38m$ .

III MEMO

Zawody matematyczne:

III MEMO, 2009

Zadania z III Środkowo-Europejskiej Olimpiady Matematycznej

Załącznik	Wielkość
III MEMO - Zadania z rozwiązaniami [4]	237.09 KB

III MEMO - Zadanie 1

Zawody matematyczne:

III MEMO, 2009

Wyznaczyć wszystkie funkcje $f\colon\mathbb R\to\mathbb R$ , spełniające dla dowolnych $x,y\in\mathbb R$ warunek

$ (1) \qquad f(xf(y))+f(f(x)+f(y))=yf(x)+f(x+f(y)). $

Uwaga: $\mathbb{R}$ oznacza zbiór liczb rzeczywistych.

Rozwiązanie

Sposób

Zauważmy, że funkcja stała, równa 0 spełnia warunek (1). Załóżmy, że $f(a)\neq0$ dla pewnego $a\in\mathbb R$ . Udowodnimy, że wówczas funkcja $f$ jest różnowartościowa.

Przypuśćmy, że $f(y)=f(z)$ dla pewnych $y,z\in\mathbb{R}$ . Stosując dwukrotnie (1), otrzymujemy wtedy

$ \begin{split} zf(x)&=&f(xf(z))+f(f(x)+f(z))-f(x+f(z))=\\ &=&f(xf(y))+f(f(x)+f(y))-f(x+f(y))=yf(x), \end{split} $

więc $yf(x)=zf(x)$ . Podstawienie $x=a$ prowadzi do $y=z$ , a tym samym dowodzi, że $f$ jest różnowartościowa.

Wstawmy $x=0$ i $y=1$ do (1). Wtedy $f(0)+f(f(0)+f(1))=f(0)+f(f(1))$ , czyli $f(f(0)+f(1))=f(f(1))$ . Z różnowartościowości $f$ wynika, że $f(0)+f(1)=f(1)$ , a stąd $f(0)=0$ .

Wykonajmy kolejne podstawienie, $y=0$ , w równaniu (1). Otrzymujemy $f(f(x))=f(x)$ dla wszystkich $x\in\mathbb R$ i na podstawie różnowartościowości $f$ dochodzimy do wniosku, że $f(x)=x$ dla wszystkich $x\in\mathbb R$ . Nietrudno sprawdzić, że taka funkcja spełnia (1).

Podsumowując, warunki zadania spełniają tylko dwie funkcje: funkcja stała $f(x)=0$ i funkcja identycznościowa $f(x)=x$ dla $x\in\mathbb R$ .

Sposób

Lemat. Istnieje liczba rzeczywista $x$ , dla której $f(x)=0$ .

Dowód lematu. Niech $a=f(0)$ . Rozważmy dwa przypadki:

Przypadek 1.: $a\neq 1$ .

Wtedy wstawiamy $y=0$ do (1) i otrzymujemy $f(xa)+f(f(x)+a)=f(x+a)$ . Stąd, dla $x=\frac{a}{a-1}$ , zachodzi $xa=x+a$ , więc $f(f(x)+a)=0$ .

Przypadek 2.: $a=1$ .

Wtedy rozważamy następujące podstawienia w (1):

$ x=0, y=1;\quad x=f(1), y=0. $

Prowadzą one do odpowiednio:

$ 1+f(1+f(1))=1+f(f(1));\quad f(f(1))+f(f(f(1))+1)=f(f(1)+1). $

W konsekwencji $f(f(f(1))+1)=0$ , co kończy dowód lematu.

Korzystając z powyższego lematu, znajdujemy liczbę $a$ , dla której $f(a)=0$ . Podstawienie $x=y=a$ w (1) prowadzi do $f(0)+f(0)=0+0$ , a zatem $f(0)=0$ .

Wstawiamy $f(0)=0$ i $y=0$ do (1) i otrzymujemy

$ (2) \qquad f(f(x))=f(x). $

Załóżmy, że $f$ nie jest funkcją zerową, tzn. istnieje liczba $c\neq0$ , dla której $f(x)=c$ . Wtedy, ze względu na (2), $f(c)=c$ . Wstawiając $x=c$ do (1) otrzymujemy $f(cf(y))+f(c+f(y))=cy+f(c+f(y))$ , a stąd $f(cf(y))=cy$ . Ostatnia równość i (2) prowadzi do

$ cy=f(cf(y))=f(f(cf(y)))=f(cy). $

Powyższa równość jest prawdziwa dla dowolnego $y\in\mathbb R$ , więc możemy ją zapisać jako $f(x)=x$ dla wszystkich $x\in\mathbb R$ .

Wykazaliśmy zatem, że jeśli $f$ spełnia (1), to $f$ jest funkcją zerową lub funkcją identycznościową. Nietrudno sprawdzić, że obie te funkcje spełniają warunki zadania.

III MEMO - Zadanie 2

Dane jest $n\geq3$ różnych kolorów. Niech $f(n)$ będzie największą liczbą całkowitą o następującej własności: Możliwe jest takie pokolorowanie wszystkich boków i przekątnych wielokąta wypukłego o $f(n)$ wierzchołkach, że

wykorzystane są co najmniej dwa różne kolory,
każde trzy wierzchołki wielokąta wyznaczają trójkąt o wszystkich bokach jednakowego koloru lub o wszystkich bokach różnego koloru.

Dowieść, że $f(n)\leq(n-1)^2$ oraz że równość zachodzi dla nieskończenie wielu wartości $n$ .

Rozwiązanie

Dla $n\geq 3$ rozważmy wielokąt wypukły o $f(n)$ wierzchołkach. Krawędzią będziemy nazywać dowolny bok lub przekątną wielokąta. Załóżmy, że pomalowaliśmy krawędzie wielokąta zgodnie z regułami zadania, mając do dyspozycji kolory $1,2,\dots,n$ .

Niech $k_i(w)$ oznacza liczbę krawędzi o jednym końcu w wierzchołku $w$ , pomalowanych $i$ -tym kolorem, dla $i=1,2,\dots,n$ . Wtedy dla dowolnego wierzchołka $w$ zachodzi

$ (1) \qquad k_1(w)+k_2(w)+\dots+k_n(w)=f(n)-1. $

Przypuśćmy, że dla pewnego wierzchołka $w_0$ i $j$ -tego koloru (możemy przyjąć, że jest to kolor niebieski) zachodzi $k_j(w_0)\geq n-1$ . To oznacza, że istnieje $n-1$ niebieskich krawędzi, których końcem jest $w_0$ . Oznaczmy przez $w_1,w_2,\dots,w_{n-1}$ pozostałe końce tych krawędzi. Ze względu na (ii) wszystkie krawędzie o obu końcach w zbiorze $\{w_1,w_2,\dots,w_{n-1}\}$ muszą być niebieskie.

Wiadomo, że nie wszystkie krawędzie są niebieskie, istnieje zatem wierzchołek $v$ i krawędź łącząca go z jakimś wierzchołkiem ze zbioru $\{w_0,w_1,\dots,w_{n-1}\}$ , która nie jest niebieska. Bez starty ogólności możemy założyć, że krawędź o końcach $v,w_0$ jest czerwona. Wtedy każda krawędź o końcach $v,w_j$ , dla $j=1,2,\dots,n-1$ , nie może być ani czerwona, ani niebieska, ze względu na (ii). Rozważanych krawędzi jest $n-1$ , a kolorów, którymi zostały pomalowane, jest nie więcej niż $n-2$ , zatem istnieją dwie krawędzie, np. $vw_i$ i $vw_j$ , pomalowane tym samym kolorem (i nie jest to ani czerwony, ani niebieski). Zauważmy jednak, że wtedy trójkąt o wierzchołkach $v$ , $w_i$ , $w_j$ jest pomalowany dokładnie dwoma kolorami, co w świetle (ii) jest niemożliwe. Otrzymana sprzeczność dowodzi, że $k_j(w)<n-1$ dla każdego wierzchołka $w$ i kolorów $j=1,2,\dots,n$ .

Zatem, wracając do (1),

$ f(n)=1+k_1(w)+k_2(w)+\dots+k_n(w)\leq1+n(n-2)=(n-1)^2, $

co kończy rozwiązanie pierwszej części zadania.

Pozostaje uzasadnić, że równość zachodzi dla nieskończenie wielu wartości $n$ . Załóżmy, że $n-1=p$ i $p$ jest liczbą pierwszą. Przypiszmy każdemu wierzchołkowi $p^2$ -kąta wypukłego inną parę $(a,b)$ , dla $a,b\in\{1,2,\dots,p\}$ . Malujemy kolorem $p+1$ każdą krawędź łączącą wierzchołek $(a,b)$ i $(a',b)$ dla $a,b,b'\in\{1,2,\dots,p\}$ . Następnie dla $k=1,2,\dots,p$ , kolorem $k$ malujemy każdą krawędź łączącą wierzchołek $(a,b)$ i $(a',b')$ , która spełnia warunek: $b\neq b'$ oraz

$ (2) \qquad k(b-b')\equiv a-a'\pmod p. $

Wiadomo, że dla dowolnej niezerowej liczby całkowitej $x$ i całkowitej liczby $y$ istnieje dokładnie jedno takie $k\in\{1,2,\dots,p\}$ , że $kx\equiv y\pmod p$ , więc za pomocą (2) przypisaliśmy każdej krawędzi jeden kolor. Ponadto nietrudno sprawdzić, że nie wszystkie krawędzie wielokąta są pomalowane tym samym kolorem.

Sprawdźmy, że spełniony jest również warunek (ii). Rozważmy trzy różne wierzchołki $(a,b)$ , $(a',b')$ , $(a'',b'')$ oraz przypuśćmy, że krawędź łącząca $(a,b)$ i $(a',b')$ jest tego samego koloru $k$ co krawędź łącząca $(a,b)$ i $(a'',b'')$ .

Jeżeli $k=p+1$ , to $b=b'$ i $b=b''$ , a stąd $b'=b''$ i z definicji naszego kolorowania wynika, że krawędź łącząca $(a',b')$ i $(a'',b'')$ jest pomalowana kolorem $p+1$ .

Jeżeli zaś $k\neq p+1$ , to $b\neq b'$ , $b\neq b''$ oraz

$ k(b-b')\equiv a-a'\pmod p\quad\text{i}\quad k(b-b'')\equiv a-a''\pmod p. $

Wtedy $kb'-a'\equiv kb-a\equiv kb''-a''\pmod p$ , zatem

$ k(b'-b'')\equiv a'-a''\pmod p. $

To oznacza, że $b'\neq b''$ i krawędź łącząca $(a',b')$ z $(a'',b'')$ jest koloru $k$ .

Pokazaliśmy, że nie istnieje trójkąt, którego boki byłyby pomalowane dokładnie dwoma kolorami, a tym samym sprawdziliśmy (ii). Powyższe kolorowanie krawędzi $p^2$ -kąta $p+1$ kolorami spełnia warunki zadania, czyli $f(p+1)\geq p^2$ . Wobec wcześniejszych rozważań zachodzi $f(p+1)=p^2$ , a ponieważ liczbę pierwszą $p$ możemy wybrać na nieskończenie wiele sposobów, wskazaliśmy nieskończenie wiele przypadków, w których $f(n)=(n-1)^2$ .

III MEMO - Zadanie 3

Niech $ABCD$ będzie czworokątem wypukłym, w którym $AB=CD$ oraz proste $AB$ i $CD$ nie są równoległe. Punkty $E$ i $F$ są środkami przekątnych $AC$ i $BD$ . Prosta $EF$ przecina odcinki $AB$ i $CD$ odpowiednio w punktach $G$ i $H$ . Udowodnić, że $\measuredangle AGH=\measuredangle DHG$ .

Rozwiązanie

Sposób I

Niech $P$ będzie środkiem odcinka $BC$ . Wtedy $EP\|AB$ , $FP\|CD$ i $|EP|=|AB|/2=|CD|/2=|FP|$ . Wobec tego trójkąt $EFP$ jest równoramienny i $\measuredangle PEF=\measuredangle EFP$ . Zatem

$ \measuredangle HGA=\pi-\measuredangle BGH=\pi-\measuredangle PEF=\pi-\measuredangle EFP=\pi-\measuredangle GHC=\measuredangle DHG. $

Sposób II

Niech $K$ będzie punktem przecięcia prostych $AB$ i $CD$ . Bez straty ogólności możemy przyjąć, że punkty leżą na prostych w kolejności: $A,B,K$ oraz $D,C,K$ . Niech ponadto $Q$ będzie takim punktem odcinka $AK$ , że $KQ=AB$ , zaś $R$ - takim punktem odcinka $DK$ , że $KR=CD$ .

Oznaczmy przez $\cal S$ zbiór wszystkich punktów $X$ , dla których $P(ABX)+P(CDX)=P(ABCD)/2$ , gdzie $P$ oznacza pole wielokąta o podanych wierzchołkach. Zauważmy, że

$ P(ABE)+P(CDE)=\frac12P(ABC)+\frac12P(ACD)=\frac12P(ABCD), $

czyli $E\in{\cal S}$ . Podobnie uzasadniamy, że $F\in{\cal S}$ .

Ponadto dla każdego $X\in{\cal S}$ zachodzi $P(ABX)=P(KQX)$ i $P(CDX)=P(KRX)$ , bo $AB=QK$ i $CD=RK$ . Stąd $P(ABX)+P(CDX)=P(QKRS)$ , a więc $P(QRX)=P(ABCD)/2-P(QRK)$ . Wynika z tego, że pole trójkąta $QRX$ jest takie samo dla wszystkich $X\in{\cal S}$ , więc zbiór $\cal S$ jest zawarty w prostej równoległej do $QR$ . Wiemy też, że $E,F\in{\cal S}$ , zatem $EF\|QR$ .

Wykazaliśmy tym samym, że $GH\|QR$ . Stąd, ponieważ trójkąt $QKR$ jest równoramienny ( $KQ=AB=CD=KR$ ), również trójkąt $KGH$ jest równoramienny, co implikuje tezę zadania.

III MEMO - Zadanie 4

Zawody matematyczne:

III MEMO, 2009

Wyznaczyć wszystkie liczby całkowite $k\geq2$ o następującej własności: liczba $n^{n-1}-m^{m-1}$ nie jest podzielna przez $k$ dla żadnej pary $(m,n)$ różnych liczb całkowitych dodatnich, mniejszych lub równych $k$ .

Rozwiązanie

Jeżeli $k\geq4$ i $k$ jest liczbą parzystą, to $(k-1)^{k-2}\equiv1^0\pmod2$ , więc nie znajdziemy rozwiązań wśród liczb parzystych większych niż 2.

Załóżmy, że $k$ jest liczbą nieparzystą. Dla $k\geq5$ przynajmniej $\frac{k+1}2+1$ liczb spośród $1^0,2^1,\dots,k^{k-1}$ jest kwadratami, ponieważ kwadratami są $1^0, 3^2, 5^4, \dots, k^{k-1}$ oraz $4^3$ . Jeśli zatem $k\geq5$ spełnia warunki zadania, to liczba reszt kwadratowych modulo $k$ musi być większa niż $\frac{k+1}2$ . (Resztą kwadratową modulo $k$ nazywamy resztę z dzielenia przez $k$ liczby będącej kwadratem liczby całkowitej.)

Z drugiej strony, $x^2\equiv(k-x)^2\pmod k$ dla $x=1,2,\dots,\frac{k-1}2$ , więc istnieje nie więcej niż $\frac{k-1}2+1=\frac{k+1}2$ różnych reszt kwadratowych modulo $k$ . Zatem żadna liczba nieparzysta większa niż 3 nie spełnia warunków zadania.

Na koniec sprawdzamy, że 1, 2 i 3 są rozwiązaniami zadania.

Odpowiedź: Jedynymi rozwiązaniami są liczby 1, 2 i 3.

III MEMO - Zadanie 5

Zawody matematyczne:

III MEMO, 2009

Dane są liczby rzeczywiste $x$ , $y$ , $z$ , spełniające zależność $x^2+y^2+z^2+9 = 4(x+y+z)$ . Dowieść, że

$ (1) \qquad x^4+y^4+z^4+16(x^2+y^2+z^2)\geq8(x^3+y^3+z^3)+27 $

oraz rozstrzygnąć, kiedy zachodzi równość.

Rozwiązanie

Sposób I

Na mocy założenia, po dodaniu $6(x^2+y^2+z^2+9)$ do lewej strony, zaś $24(x+y+z)$ do prawej strony nierówności (1), otrzymujemy równoważną nierówność

$ x^4+y^4+z^4+22(x^2+y^2+z^2)+27\geq8(x^3+y^3+z^3)+24(x+y+z). $

Nietrudno sprawdzić, że jest ona równoważna

$ (2) \qquad (x-1)^2(x-3)^2+(y-1)^2(y-3)^2+(z-1)^2(z-3)^2\geq0, $

co jest oczywiście prawdą. Tym samym dowiedliśmy (1).

Równość w (2) zachodzi wtedy i tylko wtedy, gdy $x,y,x\in\{1,3\}$ .

Sposób II

Przy założeniu $x^2+y^2+z^2+9=4(x+y+z)$ można po prostych przekształceniach zapisać nierówności (1) równoważnie jako

$ (3) \qquad (x-2)^4+(y-2)^4+(z-2)^4\geq3, $

zaś samo założenie jako

$ (4) \qquad (x-2)^2+(y-2)^2+(z-2)^2=3. $

Korzystając z nierówności między średnią kwadratową a średnia arytmetyczną dla liczb $a=(x-2)^2$ , $b=(y-2)^2$ , $c=(z-2)^2$ , otrzymujemy

$ \begin{split} \sqrt[3]{\frac{(x-2)^4+(y-2)^4+(z-2)^4}3}=\sqrt[3]{\frac{a^2+b^2+c^2}3}\geq\\ \geq\frac{a+b+c}3=\frac{(x-2)^2+(y-2)^2+(z-2)^2}3, \end{split} $

a stąd i z (4) otrzymujemy tezę (3).

Wiadomo, że w powyższej nierówności między średnimi równość zachodzi wtedy i tylko wtedy, gdy $a=b=c$ , więc równość otrzymujemy tylko gdy $(x-2)^2=(y-2)^2=(z-2)^2$ . Zatem w (1) równość zachodzi wtedy i tylko wtedy, gdy $|x-2|=|y-2|=|z-2|=1$ , lub równoważnie $x,y,x\in\{1,3\}$ .

III MEMO - Zadanie 6

Zawody matematyczne:

III MEMO, 2009

Liczby rzeczywiste $a$ , $b$ , $c$ posiadają tę własność, że dla każdych dwóch spośród równań

$ x^2+ax+b=0,\quad x^2+bx+c=0,\quad x^2+cx+a=0 $

istnieje dokładnie jedna liczba rzeczywista będąca rozwiązaniem ich obu. Wyznaczyć wszystkie możliwe wartości wyrażenia $a^2+b^2+c^2$ .

Rozwiązanie

Rozważymy dwa przypadki.

Przypadek 1. Wszystkie trzy równania mają wspólny pierwiastek $x_1$ .

Wtedy

$ x_1^2+ax_1+b=0,\quad x_1^2+bx_1+c=0,\quad x_1^2+cx_1+a=0, $

skąd

$ (a-b)x_1+b-c=0\quad\text{i}\quad(a-c)x_1+b-a=0. $

Wyznaczamy $b$ z drugiego równania, wstawiamy do pierwszego i po uproszczeniach otrzymujemy

$ (x_1^2-x_1-1)(a-c)=0. $

Zatem $a=c$ , gdyż $x_1^2-x_1+1>0$ dla wszystkich rzeczywistych $x_1$ . Podobnie wyprowadzamy zależność $a=b$ . Stąd wszystkie trzy równania kwadratowe są identyczne. Posiadają przy tym dokładnie jeden pierwiastek wspólny, więc wyróżnik $\Delta=a^2-4a$ jest równy 0. Zatem $a=b=c=0$ lub $a=b=c=4$ , a w konsekwencji $a^2+b^2+c^2=0$ lub $a^2+b^2+c^2=48$ .

Przypadek 2. Każde równanie ma dwa różne pierwiastki rzeczywiste: pierwiastkami pierwszego równania są $x_1$ i $x_2$ , pierwiastki drugiego to $x_1$ i $x_3$ , a pierwiastkami trzeciego równania są $x_2$ i $x_3$ .

Wtedy na podstawie wzorów Viete'a

$ (1) \begin{split} x_1+x_2=-a,&\quad x_1x_2=b,\\ x_1+x_3=-b,&\quad x_1x_3=c,\\ x_2+x_3=-c,&\quad x_2x_3=a. \end{split} $

Wprowadźmy oznaczenia

$ p=x_1+x_2+x_3,\quad q=x_1x_2+x_1x_3+x_2x_3,\quad r=x_1x_2x_3. $

Wówczas $x_1,x_2,x_3$ są pierwiastkami równania

$ (2) \qquad x^3-px^2+qx-r=0. $

Ponadto

$ a+b+c=q\quad\text{i}\quad-(a+b+c)=2p, $

a stąd

$ (3) \qquad 2p+q=0. $

Łatwo też sprawdzić, że

$ abc=r^2\quad\text{i}\quad-abc=(x_1+x_2)(x_1+x_3)(x_2+x_3)=pq-r, $

skąd

$ (4) \qquad r^2+pq-r=0. $

Sumę $a^2+b^2+c^2$ możemy wyrazić następująco:

$ \begin{split} a^2+b^2+c^2&=x_1^2x_2^2+x_1^2x_3^2+x_2^2x_3^2=q^2-2pr,\\ a^2+b^2+c^2&=(x_1+x_2)^2+(x_1+x_3)^2+(x_2+x_3)^2=2p^2-2q, \end{split} $

co prowadzi do

$ (5) \qquad q^2-2pr=2p^2-2q. $

Stosując (3) do (4) i (5), otrzymujemy

$ r^2-r-2p^2=0,\quad p^2-2p-pr=0. $

Gdy $p=0$ , wtedy $q=0$ i równanie (2) ma postać $x^3-r=0$ . Jednak równanie to ma tylko jeden pierwiastek rzeczywisty, wbrew założeniu, że $x_1$ , $x_2$ , $x_3$ są różnymi liczbami rzeczywistymi.

Zatem $p\neq0$ . Stąd $r=p-2$ i $p^2+5p-6=0$ . Rozwiązaniem ostatniego równania jest $p=-6$ lub $p=1$ . Gdyby $p=-6$ , to mielibyśmy $q=12$ i $r=-8$ ; wtedy $x_1$ , $x_2$ , $x_3$ byłyby pierwiastkami równania $x^3+6x^2+12x+8=0$ , które jest równoważne równaniu $(x+2)^3=0$ , nie posiadającemu trzech różnych pierwiastków. Zatem przypadek $p=-6$ wykluczamy.

Dla $p=1$ obliczamy, że $q=-2$ i $r=-1$ . Wówczas $x_1$ , $x_2$ , $x_3$ są rozwiązaniami równania

$ (6) \qquad x^3-x^2-2x+1=0. $

Na tym etapie nie możemy jeszcze stwierdzić, że otrzymaliśmy kolejną możliwą wartość $a^2+b^2+c^2=q^2-2pr=6$ , bo nie mamy pewności, że równanie (6) ma trzy różne pierwiastki rzeczywiste, spełniające jednocześnie (1) dla pewnych $a,b,c$ . Trudno wyznaczyć pierwiastki tego równania w postaci jawnej, ale możemy stwierdzić, że jako równanie trzeciego stopnia posiada przynajmniej jeden pierwiastek rzeczywisty. Przyjmijmy, że $x_1$ jest tym pierwiastkiem. Wyznaczymy teraz $x_2$ i $x_3$ za pomocą $x_1$ .

Założyliśmy, że $x_1,x_2,x_3$ spełniają (1), więc:

$ \begin{split} (7) \qquad x_1+x_2+x_2x_3&= 0,\\ (8) \qquad x_1+x_3+x_1x_2&= 0,\\ (9) \qquad x_2+x_3+x_1x_3&= 0. \end{split} $

Przekształcając równoważnie ostatnie dwa równania tego układu, wyznaczamy $x_2$ i $x_3$ :

$ \begin{split} x_3&=\frac{x_1}{x_1^2+x_1-1},\\ x_2&=-\frac{x_1(x_1+1)}{x_1^2+x_1-1}. \end{split} $

Ponadto $x_1$ spełnia \eqref{t25}, czyli $x_1^2+x_1-1=x_1^3-x_1$ . Stąd

$ \begin{split} x_3&=\frac{x_1}{x_1^3-x_1}=\frac1{x_1^2-1},\\ x_2&=-\frac{x_1(x_1+1)}{x_1^3-x_1}=-\frac1{x_1-1}. \end{split} $

Sprawdźmy, że tak wyznaczone $x_1$ , $x_2$ , $x_3$ rzeczywiście spełniają (1) dla pewnych $a,b,c$ . Równoważnie sprawdzamy kolejno (7), (8), (9):

$ \begin{split} x_1+x_2+x_2x_3 &= x_1-\frac1{x_1-1}-\frac1{x_1^3-x_1^2-x_1+1}=\frac{x_1^4-x_1^3-2x_1^2+x_1}{x_1^3-x_1^2-x_1+1}=0,\\ x_1+x_3+x_1x_2 &= x_1+\frac1{x_1^2-1}-\frac{x_1}{x_1-1}=\frac{1+x_1^3-x_1^2-2x_1}{x_1^2-1}=0,\\ x_2+x_3+x_1x_3 &= -\frac{x_1}{x_1^2-1}+\frac{x_1}{x_1^2-1}=0. \end{split} $

Pozostaje wykazać, że $x_1$ , $x_2$ , $x_3$ są parami różne. Istotnie, w przeciwnym wypadku $x_1$ spełniałby przynajmniej jedno z równań:

$ x_1=\frac{x_1}{x_1^2+x_1-1},\quad x_1=-\frac{x_1(x_1+1)}{x_1^2+x_1-1},\quad \frac1{x_1^2-1}=-\frac{1}{x_1-1}. $

Rozwiązując powyższe równania, doszlibyśmy do wniosku, że $x_1\in\{0,1,-2\}$ , a żadna z liczb 0, 1, -2 nie jest pierwiastkiem (6).

Wskazaliśmy zatem różne liczby rzeczywiste $x_1$ , $x_2$ , $x_3$ , spełniające (1) dla pewnych $a$ , $b$ , $c$ . Wobec wcześniejszych rozważań, w tym przypadku $a^2+b^2+c^2=6$ .

Odpowiedź: Możliwymi wartościami $a^2+b^2+c^2$ są: 0, 48, 6.

III MEMO - Zadanie 7

Zawody matematyczne:

III MEMO, 2009

Na tablicy napisano liczby $0,1,2,\dots,n$ ( $n\geq2$ ). W każdym kroku wymazujemy liczbę będącą średnią arytmetyczną dwóch różnych, jeszcze nie wymazanych liczb. Postępowanie to kontynuujemy tak długo, jak jest to możliwe. Niech $g(n)$ będzie najmniejszą możliwą ilością liczb pozostawionych na tablicy. Wyznaczyć $g(n)$ w zależności od $n$ .

Rozwiązanie

Zacznijmy od obserwacji, że $g(n)\geq2$ , bo nie możemy zostawić na tablicy mniej, niż 2 liczb. Ponadto jeśli $g(n)=2$ , to liczbami pozostałymi na końcu są 0 i $n$ .

Dla $n=2^k$ , gdzie $k$ jest liczbą naturalną, możemy kolejno usuwać liczby postaci $2m+1=\frac{2m+2(m+1)}{2}$ , potem wszystkie postaci $4m+2=\frac{4m+4(m+1)}{2}$ , następnie $8m+4=\frac{8m+8(m+1)}{2}$ , itd., tak długo, aż na tablicy pozostaną jedynie 0 i $n=2^k$ . Zatem $g(2^k)\geq2$ i wobec wcześniejszej uwagi $g(2^k)=2$ .

Załóżmy teraz, że $n$ nie jest potęgą 2. Przypuśćmy, że $g(n)=2$ , tzn. istnieje pewien sposób usuwania liczb, przy którym na końcu zostaje tylko 0 i $n$ . Przeanalizujemy tę procedurę od końca, zaczynając od 0 i $n$ na tablicy i dopisując w każdym kolejnym kroku nową liczbę, będącą średnią arytmetyczną pewnych dwóch liczb, będących w tym momencie na tablicy.

W pierwszym kroku musimy dopisać $\frac{n+0}{2}=\frac{n}{2}$ . W drugim mamy dwie możliwości: $\frac{n+n/2}{2}=\frac{3n}{2^2}$ i $\frac{0+n/2}{2}=\frac{n}{2^2}$ . Nietrudno zauważyć, że w $k$ -tym kroku możliwa do napisania jest jedna z liczb postaci $t\cdot\frac{n}{2^k}$ dla pewnego $t\geq 1$ .

Istotnie, zakładając indukcyjnie, że po $k-1$ krokach ( $k\geq2$ ) wszystkie liczby na tablicy są postaci $t'\cdot\frac{n}{2^{k-1}}$ dla pewnego $t'\geq0$ , w $k$ -tym kroku możemy dopisać jedynie liczbę postaci $\left.\left(t_1\cdot\frac{n}{2^{k-1}}+t_2\cdot\frac{n}{2^{k-1}}\right)\right/2=t\cdot\frac{n}{2^k}$ dla pewnego $t\geq1$ , po czym wszystkie liczby na tablicy są całkowitymi wielokrotnościami liczby $\frac{n}{2^k}$ .

Zauważmy, że 1 nie można przedstawić jako $t\cdot\frac{n}{2^k}$ , więc nigdy nie zostanie dopisana. Wracając do procedury usuwania, odpowiadającej analizowanej procedurze dopisywania liczb, wnioskujemy, że na końcu zostały nie usunięte liczby 0, 1 i $n$ . Stąd $g(n)\geq3$ . Otrzymana sprzeczność z założeniem $g(n)=2$ dowodzi, że każda procedura usuwania liczb z tablicy musi się skończyć pozostawieniem przynajmniej 3 liczb.

Uzasadnimy, że pozostawienie dokładnie 3 liczb na tablicy jest możliwe. Niech $k$ będzie liczbą całkowitą, dla której $2^k<n<2^{k+1}$ . W pierwszym etapie usuwamy kolejno $n-1$ , $n-2,\dots, 2^{k}+1$ . Jest to możliwe, bo jeżeli $m>2^k$ i usunęliśmy $n-1,n-2,\dots m+1$ , to $m$ jest średnią arytmetyczną liczb $n$ i $2m-n$ , a przy tym $2m-n>2^{m+1}-n>0$ oraz $2m-n<m$ , więc obie liczby $n$ i $2m-n$ są w tym momencie obecne na tablicy.

Po pierwszym etapie pozostały na tablicy liczby $0,1,\dots,2^k$ i $n$ . Teraz usuwamy liczby z ciągu $0,1,\dots,2^k$ , w sposób opisany w pierwszej części rozwiązania, dzięki któremu na końcu pozostają tylko dwie liczby: 0 i $2^k$ . Tym samym pozostawiamy na tablicy jedynie liczby 0, $2^k$ i $n$ .

Udowodniliśmy zatem, że $g(n)=2$ , gdy $n$ jest potęgą 2, zaś w przeciwnym wypadku $g(n)=3$ .

III MEMO - Zadanie 8

Zawody matematyczne:

III MEMO, 2009

Każde z pól szachownicy o wymiarach $2009\times 2009$ kolorujemy jednym z $n$ kolorów (nie każdy kolor musi być wykorzystany). Mówimy, że kolor jest spójny, jeżeli dla dowolnych dwóch pól tego koloru można za pomocą ciągu ruchów przeprowadzić hetmana z jednego pola na drugie, stawiając go jedynie na polach w tym kolorze. W szczególności, jeśli pewnym kolorem pomalowano tylko jedno pole, to również jest on spójny. Wyznaczyć największą liczbę $n$ , dla której przy dowolnym kolorowaniu szachownicy co najmniej jeden z kolorów jest spójny.

Uwaga: Ruch hetmanem polega na przesunięciu go o dowolną liczbę pól w pionie, poziomie lub po skosie.

Rozwiązanie

Udowodnimy, że największe takie $n$ wynosi 2. Na początku wskażemy kolorowanie planszy trzema kolorami, dla którego żaden kolor nie jest spójny.

Na rysunku przedsawiono kolorowanie częściowe planszy $11\times 11$ . Widzimy, że duże O w danym kolorze nie jest połączone z żadnym małym o w tym kolorze. (Mówimy, że pola $a$ i $b$ są połączone, jeśli hetman może przejść z $a$ na $b$ w serii ruchów zgodnych z warunkami zadania.) Kolorowanie pozostałych pól jest nieistotne.

Analogicznie możemy pomalować każdą planszę $k\times k$ dla $k\geq6$ . Przypisujemy polom współrzędne $(i,j)$ , gdzie $i,j\in\{1,\dots,n\}$ . Malujemy $(2,1)$ na czerwono, $(1,2)$ na niebiesko, $(1,1),(2,2),(2,3),(3,2)$ i $(k,4)$ na czarno. W przypadku pozostałych pól kolejne etapy kolorowania są następujące: Wszystkie pola leżące na jednej linii (pionowej, poziomej lub ukośnej), zawierające $(2,1)$ , malujemy na niebiesko. Następnie nie pomalowane jeszcze pola na liniach zawierających $(1,2)$ lub $(k,4)$ dostają kolor czerwony. Pozostałe pola malujemy dowolnie. Jeżeli $n\geq6$ , pola $(2,1)$ , $(1,2)$ i $(k,4)$ nie są połączone z żadnym innym polem w odpowiadającym im kolorze.

Udowodnimy teraz, że dla $k,m\geq1$ i dowolnego czerwono-niebieskiego kolorowania szachownicy $k\times m$ , przynajmniej jeden kolor jest spójny. Postępujemy indukcyjnie ze względu na $k+m$ .

Oczywiście gdy $k+m=2$ teza jest spełniona. Ustalmy $n,m\geq1$ i załóżmy, że teza jest prawdziwa dla dowolnej szachownicy $k'\times m'$ , gdzie $k'+m'<n+m$ . Rozważmy dowolne kolorowanie planszy $S$ o wymiarach $k\times m$ . Oznaczmy przez $S_1$ , $S_2$ , $S_3$ plansze otrzymane z $S$ przez usunięcie odpowiednio: pierwszej kolumny, ostatniej kolumny, ostatniego wiersza. Na mocy założenia indukcyjnego i zasady szufladkowej, istnieją dwie plansze, $S_i$ , $S_j$ , na których jeden z kolorów jest spójny. Możemy przyjąć, że jest to kolor czerwony. Niech $A_0=S_i\cap S_j$ , $A_1=S_j\setminus S_i$ i $A_2=S_i\setminus S_j$ .

Oto kilka łatwych do sprawdzenia obserwacji:

Kolor jest spójny wtedy i tylko wtedy, gdy każde dwa pola w tym kolorze są połączone.

Dla dowolnych pól $a$ , $b$ , $c$ , jeżeli $a$ jest połączone z $b$ , a $b$ jest połączone z $c$ , to $a$ jest połączone z $c$ .

Jeśli plansza $A_0$ jest monochromatyczna (tzn. wszystkie jej pola są tego samego koloru),

i jest niebieska, to niebieski jest kolorem spójnym na całej planszy $S$ . Wynika to z poprzedniej obserwacji i z faktu, że $A_0$ jest planszą $(k-1)\times(m-1)$ lub $(k-2)\times m$ , a w obu przypadkach każde niebieskie pole na brzegu $S$ leży w jednej linii z jakimś niebieskim polem z $A_0$ .

Jeżeli istnieje czerwone pole na $A_0$ , to czerwony jest kolorem spójnym na $S_i\cup S_j$ . Twierdzimy to na mocy poprzednich trzech obserwacji i faktu, że czerwony jest spójny zarówno na $S_i$ , jaki i na $S_j$ .

Jeżeli plansze $A_1$ i $A_2$ są monochromatyczne, powiedzmy niebieskie, to niebieski jest spójny na całej planszy $S$ . Rzeczywiście, każde niebieskie pole z $S$ leży w jednej linii z jakimś niebieskim polem z $A_1$ lub $A_2$ .

Przypuśćmy nie wprost, że ani niebieski, ani czerwony nie jest kolorem spójnym na $S$ . Wtedy, na mocy (3), plansza $A_0$ musi mieć jakieś pole czerwone. Zauważmy, że $S_i\cup S_j$ pokrywa albo całą szachownicę $S$ , albo prawie całą, z wyjątkiem jednego rogu.

W pierwszym przypadku z obserwacji (4) wynika, że czerwony jest spójny na $S$ , dochodzimy więc do sprzeczności.

W drugim przypadku jest tylko jedna możliwość znalezienia dwóch niepołączonych czerwonych pól na $S$ : róg szachownicy $c$ niepokryty przez $S_i\cup S_j$ musi być czerwony i żadne pole na liniach zawierających $c$ nie może być czerwone. Ale wtedy mamy do czynienia z sytuacją z obserwacji (5), zatem niebieski jest kolorem spójnym na $S$ . Ponownie doszliśmy do sprzeczności.

Tym samym udowodniliśmy tezę indukcyjną dla szachownicy $k\times m$ .

Uwaga: Oto alternatywna konstrukcja kolorowania szachownicy $2009\times 2009$ trzema kolorami. Ponumerujmy je 1, 2, 3, z których każdy jest niespójny: Na początku w każde z $2009^2$ pól wpisujemy liczbę 0. W polu $(2,2009)$ dodajemy 1, a w polu $(3,1)$ dodajemy 2. Teraz w każdym polu osiągalnym jednym ruchem hetmana z $(2,2009)$ dodajemy 2, przy czym nie zmieniamy liczby 1 w polu $(2,2009)$ . W każdym polu osiągalnym jednym ruchem hetmana z $(3,1)$ dodajemy 1, ale nie zmieniamy liczby 2 w polu $(3,1)$ . Zauważmy, że pola $(2,2009)$ i $(3,1)$ mają inne kolory szachowe (czarny i biały), więc goniec, startując z $(2,2009)$ , porusza się po polach innego koloru niż goniec ustawiony na $(3,1)$ . Ponadto goniec z $(2,2009)$ nie ma w zasięgu rażenia pól pierwszego wiersza, zaś w zasięgu gońca z $(3,1)$ nie leżą pola z wiersza 2009. Dlatego liczba $1+2=3$ znajduje się tylko w czterech polach: $(2,1)$ , $(2,2)$ , $(3,2009)$ , $(3,2009-1)$ . Dwa pierwsze pola nie są połączone z dwoma następnymi. Dodajemy teraz dowolnie 1 lub 2 we wszystkich polach, w których nadal jest liczba 0. Zauważmy, że żadne z nich nie jest połączone ani z polem $(2,2009)$ (z numerem 1), ani z $(3,1)$ (z liczbą 2). Zatem wszystkie kolory: 1, 2, 3, są niespójne.

III MEMO - Zadanie 9

Zawody matematyczne:

III MEMO, 2009

Niech $ABCD$ będzie równoległobokiem, w którym $\measuredangle BAD=60^\circ$ . Przekątne tego równoległoboku przecinają się w punkcie $E$ . Okrąg opisany na trójkącie $ACD$ przecina po raz drugi proste $BA$ , $BD$ , $BC$ w punktach odpowiednio $K$ , $P$ , $L$ . Prosta $EP$ przecina okrąg opisany na trójkącie $CEL$ w punkcie $M\neq E$ . Udowodnić, że trójkąty $KLM$ i $CAP$ są przystające.

Rozwiązanie

Sposób I

Czworokąty $LMCE$ i $ALKC$ można wpisać w okrąg, więc

$ \measuredangle BML=\measuredangle EML=\measuredangle ECL=\measuredangle ACL=\measuredangle AKL=\measuredangle BKL, $

a stąd punkty $L,M,K,B$ leżą na jednym okręgu. Zatem

$ \measuredangle LKM=\measuredangle LBM=\measuredangle CBD=\measuredangle BDA. $

Na czworokącie $APCD$ można opisać okrąg, więc $\measuredangle ADB=\measuredangle ADP=\measuredangle ACP$ , skąd $\measuredangle LKM=\measuredangle ACP$ . Podobnie

$ \measuredangle MLK=\measuredangle MBK=\measuredangle DBA=\measuredangle BDC=\measuredangle PDC=\measuredangle PAC. $

Udowodniliśmy, że $\measuredangle LKM=\measuredangle ACP$ i $\measuredangle MLK=\measuredangle PAC$ , z czego wynika, że trójkąty $KLM$ i $CAP$ są podobne.

Przyglądając się pięciokątowi $KCDAL$ wpisanemu w okrąg, widzimy, że $\measuredangle KLD=\measuredangle KAD=\measuredangle BAD=60^\circ$ i $\measuredangle DKL=\measuredangle DCL=\measuredangle DCB=\measuredangle BAD=60^\circ$ , więc trójkąt $DLK$ jest równoboczny i $LK=DK$ . Ze względu na $AK\|DC$ , czworokąt $AKCD$ jest trapezoidem równoramiennym, stąd $DK=AC$ . Zatem $LK=AC$ , co dowodzi przystawania trójkątów $KLM$ i $CAP$ .

Sposób II

Obierzmy na prostej $AB$ taki punkt $F$ , że $BC=BF=FC$ . W ten sposób otrzymaliśmy równoramienny trapezoid, którego okrąg opisany jest jednocześnie okręgiem opisanym na trójkącie $ADC$ . Stąd $K=F$ . Analogicznie, wybierając na $BC$ takie punkt $G$ , że $GB=GA=BA$ , dochodzimy do wniosku, że $G=L$ . Zatem $AC=KL$ , ze względu na symetrię względem dwusiecznej kąta $CBK$ (lub równoważnie $ABL$ ). Czworokąt $APCD$ jest wpisany w okrąg, więc

$ \measuredangle APC=180^\circ-\measuredangle ADC=180^\circ-120^\circ=60^\circ. $

Możemy też skonstruować $K$ i $L$ jako obrazy $A$ i $C$ w inwersji względem okręgu o środku $B$ , złożonej z symetrią względem punktu $B$ . Wtedy $P$ jest obrazem $D$ , zaś $M$ jest obrazem $E$ . Obrazami $A$ , $E$ , $C$ są $K$ , $L$ , $M$ , ponadto wiadomo, że obrazem prostek jest okrąg zawierający $B$ , więc czworokąt $BLMK$ jest wpisany w okrąg. Stąd

$ \measuredangle KML=180^\circ-\measuredangle KBL=180^\circ-120^\circ=60^\circ. $

Prócz tego

$ \measuredangle LKM=\measuredangle LBM=\measuredangle DBC=\measuredangle ADP=\measuredangle ACP, $

więc trójkąty $APC$ i $LMK$ są podobne, a nawet przystające, bo $AC=LK$ .

Sposób III

Trójkąty $ABL$ i $BCK$ są równoboczne, więc wszystkie ich kąty mają miarę $60^\circ$ . Stąd $AB=BL$ i $CB=BK$ . Ponadto $\measuredangle CBA=120^\circ=\measuredangle LBK$ . Zatem trójkąty $ABC$ i $LBK$ są przystające i

$ (1) \qquad AC=LK. $

Zauważmy, że

$ \measuredangle BKL=\measuredangle AKL=\measuredangle ACL=\measuredangle ECL=\measuredangle EML=\measuredangle BML, $

więc na czworokącie $BKML$ można opisać okrąg i $\measuredangle KMB=\measuredangle KLB$ . Stąd

$ (2) \begin{split} \measuredangle KML&=\measuredangle KMB+\measuredangle BML=\measuredangle KLB+\measuredangle BKL=\\ &=\measuredangle BAC+\measuredangle ACB=\measuredangle DCA+\measuredangle CAD=\\ &=\measuredangle DPA+\measuredangle CPD=\measuredangle CPA. \end{split} $

Zauważmy też, że

$ (3) \qquad \measuredangle MLK=\measuredangle MBK=\measuredangle PDC=\measuredangle PAC. $

Na mocy (1),(2) i (3) otrzymujemy tezę.

III MEMO - Zadanie 10

Zawody matematyczne:

III MEMO, 2009

Czworokąt $ABCD$ wpisany jest w okrąg, przy czym $CD=DA$ . Na odcinkach $AB$ i $BC$ wybrano punkty odpowiednio $E$ i $F$ , dla których $\measuredangle ADC=2\measuredangle EDF$ . Odcinek $DK$ jest wysokością trójkąta $DEF$ , zaś $DM$ jego środkową. Punkt $L$ jest symetryczny do $K$ względem $M$ . Wykazać, że proste $DM$ oraz $BL$ są równoległe.

Rozwiązanie

Niech $N$ będzie obrazem punktu $A$ w symetrii względem prostej $DE$ . Wtedy

$ \measuredangle CDN=\measuredangle CDA-\measuredangle ADN=2\measuredangle EDF-2\measuredangle EDN=2\measuredangle FDN $

i $ND=AD=CD$ , więc $N$ jest również obrazem punktu $C$ w symetrii względem prostej $DF$ . Stąd otrzymujemy następujące pary trójkątów przystających: $\triangle ADE\equiv\triangle NDE$ oraz $\triangle CDF\equiv\triangle NDF$ . W konsekwencji

$ \measuredangle END+\measuredangle DNF=\measuredangle EAD+\measuredangle DCF=\measuredangle BAD+\measuredangle DCB=180^\circ, $

i wnioskujemy, że $N$ należy do odcinka $EF$ .

Niech $d(X,YZ)$ oznacza odległość punktu $X$ od prostej $YZ$ . Wówczas

$ \begin{split} d(D,BE)&=d(D,AE)=d(D,NE)=d(D,FE)=\\ &=d(D,FN)=d(D,FC)=d(D,FB), \end{split} $

przy czym ostatnie dwie równości wynikają z przystawania odpowiednich trójkątów.

Zatem punkt $D$ znajduje się w takiej samej odległości od wszystkich trzech prostych zawierających boki trójkąta $BEF$ , jest więc środkiem okręgu dopisanego do trójkąta $BEF$ . Okrąg ten jest styczny do $EF$ w punkcie $K$ . Z własności okręgu wpisanego i dopisanego, okrąg wpisany w trójkąt $BEF$ jest styczny do $EF$ w punkcie $L$ .

Oznaczmy przez $P$ odbicie symetryczne punktu $K$ względem $D$ . Istnieje jednokładność o środku $B$ , w której obrazem okręgu wpisanego w trójkąt $BEF$ jest okrąg dopisany, więc punkty $B$ , $L$ , $P$ są współliniowe. Aby zakończyć dowód, wystarczy zauważyć, że $DM\|PL$ , a jest to prosty wniosek z twierdzenia Talesa ( $KL/KM=2=KP/DP$ ).

III MEMO - Zadanie 11

Zawody matematyczne:

III MEMO, 2009

Znaleźć wszystkie pary $(m,n)$ liczb całkowitych, spełniające równanie

$ (m+n)^4=m^2n^2+m^2+n^2+6mn. $

Rozwiązanie

Sposób I

Równanie możemy zapisać równoważnie jako

$ (m+n)^4-m^2n^2=(m+n)^2+4mn. $

Po podstawieniu $x=m+n$ i $y=mn$ , powyższe równanie przybiera postać

$ x^4-x^2=y^2+4y, $

lub równoważnie

$ x^4-x^2+4=(y+2)^2. $

Z faktu, że $x^4-x^2+4>x^4-2x^2+1=(x^2-1)^2$ dla wszystkich $x$ , oraz $x^4-x^2+4<(x^2)^2$ gdy $|x|>2$ , wnioskujemy, że jeżeli $|x|>2$ , wówczas

$ (x^2-1)^2<(y+2)^2<(x^2)^2. $

Jednak takiej zależności nie spełniają żadne liczby całkowite $x$ i $y$ . Zatem równania może mieć rozwiązanie jedynie gdy $x\in\{0,1,-1,2,-2\}$ . Sprawdzimy każdy z przypadków tych za pomocą prostych rachunków.

Dla $x=0$ , otrzymujemy $y=0$ lub $y=-4$ . W pierwszym przypadku rozwiązaniem jest $(m,n)=(0,0)$ , zaś w drugim $(m,n)=(2,-2)$ i $(m,n)=(-2,2)$ .

Dla $x=\pm1$ zachodzi $y=0$ lub $y=-4$ . Gdy $y=0$ , rozwiązaniami są pary $(0,\pm1)$ , $(\pm 1, 0)$ , a gdy $y=-4$ , wtedy nie znajdziemy żadnego rozwiązania $(m,n)$ .

Jeżeli $x=\pm2$ , to $y=2$ lub $y=-6$ i wówczas nie ma żadnych rozwiązań.

Odpowiedź: Szukane pary to: $(0,0)$ , $(2,-2)$ , $(-2,2)$ , $(-1,0)$ , $(0,-1)$ , $(0,1)$ , $(1,0)$ .

Sposób II

Dla $n=0$ otrzymujemy $m^4=m^2$ , czyli $m\in\{-1,0,1\}$ . W tym przypadku rozwiązaniami są pary: $(-1,0)$ , $(0,-1)$ , $(0,0)$ , $(0,1)$ , $(1,0)$ . Dla $m=0$ rozwiązania są oczywiście takie same.

Załóżmy teraz, że $m\neq 0$ i $n\neq 0$ . Równanie równoważnie można zapisać jako

$ \begin{split} (m^4+4m^3n+5m^2n^2+4mn^3+n^4)-(m^2+6mn+n^2)=\\=(m^2+3mn+n^2)(m^2+mn+n^2)-(m^2+6mn+n^2), \end{split} $

więc $m^2+nm+n^2$ jest dzielnikiem $5mn$ .

Niech $d=\gcd(m,n)$ , $a=m/d$ i $b=n/d$ , gdzie $a$ i $b$ są względnie pierwsze. Wtedy

$ (1) \qquad a^2+ab+b^2\mid 5ab. $

Zauważmy jednak, że $\gcd(a^2+ab+b^2,a)=\gcd(b^2,a)=1$ i analogicznie $\gcd(a^2+ab+b^2,b)=1$ , więc $\gcd(a^2+ab+b^2,ab)=1$ . Stąd i z (1)

$ a^2+ab+b^2\mid5, $

co oznacza, że $a^2+ab+b^2-c=0$ dla $c\in\{1,-1,5,-5\}$ .

Wyróżnikiem powyższego równania względem zmiennej $a$ jest $\Delta=4c-3b^2$ , więc rozwiązania mogą istnieć tylko dla $c=1$ lub $c=5$ , a ze względu na to, że szukamy rozwiązań całkowitych, $4c-3b^2$ musi być kwadratem.

Widzimy, że dla $c=5$ musi zachodzić $b=\pm1,\pm2$ , ale wtedy liczba $4c-3b^2$ nie jest kwadratem. Dla $c=1$ jedynie dla $b=\pm1$ wyrażenie $4c-3b^2$ jest kwadratem i wtedy $a=-b$ . Stąd $m=-n$ i równanie upraszcza się do $m^4-4m^2=0$ . Zatem $m=\pm2$ i otrzymujemy rozwiązania $(m,n)=(2,–2)$ i $(m,n)=(–2,2)$ .

Podsumowując, rozwiązaniami równania są pary: $(0,0)$ , $(2,-2)$ , $(-2,2)$ , $(-1,0)$ , $(0,-1)$ , $(0,1)$ , $(1,0)$ .

III MEMO - Zadanie 12

Zawody matematyczne:

III MEMO, 2009

Rozwiązać równanie

$ (1) \qquad 2^x+2009=3^y5^z $

w liczbach całkowitych nieujemnych $x$ , $y$ , $z$ .

Rozwiązanie

Zauważmy, że $x\geq2$ i $y+z\geq1$ . Porównując obie strony równania (1) kolejno modulo 4, 3 i 5, otrzymujemy: $1\equiv(-1)^y\pmod4$ , więc $y$ jest liczbą parzystą; jeżeli $y>0$ , to $(-1)^x+2\equiv0\pmod3$ i $x$ jest liczbą parzystą; jeśli $z>0$ , to $2^x-1\equiv0\pmod5$ i $x$ jest liczbą parzystą. Zatem liczba $x$ jest parzysta, bo na pewno $y>0$ lub $z>0$ .

Niech $x=2x'$ i $y=2y'$ . Przypuśćmy, że $z$ jest nieparzyste. Wtedy

$ 3^y5^z\equiv9^{y'}5^z\equiv2^{y_1}(-2)^z\equiv r_1\pmod7\quad\text{dla }r_1\in\{3,5,6\} $

oraz

$ 2^x+2009\equiv4^{x'}\equiv r_2\pmod7\quad\text{dla }r_2\in\{1,2,4\}. $

Nie jest możliwe by $r_1=r_2$ , więc, rozważając równanie (1) modulo 7, dochodzimy do sprzeczności. Z tego wynika, że $z$ musi być liczbą parzystą.

Niech $z=2z'$ . Równanie (1) możemy teraz zapisać w postaci

$ 2009=(3^{y'}5^{z'}-2^{x'})(3^{y'}5^{z'}+2^{x'})=ab, $

gdzie $a=3^{y'}5^{z'}-2^{x'}$ , $b=3^{y'}5^{z'}+2^{x'}$ . Po rozłożeniu 2009 na czynniki pierwsze $2009=41\cdot7^2$ , więc $(a,b)$ jest jedną par: $(1,2009)$ , $(7,287)$ , $(41,49)$ . Widzimy ponadto, że $b-a=2^{x'+1}$ , a różnica wyrazów w wymienionych parach jest potęgą 2 jedynie w przypadku $(41,49)$ , zatem $a=41$ i $b=49$ .

Stąd, rozwiązując układ dwóch równań, otrzymujemy $2^{x'}=4$ i $3^{y'}5^{z'}=45=3^2\cdot5$ . Prowadzi to do $x'=2$ , $y'=2$ , $z'=1$ , czyli jedynym rozwiązaniem zadania jest $x=4$ , $y=4$ , $z=2$ .