Afiliacja: Wydział Nauk Ścisłych i Przyrodniczych, Uniwersytet Pedagogiczny w Krakowie
Drogi Czytelniku, spróbuj wskazać jakieś nieprzeciętne cechy poniższych dwóch układów liczb, wpisanych w tablice o wymiarach \(5\times 5.\) \[\renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 3 & 4 & 5\\ \hline 2 & 3 & 4 & 5 & 1\\ \hline 3 & 4 & 5 & 1 & 2\\ \hline 4 & 5 & 1 & 2 & 3\\ \hline 5 & 1 & 2 & 3 & 4\\ \hline \end{array}\ \ \ \renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|c|} \hline 1 & 4 & 2 & 5 & 3\\ \hline 2 & 5 & 3 & 1 & 4\\ \hline 3 & 1 & 4 & 2 & 5\\ \hline 4 & 2 & 5 & 3 & 1\\ \hline 5 & 3 & 1 & 4 & 2\\ \hline \end{array}\] W obu przypadkach umieszczono liczby od 1 do 5, każda pojawia się pięciokrotnie – ciężko to jednak uznać za ,,nieprzeciętne cechy”. Istotniejsze jest to, że w każdym wierszu i każdej kolumnie pojawia się pełen zestaw liczb od 1 do 5. Dzięki temu oba układy zasługują na miano kwadratów łacińskich. Najistotniejszym zaś jest dla nas to, co ukazuje się naszym oczom po sparowaniu liczb stojących w odpowiednich polach tych tablic. \[\renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|c|} \hline (1,1) & (2,4) & (3,2) & (4,5) & (5,3)\\ \hline (2,2) & (3,5) & (4,3) & (5,1) & (1,4)\\ \hline (3,3) & (4,1) & (5,4) & (1,2) & (2,5)\\ \hline (4,4) & (5,2) & (1,5) & (2,3) & (3,1)\\ \hline (5,5) & (1,3) & (2,1) & (3,4) & (4,2)\\ \hline \end{array}\] Okazuje się, że otrzymany kwadrat ma niezwykłą cechę – w każdym polu znajduje się unikalna para \((x,y),\) gdzie \(x\) oraz \(y\) są liczbami z zakresu od \(1\) do \(5.\) W takiej sytuacji mówimy, że dwa kwadraty łacińskie są wzajemnie ortogonalne (krótko: ortogonalne), a połączony z nich kwadrat nazywamy kwadratem grecko-łacińskim.
Historia badania kwadratów grecko-łacińskich sięga Leonharda Eulera. Jeśli wierzyć przekazom, w drugiej połowie XVIII wieku caryca Katarzyna Wielka przesłała uczonemu następujący problem, zwany współcześnie problemem \(36\) oficerów:
Jako łamigłówka kwadraty grecko-łacińskie pojawiły się nawet wcześniej. W 1725 roku Jacques Ozanam zaproponował następujący problem: ułożyć wszystkie karty wszystkich kolorów od waleta do asa w kwadrat tak, aby w każdym rzędzie i w każdej kolumnie obecny był każdy kolor i każda wartość karty. Poniżej jedno z rozwiązań: \[\renewcommand{\arraystretch}{1.2}\begin{array}{cccc} A\spadesuit &\textcolor{red}{ K\heartsuit} & Q\textcolor{red}{ \diamondsuit }& J\clubsuit\\ Q\clubsuit & \textcolor{red}{ J\diamondsuit }& \textcolor{red}{ A\heartsuit }& K\spadesuit\\ \textcolor{red}{ J\heartsuit} & Q\spadesuit & K\clubsuit & \textcolor{red}{ A\diamondsuit}\\ \textcolor{red}{ K\diamondsuit} & A\clubsuit & J\spadesuit & \textcolor{red}{ Q\heartsuit} \end{array}\]
Ustawić \(36\) oficerów z \(6\) różnych pułków tak, aby stali w kwadracie, i tak, aby w każdej linii (zarówno poziomej, jak i pionowej) było \(6\) oficerów różnych stopni i różnych pułków.
Innymi słowy, caryca poprosiła Eulera o skonstruowanie kwadratu grecko-łacińskiego o wymiarach \(6\times 6.\) Uczony nie potrafił rozwiązać tego problemu, ale udało mu się odkryć ogólną metodę konstrukcji kwadratów grecko-łacińskich rzędu \(n,\) gdy \(n\) jest nieparzyste lub jest podzielne przez \(4.\) W swoich rozumowaniach do oznaczania elementów z pierwszego kwadratu Euler używał liter alfabetu łacińskiego, a do drugiego – greckiego, i podobno stąd wzięła się nazwa kwadrat grecko-łaciński.
Euler postawił również hipotezę, że jeśli \(n=4k+2,\) to kwadrat takiego rzędu nie istnieje, co łatwo uzasadnić dla \(k=0.\) Przypadek \(k=2,\) czyli problem 36 oficerów, czekał na rozwiązanie aż do początku XX wieku, kiedy to Gaston Tarry udowodnił, że faktycznie problem ten nie ma rozwiązania [1]. W pełnej ogólności hipoteza Eulera czekała jeszcze pół wieku, zanim została całkowicie rozstrzygnięta. W \(1959\) roku trójka matematyków – Raj Bose, Ernest Parker i Sharadchandra Shrikhande – wykazała, że hipoteza Eulera jest fałszywa dla wszystkich \(k\geq 3\) [2].
O historii problemu 36 oficerów można było też przeczytać niedawno w Delcie, w artykułach 36 splątanych oficerów (\(\Delta^{3}_{23}\)) oraz 37 lat później (\(\Delta^{12}_{23}\)).
Współcześnie wiemy już zatem, że dla \(n\notin\{1,2,6\}\) istnieją dwa wzajemnie ortogonalne kwadraty łacińskie rzędu \(n.\) A czy może ich być więcej? Jak najbardziej – spójrzmy od razu na przykład \(4\) wzajemnie ortogonalnych kwadratów łacińskich piątego rzędu. \[\renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|c|} \hline (1,1,1,1)&(2,2,2,2)&(3,3,3,3)&(4,4,4,4)&(5,5,5,5)\\ \hline(2,3,5,4)&(3,4,1,5)&(4,5,2,1)&(5,1,3,2)&(1,2,4,3)\\ \hline(3,5,4,2)&(4,1,5,3)&(5,2,1,4)&(1,3,2,5)&(2,4,3,1)\\ \hline(4,2,3,5)&(5,3,4,1)&(1,4,5,2)&(2,5,1,3)&(3,1,2,4)\\ \hline(5,4,2,3)&(1,5,3,4)&(2,1,4,5)&(3,2,5,1)&(4,3,1,2)\\ \hline \end{array}\] W podanej tabeli dowolnie wybrane dwie spośród \(4\) współrzędnych (wybieramy takie same współrzędne z każdej czwórki liczb) tworzą nowy kwadrat, który jest klasycznym kwadratem grecko-łacińskim. Okazuje się, że piątego kwadratu łacińskiego już nie znajdziemy, gdyż zachodzi następujące
Ciekawą realizacją podanego układu kwadratów łacińskich rzędu 5 może być tablica pięciu różnych słów zapisanych pięcioma różnymi krojami pisma w pięciu różnych kolorach, każde słowo umieszczone na tle jednego z pięciu różnych kolorów
Twierdzenie. Istnieje co najwyżej \(n-1\) wzajemnie ortogonalnych kwadratów łacińskich rzędu \(n.\)
Dowód. Zauważmy najpierw, że wzajemna ortogonalność jest zachowana przez permutacje (tzn. przenumerowania) liczb w dowolnym kwadracie. Korzystając z tego spostrzeżenia, możemy bez straty ogólności założyć, że w każdym kwadracie pierwszy wiersz jest postaci \(1,\ldots, n.\) Zauważmy, że w każdym z kwadratów na drugim miejscu pierwszej kolumny znajduje się liczba większa od 1 (gdyż są to kwadraty łacińskie). Ponadto muszą to być różne liczby, inaczej zaprzeczylibyśmy wzajemnej ortogonalności. Istotnie, gdyby w pewnych dwóch kwadratach w tym miejscu znajdowała się ta sama liczba \(a,\) to w połączeniu tych kwadratów dostalibyśmy w tym miejscu parę \((a,a),\) która pojawiła się już w pierwszym wierszu. Te dwie obserwacje dowodzą, że wzajemnie ortogonalnych kwadratów może być co najwyżej \(n-1.\)◻
Niech teraz \(n\) będzie liczbą pierwszą.
Skonstruujemy \(n-1\) wzajemnie ortogonalnych kwadratów łacińskich rzędu \(n\): niech element stojący w \(i\)-tym wierszu \(j\)-tej kolumny \(r\)-tego kwadratu (oznaczanego jako \(L_r\)) będzie równy \(L_r(i,j)=(i+rj)\mod n,\) przy czym \(i,j,r\in\mathbb{Z}_n\) oraz \(r\neq 0.\) Dla przykładu, jeśli przyjmiemy \(n=5,\) otrzymamy poniższe kwadraty łacińskie. \[\renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|c|} \hline0&1&2&3&4\\ \hline1&2&3&4&0\\ \hline2&3&4&0&1\\ \hline3&4&0&1&2\\ \hline4&0&1&2&3\\ \hline\end{array} \ \ \ \renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|c|} \hline0&2&4&1&3\\ \hline1&3&0&2&4\\ \hline2&4&1&3&0\\ \hline3&0&2&4&1\\ \hline4&1&3&0&2\\ \hline\end{array} \ \ \ \renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|c|} \hline0&3&1&4&2\\ \hline1&4&2&0&3\\ \hline2&0&3&1&4\\ \hline3&1&4&2&0\\ \hline4&2&0&3&1\\ \hline\end{array} \ \ \ \renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|c|c|} \hline0&4&3&2&1\\ \hline1&0&4&3&2\\ \hline2&1&0&4&3\\ \hline3&2&1&0&4\\ \hline4&3&2&1&0\\ \hline\end{array}\] Okazuje się, że tak skonstruowane kwadraty są wzajemnie ortogonalne! Załóżmy bowiem, że kwadraty \(L_{r_1}\) oraz \(L_{r_2}\) (\(r_1\neq r_2\)) nie są ortogonalne, tzn. po połączeniu na pewnych dwóch różnych miejscach: \((i_1,j_1)\) oraz \((i_2,j_2),\) mają tę samą wartość. Oznacza to, że \[\begin{split} i_1+r_1 j_1 &\equiv i_2+r_1 j_2 \pmod{n},\\ i_1+r_2 j_1 &\equiv i_2+r_2 j_2 \pmod{n}. \end{split}\] Po odjęciu tych kongruencji stronami uzyskamy \((r_1-r_2)j_1\equiv (r_1-r_2)j_2,\) a zatem \(n \mid (r_1-r_2)(j_1-j_2).\) Skoro \(r_1\neq r_2\) oraz \(n\) jest liczbą pierwszą, dostajemy \(n\mid (j_1-j_2),\) czyli \(j_1\equiv j_2\pmod{n},\) a stąd i z pierwszej równości wyżej dostajemy \(i_1\equiv i_2\pmod{n},\) co przeczy założeniu, że \((i_1,j_1)\) oraz \((i_2,j_2)\) były różnymi miejscami.
Operacja modulo \(n\) to rozważenie reszty z dzielenia liczby \(k\) przez liczbę \(n,\) co zapisujemy \(k\ {\rm mod}\ n.\) Takie reszty tworzą zbiór \(\{0,\ldots,n-1\}\) oznaczany przez \(\mathbb{Z}_n.\) W takim zbiorze można rozważyć operacje dodawania oraz mnożenia modulo. Jeśli \(a, b\in\mathbb{Z}_n,\) wynikiem \(a+b\) w tym zbiorze jest wykonanie działania \((a+b)\mod n.\) Analogicznie definiuje się mnożenie. Tym samym, jeśli na przykład \(n=7,\) \(a=3\) i \(b=6,\) to \(a+b=2\) oraz \(a\cdot b=4.\)
Dowód tego, że konstrukcja daje kwadraty łacińskie, jest bardzo podobny do przedstawionego dowodu wzajemnej ortogonalności (oraz jest prostszy), pozostawiamy go zatem jako ćwiczenie.
Spróbujmy wyabstrahować te własności zbioru reszt z dzielenia przez \(n,\) które pozwoliły nam przeprowadzić powyższą konstrukcję. Na tych resztach wykonywaliśmy działania dodawania, odejmowania i mnożenia. Ponadto – w sposób niejawny – dokonywaliśmy dzielenia, kiedy z równości \((r_1-r_2)j_1\equiv (r_1-r_2)j_2\) wnioskowaliśmy \(j_1\equiv j_2,\) i tu istotne było założenie o pierwszości \(n.\) Strukturę, w której te operacje zachowują się tak, jak jesteśmy do tego przyzwyczajeni, nazywamy ciałem. W 1893 roku Eliakim Moore udowodnił, że na skończonym zbiorze można wprowadzić strukturę ciała wtedy i tylko wtedy, gdy liczba jego elementów jest potęgą liczby pierwszej – i w takim wypadku wiadomo, jak taką strukturę wprowadzić. Oznacza to, że dla \(n\) będących potęgą liczby pierwszej potrafimy w analogiczny do powyższego sposób skonstruować \(n-1\) wzajemnie ortogonalnych kwadratów rzędu \(n\) oraz, że dla \(n\) niebędących potęgą liczby pierwszej ta konstrukcja nie działa. Nie oznacza to oczywiście, że nie ma innego sposobu…ale takiego matematycy nie znają. A bardzo chcieliby poznać (lub udowodnić, że go nie ma), gdyż pozornie niewinne ,,pełne” układy wzajemnie ortogonalnych kwadratów łacińskich to tak naprawdę inne oblicze obiektu bardzo w matematyce zakorzenionego – skończonej płaszczyzny rzutowej. Wyjaśnieniu tego związku poświęcona będzie dalsza część artykułu.
Skończona płaszczyzna rzutowa to zbiór \(X\) wraz z niepustym zbiorem \(L\) złożonym z podzbiorów \(X\) (elementy \(L\) nazywamy prostymi, a elementy \(X\) punktami) o następujących własnościach, naśladujących zależności między ,,klasycznymi” prostymi i punktami na płaszczyźnie:
O prostych i punktach w podobnym, abstrakcyjnym ujęciu pisał również Bartłomiej Bzdęga w \(\Delta^{6}_{24}.\)
dla każdej pary różnych punktów istnieje dokładnie jedna prosta zawierająca oba punkty,
przecięcie (tzn. część wspólna) dwóch różnych prostych zawiera dokładnie jeden punkt,
istnieje taki zbiór \(4\) punktów, że żadne \(3\) spośród nich nie należą do jednej prostej.
Mówimy ponadto, że płaszczyzna rzutowa jest rzędu \(n,\) jeśli do każdej prostej należy dokładnie \(n+1\) punktów. Można uzasadnić, że wtedy istnieje dokładnie \(n^2+n+1\) punktów oraz tyle samo prostych.
Najprostszym przykładem realizującym powyższe aksjomaty jest tak zwana płaszczyzna Fano – jest to układ \(7\) punktów oraz \(7\) prostych, tworzących płaszczyznę rzędu \(2.\) Wizualizacja płaszczyzny Fano została umieszczona na marginesie. Podkreślmy, że w takiej wizualizacji proste (elementy zbioru \(L\)) nie muszą być proste (w sensie geometrii euklidesowej) – w tym przypadku prosta będąca zbiorem środków boków narysowanego trójkąta równobocznego jest oznaczona jako okrąg (pozostałe sześć prostych to odcinki).
Płaszczyzna rzutowa rzędu 2 (płaszczyzna Fano)
Pokażemy teraz, jak z płaszczyzny rzutowej rzędu \(n\) uzyskać \(n-1\) wzajemnie ortogonalnych kwadratów łacińskich rzędu \(n.\) Zrobimy to na przykładzie \({n=3},\) ogólna sytuacja nie różni się istotnie.
Rozpocznijmy od (wcale nietrywialnego) narysowania tej płaszczyzny rzutowej. Na marginesie przedstawionych zostało \(13\) punktów w takim układzie, w którym do jednej prostej należą dokładnie \(4\) punkty i odwrotnie – każdy punkt należy dokładnie do \(4\) prostych. Symbolami zaznaczone zostały \(4\) punkty, z których żadne \(3\) nie leżą na jednej prostej. Taki układ punktów i prostych przeniesiemy teraz na konstrukcję kwadratów łacińskich.
Płaszczyzna rzutowa rzędu 3
Ustalmy dowolnie dwa punkty \(X\) i \(Y\) (oznaczenia jak na rysunku). Niech \(\ell\) będzie prostą, do której należą punkty \(X\) i \(Y\) (jest to prosta oznaczona przez podwójną linię ). Oznaczmy pozostałe punkty tej prostej przez \(Q_k\) (\(k\leq 2\)). Następnie liczbami od 1 do 3 numerujemy wszystkie proste zawierające \(X\) i różne od \(\ell\); podobnie postępujemy dla punktu \(Y.\) Każdy punkt nieleżący na prostej \(\ell\) jest wspólny dla dokładnie jednej pary ponumerowanych przed chwilą prostych. Niech \(P_{ij}\) będzie punktem wspólnym dla \(i\)-tej prostej zawierającej punkt \(X\) i \(j\)-tej prostej zawierającej punkt \(Y.\)
Dla każdego punktu \(Q_k\) (\(k\leq 2\)) etykietujemy proste różne od \(\ell,\) zawierające te punkty etykietami \(A,\) \(B\) i \(C.\) Wówczas każdy punkt \(P_{ij}\) leży na prostych o różnych etykietach. Konstruujemy teraz dwa kwadraty łacińskie w następujący sposób:
W \(i\)-tym wierszu i \(j\)-tej kolumnie \(k\)-tego kwadratu łacińskiego umieszczamy etykietę prostej łączącej \(P_{ij}\) z \(Q_k.\)
Zgodnie z tym algorytmem otrzymujemy poniższe kwadraty łacińskie i odpowiadający im kwadrat grecko-łaciński. \[\renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|} \hline B~& C~& A\\ \hline A~& B~& C\\ \hline C~& A~& B\\ \hline \end{array}\ \ \ \renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|} \hline C~& A~& B\\ \hline A~& B~& C\\ \hline B~& C~& A\\ \hline \end{array}\ \ \ \ \ \ \renewcommand{\arraystretch}{1.2}\begin{array}{|c|c|c|} \hline (B,C) & (C,A) & (A,B)\\ \hline (A,A) & (B,B) & (C,C)\\ \hline (C,B) & (A,C) & (B,A)\\ \hline \end{array}\] Dlaczego w ogólności otrzymane kwadraty są łacińskie? Przypuśćmy, że \(k\)-ty kwadrat taki nie jest i dla ustalenia uwagi przyjmijmy, że w \(i\)-tym wierszu powtarza się w nim pewna litera. Oznaczałoby to, że prosta z \(Q_k\) oznaczona tą literą ma dwa punkty wspólne z \(i\)-tą prostą z \(X.\) Te proste musiałyby być zatem równe, a to jest sprzeczność.
Gdyby zaś kwadraty o numerach \(k\) i \(k'\) nie tworzyły kwadratu grecko-łacińskiego, to pewne dwie proste z punktów \(Q_k\) i \(Q_{ k' }\) musiałyby przecinać się w dwóch różnych punktach \(P_{ij},\) i to też jest sprzeczność.
Co jest również ważne, algorytm można odwrócić i zamienić \(n-1\) wzajemnie ortogonalnych kwadratów łacińskich rzędu \(n\) na skończoną płaszczyznę rzutową rzędu \(n.\) Prawdziwe jest zatem następujące
Twierdzenie: Istnieje \(n-1\) wzajemnie ortogonalnych kwadratów łacińskich rzędu \(n\) wtedy i tylko wtedy, gdy istnieje skończona płaszczyzna rzutowa rzędu \(n.\)
Zgodnie z obserwacjami z pierwszej części artykułu oznacza to, że istnieją płaszczyzny rzutowe rzędu \(p^k,\) gdzie \(p\) jest liczbą pierwszą. Obecnie nie znamy przypadku płaszczyzny rzutowej wymiaru innego niż \(p^k,\) przypuszcza się więc, że to stwierdzenie charakteryzuje wszystkie \(n,\) dla których odpowiednią płaszczyznę można skonstruować.
Hipoteza: Skończona płaszczyzna rzutowa rzędu \(n\) istnieje tylko wtedy, gdy \(n\) jest potęgą liczby pierwszej.
Istnieją oczywiście pewne wyniki częściowe. Jednym z nich jest następujący fakt, pochodzący z \(1949\) roku.
Twierdzenie (Bruck–Ryser): Jeżeli istnieje płaszczyzna rzutowa rzędu \(n\) oraz \(n\equiv 1 \pmod{4}\) lub \(n\equiv 2 \pmod{4},\) to \(n\) musi być sumą kwadratów dwóch liczb całkowitych.
Ostatnie twierdzenie wyklucza w szczególności istnienie płaszczyzn rzutowych wymiaru \(6\) lub \(14,\) ale nie wyklucza istnienia płaszczyzny rzędu \(10.\) To ostatnie zostało wykazane metodami komputerowymi w \(1991\) roku. Obecnie najmniejsze \(n,\) dla którego nie wiemy, czy istnieje odpowiednia płaszczyzna rzutowa, to \(n=12.\) Warto przy tej okazji przytoczyć pracę [3], której autorzy – polscy matematycy – przedstawiają elementarny i czysto geometryczny dowód nieistnienia płaszczyzny rzutowej rzędu \(6.\)
Istnienie płaszczyzn rzutowych rzędu \(n\): \[\begin{aligned} \text{rząd} &\ \ \ \text{czy istnieje?}\\ 2 &\ \ \ \text{tak}\\ 3 &\ \ \ \text{tak}\\ 4 &\ \ \ \text{tak}\\ 5 &\ \ \ \text{tak}\\ 6 &\ \ \ \text{nie}\\ 7 &\ \ \ \text{tak}\\ 8 &\ \ \ \text{tak}\\ 9 &\ \ \ \text{tak}\\ 10 &\ \ \ \text{nie}\\ 11 &\ \ \ \text{tak}\\ 12 &\ \ \ \text{problem otwarty}\\ 13 &\ \ \ \text{tak}\\ 14 &\ \ \ \text{nie}\\ 15 &\ \ \ \text{problem otwarty} \end{aligned}\]
Na koniec wspomnijmy o jeszcze jednym zagadnieniu. Wiemy już, że płaszczyzny rzutowe rzędu \(6\) oraz \(10\) nie istnieją, wobec tego nie istnieje odpowiednio \(5\) i \(9\) wzajemnie ortogonalnych kwadratów łacińskich. Można więc postawić pytanie – jeśli nie tyle, to ile maksymalnie można ich znaleźć? W przypadku \(n=6\) odpowiedzi dostarcza nam problem \(36\) oficerów. Natomiast dla \(n=10\) odpowiedź nie jest obecnie znana – wiadomo, że istnieją dwa ortogonalne kwadraty łacińskie rzędu 10 i przypuszcza się, że nie więcej. Wreszcie, dla \(n\geq 12\) istnieje co najmniej pięć wzajemnie ortogonalnych kwadratów łacińskich rzędu \(n.\)
Literatura
[1] G. Tarry, Le Probléme de 36 Officiers, Compte Rendu de l’Association Française pour l’Avancement des Sciences (1901), 170–203.
[2] R.C. Bose, S.S. Shrikhande, E.T. Parker, Further results on the construction of mutually orthogonal Latin squares and the falsity of Euler’s conjecture, Canad. J. Math. 12 (1960), 189–203.
[3] M. Dumnicki, J. Gwoździewicz, J. Szpond, An elementary, geometric proof of the nonexistance of a projective plane of order 6, Contrib. Discrete Math. 15 (2020), 1–9.