Królem po literach, czyli zabawy matematyczno-leksykalne
Graf jako pojęcie matematyczne jest zbiorem punktów (wierzchołków) i łączących je linii (krawędzi), kojarzącym się zwykle z siecią dróg lub przewodów. O skojarzenie z szachami trudniej, choć każda figura szachowa ma swój graf – nie tylko na szachownicy, także na dowolnym fragmencie siatki kwadratowej. Wierzchołkami grafu są środki pól, zaś krawędzie odpowiadają możliwym ruchom danej figury między polami-wierzchołkami.
Skoczek i król wyznaczają dwa najpopularniejsze grafy szachowe, z których pierwszy znany jest z powodu oryginalnego ruchu konikiem, drugi – ze względu na bardzo proste, minimalistyczne posunięcie królewskie – o jedno pole w dowolnym kierunku, wprost lub na ukos. Oba grafy w wersji szachownicowej (8×8) są przedstawione na rys. 1. Do ich spopularyzowania przyczyniły się w XIX wieku czasopisma, zamieszczając w działach rozrywek umysłowych zadania zwane zwykle konikówkami i królówkami. Ten rodzaj prostych łamigłówek pojawia się czasem i dziś w publikacjach szaradziarskich, zwłaszcza adresowanych do młodych czytelników. Diagram w obu przypadkach wygląda podobnie – we wszystkie pola pokratkowanego prostokąta wpisane są w określony sposób – skoczkowy lub królewski – litery, tworzące krótki tekst, np. tytuł jakiegoś utworu lub przysłowie. Zadanie polega na odczytaniu tego tekstu. W tym celu należy obejść wszystkie pola ruchem skoczka lub króla, goszcząc w każdym tylko raz – oczywiście tak, aby odwiedzane w kolejnych krokach litery były kolejnymi w „połamanym” tekście. W tym artykule zajmiemy się wędrującym po literach królem; konik będzie miał wolne.
Diagram na rys. 2 jest zaproszeniem do przykładowej królewskiej przechadzki. Jej trasa stanowi w grafie króla podgraf, którego początek oznaczono czerwoną linią – odpowiada mu (nomen omen) słowo KRÓL. Dalszą część podgrafu-trasy, obejmującą pozostałe 26 liter, nie tak łatwo wyznaczyć, bo nie wiadomo, czego dotyczy cały szukany tekst. Jeśli jednak dobrze zacząć kontynuację albo przyjrzeć się dokładnie literom w diagramie, można szybko wpaść na właściwy trop. Królówka z rys. 2 liczy sobie blisko półtora wieku; pochodzi z łamów tygodnika Wędrowiec. W innym ówczesnym czasopiśmie, Biesiadzie Literackiej, zamieszczone było zadanie przedstawione na rys. 3. Tym razem król odszukuje w diagramie odrębne wyrazy, nie tworzące jednego ciągu – każdy zaczyna się w polu z kółkiem. Ułatwieniem jest informacja, że wszystkie słowa należą do tej samej kategorii znaczeniowej. Jakiej? – tego należy się domyślić z oznaczonej trasy jednego wyrazu (WAGA). Właściwie król niejako wykreśla słowa z diagramu, zaś część liter pozostaje poza jego trasami, czyli nie jest wykreślana. Te niezaliczone litery, czytane kolejno rzędami od góry do dołu, tworzą ostateczne rozwiązanie – tytuł fragmentów znanej XIX-wiecznej powieści; zadanie było swego rodzaju reklamą tego dzieła.
Królówki gościły w prasie przez dziesięciolecia, choć nigdy nie „królowały”, zwłaszcza od kiedy w działach rozrywek umysłowych zapanowały krzyżówki. Powróciły do łask dopiero w połowie lat 70. XX wieku w nieco innej formie – jako gra Boggle. Podstawowym rekwizytem w tej grze jest 16 typowych sześciennych kostek, ale nie z oczkami, tylko z literami na ściankach. Na początku wszystkie kostki umieszczane są w specjalnym kubku z kwadratową przykrywką i po potrząśnięciu nim, a następnie odwróceniu, wpadają do przegródek w przykrywce tak, że litery na ich górnych ściankach tworzą literowy kwadrat 4×4. Teraz do akcji wkracza król, bowiem gra polega na układaniu słów, których kolejne litery powinny znajdować się w sąsiednich polach tego kwadratu. Reguły zabraniają korzystania dwukrotnie w danym słowie z tej samej kostki (ściślej – z litery na jej ściance), tworzenia wyrazów krótszych niż 3-literowe oraz określają punktację za słowa zależną od ich długości. Układane wyrazy każdy z graczy przez 3 minuty zapisuje w sekrecie na kartce, po czym następuje finał – ujawnienie zapisów i obliczanie zdobytych przez każdego punktów. Uwzględniany jest jednak przy tym istotny, uatrakcyjniający grę warunek: nie są punktowane wyrazy zapisane przez więcej niż jednego gracza – każdy wykreśla takie powtórki ze swojej listy; punktują tylko pozostałe, unikatowe słowa, czyli premiowana jest oryginalność.
Na rys. 4 znajduje się przykład kwadratu Boggle. Król może „wychodzić” wyrazy będące – podobnie jak w grze scrabble – dowolnymi częściami mowy w dowolnej formie gramatycznej, byleby nie były to nazwy własne. W przykładowym kwadracie krótkie słowa łatwo znaleźć, np. SNY, KURZ (nie ETER, ponieważ obie litery E pochodziłyby z tej samej kostki), AUTOR, RZEPIE (poprawnie, bo dwie litery E wzięte są z różnych kostek). O dłuższe niż 6-literowe jest już znacznie trudniej. Proszę spróbować znaleźć przynajmniej dwa 7-literowe inne niż AUTORZE, jedno 8-literowe i jedno 10-literowe (9-literowego chyba nie ma). Wyzwaniem jest możliwe do odczytania słowo 16-literowe, czyli obejście królem całego kwadratu, jak w typowej królówce.
W krajach anglojęzycznych Boggle uchodzi za klasykę i cieszy się sporym powodzeniem, choć nie dorównuje pod tym względem spokrewnionej z nią grze scrabble. Istnieją też wersje w innych językach, ale o ich popularności można mówić tylko tam, gdzie zabawy słowne są silnie zakorzenione w tradycji, czyli np. we Francji. Polska wersja, formalnie nieco różniąca się od tradycyjnej, była dostępna przed kilku laty, ale dość szybko znikła z rynku. Obecnie częściej można natknąć się u nas na oryginalną wersję angielską, która służy niekiedy jako pomoc dydaktyczna przy nauce języka.
Wydaje się, że Boggle nie ma nic lub prawie nic wspólnego z matematyką. Rozgrywka wymaga tylko spostrzegawczości oraz znajomości słów, a także gramatyki w przypadku języków fleksyjnych, jak polski. Wprawdzie wyrazy odczytuje się po drogach zwanych podgrafami, ale samo matematyczne określenie to jeszcze nie matematyka. Okazuje się jednak, że wystarczy jakby odwrócić przebieg rozgrywki, aby powstała łamigłówka logiczna związana z trudnymi zagadnieniami matematycznymi. Ogólnie w łamigłówce chodzi o to, aby, znając listę słów spisanych z kwadratu Boggle, odtworzyć ten kwadrat. Lista słów powinna spełniać określone warunki, by łamigłówka miała rozwiązanie i aby było ono jednoznaczne. Ponieważ jednak obroty i odbicia lustrzane kwadratu Boggle nie wpływają na zestaw słów na liście, zatem jedno rozwiązanie istnieje z dokładnością do odbić i obrotów. Oczywistym warunkiem koniecznym jest obecność na liście wszystkich 16 liter, występujących w kwadracie. Inne warunki nie są znane, czyli, mówiąc wprost, nie wiadomo, jak ułożyć „czystą” łamigłówkę Boggle – w każdym razie dotąd nikomu się to nie udało. „Czystą” oznacza bez dodatków i ograniczeń, których nie ma w zasadach gry. Wszystkie zadania logiczne Boggle są zatem „nieczyste” – przykładowe znajduje się na rys. 5. Umieszczona obok diagramu lista liczy 6 słów. Dodatkiem są 4 ujawnione w diagramie litery, które warunkują jedno rozwiązanie (odbicia i obroty nie wchodzą w grę), a także to, że żadna litera się nie powtarza, tzn. inna jest każda z 16, które trafią do diagramu (na razie znajdują się pod nim). Ponadto w wypełnionym literami diagramie powinno być możliwe odczytanie rzędami poziomymi nazw dwóch miast.
„Czystszy” i matematycznie ciekawszy wydaje się kwadrat Boggle o jeden rząd pól mniejszy od standardowego, czyli 3×3. Niepowtarzalność liter zostaje w nim zachowana, czyli w diagramie lokowanych jest 9 różnych, jednak kwadrat na początku pozostaje pusty, więc szukane rozwiązanie stanowi jedno z ośmiu bliźniaczych (obroty i odbicia). Poza tym wszystkie słowa mają tyle samo liter. Przykładowe zadanie – diagram i 9 liter, które należy w nim rozmieścić tak, aby król mógł zeń odczytać sześć wyrazów 3-literowych, znajdujących się na zamieszczonej obok liście – jest na rys. 6.
Rozwiązywanie wypada zacząć od narysowania tzw. grafu sąsiedztwa (rys. 7a). Wierzchołkami są w nim litery, a te z nich, które sąsiadują ze sobą w słowach, połączone są krawędziami. Ten graf należy „wpasować” jako podgraf w odpowiadający diagramowi 3×3 graf króla (rys.7b). Liczba wierzchołków w obu grafach jest taka sama, więc „wpasowanie” polega na zastąpieniu odpowiednimi literami cyfr w wierzchołkach. W pierwszej chwili może się wydawać, że zadanie jest proste, a nawet że ma wiele całkiem różnych rozwiązań, bo liczba krawędzi w grafie króla (20) jest większa niż w grafie sąsiedztwa (12) i z każdego wierzchołka wychodzi ich tyle samo lub więcej. Wystarczyłoby więc usunąć 8 z nich. Ale które? Okazuje się, że wbrew pozorom łamigłówka jest trudna do ruszenia na logikę. Właściwie nie bardzo wiadomo, jak się do niej zabrać. I nic dziwnego, jest to bowiem typowy przykład zagadnienia określanego w matematyce jako problem izomorfizmu podgrafu, z którym uporanie się bez skorzystania z odpowiedniego algorytmu, a praktycznie z programu komputerowego, możliwe jest tylko w najprostszych przypadkach.
Wspomniany problem wiąże się z szerszym zagadnieniem – izomorfizmem grafów. Czym w tym przypadku jest izomorfizm, najłatwiej przedstawić na przykładzie. Załóżmy, że wierzchołki grafu na rys. 8a można przesuwać, a krawędzie są trwale połączone z wierzchołkami i rozciągliwe, czyli ich długość może się zmieniać. Przesuwamy każdy wierzchołek w miejsce, gdzie znajduje się jego kopia w takim samym kolorze (nie ruszamy tylko czerwonego, bo nie ma kopii). W rezultacie powstaje graf taki, jak na rys. 8b, który jest izomorficzny z grafem z rys. 8a. A zatem dwa grafy są izomorficzne, jeśli różnią się tylko kształtem, a takie same pozostają wszystkie ich pozostałe cechy, do których należą m.in. jednakowe liczby wierzchołków i krawędzi, równe stopnie wierzchołków (liczby krawędzi z nich wychodzących) identycznie oznaczonych oraz jednakowe ciągi stopni wierzchołków wzdłuż dowolnej drogi.
Rozstrzygnięcie, czy dwa grafy są izomorficzne, czy nie, jest w ogólnym przypadku skomplikowanym problemem obliczeniowym. Szukanie w grafie podgrafu izomorficznego z jakimś innym grafem – jak przy rozwiązywaniu zadania logicznego Boggle w kwadracie 3×3 – to problem co najmniej równie trudny. Niełatwe do rozgryzienia bywają nawet małe grafy, mimo że stopnie niektórych wierzchołków stanowią w nich klucz do rozwiązania. Tak jest np. w zadaniu na rys. 9: w grafie A należy odszukać podgraf izomorficzny z grafem B, przyporządkowując liczbom odpowiednie litery.
Wracając do wspomnianego zadania Boggle (rys. 6 i 7): jego rozwiązanie – jedyne z dokładnością do odbić i obrotów – znajduje się na rys. 10 (niebieskie krawędzie). Dojść do niego można głównie metodą prób i błędów. Do celu prowadzi np. próba oparta na założeniu, że podgraf obejmuje wszystkie osiem zewnętrznych krawędzi grafu króla. Wystarczy wówczas poszukać w grafie sąsiedztwa na rys. 7a drogi zamkniętej przechodzącej przez osiem liter. Taka droga jest tylko jedna: A-L-O-T-I-K-Ę-S-A; nie obejmuje ona litery P, która w związku z tym w rozwiązaniu trafia do środka grafu. Dowiedziono, że dla kwadratu 3×3 liczba słów 3-literowych mniejsza niż 6 nie gwarantuje jednoznaczności rozwiązania.
Problem izomorfizmu podgrafu nie jest czysto matematyczny lub łamigłówkowy. Zmagają się z nim specjaliści w różnych dziedzinach nauki – m.in. chemioinformatycy, szukając podobieństw we wzorach strukturalnych różnych substancji, oraz bioinformatycy, analizując struktury białek z wykorzstaniem baz danych, zawierających sekwencje DNA i RNA.
Zadania
1. Uzupełniamy reguły logicznego Boggle: król może odwiedzić to samo pole więcej niż raz. Taki przywilej umożliwia odczytanie jednym ciągiem z lewego kwadratu na rys. 11 imienia i nazwiska STANISŁAW STASZIC. W pustym kwadracie obok należy rozmieścić dziewięć znajdujących się pod nim liter tak, aby z kwadratu można było odczytać w taki sam sposób imię i nazwisko MARIA KONOPNICKA. Całkowicie różnych rozwiązań jest kilka, ale wystarczy odpowiedzieć na pytanie: jakie litery mogą się znaleźć w rozwiązaniu w środkowym polu kwadratu?
2. W kwadrat 4×4 wpisany jest tytuł artykułu (rys. 12). Należy zeń odczytać po królewsku – dokładnie tak, jak w grze Boggle – jak najmniej słów dłuższych niż 3-literowe, ale tak, aby we wszystkich tych słowach każda z 16 liter (każde pole) występowała przynajmniej raz. Słowa mogą być dowolnymi częściami mowy w dowolnej formie gramatycznej, ale wykluczone są nazwy własne oraz wyraz KRÓL. Za prawidłowe uznane zostaną rozwiązania z najmniejszą nadesłaną liczbą słów.
3. W diagramie 3×3 (rys. 13) należy rozmieścić 9 znajdujących się pod nim liter tak, aby król mógł zeń odczytać 4 słowa 4-literowe umieszczone obok. Zadanie jest podobne do logicznego Boggle z rys. 6 i także ma jedno rozwiązanie (z dokładnością do odbić i obrotów).
Rozwiązania prosimy nadsyłać do 31 sierpnia br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG 8/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ą Alfreda S. Posamentiera i Ingmara Lehmanna Ciekawostki matematyczne. Skarbnica zadziwiających rozrywek ufundowaną przez wydawnictwo Prószyński Media.
***
Rozwiązania zadań z numeru czerwcowego
1. Sołtys ma 70 świeżaków.
2. Są dwa sposoby podziału prostokąta 7x9 (rys. 14): po odcięciu części złożonej z 6 pól można utworzyć trapez otoczony czerwona linią, zaś odcinając część złożoną z 10 pól – trapez w zielonej linii.
3. 5929=772 jest najmniejszą sumą kwadratów jedenastu kolejnych liczb naturalnych – od 182 do 282.
Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Czy Wielki Wybuch był głośny? Karoliny Głowackiej i Jeana-Pierre’a Lasoty ufundowaną przez wydawnictwo Prószyński Media, otrzymują: : Julia Karska ze Zgorzelca, Michał Siennicki z Warszawy, Jacek Skrzymowski z Wrocławia oraz Marek Szafrański i Małgorzata Zawadzka z Warszawy.
***
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.