Giochi proiettivi — 4. Il problema dei 36 ufficiali di Eulero

“Finalmente un gioco?”.

“Sì, ma non quello di cui ti parlerò fra un po', per il quale abbiamo fatto questo studio sui piani proiettivi finiti”.

“Ah”.

“Ricordi che l'altra volta abbiamo calcolato il numero di punti e di rette di un piano proiettivo di ordine n?”.

“Sì, sono n² + n + 1”.

“Ammesso che esista, questo piano”.

“Non capisco come faccia a non esistere”.

“Per questo ti propongo un giochino: ci sono 36 ufficiali che appartengono a 6 reggimenti. Un'immagine (presa dal sito dell'AMS) ci mostra la situazione: i reggimenti sono identificati dai colori, i gradi degli ufficiali da una pedina degli scacchi”.

“Ok”.

“Il gioco consiste nel riallineare i 36 ufficiali in modo tale che ogni riga e ogni colonna contenga ufficiali di reggimenti diversi e di rango diverso”.

“Ah, una specie di doppio sudoku?”.

“Più o meno l'idea è quella. Per esempio, se gli ufficiali e i reggimenti fossero solo cinque, questa sarebbe una soluzione:”.

“Ok, chiaro”.

“Se invece fossero sette, ecco come si potrebbe fare:”.

“Bene. Provo con sei, allora?”.

“Puoi provare, ma non ce la farai”.

“Ma come?”.

“Eh, non ci si riesce”.

“Ma se ci si riesce con cinque, con sei si avranno più possibilità, no?”.

“E invece, non si può”.

“Mah. E Eulero l'ha dimostrato?”.

“No, Eulero ha congetturato che non si potesse, ma non è riuscito a dimostrarlo”.

“Ah! Ma allora è certamente un problema difficile”.

“Sì, e anche la dimostrazione è molto difficile. Il primo a dimostrare l'impossibilità è stato Tarry, nel 1900”.

“Tarry? Non l'ho mai sentito nominare”.

“Infatti non era un matematico. O, meglio, non era un matematico professionista: è famoso fondamentalmente per questa dimostrazione”.

“Ma pensa. Quindi non vediamo la dimostrazione, vero?”.

“No. Tarry ha fatto una serie di calcoli lunghi e laboriosi, poi ci sono stati tentativi successivi di semplificare la dimostrazione, qualcuno anche sbagliato”.

“Andiamo bene”.

“Nel 1936 è stata addirittura pubblicata una lista completa di tutti questi sudoku, come li chiami tu, e che in realtà si chiamano quadrati latini, e si è potuto verificare che nessuno di questi soddisfaceva la doppia condizione del problema: colori diversi e simboli diversi su ogni riga”.

“Un doppio quadrato latino?”.

“Sì, che viene chiamato quadrato greco-latino. Nel 1960 è arrivata una dimostrazione definitiva”.

“Ehi, il 1960 non è tanto tempo fa”.

“Eh, no”.

“E perché la chiami dimostrazione definitiva?”.

“Perché, utilizzando un sacco di matematica che serve per fare tutt'altro, per esempio la teoria dei codici, è stato finalmente dimostrato che esistono quadrati greco-latini di ogni ordine superiore al 2, tranne che per l'ordine 6”.

“Ah! Quindi Eulero aveva visto lontano”.

“Come al solito, direi. Ora, grazie all'uso dei computer, puoi andare su internet e trovare una lista con tutti i quadrati greco-latini fino all'ordine 8, assieme a tanti altri tipi di quadrati latini”.

“Si è persa un po' la magia, però”.

“Oppure no, se questo ci fa rendere conto di quali abilità possedessero quelli nati in un mondo senza computer”.

“Eh, vero. Ma non ho ancora capito cosa c'entri questo problema con gli spazi proiettivi”.

“La dimostrazione si basa su questo fatto: esiste un piano proiettivo di ordine n se e solo se esiste un insieme di n − 1 quadrati latini di ordine n che, a due a due, possono essere combinati per fare un quadrato greco-latino. Tutto questo a partire da n = 3, però”.

“Santo cielo”.

“Non mi addentro troppo nella dimostrazione, ti mostro solo un esempio con il caso più piccolo, il piano proiettivo di ordine 3. Ripartiamo da qui:”.

“Una vecchia conoscenza”.

“Già. Scegliamo una riga, per esempio quella verde, e scegliamo due punti su di essa, per esempio quello più in alto e quello più in basso, che chiameremo X_∞ e Y_∞”.

“Ok”.

“Avevamo n + 1 punti sulla retta verde, due li abbiamo usati, ne rimangono n − 1”.

“Sì, nel nostro caso 2”.

“Li chiameremo Q₁ e Q₂”.

“Bene”.

