L MOM - Zadanie 6

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

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź