Latinsk kvadrat

Från Rilpedia

Version från den 19 oktober 2008 kl. 20.36 av Alexbot (Diskussion)
(skillnad) ← Äldre version | Nuvarande version (skillnad) | Nyare version → (skillnad)
Hoppa till: navigering, sök
Wikipedia_letter_w.pngTexten från svenska WikipediaWikipedialogo_12pt.gif
rpsv.header.diskuteraikon2.gif

En latinsk kvadrat är en matris där elementen är ordnade på så sätt att varje rad och varje kolumn innehåller element av olika typ.

Namnet latinsk kvadrat kommer från Leonhard Euler.

Innehåll

Definition

En latinsk kvadrat är en n × n-matris där antalet distinkta element är n. Varje rad och kolumn ska innehålla exakt ett element av varje typ.

Det existerar en latinsk kvadrat för alla n, ty om man låter den översta raden vara '0 1 2 3 ... (n-1)', nästa rad vara '(n-1) 0 1 ... (n-2)' och så vidare, så har man konstruerat en latinsk kvadrat för godtyckligt n. Följande exempel är en latinsk kvadrat av ordning 4:


\begin{bmatrix}
 1 & 2 & 3 & 4 \\
 4 & 1 & 2 & 3 \\
 3 & 4 & 1 & 2 \\
 2 & 3 & 4 & 1 \\
\end{bmatrix}

Smetaniuks sats

Om färre än n element är ifyllda i en partiell latinsk kvadrat av ordning n är det alltid möjligt att konstruera en fullständig latinsk kvadrat av ordning n. Trevor Evans var den första som funderade över frågeställningen 1960 och den fick namnet Evans förmodan. Ett bevis stod Bohdan Smetaniuk för, då han bevisade satsen 1981. Till beviset av Smetaniuks sats behövs två lemman.

Lemma 1

Varje r × n latinsk rektangel där r < n, kan utökas till en (r + 1) × n latinsk rektangel och därför också till en latinsk kvadrat.

Lemma 2

Låt P vara en ofullständig latinsk kvadrat av ordning n med upp till n - 1 element och upp till \tfrac{n}{2} distinkta element. Då kan P kompletteras till en fullständig latinsk kvadrat.

Bevis av Smetaniuks sats

Beviset sker med induktion över n.
Fallet n ≤ 2 är trivialt. Vi studerar därför en latinsk kvadrat av storlek n ≥ 3 med upp till n - 1 element. Dessa element finns i rn - 1 olika rader numrerade s1,...,sr med fi element i rad i 1 ≤ ir. Från Lemma 2 kan vi anta att det finns fler än \tfrac{n}{2} olika element vilket innebär att en siffra bara finns representerat en gång. Efter permutering och omnumrering kan vi få att siffran n är representerad en gång, i rad s1. Därefter vill vi permutera raderna så att alla rader ligger under diagonalen, utom siffran n som ska ligga på diagonalen. Detta gör vi genom att först permutera rad s1 till position f1. Sedan permuterar vi kolumner så att alla element i rad s1 flyttas till den vänstra sidan. Då står siffran n som sista element i raden, på diagonalen. Rad s2 flyttas till position 1 + f1 + f2 och si, 1 ≤ ir, flyttas till position 1 + f1 + ... + fi och element i raden så långt till vänster som möjligt. För att kunna använda induktion tar vi bort siffran n från diagonalen och bortser även från den första raden och den sista kolumnen. Eftersom vi nu har en partiell latinsk kvadrat av ordning n - 1 med upp till n - 2 element kan vi använda induktionsantagandet som säger att vi komplettera vår partiella latinska kvadrat till en komplett latinsk kvadrat.
Då återstår att fylla ut den första raden och den sista kolumnen vilket kan göras med följande algoritm. Målet är att sätta siffran n på diagonalen och fylla ut övriga platser. Detta gör vi rad för rad (uppfifrån) sätta siffran n på plats (k, n), 2 ≤ k < n. Byt plats på element (k, n) och element (k, k). Om elementet på plats (k, k) inte finns i kolumn n är bytet klart. Om det redan fanns representerat på plats (j, n) 2 ≤ j < k så byter vi plats på elementen (j, n) och (j, k). Om två element fortfarande är lika i kolumn n upprepas proceduren ett ändligt antal gånger tills elementen i kolumn n är distinkta.
Nu återstår bara den första raden och eftersom lemma 1 säger att en latinsk (r × n) rektangel kan utökas till en latinsk ((r + 1)× n) rektangel kan vi komplettera vår latinska rektangel till en latinsk kvadrat.
Härmed är satsen bevisad enligt induktionsprincipen.

Eulers officerarproblem

Leonhard Euler undrade om det var möjligt att placera ut 36 officerare, från sex olika regementen med sex officerare av olika grad från varje regemente, så att de fyllde en 6 × 6 kvadrat där ingen från samma regemente eller av samma grad stod på samma rad eller kolumn. Euler anade att det inte fanns någon lösning på problemet vilket bevisades av Gaston Tarry 1901.

Ortogonala latinska kvadrater

Två latinska kvadrater A = (aij) och B = (bij) av samma storlek säges vara ortogonala om (aij,bji) är distinkta  \forall (i,j)\in \mathbb{N}_n ^2. Det existerar inte något par av ortogonala 6 × 6 latinska kvadrater, vilket visades av G. Tarry år 1900. Eulers förmodan, som motbevisades på 1900-talet, behandlar existensen av ortogonala latinska kvadrater.
Från två ortogonala latinska kvadrater kan man få fram en magisk kvadrat, dvs summan av siffrorna i varje rad och kolumn är lika.

Tillämpningar

Latinska kvadrater används på en mängd olika områden så som till att programmera parallella processer, till felrättande koder och i idrottssammanhang till spelschema för serier.
Sudoku är ett spel som kan liknas vid att konstruera en latinsk kvadrat utgående från att några element redan är kända och med den ytterligare restriktionen att de så kallade regionerna ska uppfylla samma krav som raderna och kolumnerna. I Sudoku är det av vikt att den latinska kvadraten, med denna ytterligare restriktion, är kritisk, det vill säga att det existerar exakt en lösning utifrån de givna elementen.

Referenser

Aigner, Martin; Günter M. Ziegler: Proofs from the book, Springer-Verlag, 2004. ISBN 3540404600. 
Lovász, László; Jószef Pelikán, Katalin Vesztergombi: Discrete Mathematics, Springer-Verlag, 2003. ISBN 0387955852. 
A. Bogomolny, Latin Squares from Interactive Mathematics Miscellany and Puzzles http://www.cut-the-knot.org/arithmetic/latin_intro.shtml, 11-05-2008
http://en.wikipedia.org/wiki/Latin_square, 11-05-08

Personliga verktyg