Gresk-Latin firkant

Et gresk-latinsk kvadrat eller eulerisk kvadrat av orden n , over to sett G og L for hvert n- symbol, er et kvadratisk utvalg av n rader og n kolonner, som inneholder n 2 par av L × G , og hvor en hvilken som helst rad og hver kolonnen inneholder nøyaktig en gang hvert element av L (i første posisjon i ett av n- parene) og hvert element av G (i andre posisjon). Det er superposisjonen til to latinske firkanter som er ortogonale mot hverandre. Vi sier også "bilatin firkant".

Navnet "gresk-latin" kommer av det faktum at vi ofte brukte G og L begynnelsen på de greske og latinske alfabeter .

Eksempler

To ortogonale latinske firkanter

Tenk på følgende to latinske firkanter i rekkefølge 4, på settene L = { A , B , C , D } og G = {α, β, γ, δ}:

{\ displaystyle {\ begin {bmatrix} A & B & C & D \\ B & A & D & C \\ C & D & A & B \\ D & C & B & A \\\ end {bmatrix} } \ quad \ quad {\ begin {bmatrix} \ alpha & \ gamma & \ delta & \ beta \\ \ beta & \ delta & \ gamma & \ alpha \\\ gamma & \ alpha & \ beta & \ delta \\ \ delta & \ beta & \ alpha & \ gamma \ end {bmatrix}}.}

Deres superposisjon (motsatt) er en gresk-latinsk firkant fordi ingen par L × G gjentas (derfor vises hvert par en gang og bare en gang): vi sier at de to latinske rutene er ortogonale.

To ikke-ortogonale latinske firkanter

La oss erstatte den andre av de to latinske rutene ovenfor med følgende:

{\ displaystyle {\ begin {bmatrix} \ alpha & \ beta & \ gamma & \ delta \\\ gamma & \ delta & \ alpha & \ beta \\\ beta & \ gamma & \ delta & \ alpha \\\ delta & \ alpha & \ beta & \ gamma \\\ end {bmatrix}}.}

Det er ikke lenger ortogonalt med det første, det vil si at deres superposisjon ikke gir et gresk-latinsk kvadrat:

{\ displaystyle {\ begin {bmatrix} A \ alpha & {\ color {Blue} B \ beta} & C \ gamma & {\ color {Orange} D \ delta} \\ B \ gamma & {\ color {Red} A \ delta} & D \ alpha & {\ color {Green} C \ beta} \\ {\ color {Green} C \ beta} & D \ gamma & {\ color {Red} A \ delta} & B \ alpha \\ {\ color {Orange} D \ delta} & C \ alpha & {\ color {Blue} B \ beta} & A \ gamma \\\ end {bmatrix}}.}

Vi merker oss faktisk at fire par dukker opp to ganger (og at fire er fraværende).

Historie

Første frukt

En posthum utgave ( 1725 ) av Recreations mathematiques et physique av Jacques Ozanam foreslår (vol. 4, s. 434 ) å konstruere et gresk-latinsk kvadrat i rekkefølge 4, i et puslespill formulert i form av spillkort : problemet er å ta alle ess , konger , dronninger og knekt i et standard spill og ordne dem på et 4 × 4 rutenett slik at hver rad og hver kolonne inneholder de fire tegnene ( klubber clubs , diamant ♦ , hjerter ♥ , spader ♠ ) og de fire verdiene . Det er flere løsninger.

Eulers arbeid og hans to antagelser

I 1779 definerte og studerte den sveitsiske matematikeren Leonhard Euler de gresk-latinske rutene av orden n , på de greske og latinske alfabeter og deretter på strengt positive heltall . Det produserer metoder for å konstruere noen hvis n er merkelig eller et multiplum av 4. Det gjenstår derfor å håndtere saken der n er kongruent til 2 modulo 4 . Han merker at det ikke er noe gresk-latinsk kvadrat i orden 2 og illustrerer orden 6 ved "problemet med 36 offiserer":

“36 Offiserer i seks forskjellige rekker og hentet fra seks forskjellige regimenter, som måtte ordnes i en firkant, slik at det på hver linje, både vannrett og loddrett, var seks offiserer av både forskjellige karakterer og forskjellige regimenter. "

Han antar at dette problemet ikke har noen løsning:

Nå, etter alle smertene vi har tatt for å løse dette problemet, har vi vært forpliktet til å erkjenne at en slik ordning er absolutt umulig, selv om vi ikke kan gi en grundig demonstrasjon av den. "

og til og med at mer generelt, for enhver n kongruent til 2 modulo 4, er det ingen gresk-latinsk kvadrat av orden n :

“Jeg har undersøkt et veldig stort antall kvadrater ved hjelp av denne metoden [...] og jeg har ikke nølt med å konkludere med at ingen fullstendig kvadrat på 36 kvadrater kunne produseres, og at den samme umuligheten strekker seg for tilfellene n = 10, n = 14 og generelt for alle odde partall. "

Første antagelse bekreftet og andre tilbakevist

I 1842 , takket være en uttømmende søk av tilfellene og ved å krysse resultatene, dansken Thomas Clausen styrer, i all sannsynlighet, for å demonstrere den første formodning av Euler: det er ingen gresk-latinske kvadrat av orden 6. Men det er bevis har nådde ikke oss. Det første publiserte beviset, som følger samme metode, skyldes franskmannen Gaston Tarry , i 1901.

I 1959 - 1960 ' , Bose , Parker (en) og Shrikhande fullstendig oppheve den andre: bortsett fra de to unntak allerede kjent ( n = 2 og n = 6), finnes det gresk-latinske kvadrater av orden n for alle n ≡ 2 ( mod 4) derfor til slutt: for alle n .

applikasjoner

Georges Perec strukturerte sin roman La Vie mode emploi (utgitt i 1978) på en gresk-latinsk firkant av orden 10.
Gresk-latinske firkanter brukes til design av eksperimenter og turneringsplanlegging.
Noen gresk-latinske firkanter lar deg bygge visse magiske firkanter . Mer presist: i et gresk-latinsk kvadrat av orden n på G = L = {0, 1,…, n - 1}, ved å erstatte hvert par ( x , y ) med tallet nx + y , får vi et kvadrat laget opp av tallene fra 0 til n 2 - 1, med samme sum på hver rad og hver kolonne (men ikke alltid på de to diagonalene, og omvendt kan et normalt magisk kvadrat av orden n ikke stamme fra et gresk-kvadratisk latin) .

Merknader og referanser

(i) Donald Knuth , The Art of Computer Programming , Vol. 4A, s. 3 .
L. Euler, forskere på en ny art av magisk kvadrat , E530 , presentert av Academy of St. Petersburg 8. mars 1779. Bemerkelsesverdig, denne artikkelen ved Euler er skrevet på fransk, og er den eneste som ble publisert i en nederlandsk avis (i 1782).
Euler, op. cit. , § 17.
Euler, op. cit. , § 1.
Euler, op. cit. , § 144.
(in) Dominic Klyve og Lee Stemkoski, " Graeco-Latin Squares and has Mistaken Conjecture of Euler " , College Mathematics Journal (in) , vol. 37, n o 1,2006, s. 2-15 ( les online ).
G. Tarry, " Problemet med 36 offiserer (I) ", Proceedings of the French Association for the Advancement of Science , vol. 1,1900, s. 122-123og G. Tarry, " (II) ", CR Assoc. Franc. Av. Sci. , vol. 2,1901, s. 170-203.

Relatert artikkel

Sudoku