Pătrat latin

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

În matematică , în special combinatorică , un pătrat latin este un tabel pătrat al laturii n cu un simbol pe fiecare casetă, aranjat astfel încât fiecare dintre ele să apară o dată și o singură dată în fiecare rând și în fiecare coloană. Un pătrat latin de ordinul n poate fi văzut și ca o matrice componentă n × n specială într-un set S cu n elemente, cum ar fi {1, ..., n }.

LA B. C. D. ȘI
B. C. ȘI LA D.
C. ȘI D. B. LA
D. LA B. ȘI C.
ȘI D. LA C. B.

Tabelele de compoziție

LA B. C. D.
B. C. D. LA
C. D. LA B.
D. LA B. C.
LA B. C. D.
B. LA D. C.
C. D. LA B.
D. C. B. LA

Tabelele de compoziție ale cvasigrupurilor cu n elemente (în special ale grupurilor finite) sunt pătrate latine de ordinul n și invers: fiecare pătrat latin de ordinul n definește o structură cvasigrup pe setul S al simbolurilor sale.

În special, deoarece există grupuri finite de fiecare cardinalitate, există și pătrate latine de fiecare ordine.

Pătratele latine alături sunt obținute din tabelele de compoziție ale grupului ciclic și grupul Klein .

Reprezentarea ternară

Continuând paralela cu tabelele de compoziție, un pătrat latin pe S = {1, ..., n } poate fi deci identificat cu relația ternară R pe S 3 , definită de triplele ( i , j , k ) pentru care « în caseta ( i , j ) se află simbolul k ».

Pentru definiția pătratului latin, fiecare proiecție a lui R pe două coordonate este injectivă, adică pentru fiecare alegere a două coordonate există una și o singură triplă ( i , j , k ) în R cu acele două coordonate. În mod echivalent, un pătrat latin pe S este alcătuit din n 2 triple, astfel încât în ​​fiecare pereche de indici posibilele perechi de simboluri apar o singură dată:

  • în fiecare casetă există exact un simbol;
  • în fiecare linie fiecare simbol apare exact o dată;
  • în fiecare coloană fiecare simbol apare exact o dată.

Echivalențe

Schimbând două linii, două coloane sau două simboluri (sau mai general aplicându-le o transpunere sau o permutare) a unui pătrat latin, se obține din nou un pătrat latin. Două pătrate latine care pot fi obținute una de la alta prin aceste operații se numesc izotopi . Prin urmare, izotopia este o relație de echivalență .

În reprezentarea ca relație R , cei trei indici de rând , coloană și simbol pot fi de asemenea schimbați. În special, schimbul primelor două corespunde transpunerii matricei.

Un pătrat greco-latin

Pătratul greco-latin

O variantă a pătratului latin este pătratul greco-latin : o tablă de șah pătrată cu latura n cu perechi de simboluri pe fiecare pătrat, aranjate astfel încât fiecare simbol să apară o singură dată și o singură dată în fiecare rând și în fiecare coloană și să apară fiecare pereche o singură dată.

Fiecare pătrat greco-latin este dat de o pereche de pătrate latine „ortogonale”. Inițial, cele două pătrate latine erau umplute, respectiv, cu litere din alfabetele greacă și latină, de unde și denumirea greco-latină .

Un pătrat greco-latin poate fi reprezentat de cvadrupluri de indici (i, j, k, l) pentru care se ține relația "în caseta (i, j) există perechea (k, l) ". Un pătrat greco-latin este format din n 2 cvadrupluri, astfel încât în ​​fiecare pereche de indici posibilele perechi de simboluri apar o singură dată.

În 1782 [1] Euler a propus problema ofițerilor : să aranjeze pe o tablă de șah 36 de ofițeri aparținând 6 regimente diferite și cu 6 grade diferite, astfel încât în ​​fiecare rând și în fiecare coloană să fie reprezentate toate regimentele și toate gradele. Problema ofițerilor este echivalentă cu construirea unui pătrat greco-latin cu latura 6.

Este posibil să construim pătrate greco-latine de latură n pentru fiecare n mai mare de 2 și diferit de 6. Euler a arătat că pătrate greco-latine de ordinul n pot fi construite pentru fiecare n impar sau multiplu de 4, conjecturând că acest lucru nu a fost posibil pentru n = 2 (forma 4) . În 1901 [2] Tarry a dovedit conjectura pentru n = 6, arătând astfel că problema ofițerilor nu admite nicio soluție. În 1960 [3] Bose , Parker și Shrikhande , după ce au respins deja conjectura lui Euler, au arătat că problema admite o soluție pentru fiecare n = 2 (mod 4) mai mare de 6.

Pătratul latin în literatură

Sestina lirică este o structură poetică formată din 6 strofe de 6 rânduri (plus 3 de concediu ). Una dintre regulile conform cărora este construit prevede că fiecare verset se termină cu unul din cele 6 cuvinte posibile, care nu pot apărea de două ori în aceeași cameră, și nici de două ori în același verset în camere diferite. Scriind aceste cuvinte în interiorul unui pătrat, în funcție de cameră și de direcția în care apar, se construiește un pătrat latin.

Camera 1 Camera 2 Camera 3 Camera 4 Camera 5 Camera 6
Versetul 1 LA F. C. ȘI D. B.
Versetul 2 B. LA F. C. ȘI D.
Versetul 3 C. ȘI D. B. LA F.
Versetul 4 D. B. LA F. C. ȘI
Versetul 5 ȘI D. B. LA F. C.
Versetul 6 F. C. ȘI D. B. LA

Romanul Viața: instrucțiuni pentru utilizarea oulipista Georges Perec folosește abundent pătratele greco-latine. Descrie o clădire pariziană de 100 de camere pe 10 etaje, ca într-o tablă de șah pătrată cu latura 10. Fiecare capitol este rezervat pentru narațiunea unei singure camere. Pentru a scrie romanul Perec, așa cum explică în Cahier des charges , întocmește 42 de liste de câte 10 elemente, corespunzătoare constrângerilor narative (mobilier, oameni etc.), le împarte în 21 de perechi și atribuie fiecăruia un greco-latin pătrat de latura 10, ale cărui cutii corespund camerelor clădirii. Prin urmare, fiecare cameră este caracterizată de 42 de constrângeri narative .

Notă

  1. ^ Euler, Leonhard, Recherches sur une Nouvelle Espece de Quarres Magiques , Verh. Genootsch. der Umed. Vlissingen, 9, 85-232 (1782).
  2. ^ Tarry, G., Le Problème de 36 Officiers , Comptes Rendu de l'Association Française pour l'Avancement de Science Naturel 1, 122-123 (1900); 2, 170-203 (1901).
  3. ^ Bose, RC; Shrikhande, SS; Parker, ET, Rezultate suplimentare privind construcția de pătrate latine ortogonale reciproc și falsitatea conjecturii lui Euler , Canad. J. Math. 12, 189-203 (1960).

Bibliografie

  • ( EN ) JH Dénes, AD Keedwell (1974): Latin Squares and their Applications , Academic Press
  • ( EN ) JH Dénes, AD Keedwell (1991): Latin Squares. Noi dezvoltări în teorie și aplicații , Academic Press

Elemente conexe

Alte proiecte

linkuri externe

Controlul autorității GND (DE) 4166852-2 · BNF (FR) cb119596221 (data)
Matematica Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică