Vés al contingut

Quadrat grecollatí

De la Viquipèdia, l'enciclopèdia lliure

Un quadrat grecollatí, quadrat d'Euler o quadrats llatins ortogonals d'ordre n és el nom que rep en matemàtiques la disposició en una quadrícula quadrada n × n dels elements de dos conjunts S i T, tots dos amb n elements, on cada cel·la contingui un parell ordenat (s, t), sent s element de S i t de T, de manera que cada element de S i cada element de T aparegui exactament una vegada en cada fila i en cada columna i que no hi hagi dos cel·les que continguin el mateix parell ordenat.

Si els element de S es representen amb caràcters llatins i els de T amb caràcters grecs, la disposició exclusivament dels caràcters llatins o dels grecs forma un quadrat llatí. Un quadrat grecollatí per tant es pot descompondre en dos quadrats llatins "ortogonals". En aquest cas ortogonalitat vol dir que cada un dels parells (s, t) del producte cartesià S × T apareix exactament una vegada.

  • Quadrats grecollatins
  • Ordre 3
    Ordre 3
  • Ordre 4
    Ordre 4
  • Ordre 5
    Ordre 5

Història

[modifica]

Els quadrats llatins ortogonals ja eren coneguts abans d'Euler. Segons cita Donald Knuth en el volum 4 de ”The Art of Computer Programming”,[1] la construcció del conjunt 4x4 va ser publicada per Jacques Ozanam l'any 1725 a “Récréations mathématiques et physiques” en forma de solitari de cartes.[2] El problema consistia a col·locar els asos, reis, reines i jotes d'una baralla de cartes estàndard, en un quadrat 4x4 de manera que en cada fila i en cada columna apareguin els quatre pals i les quatre figures. Aquest problema té diverses solucions.

Una variant comuna a aquest problema era establir la restricció addicional que no es repetís cap pal, ni cap figura en les diagonals principals. Segons Martin Gardner [3][4] el nombre de solucions diferents a aquest problema es va estimar incorrectament per Rouse Ball en 72, (sense comptar girs, ni simetries) i l'error es va mantenir durant molts anys abans que Kathleen Olleren demostrés que el nombre de solucions era 144. Cadascuna de les 144 solucions té 8 reflexions i rotacions i això dona un total de 1.152 solucions. Les 144 x 8 solucions es poden classificar en les dues classes següents:

Solució
Solució 1 {♠|A} {♥|K} {♦|Q} {♣|J}
{♣|Q} {♦|J} {♥|A} {♠|K}
{♥|J} {♠|Q} {♣|K} {♦|A}
{♦|K} {♣|A} {♠|J} {♥|Q}
Solució 2 {♠|A} {♥|K} {♦|Q} {♣|J}
{♦|J} {♣|Q} {♠|K} {♥|A}
{♣|K} {♦|A} {♥|J} {♠|Q}
{♥|Q} {♠|J} {♣|A} {♦|K}

Per a cadascuna de les dues solucions, es poden obtenir 576 (24 × 24) solucions permutant els quatre pals i els quatre valors de forma independent. Cap permutació convertirà les dues solucions en les altres.

El conjunt complet de solucions es pot comprovar mitjançant el següent esquema:

1. Sense pèrdua de generalitat, situem la carta A ♠ a la cantonada superior esquerra.

2. Ara, a la segona fila, les dues primeres caselles no poden ser ni as, ni piques, pel fet que es repetirien en la mateixa columna o diagonal. Per tant, en una de les altres dues caselles ha de ser-hi un as, i en l'altra una pica, ja que la carta A ♠ tampoc es pot repetir.

3. Si optem per la cel·la de la segona fila, tercera columna per a l'as, i es mantenen les restriccions, tindrem la primera solució de les de dalt, tret de la permutació dels pals i valors.

4. Per contra, si triem la cel·la (2,3) per a la pica, i es mantenen les restriccions, obtindrem la segona solució, llevat permutació dels pals i valors.

5. Atès que no hi ha altres possibilitats per a la cel·la (2,3), el conjunt de solucions és complet.

La conjectura d'Euler

[modifica]

Els quadrats llatins ortogonals van ser estudiats en detall per Leonhard Euler, que va emprar per al primer conjunt S = {A, B, C, ...} les primeres n majúscules de l'alfabet llatí, i pel segon conjunt T = {α, β, γ, ...} les primeres lletres n minúscules de l'alfabet grec, d'aquí el nom quadrats grecollatins.

En la dècada de 1780, Euler va demostrar diferents mètodes per a construir quadrats grecollatins, quan n és senar o múltiple de 4. A l'observar que no és possible construir quadrats d'ordre 2 i incapaç de construir un quadrat d'ordre sis (veure el problema dels trenta-sis oficials), va conjecturar que no hi ha quadrats grecollatins cap nombre n ≡ 2 (mod 4) o dit d'una altra manera que n sigui senar de classe par (múltiple de 2 que no és múltiple de 4). La inexistència de quadrats d'ordre 6 va ser confirmada definitivament l'any 1901 per Gaston Tarry[5][6] mitjançant l'enumeració exhaustiva de totes les possibles combinacions de símbols. No obstant això, la solució a la conjectura d'Euler va estar per resoldre durant molt de temps.

