Pătrat latin

Pătratul latin de ordinul al n -lea este un tabel L=(l ij ) de dimensiunea n × n umplut cu n elemente ale mulțimii M în așa fel încât în fiecare rând și fiecare coloană a tabelului fiecare element din M să apară exact o dată . . Un exemplu de pătrat latin de ordinul 3:

{\begin{bmatrix}A&B&C\\C&A&B\\B&C&A\\\end{bmatrix}}

care poate fi reprezentat ca {(1,1,A), (1,2,B), (1,3,C), (2,1,C), (2,2,A), (2, 3) ,B), (3,1,B), (3,2,C), (3,3,A)}, unde primul și al doilea element sunt poziția elementului în matrice, iar al treilea este valoare.

În prezent, mulțimea M este de obicei luată ca mulțime de numere naturale {1,2,…, n } sau mulțimea {0,1,…, n -1}, totuși, Leonard Euler a folosit literele alfabetului latin , de la care și-au luat numele pătratele latine . [unu]

Pătratele latine există pentru orice n , este suficient să luăm tabelul Cayley al unui grup de ordin n , de exemplu, . $l_{ij}=(i+j-1){\pmod {n))$

Istoria cercetărilor asupra pătratelor latine

Primele pătrate latine (de ordinul 4) au fost publicate în cartea „ Shams al Ma’arif ” („Cartea Soarelui Gnozei”), scrisă de Ahmad al-Buni în Egipt în jurul anului 1200.

Perechile de pătrate latine ortogonale au fost menționate pentru prima dată de Jacques Ozanam în 1725. [2] Cartea, care este o colecție de probleme de fizică și matematică, conține următoarea problemă:

Este necesar să plasați 16 cărți de joc de ași, regi, dame și valeți din toate cele patru culori sub forma unui pătrat, astfel încât toate culorile și cărțile de toate denominațiile să apară în fiecare rând și coloană exact o dată.

Această problemă are 6912 soluții (dacă în plus solicităm ca și diagonalele pătratului să îndeplinească aceeași condiție, atunci numărul de soluții va scădea cu un factor de 6 și va deveni egal cu 1152).

O piatră de hotar importantă în istoria studiului pătratelor latine a fost opera lui Euler [1] . În el, a lucrat la metode de construire a pătratelor magice și a propus o metodă bazată pe o pereche de pătrate latine ortogonale. Studiind astfel de perechi, Euler a descoperit că problema construcției lor este împărțită în trei cazuri, în funcție de restul împărțirii numărului n la 4. El a propus metode de construire a perechilor de pătrate ortogonale pentru n divizibil cu 4 și pentru n impar . Este evident că pentru n = 2 astfel de perechi nu există. El nu a reușit să construiască perechi de pătrate ortogonale latine pentru n = 6, 10 și a presupus că nu există perechi de pătrate ortogonale pentru n = 4 t +2. Pentru n = 6, el a formulat „problema ofițerilor 36”:

Este necesar să plasați 36 de ofițeri din șase regimente diferite și șase grade militare diferite într-un pătrat, astfel încât în fiecare coloană și în fiecare rând să existe exact un ofițer din fiecare regiment și fiecare grad militar.

În 1890, Cayley a derivat o formulă cu două linii pentru numărul de dreptunghiuri latine (un caz special al „ problemei de întâlnire ” combinatorii clasice, pusă de P. Montmort în 1708). [3]

În 1900, conjectura lui Euler pentru n = 6 a fost confirmată de G. Tarry . [4] El a construit toate cele 9408 pătrate latine normalizate, le-a împărțit în 17 tipuri și a arătat că este imposibil să construiești o pereche de pătrate ortogonale pentru orice combinație a acestora. Astfel, a rezolvat „ problema celor 36 de ofițeri ” în sens negativ .

În 1922, MacNeish a fost primul care a aplicat o abordare teoretică de grup pentru rezolvarea problemelor cu pătratul latin. [5] În special, el a propus o metodă de construire a pătratelor latine de ordinul n1•n2 din pătratele latine de ordinul n1 și n2 , păstrând în același timp proprietatea de ortogonalitate.

În 1925, Ronald Fisher a propus utilizarea pătratelor latine ortogonale pentru planificarea experimentelor agricole. [6]

