Płytki ojca Trucheta, czyli kombinacje parkietażowe
Kwadrat można podzielić przekątną na dwa sposoby. Dwa, ponieważ zakładamy, że symetria „nie działa”, więc mimo że figury pokrywają się po obrocie, uznajemy je za różne. Przy takim założeniu w każdym podzielonym kwadracie zaczerniamy jeden z dwu utworzonych trójkątów prostokątnych – sposoby zaczernienia dla danego podziału także są dwa. W rezultacie powstają cztery różne biało-czarne figury (rys. 1), które mogłyby być płaskimi klockami – na przykład częściami prostej dziecięcej układanki, zawierającej kilkanaście takich elementów (dla ich użytkownika oczywiście jednakowych).
W roku 1704 w annałach francuskiej Królewskiej Akademii Nauk ukazał się artykuł o kwartecie z rys. 1. Umieszczony w publikacji jako ostatni był swego rodzaju rozrywkowym dodatkiem, bowiem uzupełniały go obficie miłe dla oka parkietaże z czarno-białych kwadratów (jeden z nich na rys. 2). Tytuł – Mémoire sur le combinaisons, czyli Rozprawa o kombinacjach – sugerował jednak nieco szerszy matematyczny kontekst. Autor, wielebny Sébastien Truchet, francuski dominikanin, wyjaśniał we wstępie, że zainspirowały go ceramiczne płytki przeznaczone do układania posadzki w jednej z kaplic. Główną specjalnością Trucheta, oczywiście poza duszpasterstwem, była hydrotechnika (Ludwik XIV zlecał mu projektowanie kanałów), ale znany był także jako typograf, wynalazca, zegarmistrz i matematyk-amator. Parkietaże z artykułu Trucheta trafiły później do kilku XVIII-wiecznych publikacji, m.in. do słynnej Wielkiej encyklopedii francuskiej współredagowanej przez Diderota, w której rysunkom towarzyszyły pochodzące z artykułu źródłowego proste rozważania kombinatoryczne, a cztery figury z rys. 1 nazwano płytkami Trucheta. Potem artykuł dominikanina na ponad dwa wieki poszedł w niepamięć. Przypomniany został dopiero w roku 1987 na łamach wydawanego przez Massachusetts Institute of Technology magazynu „Leonardo”, poświęconego zastosowaniom nauki i techniki w sztuce.
Tytułowe kombinacje Trucheta ograniczają się do najprostszych, a ściślej do odpowiedzi na pytanie: ile różnych wzorów powstanie, jeśli łączyć bokami dwie płytki? W tym celu najpierw do jednej płytki (np. A) Truchet dokładał drugą płytkę A z lewej strony, potem z prawej, z góry i z dołu – tworząc cztery 2-płytkowe wzory. Następnie w ten sam sposób czterokrotnie umieszczał obok A płytkę B, potem C i na końcu D. Efektem było 16 układów dwóch płytek (rys. 3). Cały ten cykl powtarzany był czterokrotnie – z otaczaniem każdorazowo innej płytki czterema różnymi, co w sumie zaowocowało 64 wzorami. Dopiero wtedy Truchet zaczął eliminację. Najpierw usuwał wzory, które były wiernymi kopiami innych, a potem kopie obrócone o 90 lub 180°. Pozostało 10 wzorów (rys. 4), w tym 8 tworzących 4 pary lustrzane – całą tę ósemkę wypada uznać za różne układy, ponieważ nie można ich odwracać, skoro płytki są jednostronne. W przeciwnym wypadku z rys. 4 należałoby usunąć 4 wzory będące odbiciami lustrzanymi innych, czyli wszystkich pozostałoby 6.
Dalszy ciąg artykułu Trucheta dotyczy różnych parkietaży i ma charakter głównie „obrazkowy”; poprzedzony jest jednak wzmianką, że autor zaczął analizować i liczyć różne wzory z trzech, czterech i pięciu płytek, ale temat ten postanowił odłożyć do następnego artykułu. Niestety, ciąg dalszy nigdy nie nastąpił.
Analiza Trucheta układów 2-płytkowych jest nietypowa – mało matematyczna i rozwlekła. Jeśli w taki sam sposób autor zabierał się do 3-płytkowych i większych, to trudno się dziwić, że kontynuacja tematu kombinacji nie doszła do skutku. Zamiast mozolnie i siermiężnie szukać różnych wzorów z dwóch płytek, wygodniej jest zmierzać do celu, zaczynając od różnych sposobów ułożenia prostokąta 2×1 z dwóch kwadratów z przekątną – na początku bez uwzględniania kolorów. Dla jednostronnych układów sposoby są 3 (rys. 5 u góry). Jeżeli w tych trzech układach zaczernimy na wszystkie możliwe sposoby jeden trójkąt w każdym kwadracie, to powstanie tuzin wzorów, z których wystarczy usunąć dwa bliźniacze, czyli przystające względem dwu innych (obrót o 180° zmienia jedne w drugie), otrzymując zestaw z rys. 4.
Podobnie można poradzić sobie z układami 3-płytkowymi, zaczynając od sześciu różnych prostokątów 3×1 utworzonych z trzech kwadratów z przekątnymi (rys. 5 u dołu), a następnie zaczerniając na różne sposoby po jednym trójkącie w każdym kwadracie. Wśród otrzymanych 48 wzorów będzie 16 par bliźniaczych, co ostatecznie daje 32 różne wzory, jeśli pominąć, oczywiście, odwracanie płytek, czyli odbicia lustrzane.
Zadanie jest prostsze, jeśli interesuje nas tylko liczba różnych wzorów, a nie ich wygląd. Dla dwóch płytek wybranych z czterech (A, B, C, D – rys. 1) wszystkich układów 2-płytkowych, czyli wariacji z powtórzeniami jest 42=16. Zauważmy, że płytka A po obrocie o 180° zmienia się w C, czyli A=C; podobnie B=D. Stąd sześć par wzorów bliźniaczych: AA=CC, AB=DC, AD=BC, BA=CD, BB=DD, CB=DA (rys. 6) – w każdej parze jeden wzór zmienia się w drugi po obrocie o 180°. Po usunięciu z wszystkich 16 układów po jednym układzie z każdej z tych par pozostanie 10 różnych wzorów: AA, AB, AC, AD, BA, BB, BD, CA, CB, DB (rys. 4). Cztery układy oznaczone czerwonymi literami to niezmienniki – przed i po obrocie pozostają takie same.
Dla trzech płytek wszystkich układów jest 43=64. Szukanie wśród nich par bliźniaczych w celu usunięciu po jednym „bliźniaku” z każdej pary jest tym razem trywialne, bo wszystkie układy tworzą takie pary; 3-płytkowych wzorów-niezmienników, nieulegających metamorfozie w wyniku obrotu o 180° – nie ma, ponieważ obrót zawsze powoduje zmianę środkowej płytki. Stąd potwierdzenie, że są 32 różne wzory. Uogólniając: jeśli p jest liczbą nieparzystą, to złożony z p>2 płytek układ w kształcie prostokąta p×1 umożliwia utworzenie 4p/2 różnych wzorów.
W przypadku parzystej liczby płytek sprawa jest nieco bardziej skomplikowana. Dla p=4 można przyjąć, że układ składa się z dwu par płytek – pary Lewej (L) i Prawej (P). Zarówno L, jak i P może być jedną z 16 par 2-płytkowych, co w sumie daje 256 układów 4-płytkowych. Teraz najwygodniej skorzystać z par L i P, które są 2-płytkowymi niezmiennikami w układzie 2-płytkowym (AC, BD, CA, DB), aby znaleźć niezmienniki 4-płytkowe. W każdym z nich płytki A, B, C, D powinny być rozmieszczone względem siebie symetrycznie tak samo, jak w układach 2-płytkowych. Na przykład, korzystając z płytek AC i BD, można utworzyć dwa niezmienniki – ABDC i BACD; z dwu płytek AC także dwa – ACAC i AACC. W sumie powstanie więc 20 niezmienników, a 236 pozostałych to pary bliźniacze. Zatem różnych wzorów będzie 20+236/2=138.
Cztery płytki umożliwiają także utworzenie znacznie trudniejszego do analizy układu kwadratowego 2×2 (przykład na rys. 7a). Liczenie różnych 4-płytkowych wzorów takiego kwadratu warto poprzedzić ogólniejszym, podobnym problemem: na ile sposobów (S) można pokolorować 4 czyste płytki, tworzące kwadrat (rys. 7b), dysponując k kolorami? Kluczem do rozwiązania jest tzw. lemat Burnside’a, który w uproszczonej postaci wyraża się wzorem (tym razem algebraicznym, a nie jak dotąd – geometrycznym deseniem):
gdzie N jest liczbą wszystkich rodzajów permutacji, a ψ(π) liczbą niezmienników w permutacji p. Permutacja jest w tym przypadku działaniem zmieniającym orientację układu w przestrzeni bez zmiany jego wyglądu i położenia (kolory pomijamy). Mówiąc obrazowo, permutacją analizowanego płaskiego układu byłoby wyjęcie go z płaszczyzny, obrócenie o odpowiedni kąt (odwracania jednostronnego układu nie uwzględniamy) i odłożenie z powrotem dokładnie w to samo miejsce. Natomiast niezmienniki, o których była już mowa, są układami, na które określona permutacja nie działa, czyli nie wprowadza w nich żadnych zmian.
Dla kwadratu 2×2 można wyróżnić cztery rodzaje permutacji (N=4):
π1 – osobliwa, ale zawsze obecna permutacja zwana identycznością, która nie zmienia żadnego układu, więc wszystkie sposoby kolorowania kwadratu z rys. 7b są niezmiennikami, czyli ψ(π1)=k4;
π2 – obrót o 90° – tu niezmiennik pojawia się tylko wówczas, gdy wszystkie ćwiartki kwadratu są w tym samym kolorze, czyli ψ(π2)=k;
π3 – obrót o 180° – warunkiem pojawienia się niezmiennika jest jednakowy kolor ćwiartek w przeciwległych rogach; takie przypadki są 2 (przy zliczaniu niezmienników pomijamy obroty), więc ψ(π3)=k2;
π4 – obrót o 270° – sytuacja analogiczna jak przy permutacji π2, zatem ψ(π4)=k.
Po podstawieniu powyższych wartości do ogólnego wzoru na S otrzymamy wzór na liczbę różnych sposobów pokolorowania kwadratu z rys. 7b k kolorami:
Należy pamiętać, że ze względu na jednostronność układu za różne uznajemy także te kolorowania, które są względem siebie odbiciami lustrzanymi. Gdyby uznać je za jednakowe, to należałoby rozpatrzyć jeszcze 4 rodzaje permutacji, uwzględniając 4 osie symetrii kwadratu, a ostateczny wzór przybrałby postać:
Dla k=2 – a tak jest w przypadku płytek Trucheta – S=S’=6. Jeśli jednak uwzględnić specyficzny sposób kolorowania tych płytek, co przekłada się na warunki dotyczące rozmieszczenia kolorów w kwadracie 2×2, to podane wzory należałoby zmienić. W pierwszej chwili cztery rodzaje płytek kojarzą się z czterema kolorami, ale łatwo się zorientować, że takie „przełożenie” także nie działa. Jak sobie z tym poradzić? – oto jest pytanie i pierwsze z poniższych zadań.
Zadania
1. Ile różnych wzorów można ułożyć z czterech płytek Trucheta, tworząc z nich kwadrat 2×2? Aby liczba ta nie była zbyt duża, za jednakowe uznajemy dwa wzory, z których jeden powstaje z drugiego w wyniku dowolnej z poniższych permutacji:
– obrotu,
– lustrzanego odbicia,
– zmiany negatyw–pozytyw (czarne trójkąty stają się białymi, a białe czarnymi).
2. Z płytek Trucheta układamy prostokątną mozaikę o wymiarach m×n płytek. Na ile sposobów można to zrobić przy zachowaniu warunku, aby trójkąty tego samego koloru nigdzie nie stykały się bokami? Dwie mozaiki, z których jedna jest efektem permutacji drugiej (obrót lub odbicie lustrzane) uważamy tym razem za różne.
3. Na niektórych białych polach (rys. 8) należy umieścić płytki Trucheta. Liczba w czarnym polu oznacza, ile czarnych trójkątów musi stykać się przyprostokątną z tym polem. Układ wszystkich płytek powinien być taki, aby pola, które pozostaną białe, tworzyły prostokątne obszary o bokach zorientowanych poziomo, pionowo lub ukośnie pod kątem 45°. W rozwiązaniu wystarczy podać liczbę wszystkich białych kwadratów i prostokątów, które nie są kwadratami. Nad zadaniem znajduje się przykład z rozwiązaniem 7/4 (kwadraty/prostokąty).
Rozwiązania prosimy nadsyłać do 31 sierpnia br. pocztą elektroniczną (redakcja@swiatnauki.pl), wpisując w temacie e-maila hasło UG 08/21. Spośród autorów poprawnych rozwiązań przynajmniej dwóch zadań wyłonimy pięciu zwycięzców i nagrodzimy ich książką Rebekki Wragg Sykes Krewniacy. Życie, miłość, śmierć i sztuka neandertalczyków 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 czerwcowego
1. X=10 100; suma liczb od 1 do 10 100 równa jest 5(10100)50.
2. 42436; kolejne „działania” 42436 (2062) → 4243 → 243 (35) → 43 → 4.
3. Dotarcie zgodnie z podanymi warunkami od 4 do 2021 wymaga 26 etapów: 4 → 2 → 24 → 12 → 6 → 64 → 32 → 16 → 164 → 82 → 824 → 412 → 206 → 2064 → 1032 → 516 → 258 → 2584 → 1292 → 646 → 6464 → 3232 → 1616 → 808 → 8084 → 4042 → 2021.
4. 2347 jest najmniejszą liczbą pierwszą domową (LPD) trzech różnych liczb złożonych pierwotnych (LZP) – 282 (2×3×47), 694 (2×347) i 1081 (23×47).
Za poprawne rozwiązanie przynajmniej dwóch zadań książkę Kwantowa rzeczywistość. W poszukiwaniu prawdziwego znaczenia mechaniki kwantowej Jima Baggotta, ufundowaną przez wydawnictwo Prószyński Media, otrzymują: Mirosław Garnowski z Pasłęka, Tomasz Kosiacki z Łodzi, Andrzej Pokrzywa z Pomiechówka oraz Anna Radzka-Ilczuk i Joanna Wicenty-May z Warszawy.