Polityka_blog_top_bill_desktop
Polityka_blog_top_bill_mobile_Adslot1
Polityka_blog_top_bill_mobile_Adslot2

8.08.2017
wtorek

Sześcioraczki

8 sierpnia 2017, wtorek,

W lipcowym Świecie nauki zamieszczone było bardzo trudne, a ściślej – niezwykle żmudne zadanie, którego poprawne rozwiązanie nadesłała tylko jedna osoba. Postanowiłem przedstawić je także w Łamiblogu, bo być może komuś uda się znaleźć sprytny sposób uporania się z nim, czyli okaże się, że nie jest ono aż tak benedyktyńskie. Oczywiście za sposób nie uważam napisania programu komputerowego, choć wydaje się, że to także nie jest zbyt proste.

Wypełnienie prostokąta 6×5 cyframi od 1 do 5 jest częściowo magiczne: każdą kolumnę tworzy pięć różnych cyfr, a suma cyfr w każdym wierszu jest taka sama, równa 18. Prostokąt ten należy podzielić wzdłuż linii przerywanych na sześć pentomin, czyli figur (wielokątów) złożonych z pięciu kratek – tak, aby w każdym pentominie znalazło się pięć różnych cyfr. Gdyby to był koniec zadania, byłoby ono dziecinnie proste, bo sposobów takiego podziału jest mnóstwo, zaczynając od trywialnego – na pięć (poprawka: sześć) pasków-kolumn. Dodatkowy warunek, który czyni zadanie „sadystycznym”, brzmi: kształt każdego pentomina powinien być inny (kształty, które są względem siebie odbiciami lustrzanymi, uważamy za jednakowe).
Sposobów podziału jest więcej niż jeden. Wystarczy podać ile, ale mile widziane będzie przedstawienie w jakiejś formie konkretnych podziałów.

Reklama
Polityka_blog_bottom_rec_mobile
Reklama
Polityka_blog_bottom_rec_desktop

Komentarze: 18