În anii 1920-1930, structurile algebrice neasociative au început să fie studiate intens, ceea ce a condus, în special, la crearea teoriei cvasigrupurilor , strâns legată de studiul pătratelor latine, deoarece există o corespondență unu-la-unu. între pătratele latine și tabelele Cayley ale cvasigrupurilor .

În 1959, Bose și Shrikhande au construit 2 pătrate latine ortogonale pentru n = 22, iar în 1960 ei și Parker au construit un contraexemplu minim pentru n = 10 folosind un computer . Astfel, după 177 de ani, conjectura lui Euler a fost respinsă. [7]

Numărul de pătrate latine

Formula exactă pentru numărul L ( n ) de ordinul n pătrate latine nu este cunoscută. Cele mai bune estimări pentru L ( n ) sunt date de formula

\prod _{{k=1}}^{n}\left(k!\right)^{{n/k}}\geq L(n)\geq {\frac {\left(n!\right) ^{{2n}}}{n^{{n^{2}}}}}

[opt]

Fiecare pătrat latin poate fi asociat cu un pătrat latin normalizat (sau redus) al cărui prim rând și prima coloană sunt completate în conformitate cu ordinea dată pe mulțimea M . Un exemplu de pătrat latin normalizat:

{\begin{bmatrix}A&B&C\\B&C&A\\C&A&B\\\end{bmatrix}}

Numărul R(n) de pătrate latine normalizate de ordinul n (secvența A000315 în OEIS ) în n!(n-1)! ori mai mică decât L(n) (secvența A002860 în OEIS ).

Valorile exacte ale lui L(n) sunt cunoscute pentru n de la 1 la 11: [9]

Numărul de pătrate latine

n	R(n)	L(n)	Autor și anul
unu	unu	unu
2	unu	2
3	unu	12
patru	patru	576
5	56	161280	Euler (1782)
6	9408	812851200	Frolov (1890)
7	16942080	61479419904000	Sade (1948)
opt	535281401856	108776032459082956800	Wells (1967)
9	377597570964258816	5524751496156892842531225600	Bammel și Rothstein (1975)
zece	7580721483160132811489280	9982437658213039871725064756920320000	McKay și Rogoyski (1995)
unsprezece	5363937773277371298119673540771840	776966836171770144107444346734230682311065600000	McKay și Wanless (2005)

Relații de echivalență pe mulțimea pătratelor latine

Două pătrate latine se numesc izotop dacă unul dintre ele poate fi obținut din celălalt ca urmare a unei izotopii - o compoziție din permutarea rândurilor, permutarea coloanelor și înlocuirea elementelor mulțimii M prin substituție din grupul simetric S(M ) .

O izotopie este o relație de echivalență , astfel încât mulțimea de pătrate latine de ordinul al n-lea se descompune în clase de izotopie disjunse. Dintr-un pătrat latin, puteți obține 3 echivalenți folosind izotopia ( n !) , dar unele dintre ele pot coincide cu cel original, aceasta se numește autoparatopie. Proporția pătratelor latine cu un grup de autoparatopie netrivial tinde spre zero pe măsură ce n crește . [9]

Pătratul latin poate fi gândit ca o matrice ortogonală . Schimbând ordinea elementelor din fiecare triplă ordonată a acestui tablou, puteți obține 6 pătrate latine, care sunt numite parastrofe. În special, pătratul latin obținut ca urmare a transpunerii este o parastrofă.

Compoziția izotopiei și parastrofiei se numește izostrofie. Aceasta este o altă relație de echivalență, clasele sale sunt numite clase principale. Fiecare clasă principală conține 1, 2, 3 sau 6 clase izotopice. În cazul coincidenței pătratului latin original și a celui izostrofic, se vorbește de autostrofie. Pe măsură ce n crește, aproape toate pătratele latine au grupul trivial de autostrofie. [zece]

Numărul de clase de echivalență

n	Numărul claselor principale	Numărul de clase izotopice
unu	unu	unu
2	unu	unu
3	unu	unu
patru	2	2
5	2	2
6	12	22
7	147	564
opt	283657	1676267
9	19270853541	115618721533
zece	34817397894749939	208904371354363006
unsprezece	2036029552582883134196099	12216177315369229261482540

Pătrate latine ortogonale

Două pătrate latine L=(l ij ) și K=(k ij ) de ordinul n se numesc ortogonale dacă toate perechile ordonate (l ij ,k ij ) sunt diferite. Un exemplu de două pătrate latine ortogonale și perechile lor ordonate corespunzătoare:

{\begin{bmatrix}1&2&3\\2&3&1\\3&1&2\\\end{bmatrix}}\quad \quad {\begin{bmatrix}1&2&3\\3&1&2\\2&3&1\\\end{bmatrix}}\quad \quad {\begin{bmatrix}(1,1)&(2,2)&(3,3)\\(2,3)&(3,1)&(1,2)\\(3,2)& (1,3)&(2,1)\\\end{bmatrix}}

Euler a numit astfel de pătrate „complete”. În cinstea lui, în literatura științifică, ele erau numite „Eulerian” sau „grecolatin” (de vreme ce Euler folosea literele alfabetului grecesc pentru pătratul ortogonal cu cel latin).

Pătratele latine ortogonale există pentru orice n care nu este egal cu 2 și 6.

Un pătrat latin L de ordinul n are un pătrat ortogonal cu el dacă și numai dacă există n transversale disjunse în L.

De interes deosebit în legătură cu numeroase aplicații sunt seturile de mai multe pătrate latine ortogonale în perechi de ordinul n . Puterea maximă posibilă N(n) a unei astfel de mulțimi este n -1, caz în care mulțimea se numește completă.

Deoarece n tinde spre ∞, N(n) tinde și spre ∞.

Pentru n , care este o putere a unui număr prim , există întotdeauna un set complet de pătrate latine ortogonale în perechi, acesta poate fi mapat unu-la-unu la un plan proiectiv finit de ordinul n . Pentru a-l construi, se folosește metoda Bose, care folosește valorile polinoamelor din formular pentru umplerea pătratelor cu a diferit de zero peste câmp . [11] Un exemplu de construire a unui set complet de pătrate latine ortogonale în perechi de ordinul al 4-lea ( d este rădăcina unui polinom primitiv peste ): $f_{a}(x,y)=ax+y$ ${\mathrm {GF}}(n)$ $x^{2}+x+1$ ${\mathrm {GF}}(2)$

{\begin{bmatrix}0&1&d&d+1\\1&0&d+1&d\\d&d+1&0&1\\d+1&d&1&0\\\end{bmatrix}}\quad \quad {\begin{bmatrix}0&1&d&d+1\\d&d+1&0&1 \\d+1&d&1&0\\1&0&d+1&d\\\end{bmatrix}}\quad \quad {\begin{bmatrix}0&1&d&d+1\\d+1&d&1&0\\1&0&d+1&d\\d&d+1&0&1\\\end {bmatrix}}

Dacă n ≡ 1 (mod 4) sau n ≡ 2 (mod 4) și partea fără pătrat a lui n conține cel puțin un factor prim p ≡ 3 (mod 4), atunci pentru astfel de n nu există un set complet de perechi ortogonale pătrate latine.

Limitele inferioare cunoscute pentru numărul N(n) pentru n < 33 sunt date în următorul tabel (limitele care pot fi îmbunătățite sunt evidențiate):

Limitele inferioare ale numărului N(n)

n	unu	2	3	patru	5	6	7	opt	9	zece	unsprezece	12	13	paisprezece	cincisprezece	16	17	optsprezece	19	douăzeci	21	22	23	24	25	26	27	28	29	treizeci	31	32
N(n)≥			2	3	patru		6	7	opt	2	zece	5	12	3	patru	cincisprezece	16	3	optsprezece	patru	5	3	22	6	24	patru	26	5	28	patru	treizeci	31

Construcția pătratelor ortogonale este o problemă combinatorie complexă. Pentru rezolvarea acesteia se folosesc atât construcții algebrice, cât și combinatorii (transversale, tablouri ortogonale, desene, diagrame bloc, triple Steiner etc.) Există mai multe abordări pentru rezolvarea acestei probleme, acestea putând fi împărțite în două grupe. Primul grup include metode bazate pe alegerea unui pătrat latin de bază la care se caută pătrate latine ortogonale izotopice. De exemplu, cinci pătrate latine ortogonale în perechi de ordinul 12 au fost găsite ca rezultat al construirii a patru ortomorfisme ale grupului abelian , care este un produs direct al grupurilor ciclice de ordine 6 și 2. [12]

Al doilea grup include metode care utilizează obiecte combinatorii (inclusiv pătratele latine în sine) de ordine inferioară pentru a construi pătrate latine ortogonale. De exemplu, două pătrate latine de ordinul 22 au fost construite de Bose și Shrikhande pe baza a două modele de ordinul 15 și 7.

Pătrate latine diagonale

Un pătrat latin se numește diagonală dacă, pe lângă cerințele de unicitate a elementelor din rânduri și coloane, caracteristice pătratului latin, se adaugă și cerințele de unicitate a elementelor de pe diagonalele principale și secundare [13] . O estimare analitică a numărului de pătrate latine diagonale este necunoscută, numărul acestora pentru dimensiunile N<10 a fost determinat în 2016 în proiectul de calcul distribuit voluntar Gerasim@Home [14] [15] [16] (secvența A274171 în OEIS și secvența A274806 în OEIS ). Pentru pătratele latine diagonale, precum și pentru pătratele latine pur și simplu, este posibil să se construiască perechi ortogonale, dintre care unele (aproximativ 9 și 10) au fost găsite în proiectul de calcul distribuit voluntar SAT@home folosind abordarea SAT . În prezent, căutarea perechilor de pătrate latine diagonale ortogonale de ordinul 10 se realizează în proiectul de calcul distribuit voluntar Gerasim@Home folosind transversale [17] , precum și în proiectele BOINC ODLK [18] și ODLK1 [19] . La 25 aprilie 2018, a fost găsit un pătrat latin diagonal de ordinul 10 care are 10 pătrate latine diagonale ortogonale [20] . Acesta este numărul maxim cunoscut de pătrate diagonale ortogonale într-un pătrat latin de ordinul 10 diagonale ( secvența OEIS A287695 ). O problemă matematică deschisă este existența unui triplu de pătrate latine diagonale ortogonale pe perechi de ordinul 10 (în prezent, cea mai bună aproximare a soluției sale este un triplu de pătrate, în care două perechi de pătrate sunt ortogonale, iar a treia este parțial ortogonală în 74 de celule [21] ).

pătrate parțiale

Un pătrat în care fiecare element al mulțimii M apare cel mult o dată pe fiecare rând și fiecare coloană se numește pătrat parțial.

Problema recunoașterii dacă un pătrat parțial poate fi completat în latină este NP-complet .

Se introduce conceptul de mulțime critică corespunzătoare unui pătrat parțial, care poate fi completat unic cu cel latin, și niciun submulț al acestuia nu satisface condiția de unicitate. [22] Cardinalitatea C(n) a mulțimii critice pentru n × n pătrate este cunoscută pentru n < 7:

Cardinalitatea setului critic

n	unu	2	3	patru	5	6
C(n)	0	unu	3	7	unsprezece	optsprezece

Probleme nerezolvate

Pe lângă problema găsirii unei formule pentru valoarea L ( n ), există un număr mare de probleme nerezolvate referitoare la pătratele latine. O serie de astfel de sarcini au fost formulate la conferința Loops'03:

O estimare pentru numărul maxim de transversale dintr-un pătrat latin de ordinul n
Caracterizarea subpătratelor latine în tabla înmulțirii buclelor Moufang
O estimare a densității unui pătrat parțial care satisface proprietatea Blackburn
Calcularea maximului t(n) astfel încât 2 t(n) să împartă valoarea L ( n )

Aplicație

Pătratele latine sunt utilizate pe scară largă în algebră, combinatorică, statistică, criptografie, teoria codurilor și multe alte domenii.

Aplicație în criptografie. Protocol de cunoștințe zero

În prezent, pătratele latine sunt utilizate în mod activ pentru a implementa protocoale cu cunoștințe zero. În special pentru generarea MAC .
Fie q ={1,2,…, n }. Pentru un pătrat latin dat

LS= \begin{bmatrix} l_{1,1} & ... & l_{1,q} \\ . & ... & . \\ l_{q,1} & ... & l_{q,q} \\ \end{bmatrix}

b = q/2 variantele LS sunt izotopice unele față de altele.

Să presupunem că utilizatorii formează o rețea. are o cheie publică și (notăm două pătrate latine izotopice de ordinul n) și o cheie secretă (notăm izotopismul peste ). vrea să demonstreze autenticitatea , dar nu vrea să dezvăluie cheia secretă ( dovada zero-cunoștințe ). $(u_1, u_2, ..., u_k)$ $tu_{i}$ $L_ui$ $L'_ui$ $I_ui$ $L_ui$ $L'_ui$ $tu_{i}$ $u_{j}$

