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

4. A futamok geometriája

4. A futamok geometriája

Úgy tűnhet tehát, hogy bele kell nyugodnunk: 16 versenyző négyes futamokba osztása csak rendszertelenül, „szerencsésen” valósítható meg. De érdemes alaposabban meggondolni, valóban így van-e ez. Mielőtt azonban ebbe belefognánk, foglalkozzunk még kicsit az eddig kapott beosztásokkal. Ezek bizonyos értelemben többet tudnak, mint amit akartunk. A sík egyeneseinek ugyanis van egy további alapvető kombinatorikus tulajdonsága, azon kívül, hogy bármely két ponton át pontosan egy egyenes megy keresztül. Ez pedig a következő axióma:

A2 Bármely egyeneshez és hozzá nem illeszkedő ponthoz pontosan egy a ponton átmenő, az egyenest nem metsző egyenes van.

A koordinátarendszer segítségével – azaz a prímszám k -kra – kapott beosztások tehát mindkét alábbi szabálynak megfelelnek:

1. szabály. Minden versenyző mindegyik másikkal pontosan egyszer találkozik.

2. szabály. Ha adott egy futam és egy abban nem szereplő versenyző, akkor pontosan egy olyan futam van, amelyben az adott versenyző szerepel, de az adott futam egyik tagja sem szerepel.

A következő állításunkat feladat formájában közöljük; később még sokszor fogjuk ezt tenni olyan esetekben, mikor egy-egy érdekes, de a továbbiakhoz nem feltétlenül szükséges állításhoz érünk. A feladatok megoldását a cikk végén adjuk meg.

1. feladat. Lássuk be, hogy a fenti két szabály egyúttal azt is jelenti, hogy a futamokat beoszthatjuk fordulókba oly módon, hogy egy forduló futamai közül bármely versenyző pontosan egy futamban szerepeljen!

Ha tehát rendelkezésünkre áll k pálya, akkor egy-egy forduló futamait megrendezhetjük egyszerre, és minden versenyző pályára is lép mindegyik fordulóban. Ez az állítás nyilvánvalóan igaz a koordináta-rendszer segítségével kapott beosztásokra; a feladat viszont az, hogy az állítás akármilyen, a két szabálynak eleget tevő beosztásra teljesül.

Talán meglepő, hogy a 16 versenyzőre kapott „csúnya” beosztásra is teljesül ez. A fentiekben megadott húsz futamot ugyanis beoszthatjuk öt fordulóba a következőképpen:

I. forduló:

1., 2., 3., 4. futam

II. forduló:

5., 6., 7., 8. futam

III. forduló:

9., 12., 17., 20. futam

IV. forduló:

10., 14., 15., 19. futam

V. forduló:

11., 13., 16., 18. futam.

Ellenőrizhető, hogy két futam pontosan akkor diszjunkt, ha egy fordulóba tartozik, ezért a 2. szabály is teljesül.

Az olvasónak most már talán gyanús, hogy ha k 2 versenyzőt akarunk k -as futamokba beosztani, akkor az 1. szabályból következik a 2. szabály. Ez valóban így is van.

2. feladat. Bizonyítsuk be az előbbi állítást!

Ha tehát k 2 versenyzőt be tudunk osztani k -as futamokba oly módon, hogy bármely két versenyző pontosan egyszer találkozzon, akkor a versenyzők és a futamok egy különös, véges általánosítását adják az euklidészi síknak. A versenyzőket pontoknak, a futamokat pedig egyeneseknek tekintve, szabályaink az A1 és A2 axiómáknak felelnek meg.

Mindez igaz megfordítva is, ha hozzátesszük az alábbi egyszerű axiómát:

A3 Van három nem egy egyenesen lévő pont.

A következő feladat megoldásában és a továbbiakban, a geometriában megszokottakhoz hasonlóan, két egyenest párhuzamosnak nevezünk, ha nem metszik egymást.

3. feladat. Bizonyítsuk be, hogy ha adott egy véges halmaz és annak bizonyos részhalmazai úgy, hogy az alaphalmaz elemeit pontoknak, az adott részhalmazokat pedig egyeneseknek tekintve teljesülnek a A1, A2, és A3 feltételek, akkor minden egyenesen ugyanannyi pont van, és ha ezt a számot k -val jelöljük, akkor a pontok száma éppen k 2 .

Az A1, A2, A3 axiómáknak megfelelő struktúrákat affin síkoknak nevezik[2]. A véges affin síkhoz az előző feladat szerint található k számot az affin sík rendjének nevezik. Eddigi vizsgálataink alapján kimondhatjuk: pontosan akkor létezik k 2 versenyzőhöz megfelelő futambeosztás, ha létezik k -adrendű affin sík.

Az 1. feladat alapján most már világos, hogy a k -adrendű affin sík egyenesei beoszthatók olyan csoportokba (ún. párhuzamossági osztályokba), hogy két egyenes pontosan akkor párhuzamos, ha egy csoportban szerepel, és minden csoportban k egyenes szerepel, azaz együtt az összes pontot tartalmazzák. Miután egy ponton a 3. feladat megoldása szerint k + 1 egyenes megy át, ezek szerint éppen k + 1 párhuzamossági osztály van. Így az is látható, hogy az egyenesek száma k 2 + k .



[2] Könyvünkben egy másik véges ponthalmazon is létező geometriával, a projektív síkkal is megismerkedhetünk.