“Le rette che escono dai due punti X_∞ e Y_∞ le numeriamo da 1 fino a n (escludiamo quindi la retta verde, quella da cui siamo partiti con la costruzione)”.

“Bene”.

“Mentre le rette che escono dai vari punti Q_i le etichettiamo con A, B e C”.

“Ok”.

“In tutto avevamo n² + n + 1 punti, abbiamo già dato un nome a n + 1, ne rimangono n²”.

“Giusto”.

“Questi li etichettiamo con una coppia di numeri. Ognuno di essi, infatti, si trova su una retta che passa per X_∞ e su una seconda retta che passa per Y_∞”.

“Sì, perché comunque scelgo due punti c'è una retta che passa per essi”.

“Bene. Allora ognuno di questi punti viene etichettato con il numero corrispondente alle due rette che passano per X_∞ e Y_∞”.

“Ah, ecco perché si chiamano così: servono per darci delle coordinate”.

“Esattamente. Ora la situazione è questa:”.

“Vedo”.

“Ogni punto Q_i ci permette di creare un quadrato latino: quindi potremo avere n − 1 quadrati latini”.

“In che modo?”.

“Prendiamo per esempio il punto Q₂: da esso escono tre rette, che si chiamano A, B e C, che passano per tutti i nove punti con la coppia di coordinate. Per esempio, la retta A passa per (2,3), (1,2) e (3,1)”.

“Sì, vero”.

“Allora noi creiamo una tabella 3 × 3, e nelle caselle di coordinate (2,3), (1,2) e (3,1) scriviamo A”.

“Ahh! Così?”.

+---+---+---+
|   | A |   |
+---+---+---+
|   |   | A |
+---+---+---+
| A |   |   |
+---+---+---+

“Esatto. Poi facciamo la stessa cosa con la riga B, che passa per (3,3), (2,2) e (1,1), e infine con la riga C, che passa per (1,3), (3,2) e (2,1)”.

“Mi viene un quadrato fatto così:”.

+---+---+---+
| B | A | C |
+---+---+---+
| C | B | A |
+---+---+---+
| A | C | B |
+---+---+---+

“Che, come vedi, è un quadrato latino: ogni simbolo si ripete una sola volta su ogni riga e su ogni colonna”.

“Giusto. Poi si potrà fare la stessa cosa anche con Q₁, vero?”.

“Sì. Basta osservare la figura e vedere quali punti attraversano le tre righe etichettate con A, B e C. Risulta un quadrato fatto così:”.

+---+---+---+
| C | A | B |
+---+---+---+
| A | B | C |
+---+---+---+
| B | C | A |
+---+---+---+

“Confermo. Ma il quadrato greco-latino dov'è?”.

“Basta combinare i due quadrati che abbiamo trovato:”.

+----+----+----+
| BC | AA | CB |
+----+----+----+
| CA | BB | AC |
+----+----+----+
| AB | CC | BA |
+----+----+----+

“Ahh, bellissimo!”.

“Vedi che ci sono tutte le possibili coppie: ogni lettera in prima posizione si trova una volta sola su ogni riga e su ogni colonna, e la stessa cosa fanno le lettere in seconda posizione”.

“E questo metodo funziona sempre?”.

“Se hai un piano proiettivo riesci sempre a costruire un quadrato associato al punto Q_i, perché ogni retta che lo contiene interseca una sola volta le due rette X_∞ e Y_∞. Quindi ogni riga e ogni colonna del quadrato latino avranno esattamente ogni simbolo una sola volta. Inoltre, comunque tu prenda due di questi quadrati latini, potrai sempre costruire un quadrato greco-latino combinandoli insieme perché ogni retta che esce da uno dei Q_i interseca ogni altra retta che esce da un altro Q_j in un solo punto: quindi nel quadrato otterrai tutte le possibili coppie”.

“Che bello”.

“E funziona anche all'inverso: se hai n − 1 quadrati latini che, a due a due, possono formare un quadrato greco-latino, facendo questa costruzione al contrario potrai sempre costruire un piano proiettivo”.

“Molto bene”.

“Ora, il fatto che si sia riusciti a dimostrare che il problema degli ufficiali di Eulero non ha soluzione, significa che non è possibile avere un piano proiettivo di ordine 6: niente quadrati greco-latini, niente piani proiettivi”.

“Oh”.

“Quindi sappiamo che, se un piano proiettivo esiste, ha certamente n² + n + 1 punti, e altrettante rette. Ma non è detto che esista: per esempio, quello di ordine 6 non esiste”.

“E gli altri ordini?”.

“Mah”.

---

N.B. Per saperne di più sul legame tra quadrati magici e piani proiettivi, qui c'è un bell'articolo.

Qui, invece, l'esempio fatto anche in questo post, ma con più colori.