1. rearanjează aleatoriu și primește un alt pătrat latin H 2. trimite H la 3. cere fie: - să demonstreze că H și sunt izotopice - să demonstreze că H și sunt izotopice 4. îndeplinește cererea. El sau - demonstrează că H și sunt izotopice - demonstrează că H și sunt izotopice 5. și repetă pașii de 1-4 n ori $tu_{i}$ $L_ui$
$tu_{i}$ $u_{j}$
$u_{j}$ $tu_{i}$
$L'_ui$
$L_ui$
$tu_{i}$
$L'_ui$
$L_ui$
$tu_{i}$ $u_{j}$

Mai jos este pseudocodul pentru calcularea funcției hash

pentru k de la 1 la q începe d_k = 1 ; sfârşitul pentru i de la 1 la q începe pentru j de la 1 la q începe pentru k de la 1 la b începe d_l_ji = m_ij * d_l_ji ; sfârșit sfârșit sfârșit

Suma hash va fi în vectorul D=[ ] Exemplu de utilizare: Fie q =8, b =4 $d_1,...,d_n$

LS={\begin{bmatrix}1&7&3&8&5&6&4&2\\2&5&4&6&7&8&3&1\\3&8&1&7&6&5&2&4\\4&6&2&5&8&7&1&3\\7&1&8&3&4&2&5&6\\8&3&7&1&2&4&6&5\\5&2&6&4&3&1&7&8\\6&4&5&2&1&3&8&7\\\end{bmatrix}}

LS^{1}={\begin{bmatrix}7&1&8&3&4&2&5&6\\5&2&6&4&3&1&7&8\\1&7&3&8&5&6&4&2\\3&8&1&7&6&5&2&4\\8&3&7&1&4&4&6&5\\6&4&5&2&1&3&8&7\\2&5&4&6&7&8&3&1\\4&6&2&5&8&7&1&3\\\end{bmatrix}}

LS^{2}={\begin{bmatrix}8&3&7&1&2&4&6&5\\4&6&2&5&8&7&1&3\\5&2&6&4&3&1&7&8\\1&7&3&8&5&6&4&2\\7&1&8&3&4&2&5&6\\3&8&1&7&6&5&2&4\\6&4&5&2&1&3&8&7\\2&5&4&6&3&8&3&1\\\end{bmatrix}}

și

LS^{3}={\begin{bmatrix}1&7&3&8&5&6&4&2\\3&8&1&7&6&5&2&4\\7&1&8&3&4&2&5&6\\5&2&6&4&3&1&7&8\\2&5&4&6&7&8&3&1\\4&6&2&5&8&7&1&3\\8&3&7&1&2&4&6&5\\6&4&5&2&1&3&8&7\\\end{bmatrix}}

LS^{4}={\begin{bmatrix}4&6&2&5&8&7&1&3\\2&5&4&6&7&8&3&1\\6&4&5&2&1&3&8&7\\8&3&7&1&2&4&6&5\\3&8&1&7&6&5&2&4\\1&7&3&8&5&6&4&2\\5&2&6&4&3&1&7&8\\7&1&8&3&4&2&5&6\\\end{bmatrix}}

Să presupunem că este trimis următorul mesaj:

M={\begin{bmatrix}3&2&5&4&1&2&1&6\\7&8&4&5&2&3&3&1\\4&8&6&7&5&4&3&2\\1&4&5&7&8&6&6&6\\7&1&2&8&7&3&4&5\\7&8&1&1&8&2&6&5\\3&4&8&1&2&3&7&6\\2&4&5&3&3&6&8&7\\\end{bmatrix}}

Mutați rândurile pentru a obține matrice de la la $LS^{1}$ $LS^{4}$
$RP^{1}={\begin{bmatrix}5&7&1&3&6&8&2&4\\\end{bmatrix}}$
$RP^{2}={\begin{bmatrix}6&4&7&1&5&3&8&2\\\end{bmatrix}}$
$RP^{3}={\begin{bmatrix}1&3&5&7&2&4&6&8\\\end{bmatrix}}$
$RP^{4}={\begin{bmatrix}4&2&8&6&3&1&7&5\\\end{bmatrix}}$

Să setăm un vector Și vom calcula hash -ul conform algoritmului dat mai sus: Obținem $D={\begin{bmatrix}1&1&1&1&1&1&1&1\\\end{bmatrix}}$

$D={\begin{bmatrix}1&7&5&4&4&5&8&1\\\end{bmatrix}}$

Aplicație în criptografie. Schema de partajare secretă

O schemă de partajare a secretelor în care cheia este pătratul latin al ordinului . Pătratul latin este ținut secret. Între timp, ordinea pătratului latin este publicată pentru toată lumea. Partajarea secretelor se bazează pe pătratele latine parțiale ={ | seturi critice }. Unirea poate fi compusa din toate multimile critice posibile L sau din multimea multimilor critice. Numărul de seturi critice depinde de ordinea pătratului latin și de numărul de participanți care participă la schemă. Protocol: Se alege un pătrat latin L. Este dezvăluită ordinea lui n, dar pătratul latin în sine este ținut secret și folosit ca cheie. Mulțimea S este uniunea mulțimilor critice L. Fiecare participant primește o cotă (i, j, k) . Când participanții se adună, își pot pune piesele împreună și pot reconstrui pătratul L. Exemplu: Selectați trei pătrate parțiale: $L$ $n$ $S$ $A_{{i}}$ $A_{{i}}$ $L$

$C_{1}, C_{2}, C_{3}$

\begin{bmatrix} 0 & . & . \\ . & 2 & . \\ . & . & . \\ \end{bmatrix} \quad\quad \begin{bmatrix} . & . & . \\ . & 2 & . \\ . & . & 1 \\ \end{bmatrix} \quad\quad \begin{bmatrix} 0 & . & . \\ . & . & . \\ . & . & 1 \\ \end{bmatrix}

Și un L pătrat întreg

0	unu	2
unu	2	0
2	0	unu

Putem verifica cu ușurință că toate pătratele latine parțiale , , sunt mulțimi critice. Ele pot fi extinse în mod unic la un pătrat latin complet L. Această proprietate unică se pierde dacă orice element al oricărui pătrat latin parțial , , este eliminat. Fie unirea a trei multimi critice , , . Atunci = . Distribuim părți din . Oricare doi participanți pot restaura întregul pătrat latin. Exemplul simplu obținut mai sus poate fi extins la cazul general. În 1979, pătratul latin a fost propus ca un bun candidat pentru utilizare în scheme de distribuție secretă. Cu toate acestea, există anumite limitări ale aplicării sale, așa cum este descris mai jos. 1) Imediat după distribuirea părților setului critic, informațiile parțiale vor fi disponibile oricărui grup neautorizat. Aceasta înseamnă că există șanse mari ca orice grup neautorizat să descopere restul pieselor prin încercare și eroare. Astfel, schema propusă nu este ideală. 2) Circuitul nu este flexibil. În acest caz, este doar o schemă secretă de împărțire. Hashing Dacă dorim să folosim o sumă hash pentru a stoca un pătrat secret fix, cum ar fi un pătrat latin de ordinul 10, trebuie să stocăm 81 de numere (ultimul rând și coloană sunt opționale). Patru biți pot fi folosiți pentru a stoca un rând, așa că avem nevoie de 324 de biți. În acest caz, putem alege SHA-384 sau SHA-512 . Dacă trebuie să folosim SHA-256 , putem proceda după cum urmează. 10 biți vor fi folosiți pentru a reprezenta al 3-lea număr. Așa că am folosit mai întâi 250 de biți pentru a reprezenta 75 de numere și apoi următorii 4 biți pentru a reprezenta un număr. În total, putem stoca 76 de numere. Fixăm un pătrat latin parțial în următorul format. Să alegem un pătrat latin de ordinul 10, care poate fi restaurat în mod unic prin ștergerea intrărilor, așa cum se arată în tabel. Argumentul aici este că un mic procent de pătrate latine, ordinul 10, nu poate fi reconstruit în mod unic și, prin urmare, nu poate fi ales ca un secret. $C_{1}$ $C_{2}$ $C_{{3}}$ $C_{1}$ $C_{2}$ $C_{{3}}$
$S$ $C_{1}$ $C_{2}$ $C_{{3}}$ $S$ ${(1, 1, 1), (2, 2, 3), (3, 3, 2)}$
$S$

