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

30.04.2018
poniedziałek

Licha bis

30 kwietnia 2018, poniedziałek,

Powtórka lich wiąże się z pojęciem tzw. minimalnego zbioru krytycznego. Ogólnie rzecz biorąc, jest to taki najmniejszy podzbiór A zbioru B, którego znajomość pozwala – w oparciu o reguły określające zależności między elementami zbioru B – odtworzyć jednoznacznie ten zbiór.
W lichach podzbiorem są elementy wpisane w diagram, czyli cyfry. Czy w poniższym małym przykładzie pięć cyfr tworzy zbiór krytyczny?

Można to sprawdzić, próbując rozwiązać przykład po usunięciu jednej z cyfr. Jeśli usunięcie dowolnej umożliwi uzyskanie jednego rozwiązania, to 5-cyfrowy podzbiór nie jest krytyczny. W przeciwnym wypadku – jest.
Przypominam reguły: W puste pola należy wpisać takie cyfry, aby cyfra w każdej kratce oznaczała liczbę sąsiednich kratek z cyfrą nieparzystą. Sąsiednimi są kratki, stykające się bokiem lub tylko rogiem.
Nieco bardziej żmudne jest sprawdzenie, czy krytyczny jest podzbiór ośmiu cyfr w poniższym zadaniu – to wyzwanie dla wybrańców. A wszystkich zachęcam po prostu do rozwiązania tej łamigłówki, choć nie jest ona łatwa.

W rozwiązaniu wystarczy podać liczbę cyfr nieparzystych w polach na przekątnych diagramu.

Reklama
Polityka_blog_bottom_rec_mobile
Reklama
Polityka_blog_bottom_rec_desktop

Komentarze: 19

