2.1. Opzionale: piani affini finiti e quadrati latini, greco-latini e magici

Problema dei 36 ufficiali (L. Euler, 1782): C’è una delegazione di 36 ufficiali, ognuno dei quali appartiene ad uno dei 6 reggimenti $a$, $b$, $c$, $d$, $e$, $f$. I 6 gradi sono $\alpha $, $\beta $, $\gamma $, $\delta $, $\epsilon $, $\varphi $, cioè colonnello, tenente-colonnello, maggiore, capitano, tenente, sottotenente. Possono formare un quadrato $6\times 6$ in modo tale che ogni grado e reggimento è rappresentato in ogni riga e in ogni colonna (equivalentemente, in ogni riga e in ogni colonna non compaiono mai due reggimenti uguali o due gradi uguali)?

Un quadrato del genere si chiama anche “quadrato greco-latino”, perché i 36 elementi possono essere rappresentati da $a\alpha $, $a\beta $, ... $f\epsilon $, $f\varphi $.

Naturalmente lo stesso problema può essere posto per quadrati $n\times n$, ed Eulero riuscì a trovare soluzioni per ogni $n$ tranne quelli per cui $n \equiv 2 \mod 4$. Quindi congetturò che non possono esserci soluzioni se $n \equiv 2 \mod 4$.

La congettura fu dimostrata (con qualche errore) da Tarry (1901) per $n=6$ (cioè Tarry mostrò che non esiste la soluzione al problema per $n=6$),1 ma confutata per il caso in generale da Parker nel 1959, con un celebre controesempio con $n=10$ (indicato nella figura 7.1 a pagina *);2 nel 1960 fu dimostrato anche negli altri casi la congettura è falsa, cioè che anche per per ogni $n > 6$, $n\equiv 2 \mod 4$ esistono quadrati greco-latini3 In pratica esistono per ogni $n$ tranne $n\in \{ 2,6\} $.

Un quadrato magico $n\times n$ è un quadrato in cui i primi $n^2$ numeri compaiono in modo tale che la somma delle cifre per colonne e per righe è costante.4 Osserviamo che se si ha un quadrato greco-latino $n\times n$, i cui elementi sono $(i,j)$, con $i,j=0,\ldots , n-1$, allora sostituendo al posto di $(i,j)$ il numero $1+ i + nj$ di ottiene un quadrato magico. Infatti con questa sostituzione la somma dei coefficienti di ogni riga (e quella di ogni colonna) è uguale a (perché?)

\[ \sum _{i=0}^{n-1} (1+i) + n \sum _{j=0}^{n-1} j = n + \frac{1}{2} n(n-1) + \frac{1}{2} n^2 (n-1) = \frac{n}{2} (n^2+1). \]

Per costruire quadrati greco-latini, torniamo per un momento alla geometria affine.

(2.17) Nota. Le proprietà della Nota (1.13) possono essere prese come assiomi per una struttura di geometria affine (finita). Più precisamente, una struttura di incidenza è una coppia $(X,L)$, dove $X$ è un insieme finito (di punti), e $L$ un insieme finito di rette, con la relazione di incidenza $x\in l$, $\in \from X\times L \to \{ 0,1\} $. Se valgono anche gli assiomi

  1. Per ogni due punti distinti di $X$ passa una unica retta.

  2. Per ogni retta $r$ e punto $A\not\in r$, esiste una unica retta per $A$ che non interseca $r$ (detta parallela).

  3. Esistono almeno 4 punti che non contengono terne di punti allineate.

allora $X$ è un piano affine. Due rette di $X$ si dicono parallele se non si intersecano, oppure se sono uguali. Si tratta di una relazione di equivalenza: basta dimostrare che è transitiva (dato che è simmetrica e riflessiva). Siano $a$, $b$ e $c$ tre rette distinte (se due di tre rette coincidono allora evidentemente vale la proprietà transitiva per questo caso particolare), con $a\cap b = \emptyset = b \cap c$. Se esistesse un punto $P\in a \cap c$, allora $P\not\in b$, e dunque esiste una unica retta $\hat b$ parallela a $b$ passante per $P$. Ma sia $a$ che $c$ non intersecano $b$, e passano per $P$, dunque $a=c$, cioè non è vero che le tre rette non sono distinte. Quindi $P$ non esiste, cioè $a$ è parallela a $c$.

A proposito degli assiomi, in realtà si può prendere l’assioma

  1. (iii)’ : Esistono tre punti non collineari.

invece che il (iii). Occorre poi dimostrare che i due insiemi di assiomi sono equivalenti…5

