Cím: Latin négyzetek, szép sudoku megoldások és véges geometriák I.
Szerző(k):  Kiss György 
Füzet: 2010/március, 130 - 136. oldal  PDF file
Témakör(ök): Szakmai cikkek

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

1

1. Latin négyzetek
 

n-edrendű latin négyzetnek olyan n×n-es táblázatot nevezünk, amelynek mezőit úgy töltjük ki az 1,2,...,n számokkal, hogy minden sorban és minden oszlopban mindegyik szám pontosan egyszer szerepel. A jól kitöltött sudoku tábla tehát egy 9×9-es latin négyzet. Ha semmi egyéb feltételt nem támasztunk, akkor egyszerűen tudunk bármekkora latin négyzetet készíteni: az első sorba beírjuk 1-től n-ig növekvő sorrendben a számokat, majd a következő sorokat úgy készítjük, hogy az előző sort mindig ciklikusan eggyel balra léptetjük. Ilyen 6×6-os latin négyzet látható az 1. ábrán.
 
1    2    3    4    5    6  2    3    4    5    6    1  3    4    5    6    1    2  4    5    6    1    2    3  5    6    1    2    3    4  6    1    2    3    4    5  

 
1. ábra
 

Napjainkban elsősorban a statisztikusok használnak latin négyzeteket mintavételekhez. Ha például egy város 4 különböző négyévfolyamos gimnáziumába járó diákjainak tudását szeretnénk 4 tantárgyból felmérni úgy, hogy ne kelljen minden diáknak minden tárgyból megírnia a dolgozatot, de az eredmény reprezentálja az iskolák és az egyes évfolyamokra járó tanulók tudását is, akkor a következőképpen járhatunk el: az iskolákat megszámozzuk 1-től 4-ig és minden iskola minden évfolyamáról kiválasztunk egy-egy tanulót. Készítünk egy 4×4-es latin négyzetet, melynek sorai az évfolyamoknak, oszlopai pedig a négy tantárgynak felelnek meg. Ha az i-edik sor j-edik oszlopában a k számjegy áll, akkor a k-adik iskola i-edik évfolyamos tanulója a j-nek megfelelő tantárgyból ír dolgozatot.
Az első természetesen adódó kérdés a latin négyzetekkel kapcsolatban az, hogy adott n esetén hány különböző latin négyzet létezik. A továbbiakban ha a latin négyzetek számáról beszélünk, akkor mindig feltesszük, hogy az első sorban az 1,2,...,n számok növekvő sorrendben szerepelnek. Ez nem befolyásolja a négyzetek tulajdonságait, hiszen csak a jelölés megválasztását jelenti.
Könnyű belátni, hogy 2×2-es latin négyzetből egy, 3×3-asból pedig kettő van (ez utóbbi abból következik, hogy a második sor első eleme 2 vagy 3 lehet, s ennek a megadása után már egyértelműen meghatározható a többi elem). A két 3×3-as négyzet:
 
1    2    32    3    13    1    2
 
1    2    3  3    1    2  2    3    1  

 
2. ábra
 
Az n növekedésével nagyon gyorsan nő a latin négyzetek száma.
 
n     négyzetek száma  4    24    5    1344    6  9408×120     7  16927968×6!     8  535281401856×7!     9  377597570964258816×8!   
 
A pontos számot csak n15 esetén ismerjük. Ha n=15, akkor ez nagyságrendileg 1086.  M. Hall egy tétele alsó becslést ad, eszerint az n×n-es latin négyzetek száma legalább 2!3!...(n-1)!.
 
