Tercet kwadratów, czyli o L-triminie
Od czasu, gdy Martin Gardner spopularyzował „wynalezione” przez Solomona Golomba polimino, czyli w ciągu ponad półwiecza, kilka rodzajów tej układanki znalazło poczesne miejsce w poważnej matematyce, a ściślej w geometrii kombinatorycznej. Gwoli przypomnienia: „wynalazek” stanowią figury złożone z kwadratów, stykających się całymi bokami.
Szerzej znane i wnikliwie analizowane są – oprócz dwukwadratowego domina – dwie poliminowe rodziny. Pierwszą jest tetromino, czyli komplet 5 figur utworzonych z 4 kwadratów wykorzystany m.in. w kultowej grze komputerowej tetris. Drugą pentomino – zestaw 12 płytek, z których każda składa się z 5 kwadratów (rys. 1). Domina, jako prostokąta, którego jeden bok jest dwukrotnie dłuższy od drugiego, dotyczy wiele zagadnień matematycznych, o których była mowa także w tej rubryce. To jednak nie jedyna konkretna figura polimina, będąca tematem publikacji ściśle matematycznych. Inną, której geometryczne aspekty są nie mniej interesujące, jest trzykwadratowy różowy sześciokąt na rys. 1 zwany L-triminem – najmniejsze polimino nieczworokątne. Wiążą się z nim dwie grupy tematów, które można by nazwać analityczną i syntetyczną. Zaczniemy od tej pierwszej, czyli od „rozkładu”.
Podział L-trimina na trzy figury przystające, czyli o takim samym kształcie i wielkości, wynika z definicji. Niemal równie prosty jest podział na dwie takie figury – trapezy prostokątne (rys. 2a). A na cztery?
To pytanie stanowi istotę klasycznego zadania opublikowanego po raz pierwszy w 1733 roku w hiszpańskim zbiorze zabaw, gier i łamigłówek autorstwa madryckiego rytownika Pablo Mingueta. W książce podany jest logiczny sposób rozwiązywania, zaczynający się od podziału każdego z trzech składowych kwadratów na cztery mniejsze. Utworzone w ten sposób 12 kwadratów należy połączyć w 4 grupy po 3 kwadraty każda, zaczynając od grupy złożonej z 3 małych kwadratów, należących do różnych dużych (żółta figura na rys. 2b). Efektem łączenia, czyli szukanego podziału, są także trimina, a więc 4 małe figury podobne do dzielonej, która w takim przypadku zwana jest samopowtarzalną. Warto zauważyć, że trapez, będący połową trimina (rys. 2a), także jest samopowtarzalny (rys. 2c).
Z dotychczasowych podziałów wynika, że trimino można podzielić na n części przystających, gdy n=3m (dzielenie kwadratów na prostokątne paski), n=22m-1 (dzielenie trapezów na kwartety mniejszych trapezów) oraz n=4m (podziały na triminowe kwartety) – dla m=1, 2, 3, … . Druga i trzecia liczby podziałów łącznie oznaczają możliwość podziału na n=2m części. Liczby n tworzą więc ciąg: 2, 3, 4, 6, 8, 9, 12, 15, 16, 18, 21, 24, 27, … . Czy zatem trimina nie uda się podzielić na liczby części przystających n, których brak w tym ciągu: 5, 7, 10, 11, 13, 14, …?
Z podziałem na dowolną parzystą liczbę części większą niż 2 i niepodzielną przez 3 rozprawił się Martin Gardner, proponując sposób cięcia nazwany kanonicznym (sposób ten działa także dla liczb n podzielnych przez 3, ale w takim przypadku prostsze jest korzystanie ze sposobu podanego wyżej). Przyjmujemy, że dłuższy bok trimina dzielonego kanonicznie na n przystających części ma długość 2n, a każda część składowa ma kształt i wymiary takie, jak na rys. 3a (jednostką długości jest bok kratki). Dla n=4 część ta jest oczywiście triminem i da podział taki, jak na rys. 2b. Dla n≥8 (8, 10, 14, 16, 20, 22, 26, 28, …), czyli n=6k+2 i n=6k+4 (k≥1) dzielenie polega na umieszczeniu u dołu dwóch części stykających się krótkimi bokami (rys. 3b), a następnie wypełnianiu reszty trimina od góry prostokątami n×6 (każdy tworzą dwie części składowe) dopóki będzie to możliwe. Pozostały wolny obszar zajmą dwie części w układzie takim jak na rys. 3c (dla n=6k+2) lub tworzące lustrzane odbicie tego układu (dla n=6k+4). Rys. 4 przedstawia przykładowy podział tą metodą na 10 części.
Wydaje się, że nie sposób podzielić L-trimina na n części przystających, gdy n jest liczbą pierwszą większą od 3. Intuicja podpowiada, że np. dla n=5 jest to niemożliwe, ale pewności nie ma, bo dowód nie jest znany. Najmniejszą niepierwszą liczbą części, na którą podział uchodził przez pewien czas za wątpliwy, było 25. Okazało się jednak, że dość łatwo wykazać możliwość podzielenia na n=k2 części dla dowolnego k i że wszystkie takie podziały są samopowtarzalne – dwa przykłady dla k=5 na rys. 5 (o dodatkowych kolorowych oznaczeniach za chwilę). Inaczej mówiąc, każde trimino „w kratkę”, czyli obejmujące 3k2 mniejszych kwadratów (3, 12, 27, 48, 75, 108, …), uda się podzielić na jednakowe „trzykratkowe” L-trimina. Czy także na proste trimina (żółte na rys. 1) zwane I-triminami?
Okazuje się, że nie jest to możliwe dla parzystych k niepodzielnych przez 3 (2, 4, 8, 10, 14, 16, 20, …). W sprytnym dowodzie korzysta się z trójbarwnego szachownicowego deseniu (rys. 6). Każde I-trimino umieszczone na takiej L-triminowej planszy zakrywa trzy pola w różnych kolorach, czyli pokrycie całej planszy wymaga takiej samej liczby pól każdego koloru. Tymczasem liczby kolorów są zawsze różne, równe k2–1, k2 i k2+1. Jeśli więc k=4, jak na rys. 6, to mamy 15 pól żółtych, 16 niebieskich i 17 różowych.
Zagadnienie podziału trimina na n przystających części podsumował informatyk z MIT Michael Beeler, udowadniając, że taki podział jest zawsze możliwy, jeśli n jest liczbą złożoną. Podzielność lub niepodzielność na liczbę pierwszą części większą od 3 pozostaje niewyjaśniona i jest to kolejna nierozwiązana zagadka związana z liczbami pierwszymi.
Powróćmy do rys. 5. Na obu figurach oznaczone są niebieskie brzegi prostokątów 3×2 i żółte obszary. Ma to związek z drugą, czyli syntetyczną grupą zagadnień, obejmującą parkietaże, a więc pokrywanie płaszczyzny L-triminami. To temat abstrakcyjny także w tym sensie, że w praktyce (np. przy układaniu glazury) nigdy nie korzysta się z płytek o takim kształcie. Równie osobliwe jest wykładanie dużych L-trimin małymi – jak na rys. 5. Dwa problemy związane z tym szczególnym parkietem są jednak typowe. Pierwszy: jakie mogą być wymiary prostokątów, które da się pokryć L-triminami. Drugi dotyczy żółtych obszarów: czy daną figurę – zwykle prostokąt, a w tym przypadku L-trimino (k=5) – można pokryć L-triminami (k=1) tak, aby brzegi trimin nigdzie wewnątrz nie tworzyły prostokąta 3×2. Żółty obszar bez prostokąta na rys 5b obejmuje 7 trimin, czyli jest 7-krotnie większy niż na rys. 5a. Czy mógłby być jeszcze większy (nie może obejmować trimin z wydzielonych prostokątów 3×2)? 25-krotnie większy na pewno nie, co łatwo stwierdzić, analizując możliwe położenie płytek przy górnym brzegu figury.
Pole prostokąta utworzonego z trimin musi być wielokrotnością 3, a zatem taki sam warunek dotyczy przynajmniej jednego boku. Prostokąt 3×2 złożony z dwóch trimin, a także pole, które można pokryć takimi prostokątami, nazwiemy elementarnym. Na rys. 7 są zaczątki prostokątów o szerokościach 3, 6 i 9. Ich wysokości mogą być liczbą parzystą (ρ) lub nieparzystą (η). Jeśli pierwszy prostokąt będzie miał wymiary 3×ρ, to jego pole będzie elementarne. Natomiast prostokąta 3×η nie uda się pokryć triminami.
Aby tego dowieść, wystarczy zauważyć, że każde z pól oznaczonych czerwoną kropką na rys. 7a (pierwsze i ostatnie w co drugim wierszu) musi być zakryte innym triminem, co oznacza konieczność użycia 3(η+1) trimin do pokrycia pola 3η – a więc sprzeczność. Prostokąty 6×ρ i 6×η (rys. 7b) są elementarne, bo 6×ρ=2(3×ρ) a 6×η=6×3+6×ρ. Na rys. 7c prostokąt 9×ρ także jest elementarny, bo 9×ρ=3(3×ρ). Natomiast 9×η elementarny nie jest, ale triminami można go pokryć, bo 9×η=9×5+9×ρ, zaś z prostokątem 9×5 łatwo sobie poradzić – choćby tak, jak na rys. 8 (5 prostokątów elementarnych plus 5 trimin). Ponieważ każda wielokrotność 3 jest sumą wielokrotności 6 i 9, więc z analizy przykładów na rys. 7 wynika, że prawie każdy prostokąt, długość boku którego jest podzielna przez 3, uda się wyłożyć triminami. Wyjątkiem są prostokąty 3×η.
Poza możliwością pokrycia prostokąta triminami warto jeszcze ustalić na ile sposobów (s) da się to zrobić. Dla prostokątów 2×3k i 3×2k zadanie jest trywialne – w obu przypadkach s=2k (dwa układy obrócone i/lub odbite względem siebie uznajemy za różne). Od wymiaru 4×3k zaczynają się trudne wyzwania, z którymi matematycy radzą sobie, korzystając z tzw. matryc transferowych. Pomocne jest także wyodrębnianie prostokątów spójnych, czyli takich, które nie są „rozcięte” przynajmniej jednym łączącym brzegi prostokąta odcinkiem złożonym z boków trimin. 4×6 to najmniejszy prostokąt, który może być spójny (rys. 9a lub jego odbicie lustrzane), ale może być także niespójny – i to na 16 sposobów – jeśli będzie się składał z prostokątów elementarnych (rys. 9b). Natomiast sposoby ułożenia prostokąta 5×9 są 384 i oczywiście wszystkie spójne (przykład na rys. 8).
Debiut medialny polimina, który miał miejsce w roku 1954 na łamach czasopisma American Mathematical Monthly, był ściśle związany z szachownicą 8×8. Większość problemów opisanych wówczas przez Solomona Golomba sprowadzała się do pokrywania szachownicy figurami złożonymi z kwadratów. Inspirację stanowiło znane już wówczas zadanie, polegające na pokrywaniu dominami szachownicy, z której usunięto dwa pola leżące na końcach tej samej przekątnej, a ściślej: chodziło o dowód niemożności takiego pokrycia. W analogicznym zadaniu z triminami celem jest pokrycie nimi szachownicy, z której usunięto jedno pole – pozostają więc 63 pola, czyli liczba podzielna przez 3.
Analiza parkietażu takiej „wybrakowanej” planszy prowadzi do ciekawych wniosków zarówno w przypadku I-, jak i L-trimin. Dla I-trimin kluczem do analizy jest – podobnie jak poprzednio (rys. 6) – trójbarwna szachownica (rys. 10a). Każde I-trimino pokrywa trzy pola różnego koloru, a nie wszystkie liczby pól różnych kolorów są równe: żółtych i niebieskich jest po 21, różowe są 22. Usunięte powinno więc być pole różowe, ale nie dowolne. Ze względu na symetrię kwadratowej szachownicy musi to być takie pole, którego kolor w tym samym miejscu nie zmienia się po obrocie planszy o dowolną wielokrotność kąta prostego. Takie „bliźniacze” pola są tylko cztery, z zielonym brzegiem na rys. 10a, zatem tylko wykluczenie z parkietażu któregoś z nich umożliwia pokrycie pozostałych 63 pól 21 I-triminami – na przykład takie, jak na rys. 10b.
W przypadku L-trimin sytuacja jest odmienna. Pokryć nimi szachownicę bez jednego pola można zawsze – niezależnie od tego, które pole zostanie pominięte. Golomb podał elegancki dowód indukcyjny, że jest to możliwe dla każdej kwadratowej planszy o wymiarach 2n×2n (n=1,2, 3,…).
Jest oczywiste, że dla n=1, czyli dla planszy 2×2, puste może pozostać dowolne pole po umieszczeniu na niej L-trimina. Na rys. 11 oznaczone są trzy kwadraty 2n×2n, dla n=1, 2, 3 (każdy obejmuje n+1 kolejnych coraz słabszych odcieni niebieskiego) i każdy jest ćwiartką kwadratu 2n+1×2n+1, w którego środku leży L-trimino, odcinając z trzech ćwiartek po jednym polu. Ponieważ L-triminami można pokryć:
– każdą z trzech „wyszczerbionych” ćwiartek,
– ciemniejszą pełną ćwiartkę po usunięciu z niej dowolnego pola,
więc kwadrat 2n+1×2n+1, z którego wyłączono dowolne pole, także uda się pokryć L-triminami.
Wypadałoby jeszcze sprawdzić, czy pozostałe kwadratowe plansze bez jednego pola (monomina) można pokryć L-triminami bez względu na to, które pole zajmie (lub opuści) monomino. Długości boków tych plansz tworzą ciąg liczb niepodzielnych przez 3 i przez 2n, czyli: 5, 7, 10, 11, 13, 14, 17, 19, 20, … . Udowodniono, że jest to możliwe dla prawie wszystkich takich „wyszczerbionych” kwadratów. Jedyną czarną owcą jest plansza 5×5. Z sześciu możliwych do usunięcia różnie usytuowanych (z dokładnością do symetrii) pól na tej planszy (rys. 12a) tylko likwidacja dowolnego z trzech najciemniejszych (a, d, f) pozwala wypełnić resztę planszy L-tetrominami. Przykład dla monomin (d) i (f) na rys. 12b. Jak to zrobić, gdy zabraknie rogu (a) – to propozycja prostego ćwiczenia przed zadaniami konkursowymi.
Zadania
1. Prostokąt 7×4 z usuniętym narożnym polem (rys. 13) należy podzielić na 7 części, z których tylko dwie będą prostokątami elementarnymi (2×3), a pozostałe L-triminami, nigdzie nietworzącymi prostokąta 2×3. W rozwiązaniu wystarczy podać, ile rozwiązań ma to zadanie.
2. Ile najmniej L-trimin można położyć na szachownicy 8×8 (każde zakrywa dokładnie 3 pola) tak, aby umieszczenie na pozostałych wolnych polach jeszcze jednego L-trimina nie było możliwe.
3. Kwadrat 7×7 z niedostępnym (usuniętym) ciemnym polem (rys. 14), czyli w sumie 48 pól, należy podzielić na 10 części – sześć prostokątów elementarnych (2×3) i cztery L-trimina. W rozwiązaniu wystarczy podać, ile części przecinają ukośne żółte linie.
4. Które dwa sąsiednie pola (domino 1×2) należy usunąć z ciemnej części prostokąta 7×5 (rys. 15), aby 33 pozostałych pól nie udało się pokryć 11 L-triminami. Należy znaleźć wszystkie rozwiązania, czyli wszystkie takie pary pól, a jako końcowe rozwiązane wystarczy podać, ile ich jest (dwie pary są oczywiste: a,b-2 i b-1,2).
Rozwiązania prosimy nadsyłać do 30 września br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG 09/20. Spośród autorów poprawnych rozwiązań przynajmniej trzech zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Tima Jamesa Fundamentalnie. Tak fizyka kwantowa i fizyka cząstek elementarnych wyjaśnia wszystko (oprócz grawitacji) 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 lipcowego
1. Trzema najmniejszymi liczbami 5-cyfrowymi złożonymi z różnych cyfr i takimi, że w rozkładzie każdej na czynniki pierwsze nie ma cyfr takich samych, jak w rozkładanej liczbie, są: 10548=22×32×293, 10584=23×33×72, 10596=22×3×883.
2. Rozszyfrowane mnożenie: 73225×13=951925; iloczyny cząstkowe: LICZBA=219675, BELLA=73225.
3. Nieskończenie wiele kwadratów o wzorcu literowym AnBmC, gdzie n i m oznaczają dowolną liczbę kolejnych liter A i B, istnieje dla cyfr A, B, C równych: 1, 5, 6, bo 1n+15n6=(3n4)2 lub 1, 2, 5, bo 1n2n+15=(3n5)2 lub 2, 4, 5, bo 4n2n+15=(6n5)2 lub 4, 8, 9, bo 4n+18n9=(6n7)2.
Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Michaela J. Bentona Dinozaury odkryte na nowo. Jak rewolucja naukowa rewiduje historię, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Marcin Chomenko z Gdańska, Łukasz Górski z Torunia, Mariusz Myszkier ze Szczecina, Wadym Rokicki z Sulejówka, Rafał Zorychta z Kończyc.