Matematikai kiegészítés: permutációk

Látható, hogy PUSH, POP, SWAP utasítások használatával bármely két, egymás melletti elem felcserélhetõ. Egymás melletti elemek cseréjével viszont egy elem bármelyik pozícióba eljuttatható, és közben a többi elem sorrendje nem változik (ld. pl. a buborékos rendezésnél). Mutasd meg, hogy ilyen módon bármely két elem sorrendje felcserélhetõ! Mutasd meg, hogy az elemek bármilyen sorrendje elõállítható így!

Elemek cserélgetésével tehát az elemek bármely sorrendje (permutációja) elõállítható, egy permutáció természetesen többféleképpen is. Most bebizonyítjuk, hogy egy adott sorrendet vagy páros, vagy páratlan számú cserével érhetünk el, sohasem mindkét módon. Az a és b pozíción lévõ elemek cseréjét (a b)-vel jelöljük.

Elég belátni azt, hogy az eredeti állapotot csak páros számú cserével állíthatjuk vissza. Indirekt módszer: vegyünk egy cseresorozatot: (n m)(...)(...)(...), amely páratlan cserébõl áll, és visszaállítja az eredeti állapotot. Ha máshol nem szerepel benne n, máris biztos, hogy nem állíthatja vissza az eredeti állapotot, hiszen az n. pozícióra került elemet másik csere már nem távolítja el. Tehát valahol van még benne n.

Keressük meg n legutolsó elõfordulását. Ez lehet (x y)(n i) (különbözõ betûk most különbözõ számokat jelentenek). Ekkor a sorrendjük felcserélhetõ, mivel különbözõ pozíciókat érintenek: (n i)(x y). Lehet még (n x)(n i) is, ez azonos eredményt ad (n i)(i x) cserével. Lehet (i x)(n i) is, ennek eredménye azonos (n x)(i x) cserével. Mindegyik esetben az n-et tartalmazó csere eggyel korábbra került úgy, hogy a végeredmény nem változott. Tehát ebben az esetben n végül a legelsõ helyre kerül, és utána nem fordul elõ többször: ez a cseresorozat viszont az elõzõek értelmében nem adhatja vissza az eredeti állapotot.

Egy lehetõség van még: n balra léptetése során elõbb-utóbb elõáll az (n i)(n i) lehetõség. Ekkor ezt a két cserét ki lehet hagyni (egymás utánjuk ugyanis nem változtat semmit), és a cserék száma kettõvel csökkent. Tehát: ha van egy cseresorozatunk, amely visszaadja az eredeti állapotot, biztos van nála 2-vel rövidebb is. Igen ám, de így (ha a cseresorozat páratlan) eljutunk a 3, majd az 1 cseréhez. 1 csere viszont soha nem adhatja vissza az eredeti állapotot. Így minden ágon ellentmondásra jutottunk, bebizonyítottuk, hogy páratlan cserével nem kaphatjuk vissza az eredeti állapotot.

Most nézzük meg, mi történne, ha páros és páratlan számú csere egymásutánja ugyanarra az eredményre vezetne. Elõször végezzük el a páros számú cserét, majd a páratlan számúakat fordított sorrendben. Így visszakapjuk az eredeti állapotot, mégpedig páros+páratlan=páratlan számú cserével, ami az elõzõek szerint nem lehetséges.

Ennek a tételnek ismert alkalmazása a 15-ös játék egyik fejtörõjének megoldása. A 15-ös játék 4X4 négyzetbõl álló táblázat, melyen 15 szám és egy üres négyzet található. A számok az üres helyre betolhatók (vagyis helyet cserélhetnek az üres hellyel). Ezután felcserélik a négyzeteket, a cél az eredeti állapot visszaállítása tologatásokkal.

Sokan foglalkoztak a következõ feladvány megfejtésével (az utolsó két négyzet lett felcserélve), de senkinek sem sikerült visszarendeznie az eredeti állapotba. De vajon lehetséges-e? Ha sakktáblaszerûen kiszínezzük a táblát, látható, hogy az üres négyzet minden cserénél más színre kerül. Ha a végén visszakerül a helyére, tehát világos mezõre, biztos, hogy páros csere történt. Viszont az eredeti állapot egyetlen (páratlan számú) cserével visszaállítható, ezért nem állítható vissza páros cserével. A feladvány tehát megoldhatatlan.