Kołdra pani P. czyli kwadraty w kwadracie

Podzielić kwadrat na kwadraty – to bardzo proste; wystarczy go odpowiednio pokratkować, np. tak, jak na kartce papieru w kratkę. Równie łatwo spełnić dodatkowy warunek, aby nie wszystkie kwadraty były jednakowe. Jeśli jednak zażądamy, by wszystkie kwadraty różniły się wielkością, to znalezienie podziału okaże się ekstremalnie trudne, praktycznie niemożliwe bez wsparcia komputerowego. Ostatecznie uporał się z tym dopiero w 1978 roku holenderski informatyk A. J. W. Duijvestijn.

Tematy pokrewne i pośrednie, jeśli chodzi o stopień trudności, pojawiają się po przejściu do konkretów, czyli do liczb. Jedna z nich, którą nazwiemy liczbą kwadratodzielną k_d, określa, na ile kwadratów można podzielić kwadrat. Jaka może być jej wartość?

Żaden kwadrat tworzony w trakcie podziału nie może objąć dwóch rogów dzielonego kwadratu, a zatem k_d równe jest co najmniej 4 (rys. 1). W każdym podziale liczbę kwadratów można zwiększyć o 3, dzieląc jeden kwadrat na cztery (zielone linie na rys. 1), więc kwadratodzielne są wszystkie liczby o wzorze 4+3n, gdzie n=0, 1, 2, 3,…. Wystarczyłoby więc pokazać, że jakieś trzy kolejne liczby naturalne są k_d, aby móc stwierdzić, że wszystkie liczby większe od nich także są k_d. Z rys. 2, na którym znajdują się podziały kwadratu na 6, 7 i 8 kwadratów, wynika, że tak właśnie jest dla wszystkich k_d≥6. Pozostaje wyjaśnić, jak rzecz się ma z kwadratodzielnością piątki. Intuicja podpowiada, że taki podział nie jest możliwy, ale wypadałoby tego dowieść.

Załóżmy, że udało się podzielić kwadrat n×n na pięć kwadratów. Boki każdego z nich nie mogą być mniejsze lub równe n/2, bo nie „pokryłyby” wszystkich boków dzielonego kwadratu, a w skrajnym przypadku (wszystkie boki równe n/2) kwadratów byłoby 4, a nie 5. Stąd wniosek, że boki jednego kwadratu (P) są dłuższe niż n/2, a to prowadzi do takiego układu trzech kwadratów, jak na rys. 3. Podział szarego pola X na tym rysunku na dwa kwadraty nie jest oczywiście możliwy, bo kątów wypukłych jest pięć, a każdy kwadrat obejmie tylko dwa, np. dwa niebieskie, ale żaden nie obejmie czerwonego. Wstępne założenie było więc błędne. Wniosek końcowy: kwadrat można podzielić na każdą liczbę kwadratów oprócz 2, 3 i 5.

Większość kwadratodzielnych zagadnień dotyczy kwadratów o konkretnych wymiarach n×n, czyli złożonych z n² kwadracików jednostkowych. Kwadraciki te są niepodzielne, co oznacza, że ich boki wyznaczają linie podziału, które są liniami siatki kwadratowej wypełniającej kwadrat. Jedno z takich zagadnień zostało zapoczątkowane zadaniem zamieszczonym w 1898 roku w dziale rozrywek umysłowych angielskiego tygodnika Weekly Dispatch przez znanego autora zagadek matematycznych Henry’ego Dudeneya.

Pani Perkins ma kwadratową kołdrę pikowaną w 169 kwadratów. Na rys. 4a wszystkie kwadraty są szare; w rzeczywistości jednak są kolorowe, a kolory są tak dobrane, że tworzą kilkanaście jednokolorowych kwadratów. Ile konkretnie, jeśli ich liczba jest najmniejszą z możliwych?

Krótko mówiąc, chodzi o rozcięcie kwadratu 13×13 na minimalną liczbę kwadratów.

