În matematică, în special în combinatorică, un pătrat latin este un tablou de șah pătrat de latura n cu un simbol pe fiecare casetă, astfel încât fiecare dintre ele apare câte o singură dată în fiecare rând și în fiecare coloană. Un pătrat latin de ordin n poate fi, de asemenea, văzut ca o matrice particulară de n × n componente, într-un set S cu n elemente, cum ar fi {1, ..., n}.

A B C D E
B C E A D
C E D B A
D A B E C
E D A C B

Tabelele de compoziție

modificare
A B C D
B C D A
C D A B
D A B C
A B C D
B A D C
C D A B
D C B A

Tabelele de compoziție ale quasigroup cu n elemente (în special grupuri finite) sunt pătrate latine de ordin n și viceversa: fiecare pătrat latin de ordine n definește o structură quasigroup pe setul S al simbolurilor sale.

În special, deoarece există grupuri finite ale fiecărei cardinalități, există și pătrate latine ale fiecărui ordin.

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

Reprezentare ternară

modificare

Continuând paralela cu tabelele de compoziție, un pătrat latin pe S = {1, ..., n } poate fi, prin urmare, 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ă o singură triplă ( i, j, k ) în R cu cele două coordonate. În mod echivalent, un pătrat latin pe S constă din n 2 tripluri, astfel încât în fiecare pereche de indici perechile posibile de simboluri apar o singură dată:

  • în fiecare casetă există exact un simbol;
  • în fiecare rând, fiecare simbol apare exact o dată;
  • în fiecare coloană fiecare simbol apare exact o dată.

Schimbând între ele două linii, două coloane sau două simboluri (sau, mai general, aplicându-le o transpunere sau o permutare) a unui pătrat latin, obținem din nou un pătrat latin. Două pătrate latine care pot fi obținute unul de la celălalt prin aceste operațiuni se numesc izotopi . isotopie L“este, prin urmare, o relație de echivalență .

În reprezentarea ca relație R, puteți schimba, de asemenea, cele trei rânduri, coloane și indici de simboluri . În special schimbul primelor două corespunde transpunerii matricei.

 
Un pătrat greco-latin

O variantă a pătratului latin este pătratul greco-latin : un tablou de șah pătrat de latură n cu perechi de simboluri pe fiecare pătrat, aranjate astfel încât fiecare simbol să apară unul și o singură dată în fiecare rând și în fiecare coloană și ca fiecare pereche să apară 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 au fost completate cu litere din alfabetul grecesc și latin, de unde și numele greco-latin .

Un pătrat greco-latin poate fi reprezentat de cvadruplările de indici (i, j, k, l) pentru care relația „din caseta (i, j) este perechea (k, l) ”. Un pătrat greco-latin este format din n 2 cvadruple, astfel încât în fiecare pereche de indicii perechile posibile de simboluri apar una și o singură dată.

În 1782 [1] Euler a propus Problema ofițerilor : să plaseze 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 rangurile. Problema ofițerilor este echivalentă cu construcția unui pătrat greco-latin pe partea 6.

Se pot construi pătrate greco-latine de latură n fiecare n mai mare decât 2 și diferit de 6. Euler a demonstrat că se pot construi pătrate greco-latine de ordinul n pentru fiecare n sau multiplu impar de 4, presupunând că acest lucru nu a fost posibil pentru n = 2 (mod 4) . În 1901 [2] Tarry a încercat conjectura pentru n = 6, arătând astfel că problema oficială nu permite o soluție. În 1960 [3] Bose, Parker și Shrikhande, după ce au refuzat deja conjectura Euler, au arătat că problema admite soluție pentru fiecare n = 2 (mod 4) mai mare de 6. <i></i>

Pătratul latin în literatură

modificare

Sestina lirică este o structură poetică formată din 6 camere a 6 versuri fiecare (plus 3 de concediu ). Una dintre regulile conform cărora este construită necesită ca fiecare vers să se încheie cu unul dintre 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 al încăperilor diferite. Scriind aceste cuvinte în interiorul unui pătrat, în funcție de cameră și direcția în care apar, se construiește un pătrat latin.

Camera 1 Camera 2 Camera 3 Camera 4 Camera 5 Camera 6
Versul 1 A F C E D B
Versul 2 B A F C E D
Versul 3 C E D B A F
Versul 4 D B A F C E
Versul 5 E D B A F C
Versul 6 F C E D B A

Romanul "Viața: instrucțiuni de utilizare" al oulipistului Georges Perec folosește din abundență pătratele greco-latine. El descrie o clădire pariziană cu 100 de camere dispuse pe 10 etaje, ca într-o tablă de șah pătrată de latură 10. Fiecare capitol este rezervat pentru nararea unei singure camere. Pentru a scrie romanul Perec, așa cum explică el în al sau Caiet de sarcini, întocmește 42 de liste cu 10 elemente fiecare, corespunzând constrângerilor narative (mobilier, oameni etc.), le împarte în 21 de perechi și atribuie fiecăruia un pătrat greco-latin de latura 10, ale cărei cutii corespund camerelor clădirii. Prin urmare, fiecare cameră este caracterizată de 42 de constrângeri narative .

Vezi și

modificare
  1. ^ Euler, Leonhard, Recherches sur une Nouvelle Espece de Quarres Magiques, Verh. Genootsch. der Wet. 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, 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, Canad. J. Math. 12, 189-203 (1960).

Alte proiecte

modificare

Legături externe

modificare
  • en JH Dénes, AD Keedwell (1974): Latin Squares and their Applications, Academic Press
  • en JH Dénes, AD Keedwell (1991): Pătrate latine. Noi evoluții în teorie și aplicații, Academic Press