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