Latin négyzet

A Wikipédiából, a szabad enciklopédiából
4×4-es kirakós

A latin négyzet egy n × n-es táblázat, amelynek soraiban és oszlopaiban n különböző elem (szimbólum) szerepel oly módon, hogy ezek mindegyike minden sorban és minden oszlopban pontosan egyszer fordul elő. Példák másod-, harmad- és negyedrendű latin négyzetre:

\begin{bmatrix}
\alpha & \beta\\
\beta & \alpha\\
\end{bmatrix}
\quad\quad

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

\begin{bmatrix}
a & b & d & c \\
b & c & a & d \\
c & d & b & a \\
d & a & c & b\\
\end{bmatrix}

Itt pedig az arab számjegyek egy 10×10-es latin négyzetben:

10 x 10 Lateinisches Quadrat

Az elnevezés Leonhard Eulertől származik, aki latin betűket használt szimbólumokként.

A latin négyzet redukált, normalizált vagy standard alakú, ha első oszlopa és első sora megfelel a természetesen rendezett sorrendnek. A fenti háromszor hármas táblázat ilyen.

A véges csoportok, sőt a kvázicsoportok Cayley-táblái is latin négyzetet adnak.

Definíciója[szerkesztés | forrásszöveg szerkesztése]

Az n × n-es vagy n-edrendű latin négyzet egy olyan n-edrendű A négyzetes mátrix, amelynek a_{i,j} elemei az s_1,s_2,...,s_n szimbólumok közül kerülnek ki és minden sora/oszlopa az s_1,s_2,...,s_n elemek egy permutációja.

Példák[szerkesztés | forrásszöveg szerkesztése]

Példák kis latin négyzetekre:


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

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

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

Ezek rendre a következő csoportok Cayley-tábláit reprezentálják:

  • az egyelemű csoport
  • \mathbb{Z}_2, kételemű ciklikus csoport
  • \mathbb{Z}_3, háromelemű ciklikus csoport
  • \mathbb{Z}_2 \times \mathbb{Z}_2, Klein-csoport
  • \mathbb{Z}_4, négyelemű ciklikus csoport
  • \mathbb{Z}_5, ötelemű ciklikus csoport
  • egy ötelemű kvázicsoport

Redukált és izotóp latin négyzetek[szerkesztés | forrásszöveg szerkesztése]

Latin-izotop.jpg

Egy latin négyzetből akár a sorok, akár az oszlopok cseréjével, permutálásával ugyancsak latin négyzetet kapunk. A szimbólumok cseréje, permutálása szintén megtartja a definíció feltételeit. Az így kapott latin négyzeteket izotópoknak nevezzük, s ez az izotópia ekvivalencia osztályokba sorolja az összes azonos rendű elrendezést. Egy osztály reprezentálására azt a latin négyzetet választhatjuk, aminek első sorában és első oszlopában az s_1,s_2,...,s_n elemek eredeti sorrendben vannak: Redukált vagy normalizált latin négyzet.

Latin-normalt.jpg

Ez az elrendezés bármelyik latin négyzetből kiindulva az oszlopok és a sorok cseréjével elérhető. Megfordítva, egy redukált latin négyzetből sor-oszlop permutációkkal előállítható az összes izotóp négyzet és csak ezek. A redukált n × n-es latin négyzetek L(n) számából az összes n × n-es latin négyzet N(n) száma meghatározható:

N(n)=n!(n-1)!L(n).

Néhány n-re ezek az értékek:

n 1 2 3 4 5 6 7
L(n) 1 1 1 4 56 9408 16942080
N(n) 1 2 12 576 161280 812851200 61479419904000

Nem ismerünk azonban olyan egzakt képletet, amivel a redukált négyzetek L(n) száma meghatározható. A legjobb alsó és felső becslés (Lint és Wilson):

 \frac{\left(n!\right)^{2n}}{n^{n^2}}\leq L(n)\leq\prod_{k=1}^n \left(k!\right)^{n/k},

de ezek nagy n-re nagymértékben eltávolodnak, „szétnyílik az olló”. Csak 1981-ben sikerült Szmetanjuknak bizonyítania, hogy a latin négyzetek száma n növekedésével együtt szigorúan növekszik.

