Latinsk firkant

Det latinske kvadrat i n . orden er en tabel L=(l ij ) af størrelsen n × n fyldt med n elementer i mængden M på en sådan måde, at i hver række og hver kolonne i tabellen forekommer hvert element fra M nøjagtigt én gang . Et eksempel på en latinsk firkant af 3. orden:

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

som kan repræsenteres som {(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)}, hvor det første og andet element er elementets position i matrixen, og det tredje er elementet værdi.

På nuværende tidspunkt tages mængden M normalt som mængden af naturlige tal {1,2,..., n } eller mængden {0,1,..., n -1}, men Leonard Euler brugte bogstaverne i det latinske alfabet , hvoraf de latinske firkanter har fået deres navn . [en]

Latinske firkanter findes for enhver n , det er nok at tage Cayley-tabellen af en gruppe af orden n , for eksempel . $l_{ij}=(i+j-1){\pmod {n))$

Forskningshistorie på latinske firkanter

De første latinske firkanter (4. orden) blev udgivet i bogen " Shams al Ma'arif " ("The Book of the Sun of Gnosis"), skrevet af Ahmad al-Buni i Egypten omkring 1200.

Par af ortogonale latinske firkanter blev første gang nævnt af Jacques Ozanam i 1725. [2] Bogen, som er en samling af problemer i fysik og matematik, indeholder følgende problem:

Det er nødvendigt at placere 16 spillekort med esser, konger, dronninger og knægte i alle fire kulører i form af en firkant, så alle kulører og kort af alle pålydende værdier forekommer i hver række og kolonne nøjagtigt én gang.

Dette problem har 6912 løsninger (hvis vi derudover kræver, at kvadratets diagonaler også opfylder samme betingelse, vil antallet af løsninger falde med en faktor 6 og blive lig med 1152).

En vigtig milepæl i historien om studiet af latinske firkanter var Eulers arbejde [1] . I den arbejdede han på metoder til at konstruere magiske firkanter og foreslog en metode baseret på et par ortogonale latinske firkanter. Undersøgelse af sådanne par fandt Euler ud af, at problemet med at konstruere dem er opdelt i tre tilfælde, afhængigt af resten af at dividere tallet n med 4. Han foreslog metoder til at konstruere par af ortogonale kvadrater for n delelig med 4 og for ulige n . Det er indlysende, at for n = 2 eksisterer sådanne par ikke. Han undlod at konstruere par af ortogonale latinske kvadrater for n = 6, 10 og formodede, at der ikke er nogen par af ortogonale kvadrater for n = 4 t +2. For n = 6 formulerede han "36 officersproblemet":

Det er nødvendigt at placere 36 officerer fra seks forskellige regimenter og seks forskellige militære rang i en firkant, så der i hver kolonne og i hver række er nøjagtig en officer fra hvert regiment og hver militær rang.

I 1890 udledte Cayley en to-linjers formel for antallet af latinske rektangler (et specialtilfælde af det klassiske kombinatoriske " mødeproblem " fremsat af P. Montmort i 1708). [3]

I 1900 blev Eulers formodning for n = 6 bekræftet af G. Tarry . [4] Han byggede alle 9408 normaliserede latinske firkanter, inddelte dem i 17 typer og viste, at det er umuligt at konstruere et par ortogonale firkanter for enhver kombination af dem. Dermed løste han " 36 officersproblemet " negativt .

I 1922 var MacNeish den første til at anvende en gruppeteoretisk tilgang til at løse latinske kvadratproblemer. [5] Især foreslog han en metode til at konstruere latinske kvadrater af orden n1•n2 ud fra latinske kvadrater af orden n1 og n2 , samtidig med at ortogonalitetsegenskaben bevares.

I 1925 foreslog Ronald Fisher brugen af ortogonale latinske firkanter til planlægning af landbrugseksperimenter. [6]

I 1920-1930 begyndte ikke-associative algebraiske strukturer at blive studeret intensivt, hvilket især førte til skabelsen af teorien om kvasigrupper , tæt forbundet med studiet af latinske firkanter, da der er en en-til-en korrespondance mellem latinske firkanter og Cayley-tabeller af kvasigrupper .

I 1959 byggede Bose og Shrikhande 2 ortogonale latinske firkanter for n = 22, og i 1960 byggede de og Parker et minimalt modeksempel for n = 10 ved hjælp af en computer , og efter 177 år blev Eulers formodning således tilbagevist. [7]