Tak w geometrii pojawił się temat nietrywialnego podziału kwadratu n×n na najmniejszą liczbę kwadratów k(n). „Nietrywialnego” oznacza, że długości boków wszystkich kwadratów powstałych w wyniku podziału są względnie pierwsze, czyli ich największym wspólnym dzielnikiem jest 1. Trywialnym byłby więc np. podział kwadratu 6×6 na cztery kwadraty 3×3 lub na sześć kwadratów – jeden 4×4 i pięć 2×2.

W miarę skuteczny sposób na pokolorowanie kołdry pani Perkins i większości innych kwadratowych kołder podobny jest do dowodu na niekwadratodzielność piątki (rys. 3) – czyli zacząć należy od wydzielenia narożnego kwadratu P optymalnej wielkości m×m (m≥n/2), a następnie wypełnienia kwadratami o boku n–m sąsiednich rogów. Po tym zadanie sprowadza się do podzielenia pozostałego pola X na jak najmniej kwadratów. Pierwszy wydzielony kwadrat P będzie największym lub jednym z trzech równych największych w podziale. Gdy długość jego boku jest maksymalna, czyli wynosi n–1, to wszystkie pozostałe kwadraty podziału są jednostkowe, a cały podział obejmuje 2n kwadratów. Wraz ze zmniejszaniem się kwadratu P poszerza się obszar X, więc wydzielać w nim można coraz większe kwadraty, a ich liczba maleje. Dla kołdry pani P. przy kwadracie P 10×10 możliwy jest podział na 13 kwadratów (rys. 4b), a przy 9×9 – na 12 (rys. 4c).

Taki sposób dzielenia nie jest jednak do końca skuteczny, bo nie gwarantuje, że liczba k(n) będzie rzeczywiście minimalna, a wzór, określający zależność k(n) od n, nie jest znany; wiadomo tylko, że log₂n<k(n)<6log₂n, co jest bardzo grubym oszacowaniem. Niestety, lepszy sposób podziału nie istnieje, zaś gwarancję pełnej skuteczności zapewnia tylko wsparcie komputerowe albo benedyktyńska dłubanina. Wydaje się, że autor zadania sprzed 120 lat poświęcił wiele czasu na żmudne zmagania z tym problemem, czyli właściwie wszedł w rolę komputera. Świadczy o tym choćby wybór wielkości kwadratu, bowiem diagram 13×13 jest jedynym większym od 3×3 i mniejszym niż 20×20, którego nietrywialny podział na minimalną liczbę kwadratów – k(13)=11 – ma tylko jedno rozwiązanie (z dokładnością do odbić i obrotów). Do rozwiązania tego dochodzi się, zaczynając od kwadratu P 7×7. Po oznaczeniu sąsiednich kwadratów 6×6 pozostaje podzielić pozostały szary obszar na rys. 5 na 8 kwadratów. Uporanie się z tym zadaniem w czasie poniżej 3 minut to bardzo dobry wynik. Warto spróbować.

Na rys. 6 przedstawione są wszystkie całkiem różne (żaden nie powstaje z innego w wyniku obrotu lub/i odbicia) podziały k(n) dla 4≤n≤7. Nawet w tym ograniczonym zestawie są widoczne niektóre cechy nietrywialnych podziałów. Po pierwsze: wartość k(n) dla dwóch i więcej kolejnych n może pozostawać stała – bywa, że w przypadku dużych kwadratów (duże n) nie zmienia się przez kilkadziesiąt kolejnych n, a czasem nawet maleje. Na przykład, k(40)=16, a k(41)=15. Po drugie: różne podziały nie zawsze różnią się tylko innym rozmieszczeniem takiego samego zestawu kwadratów, jak w przypadku k(4), k(5) i k(7). Podział k(6)=9 jest pierwszym, w którym możliwe są dwa zestawy kwadratów: 3³2¹1⁵ i 4¹2⁴1⁴ (indeks górny oznacza liczbę kwadratów o boku równym liczbie pod indeksem).

