Sto lat kwadratokątów czyli o cięciach doskonałych
Każdą liczbę większą od 128 można zapisać jako partycję co najmniej dwóch różnych kwadratów (partycja lub podział oznacza rozkład liczby na sumę mniejszych liczb całkowitych dodatnich). Nietrudno sprawdzić, że dla 128 jest to niemożliwe, próbując wybrać kilka różnych kwadratów dających tę sumę ze zbioru 11 mniejszych {1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121}. Natomiast na przykład dla 78 da się to zrobić – i to na trzy sposoby: 4+25+49, 1+4+9+64, 1+16+25+36.
Sprawdzenie, że partycja na dwa lub więcej różnych kwadratów każdej liczby większej niż 128 (a także większości mniejszych), jest możliwa, wymaga już na ogół wsparcia komputerowego.
Zauważmy jednak, że każda liczba złożona Z=a×b jest równa polu prostokąta a×b, gdzie a≥b>1. Nie oznacza to oczywiście, że prostokąt a×b o polu równym Z zawsze uda się podzielić na k kwadratów różnej wielkości. Przeciwnie, można powiedzieć, że w tym przypadku geometria radykalnie ogranicza algebrę i jeszcze na początku XX wieku takie rozcięcie – zwane doskonałym – niektórzy uważali za niemożliwe, a nawet próbowali tego (bezskutecznie) dowieść. Wiadomo było tylko od roku 1903, że warunkiem takiego podziału jest współmierność boków prostokąta (warunek konieczny) i wraz z nimi współmierność boków wydzielanych kwadratów. Albo jeszcze inaczej: prostokąt można podzielić na k różnych kwadratów tylko wtedy, gdy da się go podzielić na jednakowe kwadraty.
Zdaniem większości było to wykonalne, a główny problem stanowiła liczba k, która powinna być odpowiednio duża. Łatwo zauważyć, że liczba ta musi być równa co najmniej 6 (4 kwadraty w rogach plus przynajmniej 2 wypełniające „braki”).
Nieco bardziej zawiły jest dowód, że k powinno być większe niż 8. Jednak do lat 20. XX wieku tematem tym nikt się bliżej na poważnie nie interesował; uznawano go za zbyt „rozrywkowy”.
Pierwszy (na świecie) podział prostokąta na 9 różnych kwadratów powstał na przełomie lat 1924/25, czyli dokładnie przed wiekiem, a w druku pojawił się na łamach „Przeglądu Matematyczno-Fizycznego” w roku 1925 (rys. 1). Autorem był Zbigniew Moroń – późniejszy matematyk, a wówczas 20-letni student Uniwersytetu Jana Kazimierza we Lwowie. Interesujący jest sposób, w jaki student Moroń, zainspirowany przez swojego mentora profesora Stanisława Ruziewicza, poradził sobie z problemem.
Była to – co wydaje się zaskakujące – metoda prób i błędów, czyli jakby łamigłówka-układanka, sprowadzająca się do usiłowania dopasowania różnych kwadratów – ale z wykorzystaniem sprytnego sposobu wspartego równaniem. Taktyka polegała na rozpoczęciu od okrężnego ułożenia czterech kwadratów – bok każdego następnego był o jednostkę dłuższy od boku poprzedniego (niebieskie na rys. 1). Takiemu ułożeniu sprzyja pojawienie się między kwadratami dodatkowego jednostkowego kwadratu (żółty), a cały układ można uznać za lewy górny róg prostokąta, który powstanie po uzupełnieniu go czterema czworokątami. Dwa z nich (różowe) są różnymi kwadratami większymi niż niebieskie, a szary jest, niestety, „bliźniakiem” jednego z niebieskich. Na domiar złego zielony prostokąt nie jest kwadratem. Na tym rysunku bok najmniejszego niebieskiego kwadratu jest 3-krotnie dłuższy od jednostkowego. A co się stanie, gdy będzie na przykład 5-krotnie dłuższy?
Zaskakujący efekt tej zmiany widoczny jest na rys. 2 – szary kwadrat stracił bliźniaczość, a zielony zbliżył się kształtem do kwadratu. Intuicja podpowiada, że dalszy wzrost małego niebieskiego kwadratu może prowadzić do wymaganego pełnego „ukwadratowienia”. Jednak zamiast prób rysunkowych wygodnie jest skorzystać z prostego równania opartego na podanych na rys. 2 wymiarach: długość boku żółtego kwadratu równa jest z założenia 1, a x oznacza długość boku małego niebieskiego kwadratu i stanowi podstawę określania długości boków pozostałych czworokątów. Wymiary zielonego czworokąta obliczone są na dwa sposoby – na podstawie sąsiedztwa z różnymi kwadratami. Ponieważ jednak chcemy, aby ten czworokąt także był kwadratem, więc wyniki tych dwu wymiarów powinny być równe, czyli: 3x-3=x+11, a stąd x=7. Ostatecznie otrzymujemy podział prostokąta 32×33 na 9 kwadratów o bokach: 1, 4, 7, 8, 9, 10, 14, 15, 18 (rys. 3), czyli pierwszą z figur, które nazwiemy ogólnie kwadratokątami (prostokąty złożone z różnych kwadratów). Podział ten odpowiada partycji na kwadraty liczby 32×33=1056. Wszystkich partycji tej liczby na 9 kwadratów jest 365, więc unikalność jednej kwadratokątnej stanowi dobitne potwierdzenie wspomnianej wyżej radykalnej „wybredności” geometrii na algebraicznym poletku.
W podobny, ale nieco bardziej złożony sposób Moroń znalazł podział jeszcze jednego prostokąta (47×65), ale tym razem na 10 kwadratów (lewa część rys. 4). Zaproponował też ogólny sposób szukania podziału kwadratu na kwadraty: gdyby udało się dwa identyczne prostokąty a×b podzielić na kwadraty na dwa całkiem różne sposoby (bez „bliźniaków” w obu podziałach razem wziętych i bez kwadratu a×a), to kwadratowy układ z ich udziałem w towarzystwie dwóch większych kwadratów – jak na rys. 5 – byłby oczekiwanym kwadratowym kwadratokątem.
13 lat później niemiecki matematyk Roland Spraque (nawiasem mówiąc, nie całkiem „poważny”, bo zajmujący się głównie matematyką rekreacyjną) zastosował ten sposób, nieznacznie go modyfikując. Wykorzystał też oba kwadratokąty Moronia – po zauważeniu, że wszystkie 19 tworzących je kwadratów jest różnej wielkości – a także ich powiększone kopie. W rezultacie powstał pierwszy kwadratowy kwadratokąt. Była to figura-gigant o boku równym 4205, czyli o powierzchni 17 682 025, złożona z 55 kwadratów – długości ich boków obejmowały zakres od 2 do 2320. Takie znalezisko w epoce przedkomputerowej należy uznać, mimo częściowego „plagiatu”, za owoc pracy ekstremalnie benedyktyńskiej.
W czasie, gdy Spraque zmagał się z kwadratem, tematem zainteresowała się grupa czterech studentów matematyki z Cambridge, działająca i publikująca artykuły pod pseudonimem Blanche Descartes (R. L. Brooks, C. A. B. Smith, A. H. Stone, W. T. Tutte). Po udowodnieniu, że 9 jest najmniejszą liczbą kwadratów, składających się na kwadratokąt (wcześniej udowodnił to Moroń), kwartet z Cambridge odkrył możliwość „przetłumaczenia” problemu na… sieć elektryczną (ściślej, odkrycie przypisano Smithowi), co praktycznie ułatwiało poszukiwanie kwadratokątów. Przykładowy „przekład” większego kwadratokąta Moronia przedstawiony jest na rys. 4 z prawej. Można powiedzieć, że jest to przeniesienie problemu w niższy wymiar: jednowymiarowe odcinki poziome w prostokącie zastąpione są bezwymiarowymi punktami (węzłami sieci), a łączące je jednowymiarowe przewody odpowiadają dwuwymiarowym kwadratom, przylegającym do poziomych odcinków. Natężenia prądów w przewodach, równe są długościom boków kwadratów i są zgodne z prawami Kirchhoffa. Prąd płynący od węzła a (górny bok prostokąta) do węzła g (dolny bok) rozgałęzia się tak, że:
• suma algebraiczna natężeń prądów zbiegających się w każdym węźle równa jest zero (I prawo Kirchhoffa);
• przy obchodzeniu każdego obwodu zamkniętego (oczka) suma natężeń prądów także równa jest zero (wynika to z II prawa Kirchhoffa, gdy opór wszystkich przewodników jest jednostkowy).
Powiązanie trudnego problemu geometrycznego z teorią obwodów umożliwiło zastosowanie prostszej metody poszukiwań: rysowano sieci i z wykorzystaniem układów równań Kirchhoffa obliczano minimalne, wyrażające się liczbami całkowitymi natężenia prądów w przewodach, a następnie rysowano prostokąty. Wprawdzie tylko nielicznym sieciom odpowiadają kwadratokąty, ale stosunkowo łatwa modyfikacja obwodów – zmiana kierunku prądów, położenia węzłów, dodawanie nowych węzłów i przewodów – powoduje, że osiąganie doskonałości nie jest zbyt skomplikowane. Grupa z Cambridge wykryła wszystkie kwadratokąty rzędu do 12. włącznie i niektóre wyższych rzędów (rzędem jest wspomniana na początku liczba kwadratów k). Uwzględniano oczywiście tylko kwadratokąty właściwe i proste. Właściwy to taki, którego częścią nie jest mniejszy kwadratokąt, a prosty oznacza, że długości boków wszystkich kwadratów w prostokącie są liczbami względnie pierwszymi, czyli nie mają wspólnego dzielnika.
Okazało się, że kwadratokąty najmniejszego rzędu (k=9) są tylko dwa. Ułożonemu przez Moronia towarzyszy okaz prawie dokładnie czterokrotnie większy, o wymiarach 61×69 (na rys. 6 w „skrótowej” formie). Kwadratokątów 10. rzędu, czyli takich, jak drugie dziełko Moronia, jest już 6, 11. rzędu – 22, a 12. – 67.
Niektóre kwadratokąty rozcinano i układanie ich proponowano miłośnikom łamania głowy, spodziewając się ciekawych komentarzy. Skądinąd bowiem wiadomo, że nierzadko osoby postronne, niebędące specjalistami w danej dziedzinie, miewają odkrywcze uwagi lub pomysły. Przypadek sprawił, że doszło do zaskakującej sytuacji. Jedna z osób otrzymała do ułożenia prostokąt pocięty na 13 kwadratów. Po długich zmaganiach udało jej się uporać z zadaniem, ale choć ułożony kwadratokąt miał takie same wymiary, jak oryginał (75×112; kwadraty o bokach: 3, 5, 9, 11, 14, 19, 20, 24, 31, 33, 36, 39, 42 – gdyby ktoś miał ochotę zmierzyć się z tą układanką), to kwadraty były w nim rozmieszczone inaczej – choć nie całkiem inaczej. To była niemal sensacja. Przeanalizowano sieci przewodów, odpowiadające obu kwadratokątom. Wnioski okazały się kluczem do poszukiwań kwadratowego kwadratokąta (KK). Skorzystano także z metody Moronia (rys. 5), ale nieco zmodyfikowanej. Studenci znaleźli dwa kwadratokąty o identycznych wymiarach, składające się z różnych kwadratów – poza jednym, narożnym. Po nałożeniu ich na siebie tak, aby narożne kwadraty się pokryły i uzupełnieniu układu dwoma kwadratami (rys. 7) przyszedł na świat drugi KK – 39. rzędu, czyli mniejszego niż Spraque’a, ale o większym boku, równym 4639.
Od tej chwili rozpoczęło się polowanie na najmniejszy KK. Pierwszym trofeum był okaz 24. rzędu o boku 175 ustrzelony w 1951 roku przez angielskiego matematyka T. Willcocksa. Nie był on jednak właściwy – podobnie jak poprzednie KK Spraque’a i grupy Blanche Descartes – zawierał bowiem wewnątrz mniejszy kwadratokąt. Willcocks udowodnił jednak kluczową hipotezę: nie istnieje KK mniejszego rzędu niż 21.
Dalszych badań i poszukiwań podjęło się pod koniec lat 50. kilku młodych informatyków holenderskich – głównie C. J. Bouwkamp i A. J. Duijvestijn z Politechniki w Eindhoven. Dzięki zastosowaniu maszyn cyfrowych eksploracja była prostsza, ale nie w takim stopniu, jak się spodziewano. Okazało się bowiem, że wraz ze wzrostem rzędu KK, których szukanie powierzano komputerom, program bardzo się komplikuje. Dopiero po niemal 20 latach Duijvestijn poradził sobie z programem, z którym z kolei poradził sobie komputer. Rezultat był olśniewający – prosty, właściwy i jak potem ustalono jedyny KK 21. rzędu o boku równym 112 (rys. 8).
Wszystko, co działo się potem, można określić jako testowanie umiejętności programistów oraz mocy obliczeniowej komputerów w procesie wyszukiwania prostych, właściwych KK wyższych rzędów. Do dziś znaleziono wszystkie takie okazy do 37. rzędu włącznie. Jest ich blisko… 28 mln – od jedynaka 21. rzędu do ponad 17 mln KK 37. rzędu.
Kwadratokąty są jednym z wielu przykładów łamigłówek-układanek, które ewoluowały jak życie na Ziemi – od nielicznych form prostych adresowanych głównie do amatorów główkowania do wielu złożonych, interesujących matematyków i programistów. Podkreśleniem rangi, jaką po latach uzyskały, jest zamieszczony powyżej znaczek pocztowy z kwadratokątem 177×176 11. rzędu (kwadraty: 99, 78, 77, 57, 43, 41, 34, 25, 21, 16, 9) emitowany w 1998 roku z okazji 23. Międzynarodowego Kongresu Matematyków w Berlinie.
Zadania
1. 11 kolejnych liczb całkowitych dodatnich nie może być długościami boków kwadratów tworzących kwadratokąt. Suma kwadratów tych liczb jest jednak zawsze liczbą złożoną, więc może być polem powierzchni prostokąta. Może być także polem powierzchni kwadratu – jaka będzie wówczas najmniejsza z tych 11 liczb?
2. Diagram (rys. 9) należy podzielić wzdłuż przerywanych linii na prostokąty. Każdy powinien obejmować jedną i tylko jedną liczbę i tyle kratek, jaka jest wartość tej liczby. Znaki zapytania zastępują kwadraty, ale nie każdy prostokąt z kwadratem musi być kwadratem. Jako rozwiązanie wystarczy podać sumę liczb w prostokątach niedotykających brzegu diagramu. Rozwiązaniem przykładu, znajdującego się nad diagramem, byłaby więc tylko liczba 6.
3. Diagram (rys. 10) należy podzielić wzdłuż przerywanych linii na prostokąty. Niektóre fragmenty linii dzielących są już oznaczone. Pozostałe należy poprowadzić tak, aby żadne dwa sąsiednie prostokąty nie tworzyły jednego większego prostokąta. Jako rozwiązanie wystarczy wskazać miejsca prostokątów, które po podziale będą kwadratami – całych kwadratów 1×1 lub lewych narożnych pól większych kwadratów. Rozwiązaniem przykładu (nad diagramem) byłyby pola b3 i c3.
Rozwiązania prosimy nadsyłać do 30 listopada 2024 roku pocztą elektroniczną (redakcja@swiatnauki.pl), wpisując w temacie e-maila hasło UG 11/24. Spośród autorów poprawnych rozwiązań przynajmniej trzech zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Biologia. Opowieść o życiu Lindsay Turnbull ufundowaną przez wydawnictwo REBIS. 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. Liczba zaczernionych kratek na przekątnych diagramu – 8.
2. Suma liczb na przekątnych diagramu – 31.
3. Liczba zaczernionych kratek na przekątnych diagramu – 13.
4. Na diagramie 7×7 można umieścić w środkach kratek maksymalnie 21 znaczników tak, aby żadne cztery nie wyznaczały wierzchołków prostokąta o bokach równoległych do boków diagramu. Przykładowe rozwiązanie na rys. 11.
Za poprawne rozwiązanie zadań książkę Lesa Johsona Przewodnik podróżnika po gwiazdach ufundowaną przez PWN otrzymują: Zbigniew Kapusta z Banina, Waldemar Karpiński z Nowego Miasta Lubawskiego, Daniel Kłobuszewski z Warszawy, Rafał Zorychta z Janowic i Andrzej Żołyński z Zielonej Góry.
***
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”.