Antal latinske firkanter

Den nøjagtige formel for tallet L ( n ) af orden n latinske firkanter kendes ikke. De bedste estimater for L ( n ) er givet af formlen

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

[otte]

Hver latinsk firkant kan associeres med en normaliseret (eller reduceret) latinsk firkant, hvis første række og første kolonne er udfyldt i overensstemmelse med rækkefølgen angivet på sættet M . Et eksempel på en normaliseret latinsk firkant:

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

Antallet R(n) af normaliserede latinske kvadrater af orden n (sekvens A000315 i OEIS ) i n!(n-1)! gange mindre end L(n) (sekvens A002860 i OEIS ).

De nøjagtige værdier af L(n) er kendt for n fra 1 til 11: [9]

Antal latinske firkanter

n	R(n)	L(n)	Forfatter og årstal
en	en	en
2	en	2
3	en	12
fire	fire	576
5	56	161280	Euler (1782)
6	9408	812851200	Frolov (1890)
7	16942080	61479419904000	Sade (1948)
otte	535281401856	108776032459082956800	Wells (1967)
9	377597570964258816	5524751496156892842531225600	Bammel og Rothstein (1975)
ti	7580721483160132811489280	9982437658213039871725064756920320000	McKay og Rogoyski (1995)
elleve	5363937773277371298119673540771840	776966836171770144107444346734230682311065600000	McKay og Wanless (2005)

Ækvivalensrelationer på sættet af latinske firkanter

To latinske firkanter kaldes isotopiske, hvis en af dem kan opnås fra den anden som et resultat af en isotopi - en sammensætning fra permutation af rækker, permutation af kolonner og udskiftning af elementer i mængden M ved substitution fra den symmetriske gruppe S(M) ) .

En isotopi er en ækvivalensrelation , så sættet af n . ordens latinske firkanter opdeles i usammenhængende isotopiklasser. Fra en latinsk firkant kan du få 3 ækvivalenter ved hjælp af isotopi ( n !) , men nogle af dem kan falde sammen med den oprindelige, dette kaldes autoparatopi. Andelen af latinske firkanter med en ikke-triviel autoparatopi-gruppe har en tendens til nul, når n vokser . [9]

Den latinske firkant kan opfattes som et ortogonalt array . Ved at ændre rækkefølgen af elementerne i hver ordnet tripel af dette array, kan du få 6 latinske firkanter, som kaldes parastropher. Især den latinske firkant opnået som følge af transponering er en parastrophe.

Sammensætningen af isotopi og parastrofi kaldes isostrofi. Dette er en anden ækvivalensrelation, dens klasser kaldes hovedklasser. Hver hovedklasse indeholder 1, 2, 3 eller 6 isotopklasser. I tilfælde af sammenfaldet af den oprindelige latinske firkant og den isostrofiske taler de om autostrofi. Når n stiger, har næsten alle latinske firkanter den trivielle autostrofigruppe. [ti]

Antal ækvivalensklasser

n	Antal hovedklasser	Antal isotopklasser
en	en	en
2	en	en
3	en	en
fire	2	2
5	2	2
6	12	22
7	147	564
otte	283657	1676267
9	19270853541	115618721533
ti	34817397894749939	208904371354363006
elleve	2036029552582883134196099	12216177315369229261482540

Ortogonale latinske firkanter

To latinske kvadrater L=(l ij ) og K=(k ij ) af orden n kaldes ortogonale, hvis alle ordnede par (l ij ,k ij ) er forskellige. Et eksempel på to ortogonale latinske firkanter og deres tilsvarende ordnede par:

{\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 kaldte sådanne firkanter "komplette". Til hans ære, i den videnskabelige litteratur, plejede de at blive kaldt "Eulerian" eller "Greco-Latin" (da Euler brugte bogstaverne i det græske alfabet til kvadratet ortogonalt i forhold til det latinske).

Ortogonale latinske firkanter findes for enhver n , der ikke er lig med 2 og 6.

Et latinsk kvadrat L af orden n har et kvadrat ortogonalt i forhold til det, hvis og kun hvis der er n usammenhængende transversaler i L.

Af særlig interesse i forbindelse med talrige anvendelser er sæt af flere parvise ortogonale latinske kvadrater af orden n . Den maksimalt mulige effekt N(n) af et sådant sæt er n -1, i hvilket tilfælde mængden kaldes komplet.

Da n har tendens til ∞, har N(n) også tendens til ∞.

For n , som er en potens af et primtal , eksisterer der altid et komplet sæt af parvise ortogonale latinske firkanter, det kan være en-til-en afbildet til et endeligt projektivt plan af orden n . For at konstruere det, bruges Bose-metoden, som bruger værdierne af polynomier i formen til at udfylde kvadraterne med ikke-nul a over feltet . [11] Et eksempel på at konstruere et komplet sæt af parvise ortogonale latinske kvadrater af 4. orden ( d er roden af et primitivt polynomium over ): $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}}

Hvis n ≡ 1 (mod 4) eller n ≡ 2 (mod 4) og den kvadratfrie del af n indeholder mindst én primfaktor p ≡ 3 (mod 4), så er der for sådanne n ikke noget komplet sæt af parvis ortogonale latinske firkanter.

Kendte nedre grænser for tallet N(n) for n < 33 er angivet i følgende tabel (grænser, der kan forbedres, er fremhævet):

Nedre grænser for tallet N(n)

n	en	2	3	fire	5	6	7	otte	9	ti	elleve	12	13	fjorten	femten	16	17	atten	19	tyve	21	22	23	24	25	26	27	28	29	tredive	31	32
N(n)≥			2	3	fire		6	7	otte	2	ti	5	12	3	fire	femten	16	3	atten	fire	5	3	22	6	24	fire	26	5	28	fire	tredive	31

Konstruktionen af ortogonale kvadrater er et komplekst kombinatorisk problem. For at løse det bruges både algebraiske og kombinatoriske konstruktioner (transversaler, ortogonale arrays, designs, blokdiagrammer, Steiner-tripler osv.) Der er flere tilgange til at løse dette problem, de kan opdeles i to grupper. Den første gruppe omfatter metoder baseret på valget af et latinsk basiskvadrat, hvortil der søges isotopiske ortogonale latinske firkanter. For eksempel blev der fundet fem parvise ortogonale latinske kvadrater af orden 12 som et resultat af at konstruere fire ortomorfismer af den abelske gruppe , som er et direkte produkt af cykliske grupper af orden 6 og 2. [12]

Den anden gruppe omfatter metoder, der bruger kombinatoriske objekter (inklusive selve de latinske firkanter) af lavere orden til at konstruere ortogonale latinske firkanter. For eksempel blev to 22. ordens latinske firkanter bygget af Bose og Shrikhande baseret på to 15. og 7. ordens design.

Diagonale latinske firkanter

En latinsk firkant kaldes diagonal, hvis der ud over kravene til elementers entydighed i rækker og kolonner, karakteristiske for den latinske firkant, tilføjes kravene til elementers entydighed på hoved- og sekundærdiagonalerne [13] . Et analytisk estimat af antallet af diagonale latinske kvadrater er ukendt, deres antal for dimensioner N<10 blev bestemt i 2016 i Gerasim@Home frivilligt distribueret computerprojekt [14] [15] [16] (sekvens A274171 i OEIS og sekvens A274806 i OEIS ). For diagonale latinske kvadrater såvel som for blot latinske kvadrater er det muligt at konstruere ortogonale par, hvoraf nogle (ca. 9 og 10) blev fundet i SAT@home frivilligt distribueret computerprojekt ved hjælp af SAT-tilgangen . I øjeblikket udføres søgningen efter par af ortogonale diagonale latinske firkanter af 10. orden i Gerasim@Home frivilligt distribueret computerprojekt ved hjælp af transversaler [17] såvel som i BOINC -projekterne ODLK [18] og ODLK1 [19] . Den 25. april 2018 blev der fundet en 10. ordens diagonal latinsk firkant, der har 10 ortogonale diagonale latinske firkanter [20] . Dette er det maksimalt kendte antal ortogonale diagonale kvadrater i en orden 10 diagonale latinske kvadrater ( OEIS -sekvens A287695 ). Et åbent matematisk problem er eksistensen af et tredobbelt parvis ortogonale diagonale latinske kvadrater af orden 10 (i øjeblikket er den bedste tilnærmelse til dets løsning en tredobbelt af kvadrater, hvor to par kvadrater er ortogonale, og det tredje er delvist ortogonalt i 74 celler [21] ).

delkvadrater

Et kvadrat, hvor hvert element i mængden M forekommer højst én gang i hver række, og hver kolonne kaldes en delkvadrat.