(2.18) Nota. Consideriamo una struttura di incidenza $(X,L)$ come sopra. Se $X$ ha $h$ elementi $x_1$, $x_2$, …$x_ h$ e $L$ ha $k$ elementi $l_1$, $l_2$, …, $l_ k$, allora ogni relazione di incidenza $X\times L \to \{ 0,1\} $ può essere descritta come una matrice $A$ di tipo $h\times k$ in cui i coefficienti $a_{ij}$ sono $0$ o $1$: per $i=1\ldots h$, e $j=1\ldots k$ si pone

\[ a_{ij}= \begin{cases} 1 & \text {se $x_ i\in l_ j$;} \\ 0 & \text {se $x_ i\not\in l_ j$.} \end{cases} \]

Nell’esercizio 7.25 vedremo come è possibile verificare gli assiomi di piano affine finito su una matrice di incidenza. È possibile –teoricamente– scrivere un algoritmo a “forza-bruta” che enumera tutte le possibili $2^{hk}$ matrici di incidenza di geometrie affini finite, scarta quelle che non soddisfano gli assiomi, e genera quindi una lista di tutte le geometrie finite (fino ad un certo numero di punti). Un approccio del genere è anche praticabile?6

Osserviamo che se $\FF $ ha $n$ elementi, allora $\AA ^2(\FF )$ ha $n^2$ punti, e le rette in $\AA ^2(\FF )$ sono costituite da $n$ punti (sono parametrizzate da $\FF $, nell’equazione parametrica $P=A+t\vv $). Quante sono le rette per un punto? Prendiamo un punto $P$ e una retta $r$ che non passa per $P$. Allora per ognuno degli $n$ punti di $r$ c’è una (unica) retta che passa anche per $P$, e queste $n$ rette sono tutte distinte (perché?). Dato che per $P$ c’è anche la parallela a $r$, in tutto ci sono $n+1$ rette per $P$. Perché non ce ne sono altre? Se $s$ è una retta per $P$ non parallela a $r$, allora $r\cap s \neq \emptyset $, e dato che se $s$ ha più di un punto di intersezione con $r$ allora $s=r$, l’intersezione è costituita da un punto di $r$. Ma allora $s$ è una delle $n$ rette già contate sopra.

Ora contiamo quanti punti e quante rette ci sono in un piano affine finito (non necessariamente un $\AA ^2(\FF )$), definito a partire dalla struttura di incidenza.

(2.19) Nota. Supponiamo che una retta di un piano affine $X$ (definito a partire però dagli assiomi della nota (1.13)…) abbia un numero finito di punti, $n$ (deve essere $n\geq 2$ perché…). Il piano si dice di ordine $n$. Dimostriamo che tutte le rette hanno $n$ punti, che per ogni punto passano $n+1$ rette, e che in totale ci sono $n^2$ punti e $n^2+n$ rette.

Dim. Sia $r$ la retta con $n$ punti e sia $P$ un punto non su $r$ (che esiste per il $(iii)$ della nota (1.13) a pagina *). Sia $x$ il numero di rette per $P$. Delle $x$ rette, una sola è parallela a $r$ (per $(ii)$); le $x-1$ rette hanno intersezione con $r$ e passano per $P$. Let intersezioni delle rette con $r$ sono necessariamente distinte, per cui $x-1\leq n$. D’altro canto per ogni punto $R$ di $r$ esiste una unica retta passante per $R$ e per $P$ (e queste rette sono tutte distinte): quindi $x-1\geq n$, cioè per ogni punto non sulla retta $r$ passano $n+1$ rette distinte.

Ora, siano $P$ e $Q$ due punti distinti. Per $(iii)$, esiste sicuramente una retta $l$ che non contenga né $P$$Q$ (altrimenti, tutte le rette contengono almeno $P$ oppure $Q$: tutte le rette intersecano la retta per $P$ e $Q$: non ci possono essere punti al di fuori di questa retta (per l’assioma delle parallele): tutti i punti sono allineati). Il numero di rette per $P$ (e il numero di rette per $Q$) è uno in più del numero di punti di $l$, e dunque il numero di rette per $P$ è uguale al numero di rette per $Q$.

Ora, se $l$ è una seconda retta (e la retta $r$ ha $n$ punti), allora scegliamo un punto $P$ non su $l$ e non su $r$ (ancora, $P$ deve esistere per $(iii)$, altrimenti tutti i punti sono in $l\cup r$, e non vale l’assioma delle parallele ... ). Segue che $r$ e $l$ hanno lo stesso numero di punti, e per l’arbitrarietà di $l$ la tesi.

