XVIII ZMPB - Zadanie 6

Fredek pisze liczby $1$ , $2$ , $\ldots$ , $n$ w pewnej kolejności, po czym sporządza listę wszystkich takich par $(i,j)$ , że $1\le i<j\le n$ oraz $i$ -ta liczba jest większa od $j$ -tej liczby w jego permutacji. Następnie Fredek wielokrotnie wykonuje następującą operację, dopóki jest możliwa: wybiera parę $(i,j)$ z bieżącej listy, zamienia miejscami liczbę $i$ -tą z liczbą $j$ -tą w bieżącej permutacji, i usuwa parę $(i,j)$ z listy. Wykazać, że Fredek może wybierać pary w takiej kolejności, że po zakończeniu procesu liczby w permutacji będą uporządkowane rosnąco.

Rozwiązanie

Rozpocznijmy od następującego spostrzeżenia: jeżeli liczby w permutacji nie są uporządkowane rosnąco, to istnieją takie pozycje o numerach $i$ , $j$ , przy czym $i<j$ , że $i$ -ta liczba w permutacji jest większa o $1$ od liczby $j$ -tej. By udowodnić to spostrzeżenie, określmy $i$ jako pierwszą taką pozycję w permutacji, że stojąca na niej liczba $k$ jest różna od $i$ . Wówczas permutacja rozpoczyna się od liczb $1$ , $2$ , $\ldots$ , $i-1$ ; ponieważ $k>i$ , więc $k-1>i-1$ i wobec tego liczba $k-1$ występuje w rozważanej permutacji na pozycji o numerze $j>i$ . Wówczas numery $i$ , $j$ mają postulowaną własność.

Niech teraz dana będzie dowolna początkowa permutacja liczb $1$ , $2$ , $\ldots$ , $n$ i niech $(i,j)$ będzie parą numerów mających powyższą własność. Para ta oczywiście znajduje się na początkowej liście. Przypuśćmy, że Fredek wybiera tę właśnie parę i zamienia miejscami liczbę $i$ -tą z liczbą $j$ -tą. Ponieważ te dwie liczby są kolejnymi liczbami całkowitymi, więc liczba stojąca na dowolnej innej pozycji jest albo mniejsza od obu zamienianych liczb, albo też jest od nich większa. Stąd wniosek, że lista takich par $(i',j')$ , dla których $i'<j'$ oraz $i'$ -ta liczba w nowo otrzymanej permutacji jest większa od liczby $j'$ -tej, będzie tożsama z listą, którą Fredek otrzymuje usuwając z początkowej listy parę $(i,j)$ .

Następnie z każdą otrzymywaną permutacją Fredek wykonuje analogiczną operację - zamienia miejscami dwie kolejne liczby całkowite w permutacji, z których większa stoi na wcześniejszej pozycji. Wówczas na każdym kroku bieżąca lista par jest zgodna z wszystkimi relacjami mniejszości w bieżacej permutacji, czyli zgodna z listą wszystkich takich par $(i',j')$ , dla których $i'<j'$ oraz $i'$ -ta liczba w bieżącej permutacji jest większa od liczby $j'$ -tej.

Ponieważ początkowa lista Fredka zawierała skończenie wiele par, więc po wybraniu wszystkich par w opisanej kolejności pozostanie pusta lista par, która będzie zgodna z wszystkimi relacjami mniejszości w końcowej permutacji. Wobec tego w tej permutacji liczby będą uporządkowane rosnąco.

Uwaga: Zauważmy, że nie dla każdego wyboru pary $(i,j)$ stwierdzenie z ostatniego zdania drugiego akapitu rozwiązania jest prawdziwe. Na przykład dla $n=5$ i początkowej permutacji $5$ , $1$ , $3$ , $4$ , $2$ lista ma postać $(1,2)$ , $(1,3)$ , $(1,4)$ , $(1,5)$ , $(3,5)$ , $(4,5)$ . Wybierając parę $(1,3)$ i zamieniając w wyjściowej permutacji liczbę pierwszą z trzecią, Fredek uzyska permutację $3$ , $1$ , $5$ , $4$ , $2$ , w której trzecia liczba jest większa od czwartej, oraz listę nie zawierającą pary $(3,4)$ . Zatem lista po wykreśleniu jednej pary nie będzie zgodna z nową permutacją.