Cyfrowanie polimina

Polimino najkrócej można zdefiniować jako wielokąt utworzony z kwadratów, ale gwoli ścisłości należałoby dodać, że kwadraty muszą się stykać całymi bokami (polimino to także zbiorowe określenie wszystkich takich wielokątów). Z dwóch kwadratów może powstać tylko prostokąt zwany dominem – przez analogię do kształtu kamienia w grze o takiej samej nazwie. Sposoby połączenia trzech kwadratów są dwa, a efektem jest trimino. Przy czterech kwadratach sposobów jest pięć – powstaje tetromino, będące podstawą kultowej gry tetris. Gdy kwadratów jest pięć, mamy dwanaście wielokątów tworzących pentomino, które znane jest od dawna jako układanka w postaci kompletu płaskich kamieni. Liczebność różnych wielokątów możliwych do utworzenia z N>5 kwadratów szybko rośnie. Hexomin (N=6) jest 35, heptomin (N=7) 108, a np. liczba dodecomin (N=12) sięga 63 600. Wszystkie te liczby dotyczą polimin „dwustronnych”, czyli odbicia lustrzane niesymetrycznych nie są uważane za inne. W matematyce rekreacyjnej rzadko pojawiają się polimina większe od hexomin, a z reguły granicę zabawy wyznacza pentomino, zatem podstawowy poliminowy arsenał, zaczynający się od pojedynczego kwadracika, czyli monomina, wygląda tak, jak na rys. 1.

Do niedawna polimino gościło niemal wyłącznie w zabawach geometryczno-kombinacyjnych, choć nie zawsze była to rozrywka dla każdego, bowiem „bawili się” nim również matematycy, analizując niełatwe problemy z zakresu tzw. geometrii dyskretnej. Wraz z modą na sudoku i podobne japońskie zadania logiczne, zainicjowaną przed 12 laty, polimino zaczęło pojawiać się w łamigłówkach w nieco innej formie – wzbogacone o cyfry. Takiej formy można doszukać się także w sudoku, bo kwadraty 3×3 i rzędy 1×9, stanowiące elementy diagramu tej łamigłówki, są wypełnianymi cyframi od 1 do 9 poliminami złożonymi z 9 kratek, czyli nonominami. W istocie jednak o nowej formie można mówić wówczas, gdy jest ona bardziej wyrazista, czyli gdy znacznie większe jest zróżnicowanie wielkości i kształtów polimin, ale też ich rozmiary rzadko i nieznacznie przekraczają te z rys. 1. Niniejszy artykuł stanowi przegląd kilku rodzajów najciekawszych zadań tego typu.

Za pierwszą ewidentnie poliminowo-cyfrową należy uznać łamigłówkę zwaną fillominem, która debiutowała w Japonii w roku 1994. Jej związek z poliminem będzie bardziej widoczny, gdy poznamy sposób układania przykładowego zadania. Zaczyna się właśnie od zestawu polimin, np. takiego, jak na rys. 2a – dwa monomina, jedno domino, dwa trimina oraz po jednym tetro-, pento- i heksominie.

Z tych ośmiu figur tworzymy kwadrat (rys. 2b). W praktyce, oczywiście, znacznie prościej jest, układając łamigłówkę, podzielić jakiś pokratkowany kwadrat na dowolne polimina. Należy tylko pamiętać o następującym warunku: polimina takiej samej wielkości nie mogą stykać się bokami. Teraz wypełniamy diagram cyframi, umieszczając w każdej kratce cyfrę równą wielkości polimina, do którego ta kratka należy (rys. 2c). Na koniec w odpowiedni, przemyślany sposób częściowo „psujemy” to, co zrobiliśmy, usuwając wszystkie granice między poliminami oraz większość cyfr. W ten sposób powstaje łamigłówka fillomino (rys. 2d), której rozwiązanie polega na odtworzeniu układu polimin, czyli oznaczeniu granic między figurami. Rozwiązujący wie, jak diagram powstał (wynika to z podanych reguł zadania), ale nie wie konkretnie, z jakich i ilu części jest utworzony. Na pierwszy rzut oka trudno to ustalić, bo nie z każdego polimina jakaś cyfra musi być ujawniona (w przykładzie brak czwórki), a inne może reprezentować kilka cyfr (w przykładzie dwie trójki i dwie szóstki). Podstawowy klucz stanowi warunek o niegraniczeniu bokami figur takiej samej wielkości. W tym przypadku łatwo wywnioskować, że aby ten warunek był spełniony, dwie trójki w lewym dolnym rogu muszą być na jednym triminie, a obie szóstki na wspólnym heksominie. Pozostaje ustalić kształt i położenie obu tych polimin. Logika fillomina jest interesująco „zakręcona”, więc nierzadko trzeba solidnie kombinować, aby uporać się nawet z małymi diagramami, np. takim jak na rys. 3a, nie mówiąc o większych (rys. 3b).