Problemet med at erkende, om et partielt kvadrat kan udfyldes til latin, er NP-komplet .

Begrebet en kritisk mængde svarende til en delkvadrat introduceres, som entydigt kan udfyldes til den latinske, og ingen delmængde af den opfylder unikhedsbetingelsen. [22] Kardinalitet C(n) af den kritiske mængde for n × n kvadrater er kendt for n < 7:

Kritisk sæt kardinalitet

n	en	2	3	fire	5	6
C(n)	0	en	3	7	elleve	atten

Uløste problemer

Udover problemet med at finde en formel for værdien L ( n ), er der en lang række uløste problemer vedrørende latinske kvadrater. En række af sådanne opgaver blev formuleret på Loops'03-konferencen:

Et skøn for det maksimale antal transversaler i et latinsk kvadrat af orden n
Karakterisering af latinske underkvadrater i multiplikationstabellen for Moufang-løkker
Et skøn for tætheden af et delvist kvadrat, der opfylder Blackburn-ejendommen
Beregning af maksimum t(n) sådan at 2 t(n) deler værdien L ( n )

Ansøgning

Latinske firkanter er meget udbredt inden for algebra, kombinatorik, statistik, kryptografi, kodeteori og mange andre områder.

Anvendelse i kryptografi. Nul viden protokol

I øjeblikket bruges latinske firkanter aktivt til at implementere nul-viden protokoller. Især til MAC- generering .
Lad q ={1,2,…, n }. For en given latinsk firkant

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

b = q/2 varianter af LS er isotopiske for hinanden.

Antag, at brugerne danner et netværk. har en offentlig nøgle og (vi betegner to isotopiske latinske kvadrater af orden n) og en hemmelig nøgle (vi betegner isotopismen over ). ønsker at bevise ægtheden , men han ønsker ikke at afsløre den hemmelige nøgle ( Nul-viden bevis ). $(u_1, u_2, ..., u_k)$ $u_{i}$ $L_ui$ $L'_ui$ $I_ui$ $L_ui$ $L'_ui$ $u_{i}$ $u_{j}$

1. omarrangerer tilfældigt og modtager endnu et latinsk kvadrat H 2. sender H til 3. spørger enten: - at bevise at H og er isotopiske - at bevise at H og er isotopiske 4. opfylder anmodningen. Han eller - beviser, at H og er isotopiske - beviser, at H og er isotopiske 5. og gentag trin 1-4 n gange $u_{i}$ $L_ui$
$u_{i}$ $u_{j}$
$u_{j}$ $u_{i}$
$L'_ui$
$L_ui$
$u_{i}$
$L'_ui$
$L_ui$
$u_{i}$ $u_{j}$

Nedenfor er pseudokoden til beregning af hash-funktionen

for k fra 1 til q begynder d_k = 1 ; _ ende for i fra 1 til q begynder for j fra 1 til q begynder for k fra 1 til b begynder d_l_ji = m_ij * d_l_ji ; _ _ _ ende ende ende

Hashsummen vil være i vektoren D=[ ] Brugseksempel: Lad 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}}

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}}

Lad os antage, at følgende besked er sendt:

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}}

Flyt rækker for at få matricer fra til $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}}$

Lad os sætte en vektor Og vi vil beregne hashen i henhold til algoritmen givet ovenfor: Vi får $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}}$

Anvendelse i kryptografi. Schema for hemmelig deling

En hemmelighedsdelingsordning, hvor nøglen er ordenens latinske firkant . Den latinske plads holdes hemmelig. I mellemtiden offentliggøres rækkefølgen af den latinske plads for alle. Hemmelig deling er baseret på delvise latinske firkanter ={ | kritiske sæt }. Unionen kan være sammensat af alle mulige kritiske sæt L eller af sættet af kritiske sæt. Antallet af kritiske sæt afhænger af rækkefølgen af den latinske firkant og antallet af deltagere, der deltager i ordningen. Protokol: Der vælges en latinsk firkant L. Rækkefølgen af n afsløres, men selve den latinske firkant holdes hemmelig og bruges som nøgle. Sættet S er foreningen af kritiske sæt L. Hver deltager modtager en andel (i, j, k) . Når deltagerne kommer sammen, kan de sætte deres brikker sammen og rekonstruere firkanten L. Eksempel: Vælg tre delkvadrater: $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}

Og en hel firkantet L

0	en	2
en	2	0
2	0	en

Vi kan nemt verificere, at alle delvise latinske firkanter , , er kritiske mængder. De kan udvides unikt til en fuld latinsk firkant L. Denne unikke egenskab går tabt, hvis et element af en delvis latinsk firkant , , fjernes. Lad foreningen af tre kritiske sæt , , . Så = . Vi distribuerer dele af . Alle to deltagere kan genoprette den fulde latinske firkant. Det enkle eksempel opnået ovenfor kan udvides til det generelle tilfælde. I 1979 blev den latinske plads foreslået som en god kandidat til brug i hemmelige distributionsordninger. Der er dog visse begrænsninger for dets anvendelse, som beskrevet nedenfor. 1) Umiddelbart efter distributionen af dele af det kritiske sæt vil delvis information være tilgængelig for enhver uautoriseret gruppe. Det betyder, at der er stor chance for, at enhver uautoriseret gruppe kan finde ud af resten af brikkerne ved at prøve og fejle. Den foreslåede ordning er således ikke ideel. 2) Kredsløbet er ikke fleksibelt. I dette tilfælde er det bare en hemmelig opdelingsordning. Hashing Hvis vi vil bruge en hash-sum til at gemme et fast hemmeligt kvadrat, såsom et latinsk kvadrat af orden 10, skal vi gemme 81 tal (den sidste række og kolonne er valgfri). Fire bits kan bruges til at gemme en række, så vi skal bruge 324 bits. I dette tilfælde kan vi vælge SHA-384 eller SHA-512 . Hvis vi skal bruge SHA-256 , kan vi fortsætte som følger. 10 bit vil blive brugt til at repræsentere det 3. tal. Så vi brugte først 250 bit til at repræsentere 75 tal og derefter de næste 4 bit til at repræsentere et tal. I alt kan vi gemme 76 numre. Vi fikser en delvis latinsk firkant i følgende format. Lad os vælge en latinsk firkant af orden 10, som kan gendannes unikt ved at slette indtastningerne, som vist i tabellen. Afvejningen her er, at en lille procentdel af latinske firkanter, orden 10, ikke kan rekonstrueres unikt og derfor ikke kan vælges som en hemmelighed. $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	.	.
.	.	.	.	.	.	.	.	.	.

Spil og puslespil med latinske firkanter

Der er en række spil, der bruger latinske firkanter. Den bedst kendte af disse er Sudoku . Det kræver, at et delkvadrat suppleres til et latinsk kvadrat af 9. orden, som har den yderligere egenskab, at alle dens ni underkvadrater indeholder alle de naturlige tal fra 1 til 9 én gang.

Også populære er problemerne med at konstruere latinske firkanter og, baseret på dem, magiske firkanter med yderligere egenskaber (for eksempel diagonale firkanter).

se også

ortogonalt array
magisk firkant
Sudoku
SAT@home er et distribueret computerprojekt, der søger efter ortogonale par af 9. og 10. ordens latinske firkanter.

Noter

