Matematyka dyskretna, zadanie nr 4832

Autor	Zadanie / Rozwiązanie
tasia postów: 17	2016-10-04 14:25:19 W rzędzie danych jest kilka liczb całkowitych dodatnich. Operacją nazwiemy wybór sąsiednich liczb x i y przy czym x leży na lewo od y oraz x>y i zamianę pary (x,y) na (y+1,x) lub (x-1,x). Pokazać, że można wykonać jedynie skończenie wiele operacji. Wiadomość była modyfikowana 2016-10-04 14:25:43 przez tasia

tumor postów: 8070	2016-10-04 18:00:24 Każda zamiana wymaga tego, by większa liczba była po lewej stronie z dwóch wybranych, a kończy się tym, że lewa liczba na pewno nie jest większa. Nie jest to sortowanie, bo liczby mogą zmieniać swoje wartości, jednakże rozumiemy, że po wykonaniu wszystkich możliwych operacji powstały ciąg będzie posortowany. Skąd wiemy, że operacji będzie skończenie wiele? Mamy n liczb w ciągu. Jeśli n=1 to nie ma co zamieniać, jeśli n=2 to zamieniamy najwyżej raz. Weźmy teraz n dowolne i $n\ge 2$. Istnieje w tym ciągu wyraz x taki, że nie ma w ciągu większego od niego, ponadto na prawo od x nie ma też równego mu. a) jeśli x jest już na n-tej pozycji, to jest nie do ruszenia żadną z naszych operacji elementarnych, wobec czego rozwiązania wymaga problem dla n-1 elementów na lewo od niego. b) jeśli x nie jest na n-tej pozycji, to możemy ten x zamienić z elementem po jego prawej stronie albo możemy nie zamieniać. Niezamienianie dzieli nam problem na możliwe operacje po lewej stronie od x i na możliwe operacje po prawej stronie od x. Gdyby dla pewnego n dało się wykonać nieskończenie wiele operacji, to istniałoby k takie, że 1<k<n dla którego też da się wykonać nieskończenie wiele operacji. Stoi to w sprzeczności z uwagą, że dla n=2 operacji jest skończona ilość.

strony: 1

Prawo do pisania przysługuje tylko zalogowanym użytkownikom. Zaloguj się lub zarejestruj