From Wikipedia, the free encyclopedia
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.
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.
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.
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.
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]
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.
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:
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]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.