Umieszczanie takiej samej cyfry N w każdej kratce polimina złożonego z N kratek występuje tylko w fillominie i jego odmianach (odmiany polegają na ograniczeniu wielkości polimin w diagramie). We wszystkich pozostałych poliminowo-cyfrowych zadaniach zasada numerowania pól jest inna, a mianowicie: w każde N-kratkowe polimino wpisywane są kolejne cyfry od x do x+N–1. Są dwie odmiany takiego numerowania – x może być równe 1, wtedy w każdym poliminie pojawiają się cyfry od 1 do N albo x jest dowolne. Odmiana z x=1 występuje częściej i była chronologicznie pierwsza. Debiutowała w Japonii w 1998 roku w łamigłówce zwanej hakyu, co stanowi skrót pełnej nazwy, przedstawianej w zapisie transkrypcyjnym jako „hakyū kōka”, czyli „Efekt falowy” lub „Efekt tętnienia”. Skąd takie dziwne określenie? – to zagadka dla wyobraźni. Poza zasadą wymagającą, aby w każdym N-ominie znalazły się cyfry od 1 do N, jest jeszcze ekstra warunek: między jednakowymi cyframi umieszczonymi w tym samym rzędzie (kolumnie) powinno być co najmniej tyle kratek, ile wynosi wartość tych cyfr, a więc przynajmniej jedno pole między dwiema jedynkami, dwa między dwójkami, trzy między trójkami itd. Przykładowe małe hakyu z rozwiązaniem przedstawione jest na rys. 4a, większe – do potrenowania przed zadaniami konkursowymi – na rys. 4b.

Jeśli w regułach hakyu odpowiednio zmienić tylko powyższy ekstra warunek, wówczas powstanie opis łamigłówki znanej m.in. pod nazwą suguru. Odpowiednia zmiana polega na tym, że dwie jednakowe cyfry nie mogą znaleźć się w sąsiednich kratkach, przy czym za sąsiednie uważa się zarówno kratki mające wspólny bok, jak i stykające się tylko rogami. W związku z tą zmianą przy rozwiązywaniu suguru nieco większą rolę odgrywa spostrzegawczość. Przykład zadania z rozwiązaniem (a) oraz niezbyt trudne suguru (b) do pogimnastykowania szarych komórek – na rys. 5.

Ostatnie z poliminowych zadań najbardziej przypomina sudoku, stąd jego nazwa – polidoku. Podobieństwo jest wyraźniejsze wówczas, gdy diagram ma wymiary 9×9 kratek (rys. 6), choć zwykle bywa mniejszym kwadratem. Celem jest, jak w sudoku, utworzenie kwadratu łacińskiego, czyli wpisanie w kratki diagramu N×N cyfr od 1 do N tak, aby w każdym wierszu i w każdej kolumnie występowało N różnych cyfr. Dodatkowy warunek dotyczy oczywiście polimin: w każdym powinno się znaleźć m kolejnych cyfr, gdzie m jest liczbą kratek tworzących dane polimino. Na przykład, w pomarańczowym pentominie na rys. 6, gdyby było puste, mogłyby pojawić się cyfry 1, 2, 3, 4, 5 lub 2, 3, 4, 5, 6 lub 3, 4, 5, 6, 7 lub 4, 5, 6, 7, 8 lub 5, 6, 7, 8, 9. Skoro jednak jest w nim ujawniona trójka i piątka, więc w grę wchodzą tylko zestawy 1, 2, 3, 4, 5 lub 2, 3, 4, 5, 6 lub 3, 4, 5, 6, 7. Logika polidoku jest zwykle „gęstsza” niż sudoku, czyli wnioskowanie przy rozwiązywaniu bywa kilkustopniowe (np. jeżeli A, to B i wtedy C, a zatem D). Przykładem może być jeden z etapów rozwiązywania małego zadania na rys. 7. Najpierw wpisywane są trójki i czwórka – kolejno w pola II-b, V-a, III-d, I-e, V-c; następnie (drugi diagram) można przeprowadzić „pokrętne” wnioskowanie: w dwóch z trzech pomarańczowych pól muszą być cyfry 2 i 4, a zatem do szarej kratki u dołu powinno trafić 1 lub 5; gdyby trafiło 1, to z jego lewej strony znalazłoby się 2, a obok trójki w przeciwnym rogu 4, więc dla piątki zostałoby środkowe pole w dolnym rzędzie – ale to trzeba odrzucić, bo piątka jest już wyżej w środkowej kolumnie. A zatem w szarej kratce powinno się znaleźć 5, co wymusza obok w rogu 4. Dalsza droga do celu jest już bardzo prosta.

Zadania

1. Rysunek 8 przedstawia odmianę fillomina, w której diagram należy podzielić wzdłuż oznaczonych linii tylko na monomina, domina i trimina. Polimina takiej samej wielkości nie mogą stykać się bokami (rogami mogą). Jak zwykle w fillominie kluczem do rozwiązania są ujawnione liczby, czyli każdy kwadracik z liczbą należy do polimina złożonego z tylu kratek, jaka jest wartość tej liczby. W rozwiązaniu wystarczy podać liczbę polimin każdego rodzaju wydzielonych w diagramie.

2. Na rys. 9 znajduje się suguru, które ma więcej niż jedno rozwiązanie. W odpowiedzi wystarczy wskazać kratki, w które można wpisać różne cyfry.

3. W polidoku na rys. 10 ujawnione są tylko cztery cyfry. Może się wydawać, że to za mało, aby było jedno rozwiązanie. A jednak... Jako odpowiedź końcową wystarczy podać cztery cyfry, które znajdą się w narożnych polach.

4. Prostokąt na rys. 11 można nazwać półmagicznym, ponieważ sumy cyfr w wierszach są jednakowe (18) i sumy cyfr w kolumnach także, choć inne niż w wierszach (15), ale za to złożone z różnych cyfr. Poza tym dwie jednakowe cyfry nigdzie nie sąsiadują ze sobą w wierszach. Prostokąt ten należy podzielić na 6 pentomin o różnym kształcie tak, aby na każdym znalazło się pięć różnych cyfr. Jako końcową odpowiedź wystarczy podać, ile rozwiązań ma to zadanie.

Rozwiązania prosimy nadsyłać do 31 lipca br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG 7/17, lub listownie: Świat Nauki, ul. Rzymowskiego 28, 02–697 Warszawa. Spośród autorów poprawnych rozwiązań przynajmniej trzech zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Krótka historia wszystkich ludzi, którzy kiedykolwiek żyli Adama Rutherforda ufundowaną przez wydawnictwo Prószyński Media.

***

Rozwiązania zadań z numeru majowego

1. Dla kryptarytmu z rys. 12a punkt 2 instrukcji Kaprekara jest następujący: utwórz liczbę Y₀ z cyfr liczby X₀, ustawiając największą cyfrę jako drugą, najmniejszą – jako czwartą, a większą z dwu pozostałych – jako trzecią (mniejsza trafi na początek liczby). Iteracja zakończy się stałą lub cyklem. Przykłady stałych: 1269 (zaczynając np. od 2017), 1089 (zaczynając od 2013), zero (od 2012); przykład cyklu: 6993>2997>4995>0999>8991>6993 (gdy zacznie się np. od 2579).

Dla kryptarytmu z rys. 12b punkt 2 instrukcji Kaprekara jest następujący: utwórz liczbę Y₀ z cyfr liczby X₀, ustawiając największą cyfrę jako pierwszą, najmniejszą – jako trzecią, a mniejszą z dwu pozostałych – jako drugą (większa trafi na koniec liczby). Iteracja również może zakończyć się stałą (np. 1089, gdy zacznie się np. od 2013) lub cyklem (np. 3087>1269>3087, zaczynając np. od 2017 lub 2016).

2. Ostatnia liczba, kończąca iteracje, musi być nieparzysta, a jedynym nieparzystym dzielnikiem 6174, który nie jest liczbą pierwszą i nie zawiera żadnej z cyfr 1, 4, 6, 7 jest 9.

3. 10474x6174=64666476.

Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Podstawy matematyki Iana Stewarta i Davida Talla ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Dawid Hanrahan z Brzegu, Daniel Kocur z Tych, Kacper Kurowski z Błonia, Piotr Pindel z Warszawy, Krzysztof Szeruga z Wrocławia.

***

Marek Penszko, z wykształcenia inż. poligrafii, jest znawcą i popularyzatorem gier i rozrywek umysłowych, głównie matematyki rekreacyjnej. Współpracuje z wieloma czasopismami, m.in. pisze blog dla Polityki.