Eredete, alkalmazása[szerkesztés | forrásszöveg szerkesztése]

A „latin négyzet” elnevezés Leonhard Eulertől származik, aki az elrendezés vizsgálatánál latin betűket használt a táblázat elemeiként. Euler több más vizsgált problémához hasonlóan matematikai fejtörőként is megfogalmazta az elrendezés egyik megoldhatatlan problémáját: „#A 36 tiszt problémája”.

A latin négyzet mint elrendezés, fontos szerepet játszik olyan kísérletek tervezésénél, amelyekben bizonyos hatások (öntözés, műtrágya, kezelési módszer, gyógyszer, takarmány stb.) együttes alkalmazásai képezik a vizsgálat tárgyát. A latin négyzet-elrendezés biztosítja az összes lehetséges kombináció kiválasztását és a kísérlet mellékhatásainak kiszűrését. Matematikán belül a kombinatorika, a véges geometria és a csoportelmélet területén, a hírközlésben a hibajavító kódok készítésénél használják.

A 19. századtól a kombinatorika több más feladatához (15-ös kombinet, átkelések, Euler-gráfok stb.) hasonlóan népszerű volt. Napjainkban a japáni eredetű szudoku és a KenKen is erre a feladatra épül. Az Interneten számos online puzzle is a latin vagy a latin-görög négyzetek előállítását tűzi ki célul. Egy részben kitöltött négyzet befejezése NP-teljes feladat.

A latin négyzet megjelenik a Kanadai Statisztikai Társaság (Statistical Society of Canada) címerében[1] és a Nemzetközi Biometrikus Társaság (International Biometric Society) logójában is.[2]

Latin-görög négyzet, ortogonalitás[szerkesztés | forrásszöveg szerkesztése]

Két azonos rendű A és B latin négyzetet egyesíthetünk oly módon, hogy az azonos helyen álló elemeikből képzett rendezett párokat helyezzük el a C mátrix megfelelő helyére: c_{i,j}=(a_{i,j}; b_{i,j}).

Latin-ortho.jpg

Ha a C mátrix olyan, hogy az s_1,s_2,...,s_n szimbólumokból képezhető n^2 számú rendezett pár mindegyike pontosan egyszer fordul elő a táblázatban, akkor az A és B latin négyzeteket ortogonálisnak, a C kompozíciójukat pedig latin-görög négyzetnek vagy Euler-négyzetnek nevezzük. Az előbbi elnevezést maga Euler használta, mivel a vizsgált ortogonális pár egyikében az elemeket latin betűkkel, a másikban görög betűkkel jelölte.

Latin-greek.jpg

Története[szerkesztés | forrásszöveg szerkesztése]

Első ismert előfordulásai az első ezredforduló körüli évekből származó hindi és arab érmékről, amulettekről, szőttesekről, mozaik-padlókról ismertek. Vegyesen fordulnak elő a bűvös négyzetek, bűvös körök és más hasonló, varázserejűnek tartott elrendezésekkel együtt, amelyeknek a gyökerei az ókori szám-misztikára vezethetők vissza. Első irodalmi említése Ahmed ibn’Ali ibn Juszuf al-Buni (meghalt i. sz. 1225-ban) könyvében (Shams al-Ma’arif al-Kubra) található. Az elrendezéssel kapcsolatos hiedelmekre jellemzőek a közölt példákban szereplő elemek : a hét napjai, a bolygók neve, az alkímia néhány eleme stb.

Az Európába áramló keleti tudomány magával hozta a mágikus elrendezések „elméletét”. A 13. században Ramón Lull spanyol filozófus és mágus műveiben jelennek meg az átvett és az általa konstruált latin, latin-görög és bűvös négyzetek, háromszögek, körök s egyéb varázserejű elrendezések.