Podział kwadratu na kwadraty (pknk), które odtąd będziemy nazywać subkwadratami, może być przedstawiony w postaci grafu, czyli zbioru punktów (wierzchołków) i łączących je linii (krawędzi). Czerwono-niebieski graf na rys. 7a odpowiada pierwszemu podziałowi k(5)=8 na rys. 6. Wierzchołkami są środki subkwadratów, krawędziami – linie łączące wierzchołki w sąsiednich subkwadratach. Czerwone krawędzie łączą subkwadraty sąsiadujące w poziomie, niebieskie – sąsiadujące w pionie. W przypadku tzw. czwórstyku, czyli punktu zetknięcia rogów czterech subkwadratów – np. c, e, f, g na rys. 7a – krawędź można poprowadzić przez czwórstyk dowolnie i również dowolnie oznaczyć kolor; na rys. 7a jest to krawędź niebieska, łącząca wierzchołki c i f. Na zewnątrz kwadratu znajdują się jeszcze 4 wierzchołki (V, X, Y, Z) – każdy umieszczony obok środka boku i połączony ze środkami subkwadratów, przylegających do tego boku. Zauważmy, że graf pozostałby taki sam, gdyby subkwadraty zmienić w prostokąty, odpowiednio „przesuwając” linie podziału – tak, aby nie znikły istniejące sąsiedztwa ani nie pojawiły się nowe. Jeden z takich bliźniaczych podziałów na prostokąty z bliźniaczym grafem znajduje się na rys. 7b. Podział ten różni się od oryginału brakiem czwórstyku, więc narysowanie krawędzi c-f jest jednoznaczne.

Graf podziału kwadratu na prostokąty (pknp) ma wiele cech specyficznych, np.: jest grafem płaskim (krawędzie nie przecinają się); wszystkie ściany wewnętrzne (obszary otoczone krawędziami) są trójkątami, których dwa i tylko dwa boki mają ten sam kolor; stopnie wszystkich wierzchołków wewnętrznych (liczby krawędzi zbiegających się w wierzchołku) równe są co najmniej 4. W związku z tymi cechami grafy pknp można rysować niezależnie od podziałów. Ściślej: dla każdej liczby wierzchołków wewnętrznych n można utworzyć rodzinę grafów pknp. Takie grafy są podstawą szukania pknk, a więc także podziałów k(n), zwykle z wykorzystaniem programu komputerowego. Zadanie sprowadza się do rozwiązania „czerwono-niebieskiego” układu równań, który dla grafu z rys. 7b ma postać:

dla tras czerwonych od X do Y:

L_a+L_b=n

L_a+L_c=n

L_d+L_e+L_c=n

L_d+L_f+L_g+L_h=n

dla tras niebieskich od V do Z:

L_a+L_d=n

L_a+L_e+L_f=n

L_b+L_c+L_f=n

L_b+L_c+L_g=n

L_b+L_c+L_h=n

Litery z indeksami od L_a do L_h oznaczają długości boków subkwadratów, w które powinny zmienić się prostokąty z literami od a do h, aby powstał pknk, a w tym konkretnym przypadku podział k(n). Wygodnie jest przyjąć n=1; wówczas wszystkie niewiadome w układzie równań będą ułamkami zwykłymi zawartymi między 0 a 1, a po pomnożeniu ich przez najmniejszy wspólny mianownik otrzymamy najmniejsze liczby całkowite równe długościom boków subkwadratów podziału k(n). Konkretnie rozwiązaniem powyższego układu równań dla n=1 są wartości L_a=3/5, L_b=L_c=L_d=2/5, L_e=L_f=L_g=L_h=1/5. A zatem graf pknp z rys. 7b prowadzi do pierwszego podziału k(5) z rys. 6. Natomiast szukanie podziału k(n), odpowiadającego grafowi z rys. 9, stanowi temat pierwszego zadania konkursowego. Aby jego rozwiązanie można było podać w zwięzłej formie, warto poznać sposób zapisu podziału kwadratu na subkwadraty – na przykładzie pierwszego podziału k(7)=9 z rys. 6.

