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$ .