Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

9. Latin négyzetek

9. Latin négyzetek

Mint láttuk, ha k //>// 1 és k nem prímhatvány, akkor nincs k elemű test. Ettől azonban még elvben létezhet k -adrendű affin sík. A legkisebb ilyen eset a k = 6 ; ezzel kapcsolatos a problémakör leghosszabb múltra visszatekintő kérdése. (A kapcsolat nem nyilvánvaló első látásra, de a későbbiekben meg fogjuk mutatni.) Euler foglalkozott a következő problémával egy 1782-ben megjelent cikkében:

A 36 tiszt feladata: Tekintsük a hadsereg hat fegyvernemét és hat rendfokozatát. Vegyünk minden fegyvernemből hat tisztet az egyes tekintett rendfokozatokkal, összesen tehát harminchat tisztet. Elrendezhetők-e ők 6 × 6 -os alakban úgy, hogy minden sorban és minden oszlopban minden fegyvernem és minden rendfokozat képviseltetve legyen?

Euler az a , b , c , d , e , f latin betűkkel jelölte a fegyvernemeket és az ? , ß , ? , ? , ? , ? görög betűket használta a rendfokozatokra. Egy katonát egy görög és egy latin betűből álló pár jelölt. A lehetséges 36 betűpárt úgy kellett beírni egy 6 × 6 -os táblázatba, hogy minden sorban és minden oszlopban pontosan egy betű forduljon elő. Ez az eredete az elnevezésnek: „a görög-latin négyzetek problémája”.

c ? b ? a ß b ß a ? c ? a ? c ß b ?

3 × 3 -as görög–latin négyzet

A feladat meglepően nehéznek bizonyult, de „kisebb társaival” az olvasó is bátran próbálkozhat:

7. feladat. Oldjuk meg a görög-latin négyzetek problémáját 2-2, 4-4 és 5-5 görög és latin betűvel (illetve 2 × 2 -es, stb. táblázattal)! Melyik esetben nincs megoldás?

Euler nem tudta megoldani a feladatot. Úgy gondolta, hogy nincs is megoldás, és azt a sejtést fogalmazta meg, hogy ha k ? 2 ( mod 4 ) , akkor k - k betűvel sincsenek k × k -as görög-latin négyzetek. A kérdés nehézségét mutatja, hogy csak 1900-ban sikerült bizonyítania Tarrynek, hogy a 36 tiszt feladata nem megoldható. 1922-ben McNeish bebizonyította Euler sejtésének megfordítását, tehát hogy k ? 0 , 1 , 3 ( mod 4 ) esetén léteznek görög-latin négyzetek.

Próbálkozásai során Euler először csak a latin betűket rendezte el. A probléma általános megközelítésében már nem betűket használnak, de erre utalva k -adrendű latin négyzetnek nevezzük a k × k -as táblázatot, ha úgy van kitöltve az 1, 2, , k számokkal, hogy minden sorban és minden oszlopban mindegyik számból pontosan egy szerepel.

Két azonos rendű latin négyzetet ortogonálisnak nevezünk, ha egymásra helyezve őket mind az n 2 lehetséges számpár megjelenik.

3 2 1 2 1 3 1 3 2 3 1 2 2 3 1 1 2 3 33 21 12 22 13 31 11 32 23

Két 3-adrendű ortogonális latin négyzet

Euler eredeti problémája tehát így is fogalmazható: van-e két 6-odrendű ortogonális latin négyzet? Természetesen adódik a következő általánosabb kérdés:

Az ortogonális latin négyzetek problémája: Adott k esetén legfeljebb hány latin négyzet adható meg úgy, hogy bármelyik kettő ortogonális legyen egymásra?

8. feladat. Oldjuk meg az ortogonális latin négyzetek problémáját k = 2 , 3, 4 és 5 esetén!

9. feladat. Mutassuk meg, hogy k //>// 1 esetén nem létezik k darab k -adrendű ortogonális latin négyzet!

Az affin síkok és az ortogonális latin négyzetek közötti kapcsolatot Bose vette észre 1938-ban. Megmutatta, hogy:

Pontosan akkor létezik k -adrendű affin sík, ha létezik ( k - 1 ) ortogonális k -adrendű latin négyzet.

A két struktúrát a következőképp feleltethetjük meg egymásnak. A sík k 2 + k egyenese ( k + 1 ) párhuzamossági osztályba sorolható (ezek felelnek meg a motorversenyek „fordulóinak”). Mindegyik párhuzamossági osztályban k egyenes van; számozzuk meg őket 1-től k -ig. Most rendezzük el a k 2 pontot egy k × k -as táblázatba a következőképpen. Válasszuk ki az egyik párhuzamossági osztályt és az 1. egyenes pontjait tegyük az 1. sorba, a 2. egyenes pontjait a 2. sorba, stb. Az egyes sorokon belül a pontok rendeződjenek el egy másik párhuzamossági osztály egyenesei szerint: az 1. oszlopba kerüljenek az 1. egyenes pontjai, a 2. oszlopba a 2. egyenes pontjai, stb. Ezután mindegyik osztálynak megfeleltethetünk egy táblázatot úgy, hogy a táblázat mezőibe beírjuk az adott osztály azon egyenesének sorszámát, amely a mezőnek megfelelő ponton halad át.

