Reklama
Polityka_blog_top_bill_desktop
Polityka_blog_top_bill_mobile_Adslot1
Polityka_blog_top_bill_mobile_Adslot2
Łamiblog - Blog Marka Penszko Łamiblog - Blog Marka Penszko Łamiblog - Blog Marka Penszko

6.11.2010
sobota

Wielkie łapska

6 listopada 2010, sobota,

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.

Reklama
Polityka_blog_bottom_rec_mobile
Reklama
Polityka_blog_bottom_rec_desktop

Komentarze: 10

Dodaj komentarz »
  1. Nie potrafię wymyślić żadnego dowodu, że nie da się mniej (ruchów) ani że nie da się więcej (książek przesunąć), podam więc najlepsze rozwiązanie jakie wymyśliłem na razie:
    4-10
    84251736
    84512736
    12738456
    12734568
    12345678
    Pozdrawiam
    Michał

    Michale, zwóć uwagę, że to jest jednak lepiej niż 4-10. Zależy co przestawić w ostatnim ruchu.
    mp

  2. Nie rozumiem, dlaczego najlepszym rozwiązaniem jest takie, w którym przenosi sie najwięcej tomów. Optymalizacja działania polega zazwyczaj na tym, by wykonać najmniejszą pracę, czyli w tym przypadku przenieść najmniej tomów

    Komentarz jest, jak sądzę, z założenia żartobliwy, więc odpowiem półżartem: to tak dla hecy.
    A jeśli serio, to: przy większej liczbie tomów trzeba więcej pogłówkować (ale chyba niewiele więcej).
    m

  3. 8 4 2 5 1 7 3 6 (5 1)
    8 4 5 1 2 7 3 6 (1 2 7 3)
    1 2 7 3 8 4 5 6 (4 5 6)
    1 2 4 5 6 7 3 8 (4 5 6 7)
    1 2 3 4 5 6 7 8

    4 ruchy, przełożonych 13 tomów
    Pozdrawiam

  4. Reklama
    Polityka_blog_komentarze_rec_mobile
    Polityka_blog_komentarze_rec_desktop
  5. A w jakim układzie początkowym stoi „Encyklopedia Łamigłówek”, bo rysunek przedstawia ułożenie początkowe „Encyklopedii Łamiguwek”. Czy to inne zadanie?

    Oczywiście w takim samym, ale bardzo lubię takie pytania, bo można pogłówkować, jak na nie odpowiedzieć z uzasadnieniem. Na przykład tak:
    Oprawę encyklopedii wykonał introligator dysortografik.
    Wyjaśniam za nonsenospedią, że
    dyzortografia jezt to taga fstrentna horoba pszes kturom lódźe robiom, mnustfo błenduf orto graficznyh i nie umiom fstawić pszecinka f otpowjednie mjejsce. Ale pszynajmiej som zwolńeni s, dyktant fszkole. Rea sumujonc fainje im ale ńiefaińe tesz.
    mp

  6. 4-13:
    1. (842) miedzy 7 a 3 – powstaje 51784236
    2. (784) na poczatek – 78451236
    3. (1236) na poczatek – 12367845
    4. (678) na koniec – 12345678
    Wydaje mi sie, ze nie mozna zrobic lepiej niz 4-13, ale dowiesc tego nie potrafie.
    a

  7. 84251736 – zabieram 517 i stawiam na początku
    51784236 – zabieram 4236 i wstawiam między 1i7
    51423678 – zabieram 51 i stawiam między 4i2
    45123678 – zabieram 45 i wstawiam między 3 i 6
    12345678
    w czterech ruchach w sumie przeniesiono 11 tomów

  8. A nawet w 4 ruchach 12 tomów, bo zamiast w
    45123678 zabrać 45, zabieramy 123 i stawiamy na początku

  9. {842}{517}36
    51{784}{236}
    5{123}{678}4
    {5678}{1234}
    Też 4-13. Zawsze zamieniamy miejscami zaznaczone grupy.

  10. 4-17
    8(425)1736
    817(34)256
    817(23456)
    8(1234567)
    12345678

  11. Więcej nawet tych 17-stek wychodzi:
    8(42517)36
    425(1783)6
    1(7834)256
    1278(3456)
    12345678

    albo

    842(51)736
    845(1273)6
    8127(3456)
    8(1234567)
    12345678

    Czas spytać komputer o zdanie…

    OK, ale to przy założeniu, że łapska są większe niż wielkie, czyli chwytają więcej niż 4 tomy.
    mp

css.php