Górne boki subkwadratów wyznaczają poziomy; na rys. 8 poziomy są cztery – od p₁ do p₄. Zapis podziału zawiera tyle par nawiasów, ile jest poziomów. Kolejne pary nawiasów dotyczą kolejnych poziomów – każda para obejmuje wielkości boków kolejnych subkwadratów, przylegających górnym bokiem do danego poziomu. Zgodny z tym schematem zapis podziału na rys. 8 podany jest pod rysunkiem.

Zadania

1. Graf pknp na rys. 9 ma 13 punktów wewnętrznych (od a do ł), więc odpowiada podziałowi kwadratu na 13 prostokątów. Prowadzi on także do podziału k(n)=13. Do ustalenia pozostaje wartość n oraz zapis pknk zgodny z opisanym wyżej schematem.

2. W środku kwadratu 16×16 wydzielono kwadrat 6×6 (rys. 10). Zadanie polega na podzieleniu pozostałego obszaru obejmującego 220 kratek na 20 kwadratów tworzących pięć kwartetów: cztery kwadraty 5×5, cztery 4×4, cztery 3×3, cztery 2×2 i cztery 1×1. Podział powinien spełniać dwa warunki:

– rozmieszczenie kwadratów ma tworzyć symetryczny układ (symetria środkowa);

– dwa kwadraty takiej samej wielkości nigdzie nie mogą się stykać, nawet rogami.

3. Nazwiemy prawie-kwadratem prostokąt o wymiarach n×(n+1). Prawie-kwadrat 15×16 na rys. 11 należy podzielić na osiem różnych prawie-kwadratów: 1×2, 2×3, 3×4, 4×5, 5×6, 6×7, 7×8, 8×9; na dobry początek najmniejszy z nich został już wydzielony.

4. Trzy kwadraty można połączyć bokami na dwa sposoby, tworząc dwie figury zwane triminem – prostokąt i sześciokąt (rys. 12a). Takimi figurami należy pokryć kwadrat 6×6 (rys. 12b), używając p trimin prostokątnych i 12-p trimin sześciokątnych. Dla jakich wartości p pokrycie kwadratu nie będzie możliwe?

5. Geometryczny podział kwadratu na trzy kwadraty nie jest możliwy, algebraiczny – tak. W dodawaniu trzech kwadratów (rys. 13), których suma także jest kwadratem, cyfry zastąpiono kratkami. Kratki takiego samego koloru zastępują jednakowe cyfry. W białych kratkach są różne cyfry, ale inne niż w kolorowych. Należy rozszyfrować działanie.

Rozwiązania prosimy nadsyłać do 31 marca br. pocztą elektroniczną (swiatnauki@proszynskimedia.pl), wpisując w temacie e-maila hasło UG 03/18, lub listownie: Świat Nauki, ul. Gintrowskiego 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ą Richarda A. Mullera Teraz. Fizyka czasu ufundowaną przez wydawnictwo Prószyński Media.

***

Rozwiązania zadań z numeru styczniowego

1. Dzielenia: b) 4807:19=253, c) 7362:18=409.

2. Przedostatnią cyfrą w kończącej się ósemką pierwszej z czterech liczb Nivena, będących kolejnymi liczbami naturalnymi, jest 9. Pierwszy taki 4-liczbowy fragment zaczyna się od 60398.

3. Przynajmniej jedna liczba Nivena będzie wśród co najmniej dziewięciu kolejnych liczb parzystych mniejszych od 2018.

4. Sześcioma kolejnymi cyframi, z których można utworzyć liczbę Nivena i sumę jej cyfr są [0,1,2,3,4,5]. Możliwe do utworzenia liczby: 3504, 3540, 5304, 5340; sumą cyfr każdej jest 12.

Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Tullisa C. Onstotta Podziemne życie. W poszukiwaniu ukrytej biosfery Ziemi, Marsa i innych planet ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Piotr Frydrysiak z Łodzi, Paweł Hołownia z Ożarowa Mazowieckiego, Waldemar Karpiński z Ożarowa Mazowieckiego, Robert Krawczyk z Obry, Aleksander Urban 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.