A latin négyzetekhez kapcsolódó első, írásban említett feladat 1723-ból származik: helyezzük el a francia kártya 16 különböző figuráját egy 4×4-es táblázatba úgy, hogy minden sorban is és oszlopban is minden szín és minden figura pontosan egyszer forduljon elő. Nem sokkal később, 1779-ben kapta Euler a következő feladatot II. Katalin cárnőtől: a cári seregben 6 különböző tiszti rendfokozat van. Kiválasztunk 6 különböző ezred tisztjei közül 36-ot úgy, hogy az azonos ezredbeliek közt ne legyenek azonos rangúak. Fel lehet-e sorakoztatni a tiszteket egy 6×6-os alakzatban úgy, hogy minden sorban és minden oszlopban minden rangból és minden ezredből pontosan egy szerepeljen közülük? Euler sejtette, hogy a feladat nem oldható meg, bizonyítani azonban nem tudta. Ezt csak 1900-ban sikerült G. Tarrynak belátnia.
Ezekben a feladatokban olyan latin négyzeteket kell konstruálnunk, melyeknek még extra tulajdonságai is vannak. Ha L latin négyzet, akkor jelölje Li,j az i-edik sorának j-edik elemét. Két n-edrendű latin négyzet, L1 és L2 ortogonális, ha az (Li,j1,Li,j2) párok 1i,jn esetén az 1,2,...,n számokból képezhető összes rendezett párt pontosan egyszer állítják elő. Például a 2. ábrán szereplő harmadrendű latin négyzetek ortogonálisak. Szemléletesen ha a két latin négyzetben szereplő számokat egy négyzetbe írjuk, akkor minden mezőben különböző rendezett párokat kapunk. Az eddigi feladatokat pedig úgy fogalmazhatjuk meg, hogy adjunk meg különböző méretű (4×4-est a kártyáknál, illetve 6×6-ost a tiszteknél) ortogonális latin négyzetpárokat.
Az n-edrendű latin négyzetek egy {L1,L2,...,Lk} halmaza ortogonális rendszert alkot, ha közülük bármely kettő ortogonális. Ismert, hogy ha n>2 és n6, akkor van n-edrendű ortogonális latin négyzetpár. (Ennek bizonyítása megtalálható a [2] könyv 12. fejezetében.) Az ortogonális rendszer mérete viszont nem lehet túl nagy.
 
Tétel. Az n-edrendű latin négyzetek bármely ortogonális rendszere legfeljebb n-1 elemű.
 
Bizonyítás. Legyen {L1,L2,...,Lk} ortogonális rendszer. Feltehető, hogy minden négyzet első sorában növekvő sorrendben szerepelnek az 1,2,...,n számok. Nézzük a négyzetek második sorának első elemét. Ez egyik négyzetben sem lehet 1, és bármelyik kettőben egymástól különböző kell, hogy legyen. Ha ugyanis ij esetén L2,1i=L2,1j=m teljesülne, akkor L1,mi=L1,mj=m miatt Li és Lj nem lenne ortogonális, mert az azonos számokat tartalmazó párok az első sorban szerepelnek. Vagyis ebbe a mezőbe legfeljebb n-1 különböző számot írhatunk.  
 
Ha létezik n-1 elemű ilyen halmaz úgy, hogy bármely kettő ortogonális, akkor a latin négyzetek teljes ortogonális rendszeréről beszélünk. Ha n prímszám, akkor egyszerűen készíthetünk teljes ortogonális rendszert.
Legyen m=1,2,...,n-1 esetén ai,jm az m(i-1)+(j-1) szám n-nel való maradékos osztásánál kapott maradék (azaz m(i-1)+(j-1) értéke modulo n) és legyen Li,jm=ai,jm+1. (Ha n=3, akkor a 2. ábra bal oldali latin négyzete L1, a jobb oldali pedig L2.) Könnyű belátni, hogy Lm minden m-re latin négyzet és az így készített n-1 latin négyzet közül bármely kettő ortogonális.
Hasonló módon készíthető teljes ortogonális rendszer minden prímhatvány esetén. Ezek a konstrukciók a véges síkok létezésén alapulnak, leírásuk megtalálható pl. a [4] könyv 1. fejezetében. Ha tehát n prímhatvány, akkor létezik latin négyzetek teljes ortogonális rendszere. Más esetekben a probléma nyitott, kivéve az n=6 és n=10 esetét. Ha n=6, akkor Tarry említett eredménye szerint már két ortogonális latin négyzet sem létezik. Ha n=10, akkor létezik ortogonális latin négyzetpár, de teljes ortogonális rendszer nem. Ez szintén véges síkokra vonatkozó eredményekből következik [4].
 
2. A sudoku tábla és a négydimenziós véges affin tér
 

A kitöltött sudoku tábla egy olyan 9×9-es latin négyzet, melynek még az a tulajdonsága is megvan, hogy ha 3×3-as kis négyzetekre osztjuk, akkor minden kis négyzetben is pontosan egyszer fordul elő 1-től 9-ig minden szám. A 3. ábrán látható sudoku táblának további érdekes tulajdonságai is vannak.
 

 
3. ábra
 