Ora, se $x$ è il numero totale di punti e $y$ il numero totale di rette, abbiamo:

(1)\begin{equation} ny = (n+1)x \end{equation}

(contando i punti al variare delle rette, alla fine ogni punto è stato contato esattamente $n+1$ volte). Ma possiamo contare anche le rette con le coppie di punti distinti: per ognuna delle $x(x-1)/2$ coppie di punti distinti c’è una retta, ed ogni retta è contata $n(n-1)/2$ volte in questo modo. Dunque

(2)\begin{equation} x(x-1) = y n(n-1). \end{equation}

Risolviamo le due equazioni (1) e (2) otteniamo subito $x=n^2$ e $y=n^2 + n$.

QED

Quindi le matrici (possibili) di incidenza per i piani di ordine $n$ hanno $h=n^2$ righe e $k=n^2+n$ colonne, e quindi sono

\[ 2^{n^2(n^2+n)}. \]

Il numero di secondi necessario (con un supercomputer ipotetico, capace di $10^{15}$ operazioni al secondo) è almeno $2^{n^3(n+1)} 10^{-15}$, cioè…

Torniamo ora ai quadrati greco-latini, che fondamentalmente sono unioni di due quadrati latini distinti (e con la proprietà che tutte le $n^2$ coppie compaiono), dove per quadrato latino si intende la parte a lettere latine. Più precisamente, un quadrato latino di ordine $n$ è una matrice $n\times n$ i cui coefficienti sono i numeri $\{ 1,2, ... ,n\} $ e in cui ogni riga e ogni colonna contiene ogni numero esattamente una volta. Anche in questo caso si ha un quadrato magico: le somme delle righe e delle colonne sono uguali a $n(n+1)/2$, oppure, se si somma $k\in \ZZ $ ad ogni coefficiente della matrice, $n(n+1)/2 + nk$.

Non è difficile vedere che la tabella di moltiplicazione di un gruppo $G$ di ordine $n$ è di fatto un quadrato magico: ... (esercizio!).

Due quadrati latini $a_{i,j}$ e $b_{i,j}$ sono ortogonali se le coppie ordinate $(a_{i,j}, b_{i,j})$ sono tutte distinte al variare di $i,j$. Quindi, i quadrati greco-latini non sono altro che coppie di quadrati latini ortogonali.

(2.20) Esempio. Un piano affine di ordine $n$ genera $n-1$ quadrati latini $n\times n$ nel modo seguente: fissiamo un punto $O$ del piano e due rette $x$ e $y$ distinte e passanti per $O$. Ci sono $n+1-2 = n-1$ altre rette per $O$ distinte, $n$ rette parallele a $x$ e $n$ rette parallele a $y$. Chiamiamo

\[ x_1, \ldots , x_ n \]

le rette parallele a $x$ e

\[ y_1, \ldots , y_ n \]

le rette parallele a $y$. Sia $z$ una delle $n-1$ rette per $O$ diverse da $x$ e $y$, e

\[ z=z_1, \ldots , z_ n \]

le rette parallele a $z$. Per ogni $i,j$ le due rette $x_ i$ e $y_ j$ non sono parallele, e quindi si intersecano in un unico punto $x_ i \cap y_ j$. Questo punto è contenuto in una sola retta parallela a $z$, cioè esiste $k\in \{ 1,\ldots , n\} $ tale che $x_ i \cap y_ j \in z_ k$. Fissato $z$, quindi, sia $A$ la matrice $n\times n$ con coefficienti $a_{i,j}$ determinati da

\[ a_{i,j} = k \iff x_ i \cap y_ j \in z_ k. \]

(2.21) La matrice $a_{i,j}$ è un quadrato latino.

Dim. Gli elementi della prima riga sono \[ a_{1,j} = k \iff x_1 \cap y_ j \in z_ k. \] Fissato $k$, cioè $z_ k$, se $x_1 \cap y_ j \in z_ k$ e $x_1 \cap y_{l} \in z_ k$ con $j\neq l$, allora in $z_ k$ ci sono due punti distinti (perché appartengono alle due rette $y_ j$ e $y_ l$ parallele distinte) che appartengono anche a $x_1$, cioè $x_1 = z_ k$, e questo è assurdo perché $x_1$ è parallela a $x$, $z_ k$ è parallela a $z$ e $x$ non è parallela a $z$. Lo stesso per le altre righe e per le colonne.
QED