Első igazi tudományos előfordulása, pontosabban alkalmazása egy francia agronómushoz köthető. Francois Cretté de Palluel 1788-ban nyújtotta be értekezését Memoires d’Agriculture d’Economie et Domestique címmel a Societé Royale d’Agriculture á Paris–nak. Ebben beszámol egy takarmányozási kísérletről, amit az ország négy különböző vidékén (G1-Ille de France, G2-Besançon, G3-Champagne, G4-Picardie) végzett. A kísérleti állatoknál négyféle takarmányozást (T1-burgonya, T2-takarmány répa, T3-cukorrépa, T4-vegyes szemestakarmány) alkalmazott. Az állatok 2, 3, 4 és 5 hónapi súlynövekedéséből állapította meg az optimális takarmányt. A helyek és időtartamok eloszlásának megfelelő kombinációjával biztosította ezek szisztematikus hatásának közömbösítését. A munkájában magát a táblázatot nem rajzolta meg, csupán a kísérlet dokumentációjából rekonstruálható az alábbi elrendezés, ahol a mezőkben a hónapokban mért időtartamok szerepelnek:

Hónap T1 T2 T3 T4
G1 2 5 4 3
G2 3 2 4 4
G3 4 3 2 5
G4 5 4 3 2

Euler is nagyjából ebben az időben foglalkozott a problémával, ami általa került a matematikusok látókörébe. A híressé vált „36 tiszt” problémát 1779-ben fogalmazta meg a Szentpétervári Tudományos Akadémia számára és 1782-ben tette közzé Recherches sur une nouvelle espèce de quarrés magiques címmel.

A 36 tiszt problémája[szerkesztés | forrásszöveg szerkesztése]

A feladat a következő: Egy díszszemlén a résztvevő 6 ezredből 6–6 különböző rendfokozatú tiszt vezénylésével kirendelt alegységeket úgy kell egy 6 \times 6-os négyzetben elrendezni, hogy minden sorban és minden oszlopban a tiszti rendfokozatok és az ezredek pontosan egyszer forduljanak elő.

16 officer.jpg
25 officer.jpg

A feladat általánosságban is egyszerűen megfogalmazható: Elkészítendő egy n × n-es latin-görög négyzet vagy keressünk ortogonális párokat n-edrendű latin négyzetek között. Euler szerint n=6 esetén a feladatnak nincs megoldása. Általánosabban azt sejtette, hogy ha n \equiv 2 \pmod 4, vagyis ha n=4k+2 alakú, akkor nincs megoldás. A legkisebb ilyen szám n=2, amire a sejtés a kevés lehetőség miatt direkt módon igazolható. A „36 tiszt problémájá”-ban szereplő n=6-ra csak 1900-ban talált bizonyítást Gaston Tarry. (Le problème des 36 officiers, C. R. Assoc. Franc. Av. Sci. 29, 1900, 170-203.). Azóta az általános esetről szóló Euler-féle sejtést Parker, Bose és Shrikhande megcáfolták, és kiderült, hogy n= 2 és 6 kivételével mindig létezik latin-görög négyzet.

A feladat n=4-re a következő pasziánszból ismert: A francia kártya négy színéhez (ezredek) tartozó négy különböző értékű (rendfokozatok) lapját kell egy 4 × 4–es alakzatban elrendezni úgy, hogy soronként és oszloponként se a színek, se a figurák ne ismétlődjenek. (A lehetséges elrendezések száma 16!= 20 922 789 888 000, és ebből csak 576 helyes.) Hasonlóan szórakoztató kirakóst kapunk öt különböző színre festett és öt különböző szimbólummal (pl. betűkkel) feliratozott zsetonokból.

További információk[szerkesztés | forrásszöveg szerkesztése]

Források[szerkesztés | forrásszöveg szerkesztése]

  • Kárteszi Ferenc: Bevezetés a véges geometriákba, Akadémiai Kiadó, Budapest 1972 (Disquisitiones Mathematicae Hungaricae 3)
  • Reinhardt, F. – Soeder, H.: SH atlasz-Matematika, Springer-Verlag, 1993
  • Ribnyikov, K. A.: A matematika története, Tankönyvkiadó, 1968
  • Sain Márton: Matematikatörténeti ABC, Nemzeti Tankönyvkiadó - Typotex, 1993
  • Andersen, Lars Døvling: The history of latin squares, Aalborg University, Dánia 2007