X	X	X	X	X	X	X	X	X	.
X	X	X	X	X	X	X	X	X	.
X	X	X	X	X	X	X	X	X	.
X	X	X	X	X	X	X	X	X	.
X	X	X	X	X	X	X	X	.	.
X	X	X	X	X	X	X	X	.	.
X	X	X	X	X	X	X	X	.	.
X	X	X	X	X	X	X	X	.	.
X	X	X	X	X	X	X	X	.	.
.	.	.	.	.	.	.	.	.	.

Jocuri și puzzle-uri cu pătrate latine

Există o serie de jocuri care folosesc pătrate latine. Cel mai cunoscut dintre acestea este Sudoku . Necesită ca un pătrat parțial să fie completat cu un pătrat latin de ordinul al 9-lea, care are proprietatea suplimentară că toate cele nouă subpătrate ale sale conțin toate numerele naturale de la 1 la 9 o dată.

De asemenea, populare sunt problemele construcției de pătrate latine și, pe baza lor, pătrate magice cu proprietăți suplimentare (de exemplu, pătrate diagonale).

Vezi si

matrice ortogonală
pătrat magic
Sudoku
SAT@home este un proiect de calcul distribuit care caută perechi ortogonale de pătrate latine de ordinul 9 și 10.

Note

↑ 1 2 Euler L. Recherches sur une nouvelle espèce de quarrés magiques. - Middelburg, 1782.
↑ Ozanam J. Récréations mathématiques et physiques. - Paris, 1725.
↑ Cayley A. On Latin Squares // Messenger of mathematics. - 1890. - T. XIX . — S. 135–137 .
↑ Tarry G. Le problème des 36 officiers // Comptes Rendus Assoc. Franta Av. Sci .. - 1900. - T. 29, partea 2 . — S. 170–203 .
↑ MacNeish, Harris F. Euler Squares // Annals of Mathematics. - 1922. - T. 23 . — S. 221–227 .
↑ Fisher R. A. Metode statistice pentru lucrătorii de cercetare. - Edinburgh, Londra: Oliver & Boyd, 1925.
↑ Bose RC; Shrikhande SS Despre falsitatea conjecturii lui Euler despre inexistența a două pătrate latine ortogonale de ordinul 4t + 2 // Proc. Nat. Acad. sci. STATELE UNITE ALE AMERICII. - 1959. - T. 45 . — S. 734–737 .
↑ van Lint JH, Wilson RM A Curs de combinatorică. — Cambridge University Press, 1992.
↑ 1 2 McKay BD, Wanless IM Despre numărul de pătrate latine // Ann. Combin.. - 2005. - T. 9 . - S. 335-344 .
↑ Cheremushkin A. V. Aproape toate pătratele latine au un grup trivial de autostrofie // Matematică discretă aplicată. - 2009. - T. 3 (5) . — S. 29–32 .
↑ Bose RS Despre aplicațiile proprietăților câmpurilor Galois la problemele de construcție a pătratelor hiper-greco-latine // Indian J. Stat.. - 1938. - Vol . Nr. 3. Part. 4 . — S. 323–338 .
↑ Dulmage AL, Johnson D., Mendelsohn NS Orthomorphisms of groups and orthogonal Latin squares I // Canada. J. Matematică .. - 1961. - T. 13 . — S. 356–372 .
↑ Colbourn CJ, Dinitz JH Handbook of Combinatorial Designs. a doua editie. Chapman & Hall, 2006. 984 p.
↑ Despre proiectul Gerasim@home - Pagina 96 - Gerasim@home - Forum Boinc.ru (link inaccesibil) . Consultat la 22 noiembrie 2016. Arhivat din original pe 23 noiembrie 2016. (nedefinit)
↑ Vatutin E. I., Zaikin O. S., Zhuravlev A. D., Manzyuk M. O., Kochemazov S. E., Titov V. S. Despre efectul ordinii de umplere a celulelor asupra ratei de generare a pătratelor latine diagonale // Informații - sisteme de măsurare de diagnostic și control (Diagnosticare - 2016). Kursk: editura SWGU, 2016. S. 33-39. . Data accesului: 22 noiembrie 2016. Arhivat din original pe 22 noiembrie 2016. (nedefinit)
↑ Vatutin EI, Zaikin OS, Zhuravlev AD, Manzuk MO, Kochemazov SE, Titov VS Utilizarea sistemelor de grilă pentru enumerarea obiectelor combinatorii pe exemplu de pătrate latine diagonale // Calcularea distribuită și tehnologiile grilă în știință și educație (GRID'16): carte de rezumate ale celei de-a 7-a conferinţe internaţionale. Dubna: JINR, 2016. p. 114-115. . Consultat la 22 noiembrie 2016. Arhivat din original la 21 septembrie 2017. (nedefinit)
↑ Căutați KF ODLC în proiectul Gerasim@home - Gerasim@home - Forum Boinc.ru (link inaccesibil) . Preluat la 18 martie 2017. Arhivat din original la 15 martie 2017. (nedefinit)
↑ ODLC . Preluat la 11 iulie 2018. Arhivat din original la 11 iulie 2018. (nedefinit)
↑ ODLK1 . Preluat la 11 iulie 2018. Arhivat din original la 11 iulie 2018. (nedefinit)
↑ Forum . Preluat la 12 iulie 2018. Arhivat din original la 12 iulie 2018. (nedefinit)
↑ Zaikin O., Zhuravlev A., Kochemazov S., Vatutin E. On the Construction of Triples of Diagonal Latin Squares of Order 10 // Electronic Notes in Discrete Mathematics. Vol. 54C. 2016.pp. 307–312. DOI: 10.1016/j.endm.2016.09.053. (link indisponibil) . Data accesului: 22 noiembrie 2016. Arhivat din original pe 22 noiembrie 2016. (nedefinit)
↑ Nelder J. Critical sets in latin squares // CSIRO Division of Math. și Statistici. - 1977. - T. Buletin informativ, 38 .