Quindi al variare di $z$ nell’insieme delle $n-1$ rette per $O$ non parallele a $x$ o a $y$ otteniamo $n-1$ quadrati latini (esercizio 7.23). Non solo sono quadrati latini distinti: sono a due a due ortogonali!

(2.22) Se $z$ e $w$ sono due rette distinte per $O$ non parallele a $x$ e a $y$, e $a_{i,j}$ e $b_{i,j}$ i quadrati latini generati come sopra, allora $a_{i,j}$ e $b_{i,j}$ sono ortogonali.

Dim. Occorre mostrare che per ogni coppia $(h,k)$, con $h,k \in 1,\ldots , n$ esiste una unica coppia di indici $(i,j)$ tale che \[ \begin{cases} a_{i,j} & = h \\ b_{i,j} & = k. \end{cases} \] Questo è equivalente a chiedere che per ogni retta $z_ h$ parallela a $z$ e per ogni retta $w_ k$ parallela a $w$ esiste unica la coppia di rette $x_ i$ e $y_ j$ tali che \[ \begin{cases} x_ i \cap y_ j \in z_ h \\ x_ i \cap y_ j \in w_ k. \end{cases} \] Ma $z_ h$ e $w_ k$ non sono parallele e quindi si intersecano in un unico punto. Esiste una unica $x_ i$ che passa per questo punto, ed esiste una unica $y_ j$ che passa per questo punto (sono fasci di rette parallele!). Quindi $x_ i \cap y_ j \in z_ h \cap w_ k$ come volevasi dimostrare.
QED


Quindi per ogni piano affine finito di ordine $n\geq 3$ è possibile trovare quadrati greco-latini. Ma per quali $n$ ci sono piani affini finiti? Certamente se $n$ è l’ordine di un campo finito (per esempio, se $n$ è primo7), altrimenti non è una domanda facile. Possiamo stabilire che non ci sono piani affini finiti di ordine $6$ (altrimenti ci sarebbe una soluzione per il problema dei 36 ufficiali di Eulero). È un esercizio molto semplice quello di usare la costruzione indicata sopra per costruire quadrati latini e greco-latini (e quindi quadrati magici). Basta prendere le due rette del sistema di riferimento standard di $\AA ^2(\KK )$, con $\KK = \ZZ _ p$ con $p$ primo, e considerare i fasci di rette di equazioni $y=x+q$ e $y=kx+q$, con $k,q\in \KK $. Allora i due quadrati hanno coefficienti

\[ a_{xy} = y-x \mod p,\quad b_{xy} = y-kx \mod p \]

con $x,y\in 0\ldots p-1$, e il quadrato magico corrispondente ha coefficienti

\[ m_{xy} = (y-kx \mod p) + p (y-x \mod p ). \]

Per esempio, per $p=5$ e $k=2$ si ottiene

 0 6 12 18 24 | 60 
 23 4 5 11 17 | 60 
 16 22 3 9 10 | 60 
 14 15 21 2 8 | 60 
 7 13 19 20 1 | 60 
-------------------------
 60 60 60 60 60 

Mentre per $p=11$ e $k=2$ :

 0 12 24 36 48 60 72 84 96 108 120 | 660 
 119 10 11 23 35 47 59 71 83 95 107 | 660 
 106 118 9 21 22 34 46 58 70 82 94 | 660 
 93 105 117 8 20 32 33 45 57 69 81 | 660 
 80 92 104 116 7 19 31 43 44 56 68 | 660 
 67 79 91 103 115 6 18 30 42 54 55 | 660 
 65 66 78 90 102 114 5 17 29 41 53 | 660 
 52 64 76 77 89 101 113 4 16 28 40 | 660 
 39 51 63 75 87 88 100 112 3 15 27 | 660 
 26 38 50 62 74 86 98 99 111 2 14 | 660 
 13 25 37 49 61 73 85 97 109 110 1 | 660 
-------------------------------------------------------
 660 660 660 660 660 660 660 660 660 660 660 

Per avere quadrati magici “perfetti” (cioè tali che anche sulle due diagonali la somma sia la costante magica), occorre cambiare leggermente le formule:

\[ m_{xy} = (y-kx + q_1 \mod p) + p (y-x +q_2 \mod p ) \]

con $q_1$ e $q_2$ costanti appropriate.

Per $p=5$ e $k=2$ si ottiene il quadrato magico perfetto:

 12 18 24 0 6 | 60 
 5 11 17 23 4 | 60 
 3 9 10 16 22 | 60 
 21 2 8 14 15 | 60 
 19 20 1 7 13 | 60 