↑ 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 officers // Comptes Rendus Assoc. Frankrig Av. Sci .. - 1900. - T. 29, del 2 . — S. 170–203 .
↑ MacNeish, Harris F. Euler Squares // Annals of Mathematics. - 1922. - T. 23 . — S. 221–227 .
↑ Fisher R. A. Statistiske metoder for forskere. - Edinburgh, London: Oliver & Boyd, 1925.
↑ Bose RC; Shrikhande SS Om det falske i Eulers formodning om ikke-eksistensen af to ortogonale latinske kvadrater af orden 4t + 2 // Proc. Nat. Acad. sci. USA. - 1959. - T. 45 . — S. 734–737 .
↑ van Lint JH, Wilson RM Et kursus i kombinatorik. - Cambridge University Press, 1992.
↑ 1 2 McKay BD, Wanless IM Om antallet af latinske kvadrater // Ann. Kombiner.. - 2005. - T. 9 . - S. 335-344 .
↑ Cheremushkin A. V. Næsten alle latinske firkanter har en triviel autostrofigruppe // Anvendt diskret matematik. - 2009. - T. 3 (5) . — S. 29–32 .
↑ Bose RS Om anvendelsen af egenskaberne ved Galois-felter til problemerne med konstruktion af Hyper-Graeco-Latin firkanter // Indian J. Stat.. - 1938. - Vol . nr. 3. Del. 4 . — S. 323–338 .
↑ Dulmage AL, Johnson D., Mendelsohn NS Ortomorfismer af grupper og ortogonale latinske firkanter I // Canada. J. Math .. - 1961. - T. 13 . — S. 356–372 .
↑ Colbourn CJ, Dinitz JH Handbook of Combinatorial Designs. anden version. Chapman & Hall, 2006. 984 s.
↑ Om Gerasim@home-projektet - Side 96 - Gerasim@home - Boinc.ru Forum (utilgængeligt link) . Hentet 22. november 2016. Arkiveret fra originalen 23. november 2016. (ubestemt)
↑ Vatutin E. I., Zaikin O. S., Zhuravlev A. D., Manzyuk M. O., Kochemazov S. E., Titov V. S. Om virkningen af cellefyldningsrækkefølge på genereringshastigheden af diagonale latinske firkanter // Information - måling af diagnostiske og kontrolsystemer (Diagnostics - 2016). Kursk: forlag af SWGU, 2016. S. 33-39. . Dato for adgang: 22. november 2016. Arkiveret fra originalen 22. november 2016. (ubestemt)
↑ Vatutin EI, Zaikin OS, Zhuravlev AD, Manzuk MO, Kochemazov SE, Titov VS Brug af gittersystemer til optælling af kombinatoriske objekter på eksempler på diagonale latinske firkanter // Distribueret databehandling og gitterteknologier i videnskab og uddannelse (GRID'16): bog af abstracts fra den 7. internationale konference. Dubna: JINR, 2016. s. 114-115. . Hentet 22. november 2016. Arkiveret fra originalen 21. september 2017. (ubestemt)
↑ Søg efter KF ODLC i Gerasim@home-projektet - Gerasim@home - Boinc.ru Forum (utilgængeligt link) . Hentet 18. marts 2017. Arkiveret fra originalen 15. marts 2017. (ubestemt)
↑ ODLC . Hentet 11. juli 2018. Arkiveret fra originalen 11. juli 2018. (ubestemt)
↑ ODLK1 . Hentet 11. juli 2018. Arkiveret fra originalen 11. juli 2018. (ubestemt)
↑ Forum . Hentet 12. juli 2018. Arkiveret fra originalen 12. juli 2018. (ubestemt)
↑ Zaikin O., Zhuravlev A., Kochemazov S., Vatutin E. Om konstruktionen af tripler af diagonale latinske kvadrater af orden 10 // Elektroniske noter i diskret matematik. Vol. 54C. 2016.s. 307-312. DOI: 10.1016/j.endm.2016.09.053. (utilgængeligt link) . Dato for adgang: 22. november 2016. Arkiveret fra originalen 22. november 2016. (ubestemt)
↑ Nelder J. Kritiske sæt i latinske firkanter // CSIRO Division of Math. og statistik. - 1977. - T. Nyhedsbrev, 38 .

Litteratur

Hall M. Combinatorics, trans. fra engelsk. M., 1970.
Denes JH, Keedwell AD Latin Squares and their Applications. Budapest, 1974.
Sachkov VN Kombinatoriske metoder til diskret matematik. M., 1977.
Denes JH, Keedwell AD Latinske kvadrater: Nye udviklinger i teorien og anvendelserne. Annals of Discrete Mathematics vol. 46 Akademisk Presse. Amsterdam. 1991.
Laywine CF, Mullen GL Diskret matematik ved hjælp af latinske firkanter. New York, 1998.
Malykh A. E., Danilova V. I. Om den historiske udviklingsproces af teorien om latinske firkanter og nogle af deres anvendelser // Bulletin of the Perm University . - 2010. - Udgave. 4 , nr. 4 . - S. 95-104 .
Tuzhilin M.E. Om historien om studier af latinske firkanter // Gennemgang af anvendt og industriel matematik. - 2012. - T. 19 , no. 2 . - S. 226-227 .
Bolshakova N.S. En anden anvendelse af latinske firkanter // Bulletin of MSTU. - 2005. - T. 8 , nr. 1 . - S. 170-173 .

Links

N. Makarova. Metoder til at konstruere latinske firkanter .
N. Makarova. Grupper af gensidigt ortogonale latinske firkanter .

Ordbøger og encyklopædier	Stor russer Britannica (online)
I bibliografiske kataloger	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	.	.
.	.	.	.	.	.	.	.	.	.