Ugrás a tartalomhoz

Latin négyzet

Ellenőrzött
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:

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

10 x 10 Lateinisches Quadrat
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]

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

Példák

[szerkesztés]

Példák kis latin négyzetekre:

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

  • az egyelemű csoport
  • , kételemű ciklikus csoport
  • , háromelemű ciklikus csoport
  • , Klein-csoport
  • , négyelemű ciklikus csoport
  • , ötelemű ciklikus csoport
  • egy ötelemű kvázicsoport

Redukált és izotóp latin négyzetek

[szerkesztés]

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 elemek eredeti sorrendben vannak: Redukált vagy normalizált latin négyzet.

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 számából az összes n × n-es latin négyzet száma meghatározható:

.

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 száma meghatározható. A legjobb alsó és felső becslés (Lint és Wilson):

,

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]

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áját”.

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]

Két azonos rendű és 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 mátrix megfelelő helyére: .

Ha a mátrix olyan, hogy az szimbólumokból képezhető számú rendezett pár mindegyike pontosan egyszer fordul elő a táblázatban, akkor az és latin négyzeteket ortogonálisnak, a 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.

Története

[szerkesztés]

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-ben) 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-Île-de-France, G2-Besançon, G3-Champagne, G4-Pikárdia) végzett. A kísérleti állatoknál négyféle takarmányozást (T1-burgonya, T2-takarmányré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]

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

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 , vagyis ha 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ások

[szerkesztés]
  1. Archivált másolat. [2009. december 17-i dátummal az eredetiből archiválva]. (Hozzáférés: 2010. február 12.)
  2. [1]
  • 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