Wielokąty NPW, czyli eksploracja jaskiń
W roku 1954 dwaj matematycy brytyjscy John Hammersley i Bill Morton wprowadzili do geometrii i kombinatoryki termin „unikającej siebie (nieprzecinającej się) ścieżki”. Określony w ten sposób obiekt nie był niczym nowym. Pojawiał się także w matematyce rekreacyjnej: nieprzecinającą się ścieżką jest na przykład najkrótsza droga przez labirynt. W tym konkretnym przypadku odpowiednim przykładem byłaby trasa (czerwona linia na rys. 1a), wiodąca liniami siatki kwadratowej (niebieskie linie przerywane) przez labirynt utworzony na tej siatce – od wejścia (A) do wyjścia (B).
Zatem, ściśle rzecz biorąc, matematykom brytyjskim chodziło o szczególny rodzaj ścieżek na siatkach kwadratowych, zwanych ogólnie ścieżkami kratowymi. Bezpośrednią inspiracją nowego określenia był artykuł amerykańskiego chemika Paula Flory’ego, przyszłego noblisty, na temat polimerów, tworzących łańcuchy przypominające takie trasy. Unikającą siebie ścieżkę i związane z nią zagadnienia można zwięźle przedstawić w formie „spacerowej”.
Wyobraźmy sobie, że stoimy na skrzyżowaniu w centrum miasta podzielonego ulicami na jednakowe kwadratowe kwartały. Ruszamy w drogę i na każdym skrzyżowaniu wybieramy na chybił trafił kierunek dalszego spaceru – wprost, w prawo lub w lewo. Jest tylko jeden warunek: nie wolno znaleźć się na skrzyżowaniu, w którym już się wcześniej było, czyli trasa nie może się zamknąć. Oczywiście, przy ograniczonej liczbie ulic i kwartałów trafienie tam, gdzie już się było, jest nieuchronne. W związku z tym są dwa podstawowe pytania: ile jest wszystkich możliwych tras oraz jaka będzie średnia odległość od miejsca startu, przy założeniu, że każda trasa jest równie prawdopodobna? Pełne odpowiedzi na oba pytania, wsparte konkretnymi wzorami uwzględniającymi wielkość miasta, na razie nie są znane.
W ograniczonym obszarze wspomnianą naturalną konsekwencją wyznaczania ścieżki jest jednak jej zamknięcie, czyli utworzenie cyklu nazwanego przez matematyków „nieprzecinającym się wielokątem” (NPW). W gruncie rzeczy jest to zwykły wielokąt prosty (łamana zamknięta), którego boki leżą na liniach siatki kwadratowej. Jest to więc także tzw. wielokąt kratowy, a ściślej taki jego rodzaj, którego kąty równe 90 lub 270° wyznaczone są przez linie siatki. Jest to równocześnie wielokąt utworzony z elementarnych kwadratów (kratek siatki), a takie wielokąty zwane są poliminami. Tu także przyda się uściślenie: każdy NPW jest poliminem, ale nie każde polimino jest NPW, ponieważ w poliminie mogą być otwory (brakujące kwadraty), a w NPW nie. Ścieżkę z rys. 1a łatwo przekształcić w NPW – wystarczy zlikwidować wejście i wyjście, a utworzyć gdzieś wewnątrz przejście, umożliwiające utworzenie trasy zamkniętej – na przykład tak, jak na rys. 1b.
NPW są głównie obiektem zainteresowania kombinatoryki enumeratywnej, czyli zajmującej się metodami ich zliczania. Obiekty są tego samego rodzaju, ale kryteria zliczania mogą być różne. Najczęściej są to powierzchnie, obwody albo liczba NPW w siatce o określonym kształcie i wielkości – zwykle jest to siatka kwadratowa n×n. Na przykład, liczba NPW o obwodzie równym 10 wynosi 6 (rys. 2), ale jeśli uwzględnić obroty i odbicia lustrzane, to liczba ta wzrośnie do 28. Gdy zaś zapytamy o ich liczbę w kwadracie lub siatce kwadratowej 4×4, to odpowiedzią będzie 172, bo uwzględnione zostaną także przesunięcia. Natomiast liczba NPW o powierzchni równej 10 (10 kwadratów) wynosi 4460. NPW o obwodzie 30, czyli takich jak na rys. 1b, jest już ponad 610 mln, a jeśli uwzględnić powierzchnię tego wielokąta, czyli 22 kwadraty, to wszystkich różnych NPW tej wielkości doliczymy się blisko 33 mld.
Liczenie i analizowanie własności NPW nie jest wyłącznie czystą matematyką, bowiem wiąże się z modelami stosowanymi w chemii i fizyce. W chemii modele dotyczą struktury polimerów pierścieniowych, w fizyce teorii perkolacji oraz tzw. modelu Isinga wykorzystywanego w mechanice statystycznej. Jednak w żadnej z poważnych dziedzin nauki NPW nie gości tak często, jak w matematyce rekreacyjnej, a praktycznie w łamigłówkach. Jak kwadrat łaciński jest podstawą wielu zadań diagramowych, poczynając od przebojowego przed laty i do dziś popularnego sudoku, tak NPW tylko nieznacznie pod tym względem mu ustępuje. We wszystkich zadaniach z NPW cel jest taki sam: odtworzyć, czyli narysować na liniach siatki kwadratowej konkretny wielokąt kratowy na podstawie kluczowych, fragmentarycznych informacji związanych z jego kształtem. Informacje te bywają oczywiście różne w różnych rodzajach zadań. Ogólnie można je podzielić na dwa typy: takie, które określają bezpośrednio elementy nienależące albo należące do wielokąta, oraz częściej takie, które wskazują na jego części pośrednio.
Najpopularniejszą łamigłówką z NPW jest bez wątpienia pokropka, której dotyczył artykuł zamieszczony w tym dziale przed sześciu laty. Gwoli przypomnienia, na rys. 3 znajduje się przykład z rozwiązaniem. Zadanie polega na narysowaniu linii łamanej zamkniętej łączącej niektóre kropki – biegnącej wzdłuż niebieskich linii przerywanych i niegoszczącej dwukrotnie w żadnej kropce. Każda cyfra – 0, 1, 2 lub 3 – oznacza, ile boków kratki z tą liczbą powinno znaleźć się na łamanej. Pokropka debiutowała w Japonii w 1989 roku i szybko stała się popularną wizytówką lansującego ją wydawnictwa Nikoli. Zadecydowały o tym proste reguły i klarowna logika. Z czasem pojawiło się kilka jej odmian oraz opartych na niej zadań z NPW. Jedno z najciekawszych, o dość zawiłej, a tym samym intrygującej logice, pojawiło się w roku 1996 pod osobliwą nazwą „baggu”, czyli „torba”. Próbując uzasadnić to określenie wyglądem rozwiązania, należałoby przyjąć, że chodzi o damską torebkę pełną zakamarków. Wyjaśnienie jest jednak mało przekonujące, więc nic dziwnego, że poza Japonią zadanie pojawia się zwykle jako „jaskinia”, ponieważ mniej lub bardziej rozgałęziony NPW – choćby taki jak na rys. 3 – przypomina plan obszernej jaskini z salami i korytarzami. Ponadto w urealnionym opisie zadania występują speleolodzy-obserwatorzy.
Jaskinia wyglądem przypomina pokropkę, czyli w kratkach siatki kwadratowej umieszczone są cyfry – różnica jest tylko taka, że oznaczają one co innego. Tym razem kluczowa informacja jest następująca: w każdej kratce z cyfrą stoi speleolog i patrząc w czterech głównych kierunkach, widzi tyle pól jaskini, ile wynosi wartość „deptanej” cyfry (liczby), wliczając w to także pole z tą cyfrą. O pokrewieństwie obu rodzajów zadań może świadczyć także to, że pokropkę z rys. 3 łatwo zmienić w jaskinię. Wystarczy usunąć zera i jedynki, bo liczby te w jaskini nie mają sensu. Utworzone w ten sposób zadanie i jego rozwiązanie znajduje się na rys. 4. Warto przy okazji zauważyć, że pod lewą dwójką mogłaby pojawić się szóstka – z tą nadmiarową informacją łamigłówka byłaby znacznie prostsza, niemal trywialna.
Metody rozwiązywania jaskiń są głównie oparte na analizie zależności między zakresami oddziaływania poszczególnych liczb, zwłaszcza względnie dużych z małymi. Umożliwia to oznaczanie kratek, które na pewno utworzą jaskinię, oraz tych, które będą litą skałą, a w następstwie takich oznaczeń rysowane są fragmenty granic wielokąta. Na przykład w zadaniu na rys. 5a liczby 8 i 3 nie mogą być połączone poziomym korytarzem, bo wówczas zostałby przekroczony zasięg trójki. Z drugiej strony poziomy korytarz z ósemką może obejmować co najwyżej 4 kratki ze względu na zasięg czwórki, więc pionowy na pewno nie tylko obejmie siódemkę, ale też przynajmniej jedną kratkę za nią, czyli wszystkie te pola, a także pole pod trójką, można oznaczyć kropką, jako należące do jaskini.
Z innej metody zwanej antyszachownicową należy skorzystać w lewym dolnym rogu: nie może być tak, aby na diagramie pojawił się kwadrat 2×2, w którym dwa pola należące do jaskini (białe) i dwa do niej nienależące (czarne) będą tworzyły fragment szachownicy, bo jaskiniowy wielokąt nie byłby wówczas NPW. Zatem do jaskini musi należeć pole z lewej strony dwójki lub nad nią, a pole z jej prawej strony – nie, czyli można je przekreślić (krzyżyk) i narysować odcinek graniczny (rys. 5b). Teraz zauważmy, że gdyby a1 znalazło się w zasięgu dwójki, czyli należało do jaskini, to czwórka z a2 musiałaby sięgnąć a4, czyli zasięgu trójki. Zatem do jaskini należy włączyć b2, a następnie c2, a to ogranicza zasięg lewej czwórki. W związku z tym należy wykorzystać zasięg prawej czwórki, zaliczając do jaskini f3 i f4 (rys. 5c).
Dalej: gdybyśmy włączyli do jaskini c3 lub e4, to zostałaby „nasycona” środkowa czwórka, ale w konsekwencji któregoś z tych posunięć od jaskini zostałaby odcięta jej część z trójką. Zatem c3 i e4 będą skałą. Z kolei jedyną możliwością dopełnienia zasięgu siódemki jest kropka w e3, co skutkuje krzyżykiem w d1 (rys. 5d).
Teraz warto skorzystać z jeszcze jednej ważnej zasady: wszystkie skały muszą tworzyć spójne grupy połączone z brzegiem – w przeciwnym razie w wielokącie pojawiłby się otwór, czyli odrębny wielokąt. Pola e2 i e4 należy więc sprowadzić do brzegu, stawiając krzyżyki w e5, f5 i e1 i oznaczając odpowiednie granice (rys. 5e). Dokończenie drążenia jaskini jest już formalnością.
Z zasięgami liczb jaskiniowych (Lj) wiąże się pewna ciekawostka matematyczna. Konkretnie chodzi o liczbę różnych układów zasięgu (Lz) dla poszczególnych Lj na nieograniczonym diagramie. Dla Lj=2 takie układy są 4 (rys. 6), dla 3 – 10, dla 4 – 20 (rys. 7). Liczby te można ustalać, sumując odpowiednie partycje liczb Lj-1, a zaskakujące jest to, że tworzą one ciąg 1, 4, 10, 20, 35, 56, 84, 120, 165, … . Ten ciąg to liczby czworościenne, a więc wyrażające się wzorem n(n+1)(n+2)/6, równe liczbie kul wypełniających czworościan foremny z n kulami wzdłuż krawędzi (rys. 8 – czworościan z 20 kul). Jak wytłumaczyć ciągowe powiązanie czworościanu z kul z zasięgami liczb jaskiniowych? – oto zagadka.
Zadania
1. Jaskinia klasyczna (rys. 9), czyli reguły są dokładnie takie, jak opisane w artykule. Jako końcowe rozwiązanie wystarczy podać liczbę skalnych kratek (pól nienależących do jaskini) znajdujących się na przekątnych diagramu.
2. Reguły są klasyczne, ale wszystkie liczby w diagramie (rys. 10) kłamią, czyli żadna nie jest właściwa – każda jest o 1 większa lub mniejsza od poprawnej. W rozwiązaniu wystarczy podać – podobnie jak w zadaniu 1 – liczbę skalnych kratek na przekątnych diagramu.
3. W jaskini na siatce heksagonalnej (rys. 11) cyfry mogą sięgać maksymalnie w sześciu kierunkach, więc możliwych jest więcej interakcji między nimi. Jako rozwiązanie wystarczy podać liczbę wszystkich sześciokątnych skalnych pól.
Rozwiązania prosimy nadsyłać do 30 listopada br. pocztą elektroniczną (redakcja@swiatnauki.pl), wpisując w temacie e-maila hasło UG 11/21. Spośród autorów poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Franka Wilczka Podstawy. Dziesięć kluczy do rzeczywistości ufundowaną przez wydawnictwo Prószyński Media. Warunkiem udziału w konkursie jest zamieszczenie w e-mailu z odpowiedzią oświadczenia:
Zapoznałam/em się z regulaminem konkursu i akceptuję jego treść oraz wyrażam zgodę na przetwarzanie danych osobowych na potrzeby realizacji konkursu.
Regulamin konkursu jest dostępny na stronie www.swiatnauki.pl
***
Rozwiązania zadań z numeru wrześniowego
1. 3276 to liczba Zuckermana, mająca następującą własność: jeśli dopisać do niej na końcu dwie cyfry – najpierw zero, a potem dowolną cyfrę c – to otrzymana w ten sposób dłuższa liczba będzie podzielna przez c.
2. Najwięcej kolejnych liczb naturalnych, które są liczbami zZ (liczby Zuckermana z zerami) jest 13: 1111011111000(/1), 1111011111001(/1), 1111011111002(/2), 1111011111003(/3), 1111011111004(/4), 1111011111005(/5), 1111011111006(/6), 1111011111007(7), 1111011111008(8), 1111011111009(/9), 1111011111010(/1), 1111011111011(/1), 1111011111012(/2).
3. Brakujące liczby Zuckermana: 3168 (powtarza się w diagramie), 31 113, 71 232. Pełne rozwiązanie na rys. 12.
Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Michio Kaku Boskie równanie. W poszukiwaniu teorii wszystkiego, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Robert Galiński z Łodzi, Mirosław Garnowski z Pasłęka, Zbigniew Kapusta z Banina, Maciej Nowakowski z Łodzi, Marcin Porębski z Opoczna.