Ha két különböző osztálynak megfelelő táblázatot egymásra helyezünk, akkor semelyik két helyen sem kapjuk ugyanazt a számpárt, hiszen semelyik két egyenes sem metszi egymást két pontban. Tehát a négyzetek ortogonálisak egymásra.

A ( k + 1 ) táblázat közül kettő nagyon egyszerű: egyikükben a sorokban állnak azonos számok, másikukban az oszlopokban. Az erre a két táblázatra való ortogonalitás miatt a többi táblázat latin négyzet. Ez a ( k - 1 ) táblázat tehát ortogonális latin négyzet.

1 1 1 2 2 2 3 3 3 1 2 3 1 2 3 1 2 3 3 2 1 2 1 3 1 3 2 3 2 1 2 3 1 1 2 3

Hármas futamok négy fordulóban – két ortogonális latin négyzet

Teljesen hasonlóan hozhatunk létre ( k - 1 ) ortogonális latin négyzetből egy k -adrendű affin síkot.

Bose és Fisher (az utóbbi tételével Gyárfás András írásában találkozhatunk) eredetileg statisztikusok voltak. A latin négyzetek és a véges síkok felé fordulásuk okát egy példával illusztráljuk. Tegyük fel, hogy egy terméket, egy alkalmazott egy bizonyos napszakban, egy alapanyagból, egy gép segítségével állít elő. A termék előállításához a cég 3 alkalmazott közül választhat, akit 3 napszak (pl. de., du., este) egyikében dolgoztathat, 3 rendelkezésre álló gép és 3 lehetséges alapanyag egyikével. A cégvezetés szeretné megérteni, hogy a termék minősége hogyan függ e négy körülménytől. Egy teljes elemzéshez mind a 3 4 = 81 variációt ki kellene próbálni. A statisztika „varianciaanalízis” nevezetű eljárásával azonban akkor is fel tudjuk tárni a minőséget befolyásoló összefüggéseket, ha a próbákat úgy szervezzük, hogy a négy közül bármelyik két ”körülmény” bármelyik megvalósulása „találkozzék” egymással egy-egy próbán. Ehhez 9 próba is elég. A 9 tervezett próbát rendezzük el 3 × 3 -as táblázatba! A fenti négy ortogonális négyzetet feleltessük meg a négy körülménynek, a bennük levő számokat pedig az adott körülmény 3 lehetséges megvalósulásának! A négy táblázat együtt megadja, hogy milyen próbákat végezzünk: pl. a bal felső elemnek megfelelő próbán az első két körülményből az 1. változatot, az utolsó kettőből a 3. változatot kell szerepeltetni. A példa persze nagyon speciális, nem várható el, hogy minden körülményt ugyanannyi módon lehessen megválasztani. Ez motiválja a véges síkok általánosításának tekinthető „blokkrendszerek” elméletének kifejlődését. De most térjünk vissza síkjainkhoz!

A 36 tiszt problémájának Tarry-féle bizonyítása után Bose tételéből következett, hogy nem létezik hatodrendű affin sík. Azt is mondhatjuk, hogy ez a sík „nagyon nem létezik”, hiszen – a salakmotorosok nyelvén szólva – már 2 + 2 = 4 fordulót sem lehet szervezni a 36 versenyzőnek. Euler sejtésének pedig az lenne a következménye, hogy k = 10 -re, 14-re stb. sincs affin sík.

Ennél kevesebbet és egyszerre többet is bizonyított Bruck és Ryser 1949-ben kimondott tételükkel:

Bruck–Ryser tétel. Ha k ? 1 , 2 ( mod 4 ) és létezik k -adrendű affin sík, akkor k előáll két négyzetszám összegeként.

Eredményük egyben új bizonyítás arra, hogy nincs 6-odrendű affin sík, hiszen 6 ? 2 ( mod 4 ) , de 6 nem két négyzetszám összege. A k = 10 eset nyitva maradt, mert 10 = 1 + 9 , de k = 14 -re és még végtelen sok k -ra bebizonyosodott, hogy nem létezik k -adrendű affin sík.

Az affin síkok és a latin négyzetek története meglepő fordulatot vett 1959-ben, amikor Parker megmutatta, hogy Euler sejtése nem igaz k = 10 -re. Egy évvel később Bose-zal és Shrikhandéval közösen bebizonyították, hogy minden 2-től és 6-tól különböző k -ra létezik két ortogonális latin négyzet! Feltámadt a remény, hogy hátha mégis van 10-edrendű affin sík. Végül a számítógép segítségét is igénybe véve Lam, Thiel és Swiercz 1989-ben tisztázták: nincs 10-edrendű sík. Mindmáig nyitott kérdés, hogy létezik-e három ortogonális 10 × 10 -es latin négyzet.

Eddig tehát csupa negatív eredmény született azzal kapcsolatban, hogy van-e nem prímhatványrendű affin sík, de végtelen sok k -ra (pl. 12-re, 15-re, 18-ra) ma sem tudjuk a választ. Lehet, hogy valaki egyszer talál ilyen síkot? Vagy egy egyszerű indok kizár minden más esetet? Lehet, hogy pl. minden véges affin sík testre építhető?

Az indok – ha van – biztosan nem ilyen egyszerű. Ez kiderül a következő két fejezetből.