-------------------------
 60 60 60 60 60 

Mentre per $p=11$ e $k=2$ :

 60 72 84 96 108 120 0 12 24 36 48 | 660 
 47 59 71 83 95 107 119 10 11 23 35 | 660 
 34 46 58 70 82 94 106 118 9 21 22 | 660 
 32 33 45 57 69 81 93 105 117 8 20 | 660 
 19 31 43 44 56 68 80 92 104 116 7 | 660 
 6 18 30 42 54 55 67 79 91 103 115 | 660 
 114 5 17 29 41 53 65 66 78 90 102 | 660 
 101 113 4 16 28 40 52 64 76 77 89 | 660 
 88 100 112 3 15 27 39 51 63 75 87 | 660 
 86 98 99 111 2 14 26 38 50 62 74 | 660 
 73 85 97 109 110 1 13 25 37 49 61 | 660 
-------------------------------------------------------
 660 660 660 660 660 660 660 660 660 660 660 

Se $n=p^ k$ con $k > 1$, la faccenda si complica, però...

Described image figs/gl10.jpeg
Raffigurazione del controesempio alla congettura di Eulero per $n=10$. È alla base della struttura del romanzo "La Vie -- mode d'emploi" (1978) di Georges Perec (1936 - 1982), e di alcuni quadri/decorazioni. Un altro problema matematico, trattato da Eulero, alla base della struttura del romanzo è il problema del \emph{percorso del cavallo}, per una scacchiera $10\times 10$.
Figura 7.1: Raffigurazione del controesempio alla congettura di Eulero per $n=10$. È alla base della struttura del romanzo La Vie – mode d’emploi (1978) di Georges Perec (1936 - 1982), e di alcuni quadri/decorazioni. Un altro problema matematico, trattato da Eulero, alla base della struttura del romanzo è il problema del percorso del cavallo, per una scacchiera $10\times 10$.


Footnotes

  1. G. Tarry, “Le problème des 36 officiers,” C. R. Assoc. Fran. Av. Sci. Vol. 1(1900), p. 122–123, Vol. 2(1901), p. 170–203.
  2. E. T. Parker, “Construction of some sets of mutually orthogonal Latin squares,” Proc. Amer. Math. Soc., Vol. 10(1959), p. 946–949. Si veda anche R. C. Bose and S.S. Shrikhande, “On the construction of sets of mutually orthogonal Latin squares and the falsity of a conjecture of Euler”, Trans. Amer. Math. Soc., 95 (1960) 191–209.
  3. R. C. Bose and S. S. Shrikhande, “On the falsity of Euler’s Conjecture about the non-existence of two orthogonal latin squares of order 4t+2,” Proc. Nat. Acad. Sci. U. S. A. Vol. 45(1959), p. 734–737. R.C. Bose, S.S. Shrikhande, and 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.
  4. In genere si richiede anche che la somma delle cifre sulle due diagonali sia uguale alla somma costante delle colonne e righe. Alcuni chiamano tali quadrati magici perfetti.
  5. È chiaro che (iii) $\implies $ (iii)’. Viceversa, se ci sono tre punti non allineati $A,B,C$, allora esistono le rette $r$ parallela ad $AB$ e passante per $C$ e $s$ parallela a $BC$ e passante per $A$. Se le rette $r$ e $s$ non si intersecano (cioè, sono parallele), dato che la relazione di parallelismo è una relazione di equivalenza, allora $BC$ (la retta per $B$ e $C$) è parallela a $AB$, e $BC$ e $AB$ si intersecano in $B$ certamente, le due rette coincidono, cioè $ABC$ sono allineati (contro ipotesi). Quindi esiste $D\in r\cap s$. I quattro punti $A$, $B$, $C$ e $D$ non contengono terne di punti allineate. Osserviamo che $AB$ e $CD$ sono parallele e $AD$ e $CB$ sono parallele. Se tre dei quattro punti fossero allineati allora le quattro rette $AB$, $CD$ e $AD$ e $CB$ sarebbero tutte tra loro parallele, e quindi coincidenti. Ma $ABC$ non sono allineati per ipotesi e questo è assurdo.
  6. Stimando molto per eccesso che un computer non può (e non potrà nei prossimi anni) eseguire più di $10^{15}$ operazioni al secondo.
  7. I campi finiti hanno ordine $n=p^ k$ per $p$ primo e $k$ intero. La Prime Power Conjecture congettura che ci sia un piano affine di ordine $n$ se e soltanto se $n$ è la potenza di un primo.