Contraexemples a la conjectura d'Euler

[modifica]

El 1959, R. C. Bose i S. S. Shrikhande van construir alguns contraexemples d'ordre 22 seguint punts de vista matemàtics. Poc més tard E. T. Parker va trobar un contraexemple l'ordre de 10 utilitzant en la recerca un UNIVAC (el que fa que sigui un dels primers problemes de combinatòria resolts amb un ordinador digital).

El 1960, Parker, Bose i Shrikhande[7] van demostrar que la conjectura d'Euler és falsa per a tot n ≥ 10. Per tant, hi ha quadrats grecollatins de costat n per a tots els n ≥ 3 excepte n = 6.

Aplicacions

[modifica]

Els quadrats grecollatins s'utilitzen en el disseny d'experiments, la programació de tornejos i la construcció de quadrats màgics. L'escriptor francès Georges Perec va escriure el 1978 la seva novel·la “La Vie mode d'emploi” al voltant d'una casa estructurada com un quadrat grecollatí de 10 × 10.[8]

Quadrats llatins mútuament ortogonals

[modifica]

Els quadrats llatins ortogonals entre si apareixen en moltes situacions. Un conjunt de quadrats llatins, es diuen mútuament ortogonals, si cada parell d'ells són ortogonals entre si.

Qualsevol parell dels següents: text, color de primer pla, color de fons i tipus de lletra formen dos quadrats llatins ortogonals:
riu cama flama pells daurat
daurat riu cama flama pells
pells daurat riu cama flama
flama pells daurat riu caixa
cama flama pells daurat riu

El quadre anterior mostra quatre quadrats llatins mútuament ortogonals d'ordre 5, que representen, respectivament:

Nombre de quadrats llatins mútuament ortogonals

[modifica]

El nombre de quadrats llatins mútuament ortogonals que puguin existir per a un determinat ordre n no és, a hores d'ara, conegut per a qualsevol n, i és una de les àrees d'investigació en combinatòria. Se sap que el nombre de quadrats llatins mútuament ortogonals no pot excedir (n - 1) i aquest límit superior s'assoleix quan n és una potència d'un nombre primer. Ara bé, el mínim és conegut doncs és 2 per a tot n excepte per n = 1, 2 i 6, on és 1. En general el nombre màxim és desconegut per als nombres compostos. Els pocs primers valors a partir de n = 2, 3, 4 [...], 9 són 1, 2, 3, 4, 1, 6, 7, 8, (seqüència A001438 in OEIS). (successió A001438 en OEIS)

S'anomena família completa al conjunt format per n - 1 quadrats llatins d'ordre n mútuament ortogonals. Quan hi ha una família completa per a un determinat ordre n llavors és possible construir un pla projectiu finit d'ordre n i llavors és possible construir una família completa de quadrats llatins mútuament ortogonals d'ordre n.[4]

Vegeu també

[modifica]

Referències

[modifica]
  1. ↑ Knuth, D. The Art of Computer Programming. Reading (MA): Addison-Wesley, 1968. ISBN 0-201-03801-3. 
  2. ↑ Ozanam, J. Récréations mathématiques et physiques, qui contiennent plusieurs problèmes d'arithmétique, de géométrie, de musique, d'optique, de gnomonique, de cosmographie, de mécanique, de pyrotechnique, & de physique. avec un traité des horloges élémentaires. Paris: Claude Jombert, 1725. 
  3. ↑ Gardner, M. A Gardner's Workout: Training the Mind and Entertaining the Spirit. Boca Raton (FL): A K Peters/CRC Press, 2001. ISBN 9781568811208. 
  4. ↑ 4,0 4,1 Gardner, M. Nuevos pasatiempos matematicos. Madrid: Alianza Editorial. ISBN 8420613916. 
  5. ↑ Tarry, G «Le Probléme de 36 Officiers». Compte Rendu de l'Association Française pour l'Avancement de Science Naturel, 1, 1900, pàg. 122 - 123.
  6. ↑ Tarry, G «Le Probléme de 36 Officiers». Compte Rendu de l'Association Française pour l'Avancement de Science Naturel, 2, 1901, pàg. 170 - 203.
  7. ↑ Bose, R. C.; Shrikhande, S. S.; Parker, E. T «Further results on the construction of mutually orthogonal Latin squares and the falsity of Euler's conjecture». Canadian Journal of Mathematics, 1960, pàg. 189 - 203.
  8. ↑ Perec, G. La vida instrucciones de uso. Barcelona: Ed. Anagrama, 1988. ISBN 84-339-3131-8. 
Obtingut de «https://ca.wikipedia.org/w/index.php?title=Quadrat_grecollatí&oldid=30861506»