Dodaj komentarz »
  1. Znalazłem dwa rozwiązania (i wykluczyłem pozostałe możliwości). Czas dłubania: ok. godziny. Możliwość pomyłki: jak zwykle, spora 🙂
    Zacząłem od wybrania jednego pola gdzieś w środku diagramu, z którego wyznaczam wszystkie możliwe pentomina (będzie ich kilka, prawie na pewno mniej niż 10). Teraz dla każdej możliwości zaczynam dłubaninę, ale wybór figury w środku diagramu powoduje, że liczba kombinacji nie jest zbyt wielka (istniejący kształt wymusza kolejne pentomino, albo sobie zablokowałem połączenia między niektórymi cyframi, albo kształty się powtarzają).

    Cyfra oznacza numer figury:

    112223
    412253
    411653
    446653
    466553

    111116
    222266
    344256
    334456
    334555

  2. Wszystkich możliwych podziałów (bez warunku o innym kształcie) jest 125.
    Z różnymi pentominami są trzy podziały.
    http://pokazywarka.pl/hvc8ur/

  3. Znalazłem programistycznie 3 rozwiązania .
    Korzystając ze strony https://isomerdesign.com/Pentomino/5×6/index.html
    Pobrałem 541 możliwych rozwiązań dla prostokątu 5×6.
    Po uwzględnieniu obrotu i odbić lustrzanych do sprawdzenia jest 2164 układów.
    Być może, że gdzieś mam błąd i jednak jest ich więcej 🙁

    Teraz myślę, jak to zrobić sprytnie.

    Poniżej rozwiązania

    IIIIIY
    LLLLYY
    PFFLTY
    PPFFTY
    PPFTTT
    ———-
    IIIIIY
    LLLLYY
    PPPLTY
    PPNNTY
    NNNTTT
    ———-
    ZZPPPI
    YZPPLI
    YZZWLI
    YYWWLI
    YWWLLI

  4. Reklama
    Polityka_blog_komentarze_rec_mobile
    Polityka_blog_komentarze_rec_desktop
  5. Znalazłem trzy rozwiązania:
    (Każda litera oznacza osobne pentomino)

    1.
    ABBCCD
    ABCCDD
    ABCEED
    ABFFED
    AFFFEE

    2.
    AAAAAB
    CCCCBB
    DDDCEB
    DDFFEB
    FFFEEE

    3.
    AAAAAB
    CCCCBB
    DEECFB
    DDEEFB
    DDEFFF

  6. Dla porządku:
    w treści zadania znalazł się drobny błąd.
    Jest:
    „zaczynając od trywialnego – na pięć pasków-kolumn”

    powinno być:
    „zaczynając od trywialnego – na SZEŚĆ pasków- kolumn”

    Zadanie „Dla wodniaków” przegapiłem z powodu pobytu „u wód”.
    Ale już cieszę się na jego rozwiązywanie 🙂

  7. Rozwiazalam metodą próbować do skutku. Skutek wyszedł taki:
    AABBBC
    DABBEC
    DAAFEC
    DDFFEC
    DFFEEC

  8. Początkowo wpis otworzył mi się bez ilustracji, czyli bez diagramu (mam słabą komórkę). Myślałam zatem, że zadanie polega na tym, żeby ułożyć diagram do rozwiązania. Ułożyłam w kilka minut:
    123435
    251244
    345123
    414351
    532512
    Juz chciałam go wysłać, gdy odsłonił mi się tamten. Trudny faktycznie, dwa dni do niego podchodziłam, zanim się udało. A jaki jest ten mój? Rozwiąże ktoś?
    Pozdravy z Moraw Południowych 🙂

  9. Olu bez warunku o różnych kształtach pentomin Twoje zadanie ma 35 różnych rozwiązań. Z tym warunkiem są tylko dwa rozwiązania.
    Układając od lewej strony są to pentomina:
    1. I P W Y V N
    2. I T W L P N

    Pozdrowienia ze (z)Dolnego Śląska.

  10. Napisanie programu okazało się nietrudne (przy wykorzystaniu w pewnym stopniu dorobku ludzkości).
    Pozwoliło to zweryfikować pewne kwestie.
    Otóż odpowiedź na propozycję OlaGm to:

    ABBBCD
    ABBCCD
    AECCDD
    AEFFFD
    AEEEFF

    Z kolei mój układ (1.) z wcześniejszego komentarza jest błędny, ale reszta się broni 🙂

  11. @Antyp: najbardziej z tym warunkiem. Zaczęłam od narysowania figur, tych oznaczonych u Ciebie jako 2.
    …i @Apartado:
    Pytam z ciekawości: zawsze piszecie program, zamiast rozwiązywać ołówkiem? To jest bardziej emocjonujące?

  12. Napisałem program i okazało się, że przegapiłem jedno rozwiązanie:

    111116
    222266
    333256
    334456
    444555

    I przy okazji potwierdzam rozwiązania Antypa z 192101 😉

    A w programie trudniej chyba wyszukać różne pentomina, niż później już z nich złożyć całą planszę. Przy takim rozmiarze program działa momentalnie.

  13. @OlaGM:
    Pozwolę sobie odpowiedzieć na pytanie: dla kogoś, kto lubi programować (a taką osobą jestem), obydwa sposoby są emocjonujące. Przy czym często sam program jest celem, a nie jego wyniki 😉 Zawsze zaczynam od rozwiązywania samemu, a później dopiero program (nie zawsze, zależy od problemu). Jeśli nie uda się samemu, to jest większa motywacja do pisania. Najlepiej jeśli uda się zrobić jedno i drugie, a jeśli na dodatek oba sposoby dadzą te same rezultaty, to już pełnia szczęścia. Jak się okaże po uwolnieniu komentarzy, pełni szczęścia nie osiągnąłem tym razem 😉

  14. @OlaGM

    „Sześcioraczki” zrobiłem najpierw ręcznie, ale potem (po małym rozpoznaniu w necie) napisałem program – często daje to jakieś dodatkowe, ciekawe obszary do penetracji.
    Ogólnie łamigłówki robię długopisem (nie lubię metody „prób i błędów”, więc ołówek i gumka nie dla mnie) – mam za sobą w ostatnich dniach sporo nurikabe – na kilku poległem i cała przyjemność po mojej stronie.

  15. Program znalazł 3 rozwiązania:

    AAAAAB
    CCCCBB
    DDDCEB
    DDFFEB
    FFFEEE

    AAAAAB
    CCCCBB
    DEECFB
    DDEEFB
    DDEFFF

    AABBBC
    DABBEC
    DAAFEC
    DDFFEC
    DFFEEC

  16. @OlaGM:

    Pisanie programów, które rozwiązują łamigłówki samo w sobie jest łamigłówką. Trzeba zdecydować, jak reprezentować dane łamigłówki w pamięci komputera, trzeba napisać funkcje obsługujące transformacje stanów łamigłówki zgodnie z jej regułami. Trzeba zadbać o wydajność programu, aby dał on efekty w sensownym czasie, bowiem dość często algorytmy brute-force, czyli sprawdzanie wszystkich możliwości po kolei, potrafią działać godzinami/dniami/latami (*oczywiście niecierpliwy programista po godzinie działania programu przerywa go, bo to już za długo). Trzeba zadbać o sensowne odcinanie częściowych rozwiązań, których nie ma sensu rozpatrywać (bo np. rozważają sytuację symetryczną do już obsłużonej albo częściowe rozwiązanie na gołe oko nie doprowadzi do lepszej odpowiedzi niż już wcześniej znalezione).

    Jest wiele aspektów, o które trzeba zadbać, a przy okazji dobrze napisany program pomaga zweryfikować ręczne rozwiązanie otrzymane za pomocą kartki i ołówka.

  17. Panowie i Panie programiści.

    Od jakiegoś już czasu chciałem utworzyć repozytorium do zbierania efektów Waszych programistycznych prac związanych z Łamiblogiem. Udało się:

    https://github.com/miodziu/penszko-lamiblog

    Zachęcam Was do wrzucania tam swoich kodów programów. Wtedy mają szansę one przetrwać nieco dłużej niż tylko na czas aktualnego wpisu na Łamiblogu…

  18. @miodziu
    Jakiś czas temu Nasz Miły Gospodarz napisał, że Łamiblog nie jest Projektem Euler i ja też wolę poświęcić czas/uwagę na kwestie ręcznego rozwiązywania łamigłówek.

    (ale jeśli czasem w wyniku działania programu pojawi się jakaś ciekawostka, to się nią tutaj podzielę ku ogólnej radości).

    Niech mi będzie wolno zakrzyknąć:
    „Panie i Panowie długopisy w dłoń!”.
    „Długopisy”, bo tak jak napisałem wcześniej: gumować ołówka nie lubię.

  19. Panie Gospodarzu, bawiłem się trochę programem i wpadła mi w oko taka ciekawostka.

    P P T T T
    P P P T Y
    U U F T Y
    U F F Y Y
    U U F F Y

    Startujemy z dowolnego pola i ruchem Króla szachowego odwiedzamy pozostałe pola i wstawiamy kolejne liczby naturalne 1-25.
    Po wstawieniu wszystkich sumujemy liczby w poszczególnych pentominach.

    Należy znaleźć trasę, dla której każda suma jest większa od 60.

css.php