Międzynarodowa Olimpiada Matematyczna

Międzynarodowa Olimpiada Matematyczna (MOM) odbywa się od 1959 roku. W zawodach tych uczestniczą uczniowie z kilkudziesięciu państw, również z Polski. Na MOM Komitet Główny powołuje sześciu uczniów, którzy uzyskali najlepsze rezultaty na zawodach trzeciego stopnia Olimpiady Matematycznej. Zawody MOM trwają dwa dni, każdego dnia uczestnicy rozwiązują po 3 zadania, na które mają 4,5 godziny czasu. Uczniowie powołani na MOM uczestniczą w obozie przygotowawczym.

L MOM

Zawody matematyczne:

L MOM, 2009

Zadania z L Międzynarodowej Olimpiady Matematycznej.

Załącznik	Wielkość
L MOM - Zadania z rozwiązaniami [1]	196.18 KB

L MOM - Zadanie 1

Zawody matematyczne:

L MOM, 2009

Dana jest dodatnia liczba całkowita $n$ oraz parami różne liczby całkowite $a_1,\dots,a_k$ ( $k\geq2$ ), będące elementami zbioru $\{1,\dots,n\}$ . Ponadto, dla każdego $i=1,\dots,k-1$ , liczba $n$ jest dzielnikiem liczby $a_i(a_{i+1}-1)$ . Udowodnić, że $n$ nie jest dzielnikiem liczby $a_k(a_1-1)$ .

Rozwiązanie

Podane w treści zadania podzielności można zapisać w postaci kongruencji:

$ a_ia_{i+1}\equiv a_i\pmod n\quad\text{dla }i=1,2,\dots,k-1. $

Wynika z nich, że

$ (1) \qquad a_1a_2\dots a_{k-1}a_k\equiv a_1a_2\dots a_{k-1}\equiv\dots\equiv a_1\pmod n. $

Aby przeprowadzić dowód nie wprost, załóżmy, że liczba $n$ dzieli iloczyn $a_k(a_1-1)$ , czyli $a_ka_1\equiv a_k\pmod n$ . Wówczas

$ (2) \begin{split} a_1a_2\dots a_k &= a_ka_1\dots a_{k-2}a_{k-1}\equiv a_ka_1\dots a_{k-2} \\ \equiv\dots &\equiv a_ka_1\equiv a_k\pmod n. \end{split} $

Z (1) i (2) wynika, że $a_1\equiv a_k\pmod n$ . To jest jednak niemożliwe, gdyż $a_1,a_k\in\{1,\dots,n\}$ oraz $a_1\neq a_k$ . Uzyskana sprzeczność dowodzi, że liczba $n$ nie dzieli iloczynu $a_k(a_1-1)$ .

L MOM - Zadanie 2

Zawody matematyczne:

L MOM, 2009

Punkt $O$ jest środkiem okręgu opisanego na trójkącie $ABC$ . Punkty $P$ oraz $Q$ są odpowiednio punktami wewnętrznymi odcinków $CA$ oraz $AB$ . Niech $K$ , $L$ oraz $M$ będą odpowiednio środkami odcinków $BP$ , $CQ$ oraz $PQ$ . Niech ponadto $\Gamma$ będzie okręgiem przechodzącym przez punkty $K$ , $L$ oraz $M$ . Załóżmy, że prosta $PQ$ jest styczna do okręgu $\Gamma$ . Wykazać, że $OP=OQ$ .

Rozwiązanie

Niech $K$ , $L$ , $M$ , $B'$ oraz $C'$ będą odpowiednio środkami odcinków $BP$ , $CQ$ , $PQ$ , $CA$ oraz $AB$ . Wówczas $MK=\tfrac{QB}2$ oraz $ML=\tfrac{PC}2$ . Z twierdzenia odwrotnego do twierdzenia Talesa wynika, że $CP\|LM$ , a stąd $\measuredangle LMP=\measuredangle QPA$ . Okrąg $k$ jest styczny do odcinka $PQ$ w punkcie $M$ , więc $\measuredangle LMP=\measuredangle LKM$ , czyli otrzymujemy równość kątów $\measuredangle QPA=\measuredangle LKM$ . Analogicznie dowodzimy, że $\measuredangle PQA=\measuredangle KLM$ . Uzyskane równości kątów dowodzą, że trójkąty $APQ$ i $MKL$ są podobne, a zatem

$ \frac{AP}{AQ}=\frac{MK}{ML}=\frac{\tfrac{QB}2}{\tfrac{PC}2}=\frac{QB}{PC}, $

czyli $AP\cdot PC=AQ\cdot QB$ .

