• Non ci sono risultati.

??βbαanella prima casella della seconda riga la coppia deve avere necessariamente

N/A
N/A
Protected

Academic year: 2021

Condividi "??βbαanella prima casella della seconda riga la coppia deve avere necessariamente"

Copied!
1
0
0

Testo completo

(1)

Matematica Discreta

Lezione del giorno 01 aprile 2009 Quadrati greco-latini.

Abbiamo visto che l’origine della teoria si fa risalire al “problema dei 36 ufficiali” di Eulero (1792):

dati 36 ufficiali di 6 gradi e 6 reggimenti differenti (sono presenti tutte le possibili coppie grado- reggimento) è possibile disporli in un quadrato con 6 righe e 6 colonne, in modo che in nessuna riga e in nessuna colonna vi siano ufficiali dello stesso grado o della stesso reggimento?

Per formalizzare il problema, Eulero indicò con 6 lettere greche i gradi e con 6 lettere latine (cioé dell’usuale alfabeto) i reggimenti.

Si trattava (se possibile) di costruire una matrice 6x6, nelle cui 36 caselle vi fossero tutte le coppie possibili (lettera greca, lettera latina) ma in modo che in nessuna riga né in nessuna colonna vi fossero coppie che avessero in comune il primo o il secondo elemento.

Si può, anche per tentativi, trovare qualche soluzione al problema di Eulero per valori di n diversi da 6.

Per n=3 una soluzione é per esempio (se ,, sono i gradi, e a,b,c i reggimenti):

 

 

βa αc γb

αb γa βc

γc βb αa

Per n=4 una soluzione é per esempio (se ,,, sono i gradi, e a,b,c,d i reggimenti):



 



 

αc βd γa δb

βa αb δc γd

γb δa αd βc

δd γc βb αa

Per n=5 una soluzione é per esempio (se ,,,, sono i gradi, e a,b,c,d,e i reggimenti):

 

 

 

 

 

 

βd γa αe δc εb

γb εc βa αd δe

αc βe δb εa γd

δa αb εd γe βc

εe δd γc βb αa

Notiamo che per n=2 il problema non ha certamente soluzione: se , sono i 2 gradi, e a,b i 2 reggimenti, e se nella prima riga poniamo per esempio le coppie a,b:

 

 

?

? βb αa

nella prima casella della seconda riga la coppia deve avere necessariamente  come primo elemento, b come secondo elemento, ma così ripetiamo la coppia b presente nella prima riga e non possiamo ottenere nella matrice tutte le 4 coppie distinte a,b, b,a.

Dall’uso delle lettere greche e latine nacque la seguente terminologia: dati un insieme A ed un

insieme B entrambi di cardinalità n, un quadrato greco-latino di ordine n é una matrice quadrata

nxn nelle cui caselle vi sono coppie di elementi del prodotto cartesiano AxB in modo che le n

2

caselle contengano coppie tutte diverse (in modo equivalente si può affermare che sono presenti

tutte le possibili n

2

coppie del prodotto cartesiano AxB) e inoltre in nessuna riga né in nessuna

colonna vi siano coppie che abbiano in comune il primo o il secondo elemento.

(2)

Invece di usare lettere greche e latine, spesso oggi i 2 insiemi A,B (la cui natura non influisce ovviamente sul problema) sono uguali all’insieme {1,2,....,n} dei primi n numeri naturali consecutivi.

Con tale convenzione l’esempio precedente di quadrato greco-latino di ordine 3 si può rappresentare nel modo seguente:

 

 

21 13 32

12 31 23

33 22 11

Eulero riuscì a implementare degli algoritmi per costruire quadrati greco-latini di qualunque ordine n che fosse dispari oppure pari ma multiplo di 4.

Non riuscì però a risolvere il problema per numeri pari della forma 2k+4 cioé per i numeri 6,10,14,18,22 etc...

Quindi Eulero fece la seguente congettura: per tutti gli n della forma n=2k+4, non é possibile costruire un quadrato greco-latino di ordine n.

Vedremo però che Eulero si sbagliava.

Tornando all’esempio precedente di quadrato greco-latino di ordine 3:

 

 

21 13 32

12 31 23

33 22 11

possiamo notare che, se “scindiamo” il quadrato in 2 quadrati (considerando nel primo quadrato solo i primi elementi delle coppie e nel secondo quadrato solo i secondi elementi delle coppie) otteniamo i quadrati seguenti:

 

 

2 1 3

1 3 2

3 2 1

 

 

1 3 2

2 1 3

3 2 1

Tali quadrati (essendo ottenuti da un quadrato greco-latino) soddisfano ognuno la proprietà che in nessuna riga né in nessuna colonna vi sono 2 elementi uguali.

Definiremo quadrato latino di ordine n una matrice quadrata nxn nelle cui caselle vi sono elementi scelti da un insieme A di cardinalità n (spesso A={1,2,....,n}) tali che in nessuna riga né in nessuna colonna vi sono 2 elementi uguali.

Dunque i quadrati ottenuti sopra dalla “scissione” di un quadrato greco-latino sono esempi di quadrati latini di ordine 3.

Due quadrati latini di ordine n sono detti ortogonali se la loro sovrapposizione (ottenuta costruendo il quadrato che ha come elementi le coppie di corrispondenti elementi dei 2 quadrati) é un quadrato greco-latino.

Dunque i 2 quadrati precedenti sono esempi di quadrati latini ortogonali di ordine 3.

L’esistenza di 2 quadrati latini ortogonali di ordine n é dunque equivalente all’esistenza di un quadrato greco-latino di ordine n.

Dati 2 quadrati latini di ordine n, l’unica cosa da verificare per concludere che sono ortogonali é che

tutte le coppie di elementi corrispondenti dei 2 quadrati (il primo elemento della coppia nel primo

quadrato, il secondo elemento nel secondo quadrato) siano distinte (in modo che siano presenti

tutte le n

2

coppie possibili).

(3)

La congettura di Eulero, con il linguaggio dei quadrati latini, diventa dunque la seguente: per tutti gli n della forma n=2k+4, non é possibile costruire una coppia di quadrati latini di ordine n.

Nel 1901 Tarry dimostrò che per n=6 tale congettura era in effetti vera: egli ridusse il problema all’esame di particolari quadrati latini di ordine 6, detti “ridotti” (in numero di 9408) e dopo un esame di tali quadrati scoprì che non ne esistevano 2 ortogonali.

Quindi in effetti non é possibile costruire una coppia di quadrati latini ortogonali di ordine 6, dunque non é possibile costruire un quadrato greco-latino di ordine 6 (e il problema dei 36 ufficiali di Eulero non ha soluzione).

Vedremo ora quale relazione scoprì Bose (1938) fra la teoria dei quadrati greco-latini e quella dei piani proiettivi.

Lemma. Siano A, B due quadrati latini ortogonali di ordine n (ad elementi 1,2,....,n). Sia poi b

ij

il generico elemento di B, in riga i e colonna j.

Se f : {1,2….,n}  {1,2,…..,n} è una funzione biunivoca (una cosiddetta “permutazione” di 1,2…,n) allora il quadrato B’ il cui elemento generico in riga i e colonna j é f(b

ij

) é un quadrato latino, ed A, B’ sono ortogonali.

Dim.: se per assurdo B’ non fosse un quadrato latino, vi sarebbero per esempio 2 elementi uguali nella riga i:

f(b

ij

)=f(b

ih

)

e per l’iniettività di f si avrebbe b

ij

=b

ih

, dunque in B vi sarebbero 2 elementi uguali nella riga i contro l’ipotesi che B è un quadrato latino. Analoga contraddizione si ottiene se supponiamo per assurdo l’esistenza di 2 elementi uguali nella colonna j di B.

Se poi per assurdo A, B’ non fossero ortogonali, nel quadrato ottenuto sovrapponendo A e B’ vi sarebbero 2 coppie uguali:

(a

ij

, f(b

ij

)) = (a

ht

, f(b

ht

)) (la prima coppia in riga i, colonna j; la seconda in riga h, colonna t) dacui si dedurrebbe:

a

ij

=a

ht

, f(b

ij

)=f(b

ht

) e per l’iniettività di f:

a

ij

=a

ht

, b

ij

=b

ht

e l’eguaglianza di coppie nel quadrato ottenuto sovrapponendo A e B:

(a

ij

, b

ij

) = (a

ht

, b

ht

)

contro l’ipotesi che A, B sono ortogonali.

Come conseguenza del Lemma, si ha che, dati 2 quadrati latini ortogonali A, B di ordine n, possiamo “trasformare” B in un quadrato latino B’ ortogonale ad A, che ha però come elementi della prima riga i numeri 1,2,....,n nel loro ordine naturale: infatti, se x

1

,...,x

n

sono gli elementi della prima riga di B, basta considerare la permutazione f : {1,2….,n}  {1,2,…..,n} che manda b

1

in 1, b

2

in 2,..., b

n

in n, e applicare il Lemma, per costruire il quadrato B’.

E’ interessante stabilire qual é il massimo numero di quadrati latini di ordine n che siano ortogonali a 2 a 2:

Teorema. Se A

1

, A

2

,..., A

k

sono quadrati latini di ordine n a 2 a 2 ortogonali fra loro, allora necessariamente il loro numero k é  (n-1).

Dim. Applicando k volte il Lemma, possiamo, come notato sopra, trasformare A

1

, A

2

,..., A

k

in altri k quadrati latini B

1

, B

2

,..., B

k

che siano ancora a 2 a 2 ortogonali fra loro.

Dunque la prima riga di ognuno dei quadrati B

1

, B

2

,..., B

k

é formata dagli elementi 1,2,....,n nell’ordine naturale.

Consideriamo l’elemento nella seconda riga e prima colonna di ognuno di tali quadrati B

i

:

(4)

B

i

=

 

 

 

 

 

 

 

 

??

n . . . 2 1

Tale elemento é certamente diverso da 1: se per assurdo fosse =1, nella prima colonna vi sarebbero 2 numeri uguali, contro l’ipotesi che il quadrato B

i

é latino.

Dunque tale elemento nella seconda riga e prima colonna di ognuno dei quadrati B

i

può assumere solo uno degli (n-1) valori 2,3,....,n.

Inoltre non possono esistere due quadrati B

i

, B

j

che abbiano lo stesso elemento x nella seconda riga e prima colonna: se per assurdo così fosse, il quadrato ottenuto sovrapponendo B

i

e B

j

avrebbe nella prima riga le coppie (1,1),(2,2),...,(n,n). e nella casella in seconda riga e prima colonna la coppia (x,x), coppia già certamente presente fra quelle della prima riga, in contraddizione con l’ipotesi che i quadrati latini B

i

, B

j

sono ortogonali.

Riassumendo: l’elemento nella seconda riga e prima colonna di ognuno di tali quadrati B

i

può

assumere solo (n-1) possibili valori, e inoltre tale valore assunto é diverso in ciascuno dei quadrati

B

i

. Si conclude dunque che il numero k dei quadrati B

i

é certamente non superiore a (n-1) cioé la

tesi.

Riferimenti

Documenti correlati

La rappresentazione (GS) di cui sopra per l’inversa di una matrice di Toeplitz, che pu` o essere molto utile per risolvere efficientemente sistemi lineari di Toeplitz [], segue

Un caso in cui è rapido verificare l’equivalenza di una relazione è quando la relazione coincide con la relazione d’equivalenza associata ad una funzione.. Si tratta

Analisi

ü  la somma degli scarti al quadrato dalla media aritmetica assume valore minimo;.. ü  la media dei valori: k⋅x i è pari a la media aritmetica ⋅ k (dove k è

Calcolare il numero delle matrici in X che non soddisfano nessuna delle seguenti condizioni:. a) la terza colonna ha tutti gli elementi nulli; b) la prima riga ha tutti gli

Si basa sul seguente risultato di insiemistica: se A,B sono insiemi finiti, con A=n, B=m, e se n>m , comunque data una funzione f: A → B, esistono sempre almeno 2

Questa eguaglianza ci dice che il numero x di blocchi di un disegno di parametri (v,k,r) dipende dai 3 parametri secondo l’equazione precedente, quindi non può essere

CISQ – Politecnico di Bari - Corso di formazione per RSPP – Modulo 6: Esempio di un insieme PED (ing. Boenzi).. Bari, 3 febbraio