Nevezzük nagy sornak, illetve nagy oszlopnak az ábrán vastag vonallal határolt 3-3 sort, illetve oszlopot tartalmazó részeket. Így 3-3 nagy sor és nagy oszlop van, bármely nagy sor és nagy oszlop metszete egy kis négyzet. Minden kis négyzet 3-3 kis sort, illetve kis oszlopot tartalmaz, melyeket fentről lefelé, illetve jobbról balra megszámozunk. Nevezzük törött oszlopnak valamely nagy sorban lévő 3 kis négyzet ugyanannyiadik kis oszlopait, törött sornak valamely nagy oszlopban lévő 3 kis négyzet ugyanannyiadik kis sorait, pozíciónak pedig a 9 kis négyzet mindegyikében egy rögzített sorszámú kis sor és egy rögzített sorszámú kis oszlop metszetét. A törött sorok, törött oszlopok és pozíciók tehát 9-9 mezőt tartalmaznak. A 3. ábrán látható sudoku megoldásra az is igaz, hogy 1-től 9-ig minden szám pontosan egyszer fordul elő minden törött sorban, törött oszlopban és pozícióban. Az ilyen kitöltést szép megoldásnak nevezzük. A továbbiakban célunk az összes szép megoldás megadása.
Ehhez először koordinátákkal látjuk el a sudoku tábla mezőit. Számozzuk meg 0,1,2-vel a nagy sorokat, az egyes nagy sorokon belül a sorokat, a nagy oszlopokat és az egyes nagy oszlopokon belül az oszlopokat a 4. ábrán látható módon fentről lefelé, illetve balról jobbra.
 

 
4. ábra
 

Ekkor minden mezőhöz egy-egy 4 hosszú, a 0, 1, 2 számjegyeket tartalmazó számnégyest rendelhetünk. Az első számjegy legyen a mezőt tartalmazó nagy sorhoz, a második a sorhoz, a harmadik a nagy oszlophoz, a negyedik pedig az oszlophoz rendelt szám. (A 4. ábrán megjelölt mezőhöz tehát az (1,2,0,1) számnégyest rendeljük.) Így a 81 mezőt megfeleltetjük a 81 db 4 hosszú 0‐1‐2 számokból álló számnégyesnek. A továbbiakban ezeket a számnégyeseket (a lineáris algebrában megszokott módon) vektoroknak nevezzük, és leírásukra az x=(x1,x2,x3,x4) jelölést használjuk. Speciálisan 0=(0,0,0,0).
Értelmezzük két vektor összegét és egy vektor egész számszorosát úgy, ahogy az elemi geometriában a szokásos vektorok esetén megszoktuk, azaz legyen x=(x1,x2,x3,x4) és y=(y1,y2,y3,y4) esetén
x+y=(x1+y1,x2+y2,x3+y3,x4+y4),
valamint tetszőleges α egész szám esetén αx=(αx1,αx2,αx3,αx4). Az összeadást és a szorzást persze modulo 3 végezzük, azaz az egész számok helyett csak azok hármas maradékát tekintjük. Tehát pl. -1=2, 1+2=0 és 2+2=22=1. Tetszőleges x1,x2,...,xk vektorok és α1,α2,...,αk egész számok esetén az α1x1+α2x2+...+αkxk vektort az x1,x2,...,xk vektorok lineáris kombinációjának nevezzük. Ha az α1x1+α2x2+...+αkxk=0 egyenlőségből következik, hogy α1=α2=...=αk=0, akkor az x1,x2,...,xk vektorokat lineárisan függetleneknek, egyébként pedig lineárisan összefüggőeknek nevezzük.
Legyenek a0 és p tetszőleges vektorok. Ekkor az
Ea,p={p+αaα=0,1,2}
halmazt a p-n átmenő a irányú egyenesnek nevezzük.
Legyenek a, b és p tetszőleges vektorok, melyek közül a és b lineárisan függetlenek. Ekkor az
Sa,b,p={p+αa+βbα,β=0,1,2}
halmazt a p-n átmenő a és b által meghatározott síknak nevezzük. Legyenek a, b, c és p tetszőleges vektorok, melyek közül a,b és c lineárisan függetlenek. Ekkor a
Ha,b,c,p={p+αa+βb+γcα,β,γ=0,1,2}
halmazt a p-n átmenő a, b és c által meghatározott hipersíknak nevezzük.
Jelölje N a 81 darab vektor által alkotott halmazt. N elemeit pontoknak nevezzük, az előzőekben definiált egyenesekkel, síkokkal és hipersíkokkal együtt pedig N a háromelemű test feletti négydimenziós affin tér. Itt most ennek csak a legfontosabb tulajdonságait ismertetjük, az érdeklődő olvasó a részleteket megtalálja a [4] könyvben.
Tetszőleges CN vektorhalmaz és tetszőleges x vektor esetén legyen C+x={c+xcC}. Ezt a halmazt a C  x vektorral való eltoltjának nevezzük. Az egyeneseket egy-, a síkokat két-, a hipersíkokat pedig háromdimenziós affin altereknek hívjuk. Azt mondjuk, hogy az A1 és A2 affin alterek párhuzamosak, ha van olyan x vektor, melyre A1=A2+x teljesül.
Egyszerűen meggondolható, hogy az affin alterek rendelkeznek a ,,szokásos'' euklidészi geometriából megismert tulajdonságokkal:
Két különböző ponthoz pontosan egy olyan egyenes van, amely mindkét pontot tartalmazza.
Ha három pont nincs egy egyenesen, akkor pontosan egy olyan sík van, amely mindhárom pontot tartalmazza.
Ha adott a P pont és az A affin altér, akkor pontosan egy P-n átmenő, A-val párhuzamos affin altér létezik.
Ha valamely A affin altér tartalmazza egy E egyenes két különböző, vagy egy S sík három nem kollineáris pontját, akkor A tartalmazza E, illetve S minden pontját.
Ha az S1 és S2 síkok nem párhuzamosak, akkor vagy pontosan egy közös pontjuk van, s ekkor S1 bármely eltoltjának is pontosan egy közös pontja van S2 bármely eltoltjával; vagy pedig metszetük egy egyenes, s ekkor pontosan egy olyan hipersík van, mely S1-et is és S2-t is tartalmazza.
Ezen kívül persze olyan tulajdonságaik is vannak, melyek a modulo 3 számolásból adódnak:
Minden egyenesen 3 pont van.
Minden síkon 9 pont és 12 egyenes van.
Minden hipersíkban 27 pont, 117 egyenes és 39 sík van.