$ \begin{split} OP^2-OQ^2&=OB'^2+B'P^2-OC'^2-C'Q^2=\\ &=(OA^2-AB'^2)+B'P^2-(OA^2-AC'^2)-C'Q^2=\\ &=(AC'^2-C'Q^2)-(AB'^2-B'P^2)=\\ &=(AC'-C'Q)(AC'+C'Q)-(AB'-B'P)(AB'+B'P)=\\ &=AQ(BC'+C'Q)-AP(CB'+B'P)=AQ\cdot QB-AP\cdot PC=\\ &=0 \end{split} $

Wynika stąd, że $OP=OQ$ .

L MOM - Zadanie 3

Zawody matematyczne:

L MOM, 2009

Ściśle rosnący ciąg $s_1,s_2,s_3,\dots$ , którego wyrazy są dodatnimi liczbami całkowitymi, ma tę własność, że jego podciągi

$ s_{s_1},s_{s_2},s_{s_3},\dots\qquad\text{oraz}\qquad s_{s_1+1},s_{s_2+1},s_{s_3+1},\dots $

są ciągami arytmetycznymi. Dowieść, że ciąg $s_1,s_2,s_3,\dots$ również jest ciągiem arytmetycznym.

Rozwiązanie

Sposób I

Niech $D$ będzie różnicą ciągu arytmetycznego $(s_{s_n})$ , czyli $D=s_{s_{n+1}}-s_{s_n}$ dla $n=1,2,\dots$ . Niech ponadto

$ d_n=s_{n+1}-s_n\qquad\text{dla}\quad n=1,2,\dots. $

Naszym celem jest pokazanie, że ciąg $(d_n)$ jest stały. Najpierw pokażemy, że jest to ciąg ograniczony. Zgodnie z założeniem, dla każdego $n$ zachodzi nierówność $d_n\geq1$ , a stąd wynika, że

$ \begin{split} d_n&=s_{n+1}-s_n=\underbrace{1+1+\dots+1}_{s_{n+1}-s_n\text{ jedynek}}\leq\\ &\leq d_{s_n}+d_{s_n+1}+\dots+d_{s_{n+1}-1}=s_{s_{n+1}}-s_{s_n}=D, \end{split} $

czyli $1\leq d_n\leq D$ , a więc istotnie, ciąg $(d_n)$ jest ograniczony. Z tego, że jest on ograniczony, a jego wyrazy są liczbami całkowitymi, wynika, że przyjmuje on wartość najmniejszą i największą:

$ m=\min\{d_n\colon n=1,2,\dots\}\qquad\text{oraz}\qquad M=\max\{d_n\colon n=1,2,\dots\}. $

Pozostaje do pokazania, że $m=M$ .

Zauważmy, że dla każdego $n$ takiego, że $d_n=m$ (czyli $s_{n+1}=s_n+m$ ) zachodzi

$ \begin{split} D=s_{s_{n+1}}-s_{s_n}=s_{s_n+m}-s_{s_n}&=d_{s_n}+d_{s_n+1}+\dots+d_{s_n+m-1}\leq\\ &\leq\underbrace{M+M+\dots+M}_{m\text{ składników}}=mM, \end{split} $

przy czym równość w powyższym wzorze zachodzi wtedy i tylko wtedy, gdy $d_{s_n}=d_{s_n+1}=\dots=d_{s_n+m-1}=M$ . Podobnie, dla każdego $n$ takiego, że $d_n=M$ zachodzi

$ \begin{split} D=s_{s_{n+1}}-s_{s_n}=s_{s_n+M}-s_{s_n}&=d_{s_n}+d_{s_n+1}+\dots+d_{s_n+M-1}\geq\\ &\geq\underbrace{m+m+\dots+m}_{M\text{ składników}}=Mm, \end{split} $

przy czym równość zachodzi wtedy i tylko wtedy, gdy $d_{s_n}=d_{s_n+1}=\dots=d_{s_n+M-1}=m$ . Z powyższych dwóch obserwacji wynika, że $D=Mm$ , a ponadto, jeśli $d_n=m$ , to $d_{s_n}=M$ , a jeśli $d_n=M$ , to $d_{s_n}=m$ .

Rozważmy ciąg $(n_k)$ liczb całkowitych dodatnich, określony następująco:

$ \begin{cases}n_1\text{ jest dowolną (na przykład najmniejszą) liczbą taką, że }d_{n_1}=m\\ n_{k+1}=s_{n_k}\quad\text{dla }k=1,2,\dots \end{cases} $

Ponieważ $d_{n_1}=m$ , więc $d_{n_2}=d_{s_{n_1}}=M$ , a stąd $d_{n_3}=d_{s_{n_2}}=m$ , itd.: wyrazy ciągu $(d_{n_{k+1}})=(d_{s_{n_k}})$ są na przemian równe $m$ oraz $M$ .

Zauważmy, że

$ s_n=s_1+d_1+d_2+\dots+d_{n-1}\geq1+\underbrace{1+1+\dots+1}_{n-1\text{ jedynek}}=n. $

Wynika stąd, że dla każdego $k$ zachodzi $n_{k+1}=s_{n_k}\geq n_k$ , czyli ciąg $n_k$ jest niemalejący. Zachodzi jeden z dwóch przypadków: ciąg $(n_k)$ jest ściśle rosnący albo $n_k=n_{k+1}$ dla pewnego $k$ . Jeśli dla pewnego $k$ zachodzi $n_k=n_{k+1}$ , wówczas również $d_{s_{n_k}}=d_{s_{n_{k+1}}}$ , a ponieważ jedna z tych liczb jest równa $m$ , a druga $M$ , to $m=M$ , czyli ciąg $(s_n)$ jest ciągiem arytmetycznym. Jeśli natomiast ciąg $(n_k)$ jest ściśle rosnący, to jego wyrazy są parami różne i w ciągu $(d_{s_n})$ nieskończenie wiele wyrazów jest równych $m$ (między innymi wszystkie wyrazy $d_{s_{n_k}}$ , gdzie $k$ jest parzyste) oraz nieskończenie wiele wyrazów jest równych $M$ (w tym wszystkie wyrazy $d_{s_{n_k}}$ , gdzie $k$ jest nieparzyste). Ponieważ ciągi $(s_{s_n})$ i $(s_{s_n+1})$ są ciągami arytmetycznymi oraz $d_{s_n}=s_{s_n+1}-s_{s_n}$ , więc również ciąg $(d_{s_n})$ jest arytmetyczny. Wynika stąd, że $m$ = $M$ , czyli ciąg $(s_n)$ jest ciągiem arytmetycznym.

Sposób II

Ponieważ $(s_{s_n})$ oraz $(s_{s_n+1})$ są ciągami arytmetycznymi, więc istnieją liczby $A$ , $B$ , $C$ oraz $D$ takie, że

$ s_{s_n}=A+nC\qquad\text{oraz}\qquad s_{s_n+1}=B+nD\qquad\text{dla}\quad n=1,2,\dots. $

Ciąg $(s_n)$ jest ściśle rosnący, więc dla każdego $n$ zachodzi $s_{s_n}<s_{s_n+1}\leq s_{s_{n+1}}$ , czyli

$ A+nC<B+nD\leq A+(n+1)C $

albo równoważnie $0<B-A+n(D-C)\leq C$ . Wynika stąd, że $D=C$ (czyli różnice ciągów arytmetycznych $(s_{s_n})$ oraz $(s_{s_n+1})$ są takie same) oraz $B-A\leq C$ . Jeśli $B-A=C$ , to dla każdego $n$ zachodzi równość

$ s_{s_n+1}=B+nC=A+(n+1)C=s_{s_{n+1}}, $

a ponieważ ciąg $(s_n)$ jest ściśle rosnący, więc $s_n+1=s_{n+1}$ , a zatem ciąg $(s_n)$ jest ciągiem arytmetycznym o różnicy 1. Pozostaje zatem do rozważenia jedynie przypadek, gdy $B-A<C$ .

Niech $m$ i $N$ będą liczbami spełniającymi równości $m=\min\{s_{n+1}-s_n\colon n=1,2,\dots\}=s_{N+1}-s_N$ . Wówczas

$ B-A=(s_{s_n+1}-D)-(s_{s_n}-C)=s_{s_n+1}-s_{s_n}\geq m, $

$ C=s_{s_{s_1+1}}-s_{s_{s_1}}=s_{B+C}-s_{A+C}\geq(B-A)m $

oraz

$ \begin{split} m(A-B+C-1)&=m((A+(N+1)C)-(B+NC+1))\leq\\ &\leq s_{A+(N+1)C}-s{B+NC+1}=s_{s_{s_{N+1}}}-s_{s_{s_N+1}+1}=\\ &=(A+s_{N+1}C)-(B+(s_N+1)C)=\\ &=(s_{N+1}-s_N)C+A-B-C=mC+A-B-C. \end{split} $

Uzyskaną nierówność można zapisać jako

$ (B-A-m)+(C-m(B-A))\leq0, $

co wraz z dwiema wcześniejszymi nierównościami daje

$ B-A=m\qquad\text{oraz}\qquad C=m(B-A). $

Gdyby ciąg $(s_n)$ nie był ciągiem arytmetycznym, wówczas dla pewnego $n$ zachodziłoby $s_{n+1}-s_n>m$ , a wówczas

$ \begin{split} m^2&<m(s_{n+1}-s_n)\leq s_{s_{n+1}}-s_{s_n}=(A+(n+1)C)-(A+nC)=\\ &=C=m(B-A)=m^2. \end{split} $

Uzyskana sprzeczność dowodzi, że ciąg $(s_n)$ jest ciągiem arytmetycznym.

L MOM - Zadanie 4

Zawody matematyczne:

L MOM, 2009

W trójkącie $ABC$ zachodzi równość $AB=AC$ . Dwusieczne kątów $CAB$ oraz $ABC$ przecinają jego boki $BC$ oraz $AC$ odpowiednio w punktach $D$ i $E$ . Punkt $K$ jest środkiem okręgu wpisanego w trójkąt $ADC$ . Załóżmy ponadto, że $\measuredangle BEK=45^\circ$ . Wyznaczyć możliwe wartości $\measuredangle CAB$ .

Rozwiązanie

Pokażemy, że jedynymi możliwymi wartościami $\measuredangle CAB$ są wartości $60^\circ$ oraz $90^\circ$ .

Niech $I$ będzie punktem przecięcia prostych $AD$ oraz $BE$ . Ponieważ proste te zawierają dwusieczne kątów wewnętrznych $CAB$ i $ABC$ trójkąta $ABC$ , więc $I$ jest środkiem okręgu wpisanego w ten trójkąt. Niech ponadto $G$ będzie punktem symetrycznym do punktu $E$ względem prostej $IC$ . Ponieważ półprosta $CI^\to$ jest dwusieczną kąta $BCA$ , więc punkt $G$ leży na prostej $BC$ . Punkty $D$ i $G$ leżą po tej samej stronie prostej $IC$ , gdyż oba leżą po przeciwnej jej stronie, niż punkt $E$ .

Jeśli $G=D$ , wówczas $\measuredangle IEC=\measuredangle IDC=90^\circ$ , czyli dwusieczna kąta $ABC$ jest prostopadła do boku $AC$ trójkąta $ABC$ . Wynika stąd, że $BC=BA$ , zatem trójkąt $ABC$ jest trójkątem równobocznym i $\measuredangle CAB=60^\circ$ .

Jeśli $G\neq D$ , wówczas $\measuredangle IGK=\measuredangle IEK=45^\circ=\measuredangle IDK$ . Wynika stąd, że punkty $I$ , $D$ , $G$ oraz $K$ leżą na jednym okręgu. Prowadzi to do następujących równości:

$ \begin{split} \measuredangle EIK&=\measuredangle GIK=\measuredangle GDK=45^\circ,\quad\text{gdy }G\in DC^\to\\ \text{lub }\measuredangle EIK&=\measuredangle GIK=180^\circ-\measuredangle GDK=45^\circ,\quad\text{gdy }G\in DB^\to\\ \measuredangle BIC&=180^\circ-\measuredangle EIK=135^\circ\\ \measuredangle CAB&=180^\circ-(\measuredangle ABC+\measuredangle BCA)=180^\circ-2(\measuredangle IBC+\measuredangle BCI)=\\ &=180^\circ-2(180^\circ-\measuredangle BIC)=180^\circ-2(180^\circ-135^\circ)=90^\circ \end{split} $

Pozostaje sprawdzić, że jeśli $\measuredangle CAB=60^\circ$ lub $\measuredangle CAB=90^\circ$ , to $\measuredangle BEK=45^\circ$ .

Gdy $\measuredangle CAB=60^\circ$ , wówczas trójkąt $ABC$ jest trójkątem równobocznym i wtedy $D=G$ , a stąd $\measuredangle BEK=\measuredangle IGK=\measuredangle IDK=45^\circ$ .

Jeśli natomiast $\measuredangle CAB=90^\circ$ , wówczas

$ \begin{split} \measuredangle ABC&=\measuredangle BCA=45^\circ,\\ \measuredangle KIE&=\measuredangle IBC+\measuredangle BCI=\tfrac12\measuredangle ABC+\tfrac12\measuredangle BCA=45^\circ,\\ \measuredangle IEA&=\measuredangle BEA=180^\circ-\measuredangle EAB-\measuredangle ABE=\\&=180^\circ-90^\circ-\tfrac12\measuredangle ABC=90^\circ-22,5^\circ=67,5^\circ,\\ \measuredangle AIE&=180^\circ-\measuredangle IEA-\measuredangle EAI=180^\circ-67,5^\circ-\tfrac12\measuredangle CAB=\\&=112,5^\circ-45^\circ=67,5^\circ. \end{split} $

Ponieważ $\measuredangle IEA=67,5^\circ=\measuredangle AIE$ , więc trójkąt $EAI$ jest trójkątem równoramiennym i dwusieczna kąta $EAI$ jest zawarta w symetralnej boku $EI$ tego trójkąta. Ponieważ zaś punkt $K$ leży na dwusiecznej kąta $EAI$ , więc leży też na symetralnej odcinka $EI$ i mamy $KE=KI$ . Wynika stąd, że trójkąt $IKE$ jest równoramienny i $\measuredangle BEK=\measuredangle IEK=\measuredangle KIE=45^\circ$ .

L MOM - Zadanie 5

Zawody matematyczne:

L MOM, 2009

Wyznaczyć wszystkie funkcje $f$ przekształcające zbiór dodatnich liczb całkowitych w zbiór dodatnich liczb całkowitych takie, że dla każdych dwóch dodatnich liczb całkowitych $a$ oraz $b$ istnieje niezdegenerowany trójkąt, którego boki mają długości

$ a,\quad f(b)\quad\text{oraz}\quad f(b+f(a)-1). $

(Trójkąt niezdegenerowany to taki, którego wierzchołki nie leżą na jednej prostej.)

Rozwiązanie

Odpoowiedź: jedyną funkcją spełniającą warunki zadania jest funkcja tożsamościowa, $f(x)=x$ .

Sprawdzimy, że funkcja $f(x)=x$ spełnia warunki zadania. Dla funkcji tej i dla dowolnych dodatnich liczb całkowitych $a$ i $b$ zachodzą nierówności:

$ \begin{split} f(b+f(a)-1)=a+b-1&<a+b=a+f(b),\\ a&<b+a+b-1=f(b)+f(b+f(a)-1)\\ \text{oraz}\quad f(b)=b&<a+b-1+a=f(b+f(a)-1)+a, \end{split} $

czyli liczby $a$ , $f(b)$ oraz $f(b+f(a)-1)$ są długościami boków pewnego niezdegenerowanego trójkąta.

Niech teraz $f$ będzie dowolną funkcją spełniającą warunki zadania. Wykażemy, że dla każdej dodatniej liczby całkowitej $x$ zachodzi równość $f(x)=x$ .

Najpierw udowodnimy, że $f(1)=1$ . W tym celu, dla dowolnej dodatniej liczby całkowitej $x$ , rozważmy liczby całkowite 1, $f(x)$ oraz $f(x+f(1)-1)$ . Są one długościami boków pewnego niezdegenerowanego trójkąta, zatem spełniona jest nierówność $|f(x)-f(x+f(1)-1)|<1$ , czyli

$ f(x+f(1)-1)=f(x). $

Wynika stąd, że gdyby zachodziła nierówność $f(1)>1$ , wówczas funkcja $f$ byłaby funkcją okresową o okresie $f(1)-1$ . Byłaby zatem funkcją ograniczoną, czyli dla pewnej dodatniej liczby $B$ zachodziłaby nierówność $f(x)<B$ dla $x=1,2,\dots$ . Niech $z$ będzie dodatnią liczbą całkowitą spełniającą nierówność $z>2B$ . Wówczas $z>2B>f(1)+f(1+f(z)-1)$ co przeczy temu, że istnieje niezdegenerowany trójkąt, którego boki mają długości $z$ , $f(1)$ oraz $f(1+f(z)-1)$ . Zatem nie może zachodzić $f(1)>1$ . Dowiedliśmy w ten sposób, że $f(1)=1$ .

Niech $x$ będzie dodatnią liczbą całkowitą. Rozważmy trójkąt o bokach mających długości $x$ , $f(1)=1$ oraz $f(1+f(x)-1)=f(f(x))$ . Zachodzi nierówność

$ |x-f(f(x))|<1, $

z której wynika, że $f(f(x))=x$ . W szczególności oznacza to, że funkcja $f$ jest różnowartościowa.

Niech $d=f(2)-1$ . Zauważmy, że $d\geq1$ , gdyż $f(2)\neq f(1)=1$ . Ponieważ dla każdej dodatniej liczby całkowitej $x$ liczby 2, $f(x)$ oraz $f(x+f(2)-1)=f(x+d)$ są długościami boków pewnego niezdegenerowanego trójkąta, więc zachodzi nierówność

$ |f(x)-f(x+d)|<2, $

czyli

$ (1) \qquad f(x+d)\in\{f(x)-1,f(x),f(x)+1\}. $

Stosując indukcję udowodnimy, że $f(1+kd)=1+k$ dla $k=0,1,\dots$ . Wykazaliśmy już, że $f(1+0\cdot d)=f(1)=1=1+0$ . Z kolei $f(1+1\cdot d)=f(f(2))=2=1+1$ . Załóżmy, że $f(1+kd)=1+k$ dla $k=0,1,\dots,n$ , gdzie $n\geq1$ . Wówczas z (1) wynika, że $f(1+(n+1)d)=f((1+nd)+d)$ jest jedną z liczb

$ f(1+nd)-1,\quad f(1+nd)\quad\text{oraz}\quad f(1+nd)+1. $

Z tego, że funkcja $f$ jest różnowartościowa oraz $d>0$ wynika, że

$ \begin{split} f(1+(n+1)d)&\neq f(1+nd)\\ \text{oraz}\quad f(1+(n+1)d)&\neq f(1+(n-1)d)=1+(n-1)=\\&\quad=(1+n)-1=f(1+nd)-1,\\ \text{zatem}\quad f(1+(n+1)d)&=f(1+nd)+1=(1+n)+1=1+(n+1). \end{split} $

Tym samym dowiedliśmy, że $f(1+kd)=1+k$ dla $k=0,1,\dots$ .

Aby zakończyć rozwiązanie zadania należy wykazać, że $d=1$ . Zauważmy, że

$ f(2)=1+(f(2)-1)=1+d=f(1+d\cdot d), $

czyli, wobec różnowartościowości funkcji $f$ , mamy $2=1+d^2$ . Zatem $d=1$ i $f(1+k)=1+k$ dla $k=0,1,\dots$ . Tym samym dowiedliśmy, że $f(x)=x$ dla każdej dodatniej liczby całkowitej $x$ .

L MOM - Zadanie 6

Zawody matematyczne:

L MOM, 2009

Liczby $a_1,a_2,\dots,a_n$ są parami różnymi dodatnimi liczbami całkowitymi, zaś $M$ jest zbiorem $n-1$ dodatnich liczb całkowitych, przy czym $M$ nie zawiera liczby $s=a_1+a_2+\dots+a_n$ . Konik polny skacze wzdłuż osi liczbowej w dodatnim jej kierunku. Zaczyna w punkcie 0 i wykonuje $n$ skoków, których długościami są liczby $a_1,a_2,\dots,a_n$ , wzięte w pewnej kolejności. Udowodnić, że kolejność tę można wybrać w taki sposób, by po żadnym ze skoków konik polny nie wylądował w punkcie należącym do zbioru $M$ .

Rozwiązanie

Przeprowadzimy dowód z użyciem indukcji matematycznej. Gdy $n=1$ , wówczas zbiór $M$ jest pusty i konik polny wykonuje skok lądując poza zbiorem $M$ . Niech $n>1$ . Załóżmy, że dla każdego $k<n$ konik polny może zaplanować wykonanie $k$ skoków o parami różnych długościach omijając przy tym $k-1$ elementowy zbiór, który nie zawiera sumy długości skoków. Udowodnimy, że jest wówczas również możliwe zaplanowanie $n$ skoków o parami różnych długościach $a_1,a_2,\dots,a_n$ tak, by ominąć $n-1$ elementowy zbiór $M$ , do którego nie należy suma $a_1+a_2+\dots+a_n$ . Bez straty ogólności możemy założyć, że $a_1<a_2<\dots<a_n$ . Niech ponadto $d=\min M$ będzie najmniejszym elementem zbioru $M$ . Rozważmy dwa przypadki:

Przypadek 1.: $d<a_n$ . Rozważmy $n$ zbiorów: $\{a_n\}$ , $\{a_1,a_1+a_n\}$ , $\{a_2,a_2+a_n\}$ , $\{a_3,a_3+a_n\}$ , \dots, $\{a_{n-1},a_{n-1}+a_n\}$ . Z tego, że liczby $a_1,a_2,\dots,a_n$ są parami różne wynika, że są to zbiory rozłączne, zatem co najmniej jeden z nich jest rozłączny z $n-1$ elementowym zbiorem $M$ .

Jeśli $M\cap\{a_n\}=\emptyset$ , wówczas konik polny wykonuje najpierw skok o długości $a_n$ , przeskakując jednocześnie co najmniej jeden z elementów zbioru $M$ (gdyż $d<a_n$ ). Pozostaje mu do wykonania $n-1$ skoków o długościach $a_1,a_2,\dots,a_{n-1}$ . Nie może przy tym wylądować w żadnym z punktów $n-2$ elementowego zbioru $M\setminus\{d\}$ , więc zaplanowanie pozostałych skoków jest możliwe na mocy założenia indukcyjnego.

Jeśli $M\cap\{a_n\}\neq\emptyset$ , czyli $a_n\in M$ , wówczas $M\cap\{a_i,a_i+a_n\}=\emptyset$ dla pewnego $i$ . Pierwsze dwa skoki, które wykonuje konik polny mają długości odpowiednio $a_i$ oraz $a_n$ . Wykonując te skoki konik polny nie ląduje w zbiorze $M$ , za to przeskakuje co najmniej dwa elementy tego zbioru: $d$ oraz $a_n$ . Pozostają mu do wykonania $n-2$ skoki przy czym nie może wylądować w żadnym z punktów $n-3$ elementowego zbioru $M\setminus\{d,a_n\}$ . Zaplanowanie tych skoków jest możliwe na mocy założenia indukcyjnego.

Przypadek 2.: $d\geq a_n$ . Jeśli pierwszy skok konika polnego ma długość $a_n$ (w przypadku, gdy $a_n=d$ , skok ten kończy się w zbiorze $M$ ), to na mocy założenia indukcyjnego pozostałe $n-1$ skoków o długościach $a_1,a_2,\dots,a_{n-1}$ można zaplanować w taki sposób, by podczas ich wykonywania nie wylądować w żadnym z punktów $n-2$ elementowego zbioru $M\setminus\{d\}$ . Uzyskujemy w ten sposób kolejno skoki o długościach $a_n,a_{i_1},a_{i_2},\dots,a_{i_{n-1}}$ . Jedynym elementem zbioru $M$ , w którym konik polny może wylądować wykonując te skoki jest $d$ . Jeśli to nie następuje, wówczas $a_n,a_{i_1},a_{i_2},\dots,a_{i_{n-1}}$ jest żądaną kolejnością wykonywania skoków. W przeciwnym przypadku konik polny ląduje w punkcie $d$ po wykonaniu $k\in\{1,2,\dots,n-1\}$ skoków, czyli $a_n+a_{i_1}+a_{i_2}+\dots+a_{i_{k-1}}=d$ i nie ląduje w żadnym innym punkcie zbioru $M$ . Zmieńmy kolejność wykonywania skoków na następującą: $a_{i_1},a_{i_2},\dots,a_{i_k},a_n,a_{i_{k+1}},\dots,a_{i_{n-1}}$ . Ponieważ zmianie uległa jedynie kolejność wykonywania $k+1$ pierwszych skoków, więc po wykonaniu każdego z ostatnich $n-k$ skoków konik polny wyląduje poza zbiorem $M$ (tak, jak przed zmianą kolejności skoków). Zauważmy jednak, że również po wykonaniu każdego spośród pierwszych $k$ skoków nie wyląduje w zbiorze $M$ , gdyż $a_{i_1}<a_{i_1}+a_{i_2}<\dots<a_{i_1}+a_{i_2}+\dots+a_{i_k}<d$ , zaś $d$ jest najmniejszym elementem zbioru $M$ .

XLVIII MOM

Zawody matematyczne:

XLVIII MOM, 2007

Zadania z XLVIII Międzynarodowej Olimpiady Matematycznej

Załącznik	Wielkość
XLVIII MOM - Zadania z rozwiązaniami [2]	161.93 KB

XLVIII MOM - Zadanie 1

Zawody matematyczne:

XLVIII MOM, 2007

Dane są liczby rzeczywiste $a_1$ , $a_2$ , $\ldots$ , $a_n$ . Dla każdego $i$ ( $1\le i\le n$ ) określamy

$ d_i=\max\{a_j:1\le j\le i\}-\min\{a_j:i\le j\le n\} $

oraz

$ d=\max\{d_i:1\le i\le n\}. $

Dowieść, że dla każdych liczb rzeczywistych $x_1\le x_2\le\ldots\le x_n$ spełniona jest nierówność

$ \max\{|x_i-a_i|:1\le i\le n\}\ge{d\over 2}.\leqno(*) $
Wykazać, że istnieją takie liczby rzeczywiste $x_1\le x_2\le\ldots\le x_n$ , dla których nierówność $(*)$ staje się równością.

Rozwiązanie

Z określenia liczby $d$ wynika, że istnieje wskaźnik $q\in\{1,2,\ldots,n\}$ , dla którego $d=d_q$ . Niech ponadto wskaźniki $p$ i $r$ ( $1\le p\le q\le r\le n$ ) spełniają warunki

$ a_p=\max\{a_j:1\le j\le q\},\qquad a_r=\min\{a_j:q\le j\le n\}. $

Wówczas prawdziwa jest równość $d=a_p-a_r$ .

Jeżeli teraz $x_1\le x_2\le\ldots\le x_n$ są dowolnymi liczbami rzeczywistymi, to na mocy nierówności $x_r-x_p\ge 0$ otrzymujemy

$ (a_p-x_p)+(x_r-a_r)=(a_p-a_r)+(x_r-x_p)\ge a_p-a_r=d. $

Wynika stąd, że przynajmniej jedna z liczb $a_p-x_p$ , $x_r-a_r$ jest nie mniejsza niż $d/2$ . Tym bardziej jedna z liczb $|x_p-a_p|$ , $|x_r-a_r|$ jest nie mniejsza niż $d/2$ i w konsekwencji uzyskujemy

$ \max\{|x_i-a_i|:1\le i\le n\}\ge\max\{|x_p-a_p|,|x_r-a_r|\}\ge{d\over 2}, $

co dowodzi tezy punktu (a).
Wykażemy, że żądane własności mają następujące liczby:

$ x_1=a_1-{d\over 2} \qquad\hbox{oraz}\qquad x_k=\max\Bigl\{x_{k-1},a_k-{d\over 2}\Bigr\}\quad\hbox{dla }k=2,3,\ldots,n. $

Z powyższego określenia wynika, że dla $k=2,3,\ldots,n$ zachodzi nierówność $x_{k-1}\le x_k$ ; otrzymujemy stąd ciąg nierówności $x_1\le x_2\le\ldots\le x_n$ . Również na mocy tego określenia uzyskujemy

$ x_k-a_k\ge-{d\over 2}\qquad\hbox{dla }k=1,2,\ldots,n. $

Ustalmy teraz wskaźnik $k\in\{1,2,\ldots,n\}$ oraz niech $m$ będzie najmniejszym takim wskaźnikiem, że $x_m=x_k$ . Wówczas jeśli $m>1$ , to prawdziwa jest nierówność $x_m>x_{m-1}$ , co oznacza, że

$ x_k=x_m=a_m-{d\over 2}. $

Jest jasne, że powyższa równość ma miejsce także w przypadku, gdy $m=1$ . Możemy zatem napisać

$ a_m-a_k\le \max\{a_j:1\le j\le k\}-\min\{a_j:k\le j\le n\}= d_k\le d, $

skąd wnioskujemy, że

$ x_k-a_k=(x_k-a_m)+(a_m-a_k)=-{d\over 2}+(a_m-a_k)\le{d\over 2}. $

Udowodniliśmy w ten sposób, iż

$ -{d\over 2}\le x_k-a_k\le {d\over 2}\qquad\hbox{dla }k=1,2,\ldots,n, $

czyli

$ \max\{|x_i-a_i|:1\le i\le n\}\le{d\over 2}. $

Ponieważ jednak $|x_1-a_1|=d/2$ , więc w powyższej nierówności ma miejsce równość. To kończy rozwiązanie części (b).

XLVIII MOM - Zadanie 2

Zawody matematyczne:

XLVIII MOM, 2007

Rozpatrzmy takich pięć punktów płaszczyzny $A$ , $B$ , $C$ , $D$ , $E$ , że czworokąt $ABCD$ jest równoległobokiem, a na czworokącie wypukłym $BCED$ można opisać okrąg. Niech $\ell$ będzie prostą przechodzącą przez punkt $A$ . Przypuśćmy, że prosta $\ell$ przecina wnętrze odcinka $DC$ w punkcie $F$ , a prostą $BC$ w punkcie $G$ . Niech ponadto $EF=EG=EC$ . Udowodnić, że prosta $\ell$ jest dwusieczną kąta $DAB$ .

Rozwiązanie

Niech $K$ i $L$ będą rzutami prostokątnymi punktu $E$ odpowiednio na proste $CF$ i $CG$ (rys. 1). Z równości $EF=EG=EC$ wynika, że punkty $K$ i $L$ są odpowiednio środkami odcinków $CF$ i $CG$ , a ponadto $EK\perp CF$ i $EL\perp CG$ .

Na czworokącie $BCED$ można opisać okrąg, zatem

$ \measuredangle CBE=\measuredangle CDE. $

To oznacza, że trójkąty prostokątne $BLE$ i $DKE$ są podobne, skąd mamy

$ (1) \qquad {BL\over EL}={DK\over EK}. $

Zauważmy dalej, że na mocy równoległości $AD\parallel BG$ trójkąty $AFD$ i $GFC$ są podobne. To pozwala przeprowadzić następujący rachunek:

${BL\over CL}= {BC\over CL}+1= {BC\over\frac{1}{2}\cdot CG}+1= {AD\over \frac{1}{2}\cdot CG}+1= {DF\over \frac{1}{2}\cdot CF}+1= {DF\over FK}+1= {DK\over FK}= {DK\over CK}. $

Łącząc uzyskaną zależność z równością (1) stwierdzamy, że

$ {EL\over CL}={EK\over CK}. $

Zatem trójkąty prostokątne $ELC$ i $EKC$ są podobne (cecha bok-kąt-bok). Mają one jednak wspólny odpowiedni bok $EC$ ; są wobec tego przystające. W konsekwencji $CK=CL$ oraz $CF=CG$ . Udowodniliśmy w ten sposób, że trójkąt $FCG$ jest równoramienny. To daje

$ \measuredangle GAB=\measuredangle GFC=\measuredangle FGC=\measuredangle FAD, $

co jest równoznaczne z tezą.

XLVIII MOM - Zadanie 3

Zawody matematyczne:

XLVIII MOM, 2007

W zawodach matematycznych niektórzy uczestnicy przyjaźnią się. Przyjaźń jest zawsze wzajemna. Grupę uczestników nazwiemy kliką, jeśli każdych dwóch zawodników tej grupy przyjaźni się. (W szczególności, każda grupa złożona z mniej niż dwóch zawodników jest kliką.) Liczbę osób, jaką liczy klika nazwiemy jej rozmiarem.

Wiadomo, że w zawodach tych rozmiar największej kliki jest liczbą parzystą. Dowieść, że uczestników zawodów można rozdzielić do dwóch pokoi tak, aby rozmiar największej kliki w jednym pokoju był równy rozmiarowi największej kliki w drugim pokoju.

Rozwiązanie

Przedstawimy algorytm rozdzielenia uczestników zawodów do dwóch pokoi, które będziemy nazywać Pokój A oraz Pokój B. Rozpoczniemy od pewnego początkowego rozdzielenia, a następnie będziemy wielokrotnie przenosić jedną osobę do drugiego pokoju, tak by w efekcie uzyskać rozdzielenie spełniające warunki zadania.

Na każdym etapie postępowania niech $A$ i $B$ oznaczają zbiory uczestników znajdujących się w odpowiednich pokojach, zaś $k(A)$ oraz $k(B)$ - rozmiary największych klik w tych pokojach.

Postępowanie składa się z czterech kroków.

Krok 1. Niech $M$ będzie jedną z klik największego rozmiaru. Z założenia rozmiar $|M|=2m$ jest liczbą parzystą. Umieśćmy wszystkich zawodników z tej kliki w pokoju $A$ , a pozostałych uczestników w pokoju $B$ .

Ponieważ $M$ jest kliką największego rozmiaru, w takim początkowym rozmieszczeniu prawdziwa jest zależność $k(A)=|M|\ge k(B)$ .

Krok 2. Dopóki zachodzi nierówność $k(A)>k(B)$ , przenosimy dowolnie wybraną osobę z pokoju $A$ do pokoju $B$ .

Zauważmy przede wszystkim, że nierówność $k(A)>k(B)$ oznacza, że pokój $A$ jest niepusty. Ponadto wszyscy aktualni mieszkańcy pokoju $A$ tworzą klikę, więc po przeniesieniu jednej osoby z tego pokoju rozmiar największej kliki w pokoju $A$ zmniejszy się o 1. Natomiast rozmiar największej kliki w pokoju $B$ nie zmienia się albo zwiększy się o 1.

Po wielokrotnym przeprowadzeniu przeniesienia jednej osoby z pokoju $A$ do pokoju $B$ otrzymamy sytuację, w której

$ k(A)=k(B)\quad\hbox{albo}\quad k(A)=k(B)-1. $

Dodatkowo w pokoju $A$ pozostało co najmniej $m$ osób, gdyż w przeciwnym razie w pokoju $B$ znalazłoby się przynajmniej $m+1$ osób należących do kliki $M$ , a w pokoju $A$ pozostałoby najwyżej $m-1$ osób; mielibyśmy więc $k(A)\le m-1$ , $k(B)\ge m+1$ , wbrew uzyskanej wcześniej alternatywie.

Jeżeli $k(A)=k(B)$ , to otrzymane rozmieszczenie uczestników spełnia warunki zadania.

Możemy więc przyjąć w dalszej części rozumowania, że $k(A)=n$ oraz $k(B)=n+1$ . Jak udowodniliśmy powyżej, mamy wówczas

$ n=|A|=|A\cap M|\ge m\quad\hbox{oraz}\quad|B\cap M|\le m. $

Krok 3.Jeżeli istnieje uczestnik $x\in B\cap M$ oraz $(n+1)$ -elementowa klika $C$ , do której uczestnik $x$ nie należy, to przenosimy uczestnika $x$ do pokoju $A$ .

Uczestnik $x$ należy do kliki $M$ i wobec tego po przeniesieniu go do pokoju $A$ w pokoju tym znajdzie się $n+1$ uczestników, z których wszyscy należą do tej kliki. W efekcie $k(A)=n+1$ . Ponadto rozmiar największej kliki w pokoju $B$ wynosił $n+1$ przed przeniesieniem uczestnika $x$ , zaś $(n+1)$ -osobowa klika $C$ pozostała w całości w pokoju $B$ . Tak więc $k(B)=n+1$ , czyli $k(A)=k(B)$ .

Zatem jeśli udało się wykonać krok 3, uzyskaliśmy żądane rozmieszczenie uczestników w pokojach. W przeciwnym razie przechodzimy do kroku 4.

Krok 4. Dopóki spełniona jest równość $k(B)=n+1$ , wybieramy dowolną $(n+1)$ -osobową klikę $C$ znajdującą się w pokoju $B$ i przemieszczamy jednego uczestnika $x\in C\setminus M$ do pokoju $A$ .

Zauważmy przede wszystkim, że procedura ta jest wykonalna:

$ |C|=n+1\ge m+1>m\ge|B\cap M|, $

co dowodzi, że zbiór $C\setminus M$ jest niepusty.

Przemieszczając jedną osobę z pokoju $B$ do pokoju $A$ zmniejszamy rozmiar $k(B)$ najwyżej o 1. Wobec tego po zakończeniu kroku 4 uzyskamy rozmieszczenie, w którym $k(B)=n$ .

Ponadto po zakończeniu kroku 4 w pokoju $A$ będzie znajdowała się $n$ -osobowa klika $A\cap M$ . Udowodnimy, że w tym pokoju nie ma większej kliki.

Niech więc $D$ będzie dowolną kliką w pokoju $A$ .

Uczestników umieszczonych w pokoju $A$ można podzielić na dwie grupy:

uczestnicy należący do kliki $M$ ;
uczestnicy, którzy w kroku 4 zostali
przeniesieni z pokoju $B$ .

Mieszkańcy pokoju $A$ należący do pierwszej grupy oczywiście przyjaźnią się ze wszystkimi osobami tworzącymi klikę $M$ . Weźmy teraz pod uwagę mieszkańca sklasyfikowanego w drugiej grupie. Ponieważ nie udało się wykonać kroku 3, więc przed rozpoczęciem kroku 4 każda $(n+1)$ -osobowa klika w pokoju $B$ zawierała $B\cap M$ jako podzbiór. Wobec tego każda osoba przeniesiona z tej kliki do pokoju $A$ przyjaźniła się ze wszystkimi osobami należącymi do kliki $B\cap M$ .

Udowodniliśmy w ten sposób, że wszyscy mieszkańcy pokoju $A$ przyjaźnią się ze wszystkimi uczestnikami kliki $B\cap M$ . Zauważmy następnie, że zbiór $D\cup(B\cap M)$ jest sumą dwóch klik: $D$ oraz $B\cap M$ ; ponadto każdy uczestnik należący do pierwszej kliki przyjaźni się z dowolnym uczestnikiem należącym do drugiej kliki. Wobec tego $D\cup(B\cap M)$ jest kliką. Jej rozmiar nie przekracza największego rozmiaru kliki wśród wszystkich uczestników zawodów, czyli liczby $|M|$ . Stąd mamy

$ |M|\ge |D\cup(B\cap M)|=|D|+|B\cap M|=|D|+|M|-|A\cap M|. $

To pociąga nierówność $|D|\le|A\cap M|=n$ . Tym samym wykazaliśmy, że dowolna klika w pokoju $A$ liczy najwyżej $n$ uczestników.

Ostatecznie $k(A)=k(B)=n$ , a to oznacza, że rozmieszczenie uczestników w pokojach po zakończeniu kroku 4 spełnia warunki zadania.

XLVIII MOM - Zadanie 4

W trójkącie $ABC$ dwusieczna kąta $BCA$ przecina okrąg opisany na tym trójkącie w punkcie $R$ różnym od $C$ , symetralną odcinka $BC$ w punkcie $P$ oraz symetralną odcinka $AC$ w punkcie $Q$ . Punkt $K$ jest środkiem odcinka $BC$ , a punkt $L$ jest środkiem odcinka $AC$ . Wykazać, że trójkąty $RPK$ oraz $RQL$ mają równe pola.

Rozwiązanie

Niech $O$ oznacza środek okręgu opisanego na trójkącie $ABC$ .

Jeżeli $AC=BC$ , to dwusieczna kąta $BCA$ jest osią symetrii trójkąta $ABC$ . Zatem punkty $P$ , $Q$ i $O$ pokrywają się, zaś punkty $K$ i $L$ są symetryczne względem tej dwusiecznej. Wobec tego trójkąty $RPK$ i $RQL$ są symetryczne względem prostej $CR$ ; w szczególności mają one równe pola.

Załóżmy więc, że $AC\ne BC$ . Dla ustalenia uwagi niech $AC<BC$ (rys. 2).

Oznaczmy: $\measuredangle BCA=\gamma$ . Trójkąty $PKC$ i $QLC$ mają kąty proste odpowiednio przy wierzchołkach $K$ i $L$ , a ponadto $\measuredangle PCK=\measuredangle QCL=\gamma/2$ . Zatem trójkąty te mają równe także trzecie kąty: $\measuredangle KPC$ i $\measuredangle LQC$ . Stąd mamy

$ \measuredangle OPQ=\measuredangle KPC=\measuredangle LQC=\measuredangle PQO. $

To dowodzi, że trójkąt $OPQ$ jest równoramienny ( $OP=OQ$ ). Ponadto

$ \measuredangle OPQ=\measuredangle KPC=90^\circ-\measuredangle KCP=90^\circ-\frac{1}{2}\gamma $

i w efekcie dostajemy zależność $\measuredangle POQ=180^\circ-2\measuredangle OPQ=\gamma$ . Dalej, zauważmy, że $OA=OR=OB$ oraz

$ \measuredangle AOR=\measuredangle ROB=2\measuredangle ACR=2\measuredangle RCB=\gamma. $

Uzyskane zależności pozwalają stwierdzić, że obrót wokół punktu $O$ o kąt $\gamma$ przeprowadza punkty $Q$ , $A$ , $R$ odpowiednio na punkty $P$ , $R$ , $B$ . Stąd wniosek, że trójkąty $RQA$ i $RBP$ są przystające.

Punkt $K$ jest środkiem odcinka $BC$ , więc jego odległość od prostej $CR$ jest równa połowie odległości punktu $B$ od tej prostej. To oznacza, że

$ [RPK]=\frac{1}{2}[RBP], $

gdzie przez $[{\cal F}]$ oznaczamy pole figury ${\cal F}$ . Analogicznie

$ [RQL]=\frac{1}{2}[RQA]. $

Łącząc dwie powyższe równości z wykazanym wcześniej przystawaniem trójkątów $RBP$ i $RQA$ dostajemy tezę zadania:

$ [RPK]=\frac{1}{2}[RBP]=\frac{1}{2}[RQA]=[RQL]. $

XLVIII MOM - Zadanie 5

Zawody matematyczne:

XLVIII MOM, 2007

Niech $a$ oraz $b$ będą liczbami całkowitymi dodatnimi. Dowieść, że jeśli liczba $(4a^2-1)^2$ jest podzielna przez $4ab-1$ , to $a=b$ .

Rozwiązanie

Przypuśćmy, że teza zadania jest fałszywa. Niech $S$ oznacza zbiór wszystkich takich par $(a,b)$ liczb całkowitych dodatnich, że $a\ne b$ oraz liczba $(4a^2-1)^2$ jest podzielna przez $4ab-1$ .

Z przyjętego założenia wynika, że zbiór $S$ jest niepusty. Udowodnimy ponadto, że:

Dla każdej pary $(k,m)\in S$ spełniającej warunek $k<m$ istnieje para $(k,n)\in S$ , w której $n<k$ .
Jeżeli para $(k,m)$ należy do zbioru $S$ , to para $(m,k)$ również.

Dowód zdania1. Przyjmijmy

$ w={(4k^2-1)^2\over 4km-1}. $

Para $(k,m)$ należy do zbioru $S$ , zatem liczba $w$ jest całkowita. Zależności $(4k^2-1)^2\equiv 1\,\,\mod{4k}$ oraz $4km-1\equiv -1\,\,\mod{4k}$ w połączeniu z równością $(4k^2-1)^2=(4km-1)w$ dowodzą, że $m\equiv -1\,\,\mod{4k}$ , czyli $w=4kn-1$ dla pewnej liczby całkowitej dodatniej $n$ . Wykażemy, że liczba $n$ spełnia tezę zdania 1.

Rzeczywiście, z określenia liczby $w$ wynika, że jest ona dzielnikiem liczby $(4k^2-1)^2$ . Z uwagi na równość $w=4kn-1$ dostajemy więc $(k,n)\in S$ . Ponadto na podstawie zależności $k<m$ możemy napisać

$ 4kn-1=w={(4k^2-1)^2\over 4km-1}<{(4k^2-1)^2\over 4k^2-1}=4k^2-1, $

skąd płynie wniosek, że $n<k$ .

Dowód zdania2. Należy dowieść, że z podzielności $4km-1\,|\,(4k^2-1)^2$ wynika podzielność $4km-1\,|\,(4m^2-1)^2$ . Ponieważ liczba

$ \begin{split} k^2(4m^2-1)^2-m^2(4k^2-1)^2 &=16m^2k^2(m^2-k^2)+k^2-m^2=\cr &=(m^2-k^2)(4km-1)(4km+1) \end{split} $

jest podzielna przez $4km-1$ , więc z zależności $4km-1\,|\,(4k^2-1)^2$ otrzymujemy $4km-1\,|\,k^2(4m^2-1)^2$ . Jednak liczby $k^2$ i $4km-1$ są względnie pierwsze, co pociąga podzielność $4km-1\,|\,(4m^2-1)^2$ .

Zbiór $S$ jest niepusty, więc wśród wszystkich par $(c,d)\in S$ możemy wybrać parę, dla której wartość $2c+d$ jest najmniejsza.

Przypuśćmy, że $c<d$ . Wówczas na mocy zdania 1. istnieje w zbiorze $S$ taka para $(c,d')$ , że $d'<c$ . Zatem $2c+d'<2c+c<2c+d$ , wbrew minimalności liczby $2c+d$ . Wobec tego zachodzi nierówność $c>d$ . Zdanie 2. dowodzi, że para $(d,c)$ należy do zbioru $S$ . Jednakże $2d+c<2c+d$ , co ponownie prowadzi do sprzeczności z minimalnością liczby $2c+d$ .

Uzyskana sprzeczność dowodzi, że rozpatrywana teza jest prawdziwa.

XLVIII MOM - Zadanie 6

Zawody matematyczne:

XLVIII MOM, 2007

Niech $n$ będzie liczbą całkowitą dodatnią. Rozpatrujemy

$ S=\{(x,y,z):x,y,z\in\{0,1,\ldots,n\},\,x+y+z>0\} $

jako zbiór $(n+1)^3-1$ punktów w przestrzeni trójwymiarowej. Wyznaczyć najmniejszą możliwą liczbę płaszczyzn, których suma zawiera zbiór $S$ , ale nie zawiera punktu $(0,0,0)$ .

Rozwiązanie

Udowodnimy najpierw następujący

Lemat

Niech $P(x_1,x_2,\ldots,x_k)$ będzie wielomianem $k$ zmiennych. Przypuśćmy, że dla dowolnych liczb $a_1,a_2,\ldots,a_k \in\{0,1,\ldots,n\}$ , nie wszystkich równych zeru, zachodzi równość $P(a_1,a_2,\ldots,a_k)=0$ , natomiast $P(0,0,\ldots,0)\ne 0$ . Wówczas stopień wielomianu $P$ jest nie niższy niż $kn$ .

Dowód

Przeprowadzimy indukcję ze względu na wartość $k$ .

Dla $k=1$ teza jest prawdziwa, gdyż wielomian $P$ ma $n$ pierwiastków: 1, 2, $\ldots$ , $n$ , lecz nie jest wielomianem zerowym ( $P(0)\ne 0$ ). Jego stopień jest zatem równy co najmniej $n$ .

Niech teraz dany będzie wielomian $P(x_1,\ldots,x_{k-1},x_k)$ , gdzie $k\ge 2$ . Niech $W(x_1,\ldots,x_{k-1},x_k)$ i $R(x_1,\ldots,x_{k-1},x_k)$ będą odpowiednio ilorazem i resztą z dzielenia wielomianu $k$ zmiennych $P(x_1,\ldots,x_{k-1},x_k)$ przez wielomian jednej zmiennej $x_k$ określony wzorem $Q(x_k)=x_k(x_k-1)\ldots(x_k-n)$ . Inaczej mówiąc, prawdziwa jest równość wielomianów

$ (1) \qquad P(x_1,\ldots,x_{k-1},x_k)= Q(x_k)W(x_1,\ldots,x_{k-1},x_k)+R(x_1,\ldots,x_{k-1},x_k), $

przy czym wszystkie potęgi zmiennej $x_k$ występujące w wielomianie $R$ mają wykładniki mniejsze od stopnia wielomianu $Q$ .

Liczby 0, 1, 2, $\ldots$ , $n$ są pierwiastkami wielomianu $Q$ , zatem na mocy równości (1) otrzymujemy

$ P(a_1,\ldots,a_{k-1},a_k)=R(a_1,\ldots,a_{k-1},a_k) \quad\hbox{dla }a_1,\ldots,a_{k-1},a_k\in \{0,1,\ldots,n\}; $

oznacza to, że wielomian $R$ również spełnia założenia lematu. Ma on ponadto stopień nie wyższy niż wielomian $P$ . Wystarczy więc dowieść, że stopień wielomianu $R$ jest równy co najmniej $kn$ .

Ponieważ $Q$ jest wielomianem zmiennej $x_k$ stopnia $n+1$ , więc wszystkie potęgi zmiennej $x_k$ występujące w wielomianie $R$ mają wykładnik nie większy niż $n$ . Wobec tego istnieje przedstawienie postaci

$ (2) \qquad R(x_1,\ldots,x_{k-1},x_k)= \sum_{i=0}^n R_i(x_1,\ldots,x_{k-1})x_k^i, $

gdzie $R_n$ , $R_{n-1}$ , $\ldots$ , $R_0$ są wielomianami $k-1$ zmiennych.

Wykażemy, że do wielomianu $R_n(x_1,\ldots,x_{k-1})$ można zastosować założenie indukcyjne.

Rozważmy wielomian $T(y)=R(0,\ldots,0,y)$ zmiennej $y$ . Na mocy równości (2) ma on stopień co najwyżej $n$ ; ponadto liczby $1, 2, \ldots, n$ są jego pierwiastkami, zaś liczba 0 - nie jest. Skutkiem tego wielomian $T$ ma stopień równy $n$ , a współczynnik przy potędze $y^n$ , czyli $R_n(0,\ldots,0)$ , jest różny od zera.

Podobnie, niech $a_1,\ldots,a_k\in\{0,1,\ldots,n\}$ będą dowolnymi liczbami, z których przynajmniej jedna jest różna od zera i weźmy pod uwagę wielomian $T(y)=R(a_1,\ldots,a_n,y)$ zmiennej $y$ . W tym przypadku wielomian $T$ ma $n+1$ pierwiastków: 0, 1, $\ldots$ , $n$ , lecz jego stopień nie przekracza $n$ . Wobec tego wielomian $T$ jest zerowy i jego współczynnik $R_n(a_1,\ldots,a_{k-1})$ przy potędze $y^n$ jest równy zeru.

Udowodniliśmy w ten sposób, że

$ R_n(0,\ldots,0)\ne0\qquad\hbox{oraz}\qquad R_n(a_1,\ldots,a_{k-1})=0 $

dla dowolnych liczb $a_1$ , $\ldots$ , $a_{k-1}\in\{0,1,\ldots,n\}$ , nie wszystkich równych zeru.

Na mocy założenia indukcyjnego wielomian $R_n(x_1,\ldots,x_{k-1})$ ma więc stopień nie niższy niż $(k-1)n$ . Stąd wniosek, że wielomian $R_n(x_1,\ldots,x_{k-1})x_k^n$ zawiera jednomian stopnia co najmniej $kn$ , w którym występuje czynnik $x_k^n$ . Jednomian ten nie skróci się z żadnym z jednomianów występujących w składnikach postaci $R_i(x_1,\ldots,x_{k-1})x_k^i$ dla $i=0,1,\ldots,n-1$ , ponieważ te ostatnie zawierają potęgi zmiennej $x_k$ o wykładniku nie przekraczającym $n-1$ . Stąd i z zależności (2) wynika, że wielomian $R(x_1,\ldots,x_{k-1},x_k)$ zawiera jednomian stopnia co najmniej $kn$ . To kończy rozumowanie indukcyjne i dowód lematu.

Przechodzimy do rozwiązania zadania.

Przypuśćmy, że danych jest $N$ płaszczyzn, których suma zawiera zbiór $S$ , ale nie zawiera punktu $(0,0,0)$ . Niech $i$ -ta płaszczyzna ( $i=1,2,\ldots,N$ ) zadana będzie równaniem $a_ix+b_iy+c_iz+d_i=0$ . Rozpatrzmy wielomian $P(x,y,z)$ będący iloczynem $N$ wielomianów postaci $a_ix+b_iy+c_iz+d_i$ . Jest to wielomian stopnia $N$ o następujących własnościach:

$P(x_0,y_0,z_0)=0$ dla każdego punktu $(x_0,y_0,z_0)\in S$ ;
$P(0,0,0)\ne 0$ .

Zatem wielomian $P(x,y,z)$ spełnia założenia lematu. Wobec tego jego stopień jest nie niższy niż $3n$ , skąd otrzymujemy nierówność $N\ge 3n$ .

Pozostaje zauważyć, że suma $3n$ płaszczyzn zadanych równaniami

$ x+y+z=i\qquad\hbox{dla }i=1,2,\ldots,3n $

zawiera zbiór $S$ - gdyż punkty tego zbioru mają współrzędne całkowite, których suma należy do przedziału $\langle 1; 3n\rangle$ - oraz nie zawiera punktu $(0,0,0)$ .

Odpowiedź: Szukana najmniejsza liczba płaszczyzn wynosi $3n$ .