DT                    D é n e s   T a m á s matematikus                                         TD

független szakértõ            

   e-mail: tdenest@freemail.hu

Latin és bûvös négyzetek a játékos alkalmazásoktól az ûrtávközlésig

Nem egyedülálló a matematika történetében, hogy egyes fejezetei a szórakozás, a játék területén fogantak és hosszabb-rövidebb fejlõdés után a matematika új fejezeteivé váltak. Ezt az utat járta be a kombinatorika egy alig 300 éves fejezete, a latin négyzetek elmélete. Különössége mégsem abban áll, hogy fejlõdésének és fõleg alkalmazásainak jelentõs része a XX. század gyümölcse, hanem abban, hogy a klasszikus numerikus gondolkodást felcserélte a struktúrák belsõ összefüggéseinek elemzésével és igen szemléletes ábrázolásával.

Jelen dolgozatomban a latin négyzetek szerteágazó, klasszikus és egészen modern alkalmazásainak és lehetõségeinek vázlatos bemutatását tûztem ki célul, a szórakoztató matematikától, a XXI. század információs társadalmában kulcs jelentõségû adatátvitelen keresztül, a kriptográfiáig[1].

Alapfogalmak és definíciók történeti illusztrációkba ágyazva

Mivel a latin négyzetek elmélete egyelõre nem képezi matematika oktatásunk törzsanyagát, így a jelen dolgozat megértéséhez az olvasónak néhány alapfogalom megismerésére lesz szüksége. Ezeket az alapvetõ fogalmakat és összefüggéseket, valamint a keletkezésük történeti hátterét ismertetem vázlatosan a következõkben.

Egy n-ed rendû latin négyzeten egy olyan n x n méretû négyzetes mátrixot értünk, amelynek soraiban és oszlopaiban az a_1, a₂,………,a_n  elemek mindegyike pontosan egyszer szerepel. Általában az a_1, a₂,………,a_n  elemek az 1,2,……,n természetes számok. Az 1/a., 1/b.ábra példát mutat egy-egy 4-ed rendû latin négyzetre.

1	2	3	4
2	3	4	1
3	4	1	2
4	1	2	3

                                 1/a. ábra 

1	2	3	4
2	1	4	3
3	4	1	2
4	3	2	1

                                                  1/b.ábra

A definícióból világosan kiderül, hogy jelen esetben nem az a_1, a₂,………,a_n  elemek számértéke számít, csupán csak különbözõségük, valamint a mátrixban elfoglalt helyük (struktúrájuk).

Egy latin négyzetet ciklikusnak nevezünk, ha egymás alatti soraiban az elemek sorrendje azonos, csak egy hellyel jobbra (vagy balra) vannak az elemek eltolva (lásd 1/b.ábra).

Egy n-ed rendû latin négyzet egy tranzverzálisán értjük n darab olyan elemét, amelyek mindegyike különbözõ sorában, illetve oszlopában helyezkedik el és nincs köztük két azonos. Az 1/a. ábrán látható latin négyzetben a satírozott négy elem például egy tranzverzálist alkot.

Két n-ed rendû latin négyzetet akkor nevezünk ortogonálisnak, ha egymásra helyezve õket, az egymás felett levõ elemekbõl alkotott párok mind különbözõek. Példaképpen bemutatjuk az l/a. ábrán szereplõ latin négyzet egy ortogonális párját (lásd 2.ábra), majd a két latin négyzet egymásra helyezésével nyert számpárokat. (Az olvasó a 3.ábra segítségével könnyen meggyõzõdhet arról, hogy a 16 számpár mind különbözõ.)

2.ábra

3. ábra

Az ortogonális latin négyzet párok létezése, mint látni fogjuk, szoros kapcsolatban van a tranzverzálisokkal. Erre vonatkozó alapvetõ eredmény Dulmage-Mendelshon tétele:

Két n-ed rendû latin négyzet ortogonalitásának szükséges és elégséges feltétele, hogy a diszjunkt diagonálisaik száma pontosan  n  legyen.

L₁, L₂,….,L_k n-ed rendû latin négyzetek egy ortogonális rendszert alkotnak, ha bármely két különbözõ latin négyzetet véve a k darab közül, azok ortogonális párt képeznek. Bebizonyítható, hogy nxn-es latin négyzetekbõl legfeljebb n-1 olyan létezhet, amelyek közül bármely kettõ ortogonális, ha viszont ezek mind léteznek, akkor az ortogonális latin négyzetek teljes rendszerérõl beszélünk. A XX. század elején kiderült, hogy számos súlyos kombinatorikai probléma mélyén az ilyen rendszerek létezésének kérdése rejlik.

Egy L latin négyzetet akkor nevezünk vízszintesen teljesnek, ha bármely a latin négyzetben szereplõ a, b (a¹b) elempárra van olyan sora L-nek, amelyben az a elemet b követi. (Ha a leírt tulajdonság oszlop irányban teljesül, akkor az L latin négyzetet függõlegesen teljesnek nevezzük.) Egy latin négyzetet, amely vízszintesen és függõlegesen is teljes, teljes latin négyzetnek nevezzük. A 4. ábrán látható latin négyzet teljes (errõl meggyõzõdhet az olvasó, ha a kívánt tulajdonságot megvizsgálja az összes lehetséges (1,2), (1,3), (1,4), (2,3), (2,4), (3,4) elempárokra).

4. ábra

Kártyalapok és a 36 tiszt problémája

Leonhard Euler (1707-1783) a XVIII. századi matematika egyik óriása a latin négyzetek névadója, mivel Õ alkalmazott a négyzetes mátrixbeli elemek jelölésére latin betûket, az addig szokásos számok helyett. Ez az algebrai struktúrák területén hasonló jelentõséggel bírt, mint F. Viéte (1540-1603) 200 évvel korábbi tette, az algebrai egyenletek szimbólumainak bevezetésével. L. Eulert szokták említeni, mint aki bevezette az ortogonális latin négyzet párok fogalmát is. Azonban már Eulert megelõzõen is ismerték az Eulernek tulajdonított két fogalmat. Szeretném a történelmi hûség kedvéért az olvasó figyelmét Claude-Gaspar Bachet de Méziriac-ra (1581-1638) M. Ozanam-ra (1640-1712) felhívni, akik már Euler elõtt is játék kártyával kapcsolatosan jutottak a latin négyzetek, illetve ezekbõl alkotott ortogonális párok fogalmához. (lásd [1], [9], [10]). Az 5/a. ábrán látható negyed rendû ortogonális latin négyzet pár [1]-bõl való, amely tulajdonképpen a következõ feladatot oldja meg: hogyan lehet a römi kártya négy színû (coeur, treffe, carreau, pique) figuráiból (ae, roi, dame, valet) 16 lapot úgy kiválasztani és egy 4x4 méretû mátrixban elrendezni, hogy minden szín minden figurával elõforduljon és minden sorban, illetve oszlopban minden szín és minden figura pontosan egyszer forduljon elõ.