Dodaj komentarz »
  1. Łatwa, szło jak po sznurku z góry na dół 🙂
    14341212
    23332221
    24642022
    23332221
    36563434
    35453633
    36565654
    23333331
    Co do drugiej części – mnie się przydały wszystkie liczby, więc stwierdzam, że wszystkie były potrzebne 😉

  2. Jest 6 nieparzystych na jednej przekątnej (1,3,3,3,3,1), druga przekątna ma tylko elementy parzyste. Nie była znacząco trudniejsza od poprzedniej 😉

  3. Liczba cyfr nieparzystych w polach na przekątnych diagramu to 6.

    Trudno obiektywnie ocenić trudność, ale chyba trudne, chociaż ustąpiło nadspodziewanie gładko.
    Korzystałem z wszystkich wpisanych cyfr, ale nie mam pewności, że jest to konieczne.

  4. Reklama
    Polityka_blog_komentarze_rec_mobile
    Polityka_blog_komentarze_rec_desktop
  5. Pięciocyfrowy zbiór nie jest krytyczny. Można usunąć 3 lub 4 z dolnego rzędu.
    Na jednej przekątnej jest 6 cyfr nieparzystych, na drugiej 0 nieparzystych.

  6. Przekątne: {{1,3,6,3,3,6,3,1},{2,2,0,2,6,4,6,2}} – tylko pierwsza zawiera 6 lich, druga żadnego.
    Pełne rozwiązanie:
    14341212
    23332221
    24642022
    23332221
    36563434
    35453633
    36563434
    23332221

  7. W drugim zadaniu będzie jedno rozwiązanie, gdy pominie się 2 z lewego dolnego rzędu

  8. W oparciu o informacje od @logi (lekko żartobliwie):
    Wygląda na to, że mamy następującą zależność: diagram o boku N implikuje rozmiar zbioru krytycznego: N-1.

    Zbadałem że dla N=2 to działa – łamigłówka wygląda tak:
    3x
    xx
    a rozwiązanie tak:
    33
    33

  9. Liczba cyfr nieparzystych na diagonalach została już ujawniona (6 i 0) więc podam całe diagonale (z lewej do prawej):
    1,3,6,3,3,6,3,1
    2,6,4,6,2,0,2,2

    Jeśli wyciąć z warunków początkowych dwójkę w lewym dolnym rogu, to istnieje inne rozwiązanie z jedynką w tym miejscu (ma 5 i 1 cyfr nieparzystych diagonalnych).
    Przypuszczam więc, że zbiór początkowy tej łamigłówki jest minimalny, ale przeraża mnie żmudne badanie tego bez gwarancji sukcesu, bo jeśli czegoś nie umiemy znaleźć, to nie znaczy że to nie istnieje (a dowód nieistnienia to już zupełnie inna bajka).

    Natomiast sama idea jest b. ciekawa, przypomina jakby programowanie matematyczne dyskretne albo model jakichś procesów samoregulacji.

  10. Zbiór ośmiu cyfr nie jest krytyczny – można zrezygnować z jednej z cyfr z dwóch najniższych rzędów. Sprawdzić można to tak:

    Od początku posługuję się rozwiązaniem tymczasowym. W miejsce cyfr nieparzystych wpisuję w kratki kropkę, a w miejsce parzystych coś innego, np. krzyżyk. Wypełniam diagram od góry – najpierw sześć górnych rzędów. Można je jednoznacznie wypełnić kropkami i krzyżykami w oparciu o umieszczone tam sześć liczb (bez dwóch ostatnich, w dolnych rzędach).

    W następnym kroku, nie uwzględniając jednej z cyfr z rzędu przedostatniego (4) lub ostatniego (2) otrzymujemy ten sam wynik i w całości wypełniony diagram.

  11. Jest jedno rozwiązanie:
    1,4,3,4,1,2,1,2
    2,3,3,3,2,2,2,1
    2,4,6,4,2,0,2,2
    2,3,3,3,2,2,2,1
    3,6,5,6,3,4,3,4
    3,5,4,5,3,6,3,3
    3,6,5,6,3,4,3,4
    2,3,3,3,2,2,2,1

    Teraz będziemy wyrzucać różne kombinacje liczb.

    Oznaczmy:
    A=(2,1)=2 co znaczy dwójkę z 2 wiersza i 1 kolumny.
    Analogicznie przyjmijmy:
    B=(6,3)=4
    C=(6,6)=6
    D=(7,8)=4

    W poniższej tabelce krzyżyki w kolumnie mówią, że można wyrzucić jednocześnie odpowiednie liczby i nadal otrzymamy tylko jedno, cały czas to samo rozwiązanie. Kółka oznaczają, że tej liczby nie wyrzucamy.
    A|XOOOXXXOX
    B|OXOOXOOXX
    C|OOXOOXOOO
    D|OOOXOOXXX
    Pierwsze 4 kolumny to wyrzucenia pojedynczych liczb.
    Następne 4 kolumny to wyrzucenia kombinacji 2 liczb.
    A ostatnia kolumna jest najciekawsza bo mówi nam, że możemy jednocześnie wyrzucić aż 3 liczby: {A, B, D} i
    wciąż otrzymamy tylko jedno rozwiązanie.

  12. Chyba jednak zbiór generatorów naszego rozwiązania można zmniejszyć. Dwójka w prawym górnym rogu wydaje się nadmiarowa tj. wynika jednoznacznie z pozostałych cyfr.

    Symetryczny układ 4 cyfr w centrum jest bardzo wymagający – generuje jednoznacznie postać rozwiązania w centrum, a zero wymusza je aż do brzegów w prawym górnym fragmencie. Dlatego w samym jego rogu może stać tylko dwójka.

    Pozostałe 3 cyfry generatora centralnego nie są aż tak determinujące jak zero i wymagają dodatkowych warunków (w okolicach rogów) dla doprecyzowania rozwiązania. Przykładowo, zmieniając dwójkę w lewym dolnym rogu jedynką, dostaniemy inne rozwiązanie, ale b. podobne – różnice ograniczają się do ostatniego wiersza i 2 cyfr w przedostatnim wierszu.

  13. Na przekątnych jest 6 nieparzystych liczb. Dołączam do fanów lich. Pozdrawiam z okolic Siewierza tym razem i miłej końcówki majówki życzę wszystkim.

  14. I jaki z tego morał? Czy zbiór początkowy to minimalny generator rozwiązania? Moim zdaniem nie, bo można pominąć dwójkę w prawym górnym rogu a dostaniemy to samo rozwiązanie.

    Podzielam zdanie Markoniusza, ale nie potrafię stwierdzić, czy zbioru początkowego nie można jeszcze bardziej ograniczyć. Nie mówiąc już o tym, że póki co nie znam rozwiązania zagadki: jaki jest najmniejszy zbiór krytyczny w tego typu zadaniach dla określonej wielkości diagramu n x n.
    mp

  15. Kwestię diagramu o boku n=2 „omówiłem” powyżej.

    Dla diagramów o rozmiarach n=3 oraz n=4 wielkość zbioru krytycznego to 0 (zero) – czyli żeby ustalić jednoznaczne rozwiązanie, nie potrzebujemy jakiejkolwiek wpisanej na początku cyfry.

    Dla mnie to ciekawe – pewnie dlatego, że nad mini-diagramami dotąd w ogóle się nie zastanawiałem.
    mp

  16. W przypadku obu zadań najmniejszymi zbiorami minimalnymi (dającymi jedyne rozwiązanie) jakie znalazł mi program były zbiory 5 elementowe.
    Można zapytać: Czy istnieje 4 elementowy zbiór dający jedyne rozwiązanie ?

  17. @ apartado
    Twój wniosek dla n=2 jest błędny. Poza rozwiązaniem
    3 3
    3 3
    są jeszcze 2 rozwiązania nietrywialne (z dokładnością do obrotów):
    2 1
    1 2
    oraz
    2 2
    1 1
    więc pojedynczy element nie determinuje rozwiązania dla n=2 (3 tak, ale 1 i 2 nie).

  18. Dla n=3 i 4 istnieją tylko rozwiązania zerowe więc inne uwagi są tego prostym skutkiem.

    Dla n=5 można znaleźć dwa różne rozwiązania o wspólnym wierszu (kolumnie), więc 5 elementów skupionych w wierszu nie tworzy krytycznego zbioru początkowego (nie generuje jednoznacznie rozwiązania). Jeśli więc pewne zbiory początkowe 5-elementowe (rozzrzucone żeby oddziaływały na cały obszar) faktycznie są minimalne (nie można ich pomniejszyć bez utraty jednoznaczności rozwiązania), to nie odwrotnie: 5-elementowy zbiór początkowy nie musi być nawet krytyczny.
    Wiele zależy od konkretnego rozwiązania i kształtu zbioru początkowego więc nie da się opisać tych złożonych sytuacji tylko liczebnością zbioru początkowego.

  19. Dopiero teraz przeczytałem ostatni post Spytka z Melsztyna pod tematem Licha. Wg jego analizy komputerowej jest 9 różnych MZK dla tamtego rozwiązania i wszystkie są 5-elementowe (nie ma 4-elementowych, a nie niektóre elementy są jakby bazowe).

css.php