Capitolo D63:
quadrati latini
Contenuti delle sezioni
a. quadrati latini [1] p.2
b. simmetrie dei quadrati latini p.6
c. quadrati latini standard e quasigruppi p.10 d. biparit`a dei quadrati latini p.13
e. quadrati latini dei gruppi p.14 f. rompicapo Sudoku e KenKen p.15
Mario g. sistemi di quadrati latini ortogonali p.17
17 pagine
D63:0.01 Il capitolo `e dedicato a una introduzione dei quadrati latini, strutture discrete che hanno destato interesse sia in quanto fonti di passatempi, sia pi`u recentemente, in quanto utili per svariate applicazioni.
In particolare i quadrati latini sono utilizzati per la definizione di codici per le comunicazioni, per la pianificazione e l’analisi di esperimenti statistici e per la determinazione di strutture algebriche e geometriche finite.
Nella prima parte, dopo le prime definizioni, si espongono le propriet`a di simmetria del loro insieme, si sottolineano i collegamenti tra le corrispondenti classi di simmetria e si espone la loro caratterizzazione mediante la loro biparit`a.
Successivamente si introduce la relazione di ortogonalit`a tra quadrati latini e si presenta il problema dei 36 ufficiali affrontato da Euler e costituente uno dei primi problemi discreti affrontato con strumenti matematici.
D63:a. quadrati latini [1]
D63:a.01 Sia n un intero positivo maggiore o uguale a 2 ed X un insieme finito.
Si dice quadrato latino di ordine n su X una matrice quadrata n × n le cui entrate appartengono a X e si dispongono in modo che ogni elemento di X compare precisamente una volta in ogni sua riga ed in ogni sua colonna.
Chiaramente ogni x ∈ X deve comparire in n caselle della matrice, in accordo con il fatto che X `e costituita da n2/n = n elementi.
Quattro esempi di quadrati latini (termine che i queste pagine abbrevieremo con quadrati-L) aventi, risp., ordine 4, 4, 5 e 6 sono:
A B C D
B A D C
C D A B
D C B A
α β γ δ
γ δ α β
δ γ β α
β α δ γ
0 1 2 3 4
1 2 4 0 3
2 4 3 1 0
3 0 1 4 2
4 3 0 2 1
0 1 2 3 4 5
1 0 3 4 5 2
2 5 4 1 3 0
3 2 0 5 1 4
4 3 5 0 2 1
5 4 1 2 0 3
D63:a.02 Evidentemente la matrice trasposta di un quadrato latino `e ancora un quadrato latino. In effetti nella definizione dei quadrati latini le righe e le colonne hanno ruoli scambiabili.
Dunque la trasposizione delle matrici di quadrati latini `e un’involuzione; si possono quindi distin- guere quadrati latini simmetrici e quadrati latini costituenti duetti scambiabili per trasposizione. Dei quadrati latini presentati in precedenza solo il primo e il terzo sono simmetrici.
Un quadrato latino di ordine n su X si pu`o considerare ottenuto affiancando n permutazioni di X disposte a formare n colonne e si pu`o considerare ottenuto sovrapponendo n permutazioni di X disposte a formare n righe.
Individuare un quadrato latino di ordine n su un insieme X di n elementi corrisponde a individuare una n-upla di permutazioni di X tale che leggendo le loro componenti in una qualsiasi delle loro n successive posizioni si ottiene un’altra permutazione di X.
Per lo studio delle propriet`a combinatorie dei quadrati latini, chiaramente, l’individualit`a degli elementi dell’insieme X non conta.
Dunque quando non si `e condizionati da esigenze applicative ci si pu`o limitare a studiare quadrati latini con le entrate pi`u opportune.
In genere si trattano quadrati-L con entrate numeriche; qui preferiamo trattare quadrati-L di ordine n con le entrate facenti parte dell’intervallo [n) per poter utilizzare le propriet`a modulari di questi intervalli.
D63:a.03 Chiamiamo dunque quadrato latino canonico di ordine n un quadrato latino n × n avente righe, colonne ed entrate individuate dagli interi 0, 1, ..., n − 1.
Nel seguito studieremo prevalentemente quadrati latini canonici e, salvo avviso contrario, riterremo implicito l’attributo canonico per i nostri quadrati.
Denoteremo con SqL la collezione dei quadrati latini (canonici) e con SqL(n)la collezione di quelli di ordine n. Inoltre ci serviremo delle scritture [n) := {0, 1, ..., n − 1}, della Id(n) per la permutazione identit`a dell’intervallo [n).
Il generico quadrato latino di ordine n sar`a denotato con la scrittura L = [i, j = 0, ..., n − 1 :| Li,j] .
D63:a.04 Non `e difficile elencare tutti i quadrati latini degli ordini 2 e 3.
(1) 0 1
1 0
1 0 0 1
0 1 2 1 2 0 2 0 1
0 1 2 2 0 1 1 2 0
0 2 1 1 0 2 2 1 0
0 2 1 2 1 0 1 0 2
(2)
1 0 2 2 1 0 0 2 1
1 0 2 0 2 0 2 1 1
1 2 0 2 0 1 0 1 2
1 2 0 0 1 2 2 0 1 2 0 1
0 1 2 1 2 0
2 0 1 1 2 0 0 1 2
2 1 0 0 2 1 1 0 2
2 1 0 1 0 2 0 2 1 Tra i quadrati latini di ordine 4 limitiamoci a presentare i seguenti
(3)
0 1 2 3
1 2 3 0
2 3 0 1
3 0 1 2
0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0
0 1 2 3
1 0 3 2
2 3 1 0
3 2 0 1
0 1 2 3
1 3 0 2
2 0 3 1
3 2 1 0
.
Al crescere dell’ordine n la generazione di tutti i quadrati latini si fa subito estremamente onerosa: si trova in particolare che i numeri dei quadrati latini degli ordini 4, 5, 6, 7 e 8 sono, risp., 576, 161 280, 812 851 200, 61 479 419 904 000 e 108 776 032 459 082 956 800.
D63:a.05 In effetti i quadrati latini, come molte altre configurazioni discrete, non si sanno tenere bene sotto controllo e a tutt’oggi il loro insieme costituisce una popolazione vasta e poco nota.
Come in parte vedremo, tra i quadrati latini di un certo ordine se ne trovano sottoinsiemi che godono di propriet`a specifiche i quali sono molto meno numerosi e si possono controllare con minori difficolt`a.
La maggioranza invece sfugge alle classificazioni e alle possibilit`a di manipolazione efficiente.
Molte configurazioni discrete per molti scopi possono essere prese in visione, confrontate, analizzate e manipolate solo servendosi del computer, cio`e empiricamente; questo in particolare si riscontra per le applicazioni dei quadrati latini.
In particolare non si conosce una formula ragionevolmente maneggevole per il numero dei quadrati latini dei diversi ordini.
Sono noti solo i cardinali relative ai primi ordini e questi sono state ottenuti con laboriosi procedimenti specifici, facendo uso del computer e di gruppi di simmetrie.
Le successioni di questi cardinali sono presenti nell’archivio OEIS (we)come successioni A002860 ed A000315.
D63:a.06 Vengono studiati anche i rettangoli latini, matrici di profilo k × n con k 6= n che in ogni riga e in ogni colonna presentano componenti non ripetute appartenenti a un insieme di max(n, k) elementi.
Un semplice esempio di rettangolo latino di profilo 5 × 7 `e il seguente:
0 1 2 3 4 5 6
1 2 3 4 5 6 0
2 3 4 5 6 0 1
3 4 5 6 0 1 2
Questa matrice si pu`o chiamare rettangolo latino largo; con la trasposizione si ottengono rettangoli latini alti, dotati di propriet`a del tutto equivalenti.
Chiaramente i quadrati latini si possono considerare casi particolari di rettangoli latini.
D63:a.07 Una ragione della ridotta controllabilit`a dei quadrati latini risiede nella impossibilit`a di stabilire collegamenti semplici e sistematici tra i quadrati latini di un certo ordine n e quelli degli ordini immediatamente successivi come n + 1 ed n + 2, come accade invece per strutture come le permutazioni e le partizioni.
In effetti, se diciamo sottoquadrato latino di un quadrato-L una sottomatrice che sia un quadrato-L, vale l’enunciato che segue.
(1) Prop.: In un quadrato latino di ordine n non si trova alcun sottoquadrato latino che abbia l’ordine superiore ajn
2 k
.
Dim.: La cosa si dimostra per assurdo. Si pu`o supporre per semplicit`a di notazioni, che un quadrato latino L canonico di ordine n L possegga un sottoquadrato latino di ordine k che occupa le sue prime k righe e le sue prime k colonne, con k > n
2 e che esso inoltre abbia come entrate gli interi 0, 1, ..., k − 1.
La supposizione `e lecita in quanto ogni coppia formata da un quadrato latino di ordine n e da un suo sottoquadrato latino di ordine k si pu`o ricondurre alla precedente mediante permutazioni di righe, colonne ed entrate.
Nel rettangolo R costituito dalle righe di L con indici k, k + 1, ... ed n − 1 e dalle prime k colonne si possono trovare solo gli n − k interi k, k + 1, ... ed n − 1. Dato che k > n
2 equivale a k > n − k, nelle colonne di R si devono avere interi ripetuti e quindi il rettangolo R non pu`o far parte di un quadrato latino
La impossibilit`a sopra dimostrata si pu`o rendere evidente con il tentativo di precisare un rettangolo latino che sia una variante di quello in a06 comprendente un sottoquadrato latino 4 × 7.
0 1 2 3 4 5 6
1 2 3 0 5 6 4
2 3 0 1 6 4 5
3 0 1 2 x x x
D63:a.08 Accade invece che in molti quadrati latini si trovano non pochi sottoquadrati latini di ordine piccolo.
In genere si trovano numerosi sottoquadrati latini di ordine 2: queste sottomatrici sono dette intercalati.
Nel primo quadrato latino presentato in a01 tutte le 4 sottomatrici di ordine 2 ottenute “tagliandolo in 4”. Si trovano inoltre 5 intercalati con righe e colonne non adiacenti, quelli individuati dalle coordinate delle caselle estreme: 11 con 33, 12 con 34, 21 con 43, 22 con 44 e 11 con 44.
Gli intercalati di questo tipo spesso non sono rapidamente riconoscibili.
Nel quadrato latino 6 × 6 dato in a01 si riconoscono 6 intercalati, tutti contenenti due 0.
Osserviamo che la presenza di un intercalato I in un quadrato latino consente di individuare subito un altro quadrato: quello ottenuto scambiando le due entrate di I. Per esempio il terzo dei quattro quadrati-L in 104(3) si ottiene dal secondo modificando l’intercalato delle ultime righe e delle ultime colonna.
Pi`u in generale da un quadrato latino di ordine n nel quale si trova un sottoquadrato latino di ordine k (minore dijn
2 k
) si possono ricavare facilmente altri quadrati latini trasformando il sottoquadrato in uno qualsiasi degli altri |SqL(k)| − 1 sottoquadrati di ordine k contenenti le stesse k entrate ottenendo altrettanti quadrati latini di ordine n.
D63:a.09 Si possono inoltre costruire facilmente nuovi quadrati latini canonici affiancando e sovrap- ponendo quadrati latini dello stesso ordine k, con l’accorgimento di aumentare di opportuni multipli di k tutte le entrate di alcuni quadrati.
Consideriamo a es. i primi quattro quadrati latini di ordine 3 in a04 ed accostiamoli in modo da formare una prima delle matrici 6 × 6 sottosegnalate.
Evidentemente abbiamo ripetizioni sistematiche in tutte le linee. Queste ripetizioni tuttavia si elimin- ano aumentando di 3 tutte le componenti del secondo e del terzo quadrato 3 × 3 (seconda delle matrici sottosegnalate), oppure tutte le componenti del primo e del quarto quadrato (terza matrice).
0 1 2 0 1 2
1 2 0 2 0 1
2 0 1 1 2 0
0 2 1 0 2 1
1 0 2 2 1 0
2 1 0 1 0 2
0 1 2 3 4 5
1 2 0 5 3 4
2 0 1 4 5 3
3 5 4 0 2 1
4 3 5 2 1 0
5 4 3 1 0 2
3 4 5 0 1 2
4 5 3 2 0 1
5 3 4 1 2 0
0 2 1 3 5 4
1 0 2 5 4 3
2 1 0 4 3 5
D63:a.10 In generale, per r e k interi qualsiasi superiori ad 1, si ottiene un nuovo quadrato latino a partire da un quadrato latino guida L di ordine r, e da r2quadrati latini di ordine k che denotiamo con M(p,q)con p, q = 0, 1, ..., k − 1, non necessariamente diversi tra di loro. Questi quadrati si dispongono a formare un quadrato r k × r k e successivamente si aumentano tutte le componenti di M(p,q)di k · Lp,q, multiplo della componente del quadrato guida corrispondente alla “macroposizione” del quadrato di ordine k in esame.
Il quadrato latino cos`ı ottenuto lo chiamiamo assemblaggio latino guidato da L dei quadrati latini M(p,q). Alcuni esempi di assemblaggi latini guidati da quadrati di ordine 3 utilizzanti quadrati di ordine 2 sono i seguenti:
0 1 3 2 4 5
1 0 2 3 5 4
2 3 4 5 1 0
3 2 5 4 0 1
5 4 0 1 3 2
4 5 1 0 2 3
0 1 4 5 3 2
1 0 5 4 2 3
2 3 1 0 4 5
3 2 0 1 5 4
4 5 3 2 0 1
5 4 2 3 1 0
4 5 2 3 1 0
5 4 3 2 0 1
0 1 5 4 2 3
1 0 4 5 3 2
2 3 1 0 5 4
3 2 0 1 4 5
Permutando righe e colonne dei quadrati-L assemblati si ottengono altri quadrati-L ricchi di sottoqu- adrati latini riguardanti righe e colonne non consecutive.
D63:a.11 Eserc. Mostrare che i 4 quadrati-L di ordine 4 presentati in a04(3) sono gli unici che presentano Id(4) sia nella prima riga che nella prima colonna.
D63:a.12 Eserc. Mostrare che se un quadrato-L di ordine pari 2 k possiede un sottoquadrato latino di ordine k, allora `e ottenibile come assemblaggio latino.
D63:a.13 Eserc. Trovare una espressione per un quadrati-L di ordine n qualsiasi che si possa ottenere come assemblaggio dei quadrati degli ordini 2, 3 e 4 dati in a04.
D63:a.14 Eserc. Mostrare che assemblando quadrati-L degli ordini 2 e 3 si possono ottenere 47 616 quadrati-L di ordine 6.
D63:b. simmetrie dei quadrati latini
D63:b.01 Nello studio di configurazioni combinatorie numerose e non facili da controllare come i quadrati latini risulta molto utile individuare le loro propriet`a di simmetria.
Abbiamo gi`a visto la simmetria di SqL(n)relativa alla trasposizione.
Altre trasformazioni che portano quadrati latini in quadrati latini sono le permutazioni delle righe e le permutazioni delle colonne.
Pi`u precisamente ciascuna di queste azioni `e una biiezione di SqL(n); infatti applicando una permu- tazione di [n) diversa dalla identit`a, alle righe [risp. colonne] di un quadrato latino, ciascuna delle sue colonne [righe] viene modificata.
D63:b.02 Inoltre applicando alle righe di un quadrato latino L ∈ SqL(n) le n! permutazioni di [n) si ottengono n! quadrati di SqL(n) diversi: infatti due di questi quadrati devono presentare, ad esempio, la prima colonna diversa perch´e ottenuta dalla permutazione nella prima colonna della L applicando due permutazioni diverse.
Dualmente-T, applicando alle colonna di un quadrato latino in SqL(n) le n! permutazioni di [n) si ottengono n! quadrati di SqL(n)diversi.
Se π `e una permutazione di [n), denoteremo, risp., con Rπ, con Cπe con Eπle trasformazioni consistenti nel sottoporre a π risp. le righe, le colonne e le entrate di un quadrato-L di ordine n.
Pi`u esplicitamente definiamo:
Rπ(L) := [i, j ∈ [n) :| Lπ−1(i),j] , Cπ(L) := [i, j ∈ [n) :| Li,π−1(j)] , Eπ(L) := [i, j ∈ [n) :| π(Li,j)]
D63:b.03 Vogliamo ora estendere significativamente le simmetrie precedenti facendo riferimento ai gruppi di trasformazioni dei SqL(n).
In precedenza abbiamo individuato quattro gruppi di trasformazioni di SqL(n). Il primo `e costituito dalla identit`a In := Id(SqL(n)) e dalla trasposizione che denoteremo XR,Cper segnalare che sono stati scambiati i ruoli delle righe e delle colonne. Il secondo `e formato dalle permutazioni delle righe e lo denoteremo con RSymn; il terzo CSymn`e costituito dalle permutazioni delle colonne; il quarto ESymn
`e formato dalle permutazioni delle entrate, ovvero dalle permutazioni del codominio dei quadrati-L visti come funzioni del genere {[n) × [n) . [n)} .
Ciascuno di questi gruppi, come per tutti i gruppi di trasformazioni, determina una partizione dell’insieme SqL(n)su cui opera, ovvero una relazione di equivalenza e le relative classi blocchi, cio`e i sottoinsiemi invarianti per le trasformazioni, ossia le orbite dei gruppi.
Come si `e gi`a notato, le classi di simmetria per trasposizione sono i singoletti dei quadrati-L simmetrici e le coppie di quadrati-L diversi ma ottenibili l’uno dall’altro per trasposizione. Ciascuna delle classi di simmetria per i gruppi RSymn, CSymn ed ESymn sono invece tutte costituite da n! quadrati-L.
D63:b.04 Nella definizione di quadrato latino intervengono tre entit`a, le righe, le colonne e le entrate.
Questa constatazione suggerisce di individuare una completa simmetria di ruoli per le tre entit`a che allarghi quella riguardante righe e colonne. In effetti attraverso una versione tridimensionale dei quadrati-L si descrive agevolmente una tele simmetria.
Diciamo cubo latino di ordine n ogni schieramento tridimensionale binario H = [i, j, k ∈ [n) :| Hi,j,k] tale che:
∀i, j ∈ [n) esiste esattamente un k ∈ [n) tale che Hi,j,k= 1 ,
∀i, k ∈ [n) esiste esattamente un j ∈ [n) tale che Hi,j,k= 1 ,
∀j, k ∈ [n) esiste esattamente un i ∈ [n) tale che Hi,j,k= 1 .
I cubi latini non sono semplici da visualizzare; si visualizzano pi`u agevolmente le matrici utilizzate per la definizione iniziale dei quadrati-L [a01].
Questo induce talora a rappresentare un cubo latino con la sequenza delle terne che caratterizzano i punti con valore 1. Questa rappresentazione mediante terne si ricava anche dal quadrato latino equivalente L e le si pu`o dare la forma
i ∈ [n), j ∈ [n) :| hi, j, L(i, j)i .
Si tratta di una rappresentazione piuttosto prolissa, ma fornita da oggetti, terne di interi positivi, molto semplici.
I cubi latini hanno il vantaggio di consentire di individuare le simmetrie dei quadrati-L molto chiara- mente.
Innanzi tutto si osserva che nella definizione le loro tre dimensioni, ovvero le posizioni 1, 2 e 3 dei loro indici intervengono in modo completamente simmetrico. Quindi sottoponendo un cubo latino a una qualsiasi delle 6 permutazioni delle posizioni degli indici si ottiene ancora un cubo latino.
D63:b.05 Visivamente un cubo latino si pensa come una opportuna disposizione di zeri e uni nei punti aventi coordinate intere 0, 1, ..., n − 1 dello spazio a tre dimensioni riguardanti le tre posizioni degli indici.
Denotiamo con x1, x2 ed x3 le variabili nell rispettive dimensioni, con Ox1, Ox2 ed Ox3 i rispettivi assi (cio`e le rette caratterizzate, risp., dalle equazioni x2= x3= 0, x1= x3= 0 e x1= x2= 0) e con Ox1x2, Ox2x3, Ox3x1 i rispettivi piani caratterizzabili con le equazioni x1= 0, x2= 0 e x3= 0.
Le sei permutazioni delle posizioni degli indici si interpretano come segue:
Id{1,2,3} identit`a del cubo;
(1, 2) riflessione rispetto al piano x1= x2; (1, 3) riflessione rispetto al piano x1= x3; (2, 3) riflessione rispetto al piano x2= x3;
(1, 2, 3) rotazione di 120◦intorno alla retta x1= x2= x3
che manda l’asse Ox1 nell’Ox2, Ox2 in Ox3 ed Ox3 in Ox1;
(1, 3, 2) rotazione inversa della precedente, ovvero quadrato della precedente.
Si `e quindi individuato un gruppo di simmetria per l’insieme dei cubi latini il quale `e isomorfo a Sym3. Questo gruppo viene detto gruppo di parastrofia dei quadrati-L.
D63:b.06 Osserviamo che le n matrici binarie ottenute considerando i diversi valori per il primo indice i = 0, 1, ..., n − 1 sono matrici permutative n × n; analogamente si ottengono n matrici di questo genere fissando i valori per il secondo e per il terzo indice.
Un cubo latino di ordine n si pu`o quindi considerare ottenuto accostando n matrici permutative traslate secondo una qualsiasi delle tre direzioni xh in modo da presentare esattamente un valore 1 in ciascuna delle n2 linee parallele all’asse di traslazione.
D63:b.07 Si vede facilmente che sottoponendo a una permutazione qualsiasi una delle tre n-uple di matrici accostate (secondo la direzione Ox1, secondo la direzione ox2 o secondo la direzione Ox3) si ottiene ancora un cubo latino.
Si `e quindi individuato un secondo gruppo di simmetria per l’insieme dei cubi latini; questo gruppo viene detto gruppo di isotopia.
Si vede anche che le permutazioni di matrici permutative applicate nelle tre direzioni commutano tra di loro. Quindi il gruppo di isotopia dei cubi latini di ordine n `e isomorfo al prodotto diretto Symn× Symn× Symn.
Il gruppo di simmetria dell’insieme dei cubi latini di un ordine n generato dalle parastrofie e dalle isotopie pu`o chiamarsi gruppo di parastrofia-isotopia.
D63:b.08 Procediamo ora a porre in corrispondenza biiettiva cubi latini e quadrati latini.
Sia H un cubo latino; dice mappa sul piano Ox1x2 di H la seguente matrice n × n:
[i, j ∈ [n) :| k Hi,j,k= 1],
Accanto alla precedente si possono considerare le 5 matrici ottenute considerando le altre 5 coppie ordinate di dimensioni per H, cio`e le mappe sui piani Ox2x1, Ox1x3, Ox3x1, Ox2x3ed Ox3x2.
[j, i ∈ [n) :| k Hi,j,k= 1], [i, k ∈ [n) :| j Hi,j,k= 1], [k, i ∈ [n) :| j Hi,j,k= 1], [j, k ∈ [n) :| i Hi,j,k= 1], [k, j ∈ [n) :| i Hi,j,k= 1],
Si osserva anche che le tre proiezioni di un cubo latino K, risp., sui piani Ox1x2, Ox1x3, Ox2x3, sono tre quadrati-L che si possono considerare mappe delle quote della struttura tridimensionale K.
D63:b.09 Le costruzioni precedenti si possono ricondurre facilmente alla prima.
La seconda si ottiene anche come mappa sul piano Ox1x2 del cubo latino ottenuto da H scambiando gli indici delle posizioni 1 e 2, ovvero scambiando le sue dimensioni 1 e 2.
La terza si ottiene come mappa sul piano Ox1x2 del cubo latino ottenuto da H scambiando gli indici delle posizioni 2 e 3,
La quarta si ottiene come mappa sul piano Ox1x2 del cubo latino ottenuto da H con la rotazione di 120◦ intorno all’asse x1= x2= x3.
La quinta si ottiene come mappa sul piano Ox1x2 del cubo latino ottenuto da H con la rotazione inversa della precedente.
Si possono allora dimostrare facilmente i fatti che seguono e che consentono di collegare cubi latini e quadrati latini.
D63:b.10 (1) Prop.: Le mappe di un cubo latino di ordine n sono quadrati-L canonici n × n (2) Prop.: Il passaggio da un cubo latino a ciascuna delle sue 6 mappe `e una biiezione
(3) Prop.: Per un cubo latino invariante per riflessione rispetto al piano x1= x2come mappa rispetto al piano Ox1x2 si ha un quadrato-L simmetrico
(4) Prop.: Per un cubo latino invariante per riflessione rispetto al piano x1= x3come mappa rispetto al piano Ox1x3 si ha un quadrato-L invariante rispetto allo scambio dei ruoli tra righe ed entrate (5) Prop.: Per un cubo latino invariante per riflessione rispetto al piano x2= x3 come mappa rispetto al piano Ox2x3 si ha un quadrato-L invariante rispetto allo scambio dei ruoli tra colonne ed entrate
D63:b.11 Denotiamo con XR,E e con XC,E, risp., le due trasformazioni di quadrati-L che scambiano i ruoli, risp., di righe ed entrate e di colonne ed entrate.
Introduciamo poi XR,C,E:= XC,E◦lrXR,C ed XE,C,R:= XR,E◦lrXR,C.
L’insieme formato dall’identit`a In, XR,C, XR,E, XC,E, XR,C,Eed XE,C,Rviene detto gruppo di parastrofia di Qln.
Le relative orbite in SqL(n)sono dette classi di parastrofia di quadrati-L.
D63:b.12 (1) Prop.: Il quadrato-L XR,E(L) si ottiene da L sostituendo ciascuna delle sue colonne con la sequenza di interi relativa alla permutazione inversa
(2) Prop.: Il quadrato-L XC,E(L) si ottiene da L sostituendo ciascuna delle sue righe con la sequenza di interi relativa alla permutazione inversa
(3) Prop.: Il quadrato-L XR,C,E(L) si ottiene da L sostituendo ciascuna delle sue righe con la sequenza di interi relativa alla permutazione inversa e quindi effettuando la trasposizione della matrice ottenuta
(4) Prop.: Il quadrato-L XE,C,R(L) si ottiene da L sostituendo ciascuna delle sue colonne con la sequenza di interi relativa alla permutazione inversa e quindi effettuando la trasposizione della matrice ottenuta
(5) Prop.: Il passaggio dai cubi latini di ordine n alle loro mappe su uno dei sei piani Oxdxe `e un isomorfismo tra gruppi di parastrofia dei cubi latini di ordine n e di SqL(n)
(6) Prop.: Il gruppo di parastrofia ridotto ai quadrati-L di una classe di parastrofia `e omomorfo di Sym3. Conseguentemente le classi di parastrofia dei quadrati-L sono costituite da 6, 3, 2 elementi o da un solo elemento
D63:b.13 Prop. Sottoporre un quadrato latino a una permutazione ρ delle righe seguita da una permutazione κ delle colonne e da una permutazione η delle entrate equivale a sottoporlo alle tre permutazioni in uno qualsiasi degli altri 5 ordini.
In effetti con tutte le sei possibili trasformazioni si porta L = [i, j ∈ [n) | Li,j] nel quadrato latino [i, j ∈ [n) | η(Lρ(i),κ(j))]
D63:c. quadrati latini standard e quasigruppi
D63:c.01 Tra i quadrati-L ottenibili da L applicando permutazioni delle righe se ne trova esattamente uno, L0, che presenta nella prima colonna la sequenza crescente h0, 1, ..., n − 1i, ovvero che presenta nella colonna etichettata da 0 la Id(n), cio`e la permutazione identica di [n),
Questo L0 si ottiene applicando alle righe di L la permutazione inversa delle permutazione costituente la prima colonna di L stesso.
Dualmente-T, tra i quadrati latini ottenibili permutando le colonne di L se ne trova esattamente uno che presenta nella riga etichettata da 0 la permutazione identica di [n).
D63:c.02 Definiamo come quadrato latino standard di ordine n ogni quadrato latino canonico di ordine n il quale presenta nella prima riga e nella prima colonna la permutazione identica h0, 1, ..., n − 1i.
Denotiamo con SqLS(n)l’insieme di queste matrici ad entrate intere.
Si pu`o ora osservare che un quadrato latino L = [i, j ∈ [n) :| Li,j] si pu`o ricondurre a un quadrato standard prima sottoponendo le sue colonne alla permutazione inversa di quella costituente la sua prima riga, hj ∈ [n) :| L0,ji e quindi sottoponendo le righe del nuovo quadrato alla permutazione che trasforma la prima colonna nella Id(n)(senza modificare la sua prima riga).
Si constata che lo stesso risultato si ottiene effettuando su L prima la permutazione opportuna delle sue righe e successivamente la permutazione sopra indicata delle sue colonne.
A questo punto siamo portati a introdurre la equivalenza Eprc tra quadrati latini di SqL(n) trasfor- mabili l’uno nell’altro mediante una generica permutazione delle sue colonne seguita (o preceduta) da una qualsiasi permutazione delle sue righe.
D63:c.03 Prop. Ogni classe di equivalenza di Eprc `e costituita da n! · (n − 1)! quadrati-L e tra questi esattamente uno `e un quadrato-L standard.
Dim.: Per quanto detto sopra ogni classe di SqL(n)/Eprc contiene almeno un quadrato standard. Me- diante permutazioni di righe e di colonne un quadrato standard L non pu`o essere trasformato in un diverso quadrato standard: infatti una tale trasformazione si potrebbe ottenere con una permutazione delle righe seguita (o preceduta) da una permutazione delle colonne.
Con la prima di queste trasformazioni si deve trasformare una colonna di L nella identit`a Id(n).
D63:c.04 Prop. Se QlSn denota il numero dei quadrati latini standard, si conoscono solo i seguenti valori
n 2 3 4 5 6 7 8 9
QlSn 1 1 4 56 9408 16 942 080 535 281 401 856 377 597 570 964 258 816
n 10 11
QlSn 7 580 721 483 160 132 811 489 280 5 363 937 773 277 371 298 119 673 540 771 840
D63:c.05 prmnt Si `e cercata lungamente una espressione che consentisse di calcolare QlSn per ogni n e solo nel 1992 Jia-yu Shao e Wan-di Wei hanno fornito la seguente formula
QlSn = n! X
A∈Bn
(−1)σ0(A)prmnt(A) n
,
dove Bndenota l’insieme delle matrici binarie di profilo n × n, σ0(A) fornisce il numero degli zeri nella matrice A e prmnt(A) esprime il permanente della A.
Si tratta comunque di una espressione estremamente impegnativa da calcolare per la crescita esponen- ziale del numero degli addendi da prendere in considerazione.
Si conoscono espressioni generali relativamente semplici solo per valutazioni di valori inferiori e valori superiori:
(n!)2n
nn2 ≤ QlSn ≤
n
Y
k=1
(k!)n/k .
D63:d. biparit` a dei quadrati latini
D63:d.01 Ad ogni riga e a ogni colonna dei quadrati latini sopra un insieme X risulta associata la parit`a della permutazione corrispondente. I due vettori delle parit`a delle righe e delle colonne non sono molto sostanziali, in quanto ogni permutazione delle righe e/o delle colonne li pu`o trasformare.
Accade invece che il prodotto delle parit`a delle righe e il prodotto delle parit`a delle colonne sono invarianti per queste trasformazioni e anche per ogni permutazione delle entrate, ossia sono invarianti per parastrofia.
Ogni classe di parastrofia di quadrati-L `e quindi caratterizzata dalla coppia delle parit`a sulle righe e sulle colonne. Tale coppia la chiamiamo biparit`a del quadrato latino.
Evidentemente la trasposizione dei quadrati-L scambia i due componenti della biparit`a.
D63:d.02 Si possono quindi individuare per ogni ordine n 4 insiemi di quadrati-L che denotiamo, risp., con QLn++, con QLn+−, con QLn−+ e con QLn−−,
E poi evidente che i quadrati-L +− e i quadrati-L −+ sono in posti in biiezione dalla trasposizione e` quindi hanno lo stesso cardinale.
Si dimostra poi facilmente che per n dispari le quattro classi di quadrati-L di ordine n sono in biiezione ed hanno gli stessi cardinali.
Accade invece che per n pari il numero di quadrati-L ++ ed il numero di quadrati-L −− sono diversi.
Si constata in particolare che si hanno i seguenti valori
|QL6++| = |QL6+−| = |QL6−+| = 1 776 , |QL6−−| = 4 080 ;
|QL8−−| = |QL8+−| = |QL8−+| = 138 478 485 504 , |QL8−−| = 132 267 638 784 ;
D63:e. quadrati latini dei gruppi
D63:e.01 La tavole di moltiplicazione di ogni gruppo finito di ordine n costituisce un quadrati-L di ordine n.
D63:e.01
D63:f. rompicapo Sudoku e KenKen
D63:f.01 Il Sudoku(wi)`e un rompicapo di origine giapponese che ha conosciuto una diffusione mondiale e una vasta popolarit`a a partire dal 2005.
Al solutore viene proposta una matrice 9 × 9 che in un certo numero k di caselle presenta un intero dell’intervallo I9 := {1, 2, 3, ..., 9} e che ha vuote le restanti 81 − k. Nella matrice si distinguono le 9 sottomatrici di ordine 3 ottenute dall’intersezione di una delle tre terne di righe consecutive con una delle tre terne di colonne consecutive; nel seguito della sezione queste sottomatrici saranno dette regioni.
Al solutore viene richiesto di procedere a riempire ciascuna delle caselle vuote con un intero di I9 in modo di ottenere un quadrato latini di ordine 9 tale che in ciascuna delle 9 regioni compaiano tutti gli interi di I9 (ovviamente ciascuno una volta sola).
In quadrati latini 9 × 9 che soddisfano questa propriet`a saranno detti quadrati Sudoku.
D63:f.02 Dunque il rompicapo Sudoku riguarda il completamento di un quadrato Sudoku incompleto.
La soluzione va ottenuta considerando quali possibili interi di I9 si possono via via aggiungere al quadrato Sudoku incompleto rispettando i vincoli della non ripetizione delle entrate in ciascuna delle 9 righe, in ciascuna delle 9 colonne e in ciascuna delle 9 regioni.
In particolare si cercano caselle nelle quali le entrate presenti ed i vincoli conducono a una sola possibile entrata concessa.
In genere si devono anche considerare quadrati incompleti nei quali alcune caselle contengono segna- lazioni di 2 o pi`u entrate consentite dalle considerazioni sui vincoli che le influenzano; buona parte del lavoro per la soluzione consiste nella progressiva eliminazione delle possibilit`a consentite fino a giungere a determinazioni univoche per le entrate di date caselle.
La soluzione quindi richiede di sviluppare, tendenzialmente procedendo in modo ordinato e organico, considerazioni sulle possibili scelte. Per queste occorre evidentemente effettuare analisi critiche su diverse configurazioni e queste richiedono di seguire logiche piuttosto stringenti. Se si azzardassero tentativi non supportati dalla logica si potrebbero incontrare situazioni erronee che sarebbe troppo complicato cercare di correggere.
Si tratta quindi di un gioco che richiede l’applicazione di considerazioni matematiche riguardanti configurazioni combinatorie (non riguardanti situazioni numeriche, i 9 interi usati per le entrate sono solo degli identificatori di 9 stati per le 81 caselle).
D63:f.03 I quadrati Sudoku incompleti proponibili come istanze del rompicapo devono essere tali da condurre a uno e un solo quadrato Sudoku completo. Non sono considerati proponibili n´e quadrati Sudoku incompleti che non conducono ad alcun quadrato Sudoku completo (rompicapo non risolvibili), n´e quadrati incompleti che possono condurre a pi`u soluzioni (questi sono considerati ambigui).
Dato un quadrato incompleto proponibile, salvo poche eccezioni, si ha la possibilit`a di giungere alla soluzione (unica) attraverso diversi procedimenti inquadrabili in diverse strategie. Per esempio accade di poter scegliere se sistemare per prima una certa riga, oppure un’altra, oppure una colonna, oppure una data entrata.
In linea di massima i quadrati incompleti con poche entrate (ad esempio 20) comportano soluzioni pi`u laboriose di quelli con molte entrate (ad esempio 35). Tuttavia questa corrispondenza non `e assoluta:
pu`o contare molto anche la disposizione delle entrate proposte. Si possono individuare coppie di
quadrati incompleti tali che il meno popolato consente soluzioni attraverso processi meno impegnativi di quelli che permettono di risolvere il pi`u popolato.
D63:f.04 `E interessante individuare le simmetrie dei quadrati Sudoku. Evidentemente la trasposizione e ogni permutazione delle entrate trasformano un quadrato Sudoku in un altro quadrato Sudoku.
Tra le permutazione delle righe sono ammesse solo quelle che trasformano ciascuna delle tre terne h0, 1, 2i, h3, 4, 5i, h678i, in un’altra di tali terne o in una sua permutazione. Stessa considerazione per le permutazione delle colonne.
D63:f.05 Accenniamo anche al pi`u recente rompicapo KenKen proposto nel 2005 da Tetsuya Miyamoto [KenKen(we)]. Al solutore viene proposto una matrice n × n, con n che pu`o assumere un valore intero maggiore o uguale a 3 (non pi`u necessariamente uguale a 9) e che ancora deve essere completata fino a ottenere un quadrato latino. Nella matrice proposta non si ha alcuna entrata, ma viene segnata una partizione delle sue caselle in parti che costituiscono dei poli`omini e che vengono accompagnate da una coppia costituita da un intero positivo e da un segno di operazione numerica. Con tale coppia si chiede che effettuata l’operazione segnalata sopra le entrate del poliomino si otterr`a come risultato l’intero segnalato. In ciascun poliomino si possono avere entrate ripetute, mentre si chiede che ciascuna riga e ciascuna colonna contengano una permutazione di In.
Anche la soluzione di questo rompicapo richiede di procedere sopra ipotesi sulle entrate che devono essere sottoposte a controlli sistematici.
D63:g. sistemi di quadrati latini ortogonali
D63:g.01 Nel 1780 Euler si pose il cosiddetto problema dei 36 ufficiali.
Si tratta di stabilire se si possono disporre 36 ufficiali di 6 gradi diversi e appartenenti a 6 reggimenti diversi in modo da formare uno schieramento quadrato, 6 × 6, in modo che in ogni linea siano rappre- sentati tutti i gradi e tutti i reggimenti.
Euler rappresent`o ogni schieramento con un cosiddetto quadrato greco-latino; in generale una tale confi- gurazione di ordine n `e una matrice n × n in ciascuna casella della quale si trova una coppia costituita da una delle prime n lettere greche e di una delle prime n lettere latine, con la condizione che in ogni linea ogni lettera greca e ogni lettera latina compaia esattamente una volta.
Una tale configurazione equivale a una coppia di quadrati latini, il primo ottenuto limitandosi alle lettere greche, il secondo alle latine. Per inciso segnaliamo che da questa decomposizione deriva lo stesso termine di quadrato latino.
D63:g.02 Definiamo dunque duetto di quadrati latini mutuamente ortogonali, in sigla MOLS, una coppia di quadrati latini dello stesso ordine n, L ed M tale che la collezione delle coppie delle entrate relative alle varie posizioni copra tutte le n2 posibilit`a: {r, c ∈ [n) | hLr,c, Mr,ci} = [n) × [n).
Il problema posto da Euler e la sua congettura relativa all’impossibilit`a di trovare una coppia di MOLS di ordine 6, costituirono un tema ampiamente dibattuto. Nel 1900 Gaston Tarry `e riuscito a dimostrare la non esistenza di una coppia di MOLS di ordine 6. Nel 1943 Henry Mann ha mostrato come costruire una coppia di MOLS per ogni ordine che non fosse il doppio di un numero dispari. Finalmente nel 1960 R. C. Bose, S. S. Shrikhande e E. T. Parker hanno mostrato che il problema degli n2 ufficiali `e irrisolvibile solo per n = 6.
Testi dell’esposizione in http://www.mi.imati.cnr.it/alberto/ e in http://arm.mi.imati.cnr.it/Matexp/
