Wielkie łapska

6 listopada 2010
Marek Penszko

Zacznę od powrotu do biblioteki w związku z zadaniem, które brzmiało tak:

Na półce stoi osiem tomów Encyklopedii Łamigłówek, ale w kolejności niezgodnej z ich numeracją:

Trzeba je ustawić we właściwym porządku – od 1 do 8 (od lewej do prawej) – wykonując minimalną liczbę ruchów-przestawień. Każdy ruch polega na wyjęciu jednego tomu, przesunięciu kilku stojących na półce i wsunięciu wyjętego w nowe miejsce.
Ile ruchów wystarczy (i jakich), by tomy zostały ustawione jak należy?

Jeśli ktoś z Państwa uznał to zadanie za proste, nawet bardzo, to zgoda. A jeżeli ktoś twierdzi, że było trochę przewrotne, to także zgoda, bo niewiara w prostotę wzbudza podejrzliwość i skłania do szukania lepszych rozwiązań, których… nie ma. Poniżej pięciu ruchów zejść nie sposób, co zwięźle wyjaśnili Michał i Agnieszka. Po każdym ruchu liczba tomów ustawionych we właściwej kolejności może zwiększyć się co najwyżej o jeden, a na początku najdłuższy ciąg rosnący tworzą trzy; ponieważ wszystkich tomów jest osiem, zatem 8 – 3 = 5. Wystarczy tylko odrobinę pokombinować; najwygodniej skorzystać ze schematu ustawiania właściwych kolejności równocześnie od początku i od końca (1 na początek, 8 na koniec, 2 na drugie miejsce, 7 na przedostatnie, 3 na trzecie – i gotowe).

To przypomnienie było przygrywką. Teraz będzie nieco trudniej.
Wyobraźmy sobie, że osoba przestawiająca książki ma wielkie łapska – może chwycić równocześnie dwa, trzy, a nawet cztery tomy encyklopedii. Chyba wielu czarnoskórych koszykarzy nie miałoby z tym problemu, a na pewno nie miałby Ukrainiec Leonid Stadnik, najwyższy człowiek na świecie (259 cm) o dłoniach długości 31 cm.
Każdy ruch-przestawienie tym razem zaczyna się więc od chwycenia jednego albo dwóch, trzech lub czterech sąsiednich tomów stojących na półce. Reszta zadania pozostaje bez zmian. Ale to nie wszystko. Tak jak poprzednio szukamy minimalnej liczby ruchów (x), prowadzących do ustawienia tomów w kolejności od 1 do 8. Jednak wśród rozwiązań w x ruchach należy znaleźć najlepsze – takie, w którym chwytana będzie i przenoszona w sumie (x-krotnie) maksymalna liczba tomów. Na przykład: najlepszym rozwiązaniem w trzech ruchach byłoby 3-12, czyli Leonid trzykrotnie chwytałby i przestawiał po cztery tomy.
Na razie (z pierwszej wersji zadania) znamy najgorsze rozwiązanie: 5-5

Komentarze z prawidłowymi rozwiązaniami uwalniane są wieczorem w przeddzień kolejnego wpisu. Wpisy pojawiają się co 3-4 dni.