Ezeknek a tulajdonságoknak a bizonyítását feladatnak hagyjuk. Segítségként megadjuk a=(1,0,0,0) és b=(0,1,0,0) esetén az Sa,b,0 sík egy lehetséges leírását. A véges affin síkokról részletesen olvashatunk a lapunk 2006. decemberi számában megjelent [3] cikkben, vagy a [4] könyvben.
Mivel Sa,b,0 minden pontjának harmadik és negyedik koordinátája 0, azért csak az első és a második koordinátákat adjuk meg. A síkot legegyszerűbben egy derékszögű koordináta-rendszerrel ellátott klasszikus euklidészi sík mintájára képzelhetjük el, csak most a valós számok helyett a {0,1,2} halmaz elemeivel koordinátázunk és modulo 3 számolunk. A sík pontjai az olyan rendezett (a,b) párok, ahol a,b{0,1,2} (a klasszikus esetben a sík pontjai a valós számokból készített rendezett pároknak felelnek meg). Az egyenesek kétfélék: egyrészt az [m,d] típusú rendezett párok, ahol m,d{0,1,2}, másrészt a [c] típusú elemek, ahol c{0,1,2} (a klasszikus esetben a sík nem függőleges egyenesei egyértelműen megadhatók m meredekségükkel és azzal a (0,d) ponttal, ahol az Y tengelyt metszik, míg a függőleges egyenesek egyértelműen leírhatók azzal a (c,0) ponttal, ahol az X tengelyt metszik). Két egyenes párhuzamos, ha mindkettő [c] típusú, vagy ha mindkettő [m,d] típusú és a két egyeneshez tartozó m értékek megegyeznek. Az (a,b) pont akkor és csak akkor van rajta az [m,d] egyenesen, ha teljesül, hogy bma+d(mod  3) (azaz az ma+d szám 3-mal osztva b-t ad maradékul), a [c] egyenesen pedig pontosan akkor, ha a=c. A klasszikus esethez hasonlóan azt mondjuk, hogy az [m,d] egyenes egyenlete Y=mX+d, illetve a [c] egyenes egyenlete X=c. A síkon tehát 33=9 pont és 33+3=12 egyenes van. Az 5. ábrán Sa,b,0 pontjai koordinátáikkal, egyenesei pedig (amik persze az ábrán nem rajzolhatók meg úgy, mint az euklidészi sík egyenesei) egyenletükkel együtt szerepelnek.
 

 
5. ábra
 

Irodalomjegyzék
 


[1]Bailey, R., Cameron, P. J. és Connelly, R.: Sudoku, gerechte designs, resolutions, affine space, reguli and Hamming codes, Amer. Math. Monthly (2008), 383‐404.
[2]Dénes, J. és Keedwell, A. D.: Latin Squares and their Applications, Akadémiai Kiadó (Budapest, 1974).
[3]Kiss Gy.: Hogyan szervezzünk körmérkőzéses focibajnokságot? KöMaL, 56 (2006), 514‐525.
[4]Kiss Gy. és Szőnyi T.: Véges geometriák, Polygon Kiadó (Szeged, 2001).

1A cikk elkészítését az NK 67867 és a K 81310 számú OTKA pályázat támogatta.