Literatură

Sala M. Combinatorică, trad. din engleza. M., 1970.
Denes JH, Keedwell AD Latin Squares și aplicațiile lor. Budapesta, 1974.
Sachkov VN Metode combinatorii ale matematicii discrete. M., 1977.
Denes JH, Keedwell AD Latin squares: Noi evoluții în teorie și aplicații. Analele matematicii discrete vol. 46 Presa Academică. Amsterdam. 1991.
Laywine CF, Mullen GL Matematică discretă folosind pătratele latine. New York, 1998.
Malykh A. E., Danilova V. I. Despre procesul istoric de dezvoltare a teoriei pătratelor latine și unele dintre aplicațiile lor // Buletinul Universității Perm . - 2010. - Emisiune. 4 , nr. 4 . - S. 95-104 .
Tuzhilin M.E. Despre istoria studiilor pătratelor latine // Review of Applied and Industrial Mathematics. - 2012. - T. 19 , nr. 2 . - S. 226-227 .
Bolshakova N.S. O altă aplicație a pătratelor latine // Buletinul MSTU. - 2005. - T. 8 , nr 1 . - S. 170-173 .

Legături

N. Makarova. Metode de construire a pătratelor latine .
N. Makarova. Grupuri de pătrate latine reciproc ortogonale .

Dicționare și enciclopedii	Rusă mare Britannica (online)
În cataloagele bibliografice	BNF : 119596221 GND : 4166852-2 SUDOC : 027588483

X	X	X	X	X	X	X	X	X	.
X	X	X	X	X	X	X	X	X	.
X	X	X	X	X	X	X	X	X	.
X	X	X	X	X	X	X	X	X	.
X	X	X	X	X	X	X	X	.	.
X	X	X	X	X	X	X	X	.	.
X	X	X	X	X	X	X	X	.	.
X	X	X	X	X	X	X	X	.	.
X	X	X	X	X	X	X	X	.	.
.	.	.	.	.	.	.	.	.	.

X	X	X	X	X	X	X	X	X	.
X	X	X	X	X	X	X	X	X	.
X	X	X	X	X	X	X	X	X	.
X	X	X	X	X	X	X	X	X	.
X	X	X	X	X	X	X	X	.	.
X	X	X	X	X	X	X	X	.	.
X	X	X	X	X	X	X	X	.	.
X	X	X	X	X	X	X	X	.	.
X	X	X	X	X	X	X	X	.	.
.	.	.	.	.	.	.	.	.	.

X	X	X	X	X	X	X	X	X	.
X	X	X	X	X	X	X	X	X	.
X	X	X	X	X	X	X	X	X	.
X	X	X	X	X	X	X	X	X	.
X	X	X	X	X	X	X	X	.	.
X	X	X	X	X	X	X	X	.	.
X	X	X	X	X	X	X	X	.	.
X	X	X	X	X	X	X	X	.	.
X	X	X	X	X	X	X	X	.	.
.	.	.	.	.	.	.	.	.	.