Moc macek, czyli o sięganiu bezkonfliktowym

Koliste niebieskie „stworki” w polach diagramu na rys. 1 – nazwiemy je kolikami – mogą wysuwać z czterech punktów na swoim brzegu macki w rzędzie lub kolumnie, czyli w każdym z czterech głównych kierunków. Macka dociera do środka jakiejś kratki, więc jeśli sięga dalej niż do sąsiedniego pola, to po drodze „zalicza” inne kratki. Liczba w koliku oznacza jego moc, a więc łączną moc jego macek, czyli dokładną liczbę pól, które powinny objąć zasięgiem wszystkie jego macki. Zadanie polega na oznaczeniu macek wysuniętych przez wszystkie koliki.

Zwykle w takiej łamigłówce pojawiają się jeszcze warunki dodatkowe: (1) macki kolików powinny „obsłużyć” wszystkie puste pola; (2) żadnego pola nie może odwiedzić więcej niż jedna macka; (3) żadnego pola z kolikiem nie może sięgnąć macka wychodząca z innego kolika. Warunki (2) i (3) są praktycznie przydatne, choć podawanie ich nie jest konieczne, ponieważ suma liczb w kolikach równa jest liczbie pustych pól.

Przy rozwiązywaniu korzysta się zwykle z dwóch prostych metod, uwzględniających konieczność dotarcia macką do jakiegoś pola w dwóch przypadkach. Po pierwsze – gdy dane pole jest w zasięgu tylko jednej konkretnej macki; po drugie – gdy kolik „rozpycha się” mackami, a zatem ich moc trzeba w pełni wykorzystać. Stosuje się też metodę nie wprost, zakładając, że macka sięga danego pola, co doprowadza do sprzeczności. Sprzeczność polega na tym, że macka staje się jakby ścianką, odcinającą obszar złożony z liczby pól nierównej łącznej mocy „obsługujących” ten obszar kolików. Wówczas w obszarze tym albo zabraknie pól dla macek, albo odwrotnie – będzie ich za dużo. Na rys. 2 znajduje się rozwiązanie zadania z rys. 1. Macki jakby dzielą diagram na wielokąty złożone z kratek objętych mackami, których zalążkami są poszczególne koliki, co uzasadnia zaliczenie łamigłówki do grupy parkietażowych.

O łamigłówkach z mackami była już mowa w tej rubryce przed kilku laty, choć w innej scenerii. Koliki były światowidami, a zasięg ich wzroku odpowiadał mackom. „Wcieleń” tego zadania wymyślono zresztą przynajmniej kilka od czasu, gdy zagościło ono po raz pierwszy przed 30 laty w japońskim magazynie z łamigłówkami jako ścianki logiczne. Później na świecie pojawiły się inne nazwy – m.in. cztery wiatry, promienie, kiełki, wypustki, a wreszcie macki. Przy tym ostatnim określeniu pozostaniemy. Powrót do tematu wynika nie tyle z okrągłej rocznicy, ile ze względu na warte omówienia aspekty matematyczne związane z tą niemal klasyczną łamigłówką, a także niektóre z jej licznych odmian, powstałych w minionych latach. Odmiany te są ciekawym przejawem kreatywności autorów logicznych zadań diagramowych.

Podstawy matematyczne macek można wyrazić prostym wzorem – p=k+m_k, czyli liczba pól diagramu (p) równa jest sumie liczby kolików (k) i sumie ich mocy, która jest sumą znajdujących się w kolikach liczb (m_k). Przykład na rys. 1 jest nieco nietypowy i szczególny. Nietypowy, ponieważ diagram ma kształt prostokątny (7×5), podczas gdy standardem w zadaniach diagramowych jest kwadrat. Natomiast szczególny dlatego, że liczby w kolikach są nie tylko różne, ale w dodatku tworzą ciąg liczb naturalnych od 1 do k, gdzie k=7. Typowe macki są więc kwadratem, a liczby w nich mogą być dowolne, byleby oczywiście ich suma (m_k) była równa liczbie pustych pól (p–k). Typowy i nieszczególny przykład mógłby więc wyglądać tak, jak na rys. 3, chyba że za szczególne uznalibyśmy symetryczne rozmieszczenie kolików; symetria układu pojawia się jednak dość często.

Z typowym, ale szczególnym przypadkiem wiąże się ciekawy problem matematyczny: jaką wielkość powinien mieć kwadratowy diagram macek z umieszczonymi w kolikach różnymi kolejnymi liczbami naturalnymi od 1 do k? Przy takim założeniu suma liczb w k kolikach jest tzw. liczbą trójkątną, wyrażającą się wzorem m_k=k(k+1)/2. Stąd liczba wszystkich pól kwadratu p=k+k(k+1)/2=k(k+3)/2. Skoro p powinno być kwadratem (p=n²), więc aby znaleźć wartości k i n należy uporać się z równaniem k(k+3)/2=n², czyli k²+3k–2n²=0. Rozwiązując to równanie względem niewiadomej k, otrzymamy najpierw Δ=9+8n², a potem wzór na interesującą nas dodatnią wartość . Teraz trzeba znaleźć takie n, aby suma pod pierwiastkiem była kwadratem jakiejś nieparzystej liczby x. Inaczej mówiąc, należy rozwiązać równanie diofantyczne (w grę wchodzą tylko liczby całkowite) z dwiema niewiadomymi x²–8n²=9. W ten sposób od formalnie prostej łamigłówki dotarliśmy do trudnego zagadnienia z algebraicznej teorii liczb, w której podane równanie w uogólnionej postaci (x²–ay²=b; a nie jest kwadratem) stanowi od starożytności obiekt wnikliwych analiz.

Zwane jest od XVIII wieku równaniem Pella-Fermata albo tylko Pella, jeśli b=1. Jedno rozwiązanie równania 9+8n²=x² łatwo znaleźć, podstawiając pod n kolejne liczby dotąd, aż po lewej stronie pojawi się kwadrat. Właściwie już pierwsze podstawienie owocuje „niepraktyczną” parą (n, x) = (0, 3), ale wkrótce pojawia się praktyczna (3, 9), co daje k=3. Ta wartość przekłada się na macki z trzema kolikami (1, 2, 3) rozmieszczonymi w kwadracie 3×3 – ich różnych układów (z dokładnością do obrotów i odbić lustrzanych) z jednym rozwiązaniem jest dziesięć. Jak szybko uda się Państwu znaleźć dwa, których brakuje na rys. 4? Szukanie kolejnych par (n, x) lepiej powierzyć komputerowi, choć do następnej nie jest zbyt daleko (18, 51), ale potem dystanse stają się coraz większe: …, (105, 297), (612, 1731), (3567, 10089), (20790, 58803), …

Znajdowanie tych par bez komputerowego wsparcia, czyli rozwiązywanie równania x²–8n²=9, jest skomplikowane nie tylko dlatego, że rozwiązań jest nieskończenie wiele. Stanowi ono trudny przypadek równania Pella-Fermata (x²–ay²=b) ze względu na zależność b>√–a. Gdy w równaniu taka zależność nie występuje, wtedy skuteczne jest stosowanie jednej konkretnej, choć nieprostej metody rozwiązywania (zwykle korzysta się z ułamków łańcuchowych). Tutaj jedna metoda nie wystarcza. W ogóle równania Pella-Fermata należą do najbardziej „kapryśnych” równań diofantycznych. Na szczęście często po znalezieniu kilku początkowych rozwiązań skuteczna okazuje się rekurencja.

Tak jest również w przypadku równania x²–8n²=9: każda następna para wartości (n, x) powstaje z dwu poprzednich – wystarczy poprzednią pomnożyć przez 6 i od iloczynu odjąć przedpoprzednią. Na przykład: (n, x)₄ = 6×(n, x)₃ – (n, x)₂, czyli 6×(18, 51) – (3, 9) = (108, 306) – (3, 9) = (105, 297). Warto wspomnieć, że sposób rekurencji – jak przystało na wspomnianą „kapryśność” – bywa różny w zależności od konkretnego równania. Na przykład dla podobnego równania x²–10n²=9 dopiero obliczenie sześciu początkowych par (n, x) umożliwia skorzystanie z następującej rekurencji: (n, x)_i = 38×(n, x)_i-3 – (n, x)_i-6.

Ze znalezionych wartości n (18, 105, 612,…) dla równania x²–8n²=9 wynika k, czyli liczba kolików z liczbami od 1 do k, które powinny znaleźć się w odpowiednich diagramach (24, 147, 432, …). To oczywiście tylko teoria, bo o ile amatorzy zadania na diagramie 18×18 z ulokowanymi w nim 24 kolikami może by się znaleźli, o tyle format 105×105 ze 147 kolikami byłby co najwyżej kandydatem do księgi rekordów.

Czy zatem kwadratowe macki 6×6 na rys. 5 – z siedmioma kolikami z liczbami od 1 do 7 – są błędne, skoro pustych pól jest w nich więcej, niż wynosi suma liczb? Można by je za takie uznać, gdyby nie dodatkowa informacja: jedno pole diagramu musi pozostać nietknięte mackami. Które? – to można ustalić w trakcie rozwiązywania albo nawet przed nim, jeśli na diagramie znajduje się kratka, której nie ma w zasięgu żaden kolik (tak jest na rys. 5). Macki z jednym lub więcej „niemacanymi” polami są logicznie nieco uboższe, bo przy rozwiązywaniu odpada metoda wnioskowania, polegająca na tym, że danego pola trzeba sięgnąć, gdyż w przeciwnym razie nie byłoby ono w ogóle macane.v Na rys. 6 jest przykład takiego zadania, pochodzący z łamigłówkowych mistrzostw Japonii. „Nieczynne” są w nim dwa pola. Jeśli zauważyć, że sprytny klucz do rozwiązania stanowią dwie trójki przy lewym dolnym rogu, to niemacane pola udaje się szybko rozszyfrować, a całość idzie jak po sznurku.

Trudniejsza i logicznie ciekawsza jest odmiana zwana n-mackami, w której nieczynne kratki są „zdyscyplinowane”, a konkretnie: jest ich n w diagramie n×n – po jednej w każdym wierszu i w każdej kolumnie. Gdybyśmy teraz, jak poprzednio, szukali przypadków szczególnych, czyli z k kolikami z liczbami od 1 do k, to należałoby zacząć od wzoru uzupełnionego o n nieczynnych pól, czyli k+k(k+1)/2+n=n². Po przekształceniach otrzymamy równanie kwadratowe k²+3k–2n(n–1)=0, którego dodatni pierwiastek wyraża się wzorem . Równanie Pella-Fermata ma teraz postać x²–8n(n–1)=9, a jego kolejnymi rozwiązaniami są pary (n, x): (2, 5), k=1; (5, 13), k=5; (10, 27), k=12; (27, 75), k=36,… Para (2, 5) jest niepraktyczna, bo na diagramie 2×2 z dwoma nieczynnymi polami kolik będzie zablokowany, czyli nie wysunie macki. Za to następna para może realizować się w konkretnym zadaniu, na przykład takim, jak na rys. 7 – prostym, ale z całkiem zgrabną logiką i jednym rozwiązaniem. Logika wiąże się z koniecznością uwzględniania obecności w każdym wierszu i w każdej kolumnie jednej nieczynnej kratki. Inny typowy, czyli kwadratowy, ale nieszczególny (dowolne liczby w kolikach) przykład n-macek (rys. 8) jest mimo niewielkiego formatu znacznie trudniejszy.

Wśród odmian z nieczynnymi polami na uwagę zasługuje jeszcze wariant stop-. Dodatkowa reguła jest oryginalna i prosta, ale jej opis może być niejasny, więc lepiej przedstawić ją graficznie: w diagramie na dwóch sąsiednich polach nigdzie nie może pojawić się taki układ macka-macka lub macka-puste pole, jak na rys. 9 u góry – oczywiście z uwzględnieniem obrotów obu tych układów. Rysunek 9 to przykład stop-macek do rozwiązania. Odejmując sumę liczb w kolikach (22) od liczby pustych pól (28), ustalimy, że 6 pól powinno pozostać nietkniętych mackami – ale oczywiście nie, jak w n-mackach, po jednym w każdym wierszu i w każdej kolumnie. Niektóre z nich można oznaczyć na starcie, pozostałe ujawniają się w trakcie rozwiązywania.

Czy liczby w kolikach mogą oznaczać co innego niż sumaryczną moc wysuwanych przez nie macek? Także w tym zakresie autorzy zadań wykazali się sporą inwencją. Pierwszy pomysł wydaje się bardzo prosty: cyfra w koliku równa jest liczbie wysuwanych macek, czyli możliwości są cztery – 1, 2, 3, 4. Tylko czy to wystarczy do ułożenia ciekawego zadania z jednym rozwiązaniem? Tak, ale po następującym małym uzupełnieniu reguł: jeśli w koliku jest liczba większa niż 1, to wysuwane macki są różnej długości.

Spróbujmy przerobić na taki wariant, zwany kiełkami, klasyczne macki z rys. 3. W rozwiązaniu zadania z rys. 3 są niestety koliki z mackami jednakowej długości, czyli niemożliwymi do odtworzenia w kiełkach. Mimo to po wymianie cyfry w każdym koliku na oznaczającą liczbę jego macek powstanie układ, wymagający tylko skorygowania kilku cyfr, a całe zadanie – bardzo proste, z jednym, choć całkiem innym rozwiązaniem (jakim?) – będzie wyglądać tak, jak na rys. 10.

A co oznaczają zera w kolejnej odmianie macek (rys. 11)? „Zero to brak macek” – to odpowiedź częściowo poprawna, bo dotycząca szczególnej sytuacji. Ogólnie w tej odmianie, zwanej różnicową, każda cyfra jest bezwzględną wartością różnicy między mocą (liczbą sięgniętych pól) macek poziomych i pionowych wychodzących z danego kolika, a macane są oczywiście wszystkie wolne pola. Teraz nie sposób określić zależności między liczbą wolnych pól (p–k) a sumą liczb w kolikach (m_k), która w tym przypadku nie jest, jak w zwykłych mackach, sumą mocy macek. Można tylko stwierdzić, że moc każdego kolika jest większa niż umieszczona w nim liczba, jeśli ta liczba jest większa od zera (dla zera może być równa zeru) oraz że 0≤m_k≤p–k. Układ kolików na rys. 11 jest szczególny w tym sensie, że liczba kolików k=m_k.

Na koniec powrócimy do zwykłych macek, czyli z liczbami w kolikach, oznaczającymi ich moc i bez niemacanych pól. Tylko że w kolikach liczb… nie ma (rys. 12). Niektóre w ogóle zniknęły, a większość zmieniła miejsce i postać. Przed i nad każdym rzędem diagramu (wierszem i kolumną), w którym są przynajmniej dwa koliki, jest suma umieszczonych w nich, ale ukrytych liczb. To najtrudniejszy wariant macek, zwany sumowym – zwykle wymagający korzystania z metody prób i błędów. Z sum przy brzegach można wnioskować o zakresach liczb w kolikach. Na rys. 12 jest to proste, ponieważ wszystkie zakresy obejmują tylko dwie cyfry (wykluczamy zera, które pojawiają się tylko w odmianie różnicowej). W diagramie powstają zatem cztery sprzężone parami piątki kolików oznaczone różnymi kolorami na rys. 13. Składają się one na jakby cztery różne choć bliźniacze zadania. Rozwiązywanie tylko jednego z nich udaje się doprowadzić do końca; w trzech pozostałych występuje sprzeczność.

Macki we wszystkich powyższych rodzajach zadań nie wchodzą sobie w paradę. Bezkonfliktowo, jak w tytule, dzielą między siebie cały lub prawie cały obszar diagramu. A mogłoby być i bywa inaczej, gdy macki spotykają się, a nawet krzyżują (miecze) na polach, do których roszczą sobie prawa dwie, a nawet trzy lub cztery. Takimi antagonizmami zajmiemy się już jednak przy innej okazji.

Zadania

Zadania konkursowe obejmują trzy z pięciu opisanych odmian macek. Tylko w n-mackach w rozwiązaniu pozostają puste niemacane pola.

1. N-macki (rys. 14), czyli wariant z jednym niemacanym polem w każdym wierszu i w każdej kolumnie. Jako rozwiązanie wystarczy podać… liczbę rozwiązań.

2. Kiełki (rys. 15), czyli cyfra w każdym koliku oznacza liczbę wysuwanych z niego macek; jeśli liczba ta jest większa niż 1, to długości macek są różne. Jako rozwiązanie wystarczy podać sumę liczb, od których wychodzą macki, sięgające 13 pól na przekątnych diagramu (jeśli od liczby wychodzą dwie lub więcej macek, sięgających kratek na przekątnych, liczbę tę należy wliczyć do sumy tylko raz).

3. Macki różnicowe (rys. 16), czyli cyfra w każdym koliku jest bezwzględną różnicą sumy zasięgów jego macek poziomych (w wierszu) i pionowych (w kolumnie). Jako rozwiązanie wystarczy podać, ile jest macek jednostkowych, czyli takich, które sięgają tylko jednej pustej kratki.

Rozwiązania prosimy nadsyłać do 31 marca br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG 03/20. Spośród autorów poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Alfreda S. Posamentiera, Bernda Thallera Liczby. Ich dzieje, rodzaje, własnoś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 styczniowego

1. Są tylko dwie trzycyfrowe liczby pierwsze takie, że suma kwadratów tworzących je cyfr jest kwadratem – 263 (49) i 269 (121).

2. 1634 (12+62+32+42=62; 14+64+34+44=1634).

3. D=415, E=230.

Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Adama Rutherforda Księga ludzi. Opowieść o tym, jak staliśmy się nami, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Bogdan Gogółka z Cieszyna, Rafał Mazurek z Sierakowic, Alicja Musielak z Radostowa Górnego, Andriy Sopilnyak z Łodzi, Przemysław Ziobro z Krakowa.