Az 1998. évi könyvhéten kiemelkedõ érdeklõdés kísérte Vámos Miklós új könyvét, melybõl az átlagosnál jóval többet adtak el, és az utóbbi években ritkán látott módon több százan álltak sorba dedikálásért. A szerzõ maga sem titkolja, hogy sikerében jelentõs része van “Lehetetlen” címû televíziós mûsorának, amelynek nézettsége néha a hárommilliót is elérte. A “Lehetetlen”-nek az volt az egyik mondanivalója, hogy lehetetlen nincs (csak esetleg az egyes emberek tehetetlenek). Bár a Vámos-mûsor címét választottam e dolgozat címének, a mûsortól eltérõen azt kívánom megmutatni, hogy a matematikában a lehetetlennek éppoly fontos szerepe van, mint a lehetségesnek, és a lehetetlennel kapcsolatos kérdések a matematika legizgalmasabb fejezetei közé tartozhatnak.

  Minden más tudománytól eltérõen a matematikában ugyanis gyakran igazoljuk, hogy valami nem lehetséges, valami nincs. Mielõtt erre példákat mutatnánk a matematika történetébõl, tekintsünk néhány egyszerûbb feladatot!

1. feladat. Újságok rejtvényoldalain gyakran találkozhatunk azzal a feladattal, hogy egy adott ábrát kell lerajzolni a ceruza felemelése nélkül. Például rajzoljuk le az 1. ábrát ilyen módon!

  Több-kevesebb sikertelen próbálkozás után az emberben óhatatlanul felmerül a kérdés, hogy a feladat egyáltalán végrehajtható-e, és valóban, mint azt alább megmutatjuk, a fenti lerajzolás nem lehetséges. Itt tehát nem arról van szó, hogy mi nem tudjuk lerajzolni, vagy hogy eddig még senkinek sem sikerült ez, hanem arról, hogy felesleges is ilyet keresni, mert ilyen nincs.
 
 

1. ábra. Megrajzolható-e egy vonallal a ceruza felemlése nélkül?	2. ábra "Tologatós játék"	3. ábra. A "tologatós" játék az "1" és a "2" felcserésével

  2. feladat. Tekintsük a jól ismert tologatós (más néven tizenötös) játékot (2. ábra), amelynek egyes négyzeteit csúsztathatjuk, ha a szomszédos mezõ üres! A játék abból áll, hogy egy “összekevert” állásból kell az eredeti 1, 2, ..., 15 sorrendet visszaállítani. Mármost tételezzük fel, hogy valaki nem csúsztatásokkal állítja elõ az “összekevert” állást, hanem kiszedi a kis négyzeteket, és azokat valamilyen sorrendben visszarakja. Például tételezzük fel, hogy úgy rakjuk õket vissza, hogy minden a helyére kerül, kivéve az 1-es és 2-es számú négyzeteket, amelyeket viszont megcserélünk (3. ábra). A kérdés az, hogy ekkor is elõ tudjuk-e állítani az eredeti sorrendet a játék szerinti csúsztatásokkal.

  Mint látni fogjuk, ez a fenti konkrét esetben nem lehetséges.

  3. feladat. Biztosan sokan ismerik a 4. ábrán látható tüske (más néven szoliter) játékot, amelynél egy lyukakat tartalmazó tábla bizonyos lyukaiba tüskéket teszünk, és a játék során egy tüskével (vízszintesen vagy függõlegesen) átugorhatunk egy mellette levõ tüskét, feltéve, hogy annak másik oldalán szabad lyuk van, viszont a lépés során az átugrott tüskét le kell venni a tábláról (5. ábra). A játék különféle táblákon ismeretes, és általában az a cél, hogy a lehetõ legtöbb tüskét vegyük le a fenti módon.
 
 

4. ábra. A tüskejáték	5. ábra. A cél, hogy a lehetõ legtöbb tüskét vegyük le

  A mi feladatunk viszont kissé más, nevezetesen azt kérdezzük, hogy üres részre milyen messzire lehet eljutni a fenti játékban; pontosabban tételezzük fel, hogy a tábla mérete tetszõleges nagy, és a kezdeti tüskék mind egy adott vonalon vagy az alatt helyezkednek el (6. ábra). A kérdés az, hogy tetszõleges (általunk választott) kezdõállásból kiindulva milyen magasra tudunk a vonal fölé feljuttatni egy tüskét.

  Már az sem világos, hogy nem lehet akármilyen magasra feljuttatni, de hoszszabb-rövidebb próbálgtatás után rájövünk, hogy 4 magasra még sikerül tüskét feljuttatni, de 5 magasra sohasem, és valóban, az igazolandó, hogy teljesen mindegy, milyen kezdeti helyzetbõl indulunk ki és a játék során milyen stratégiát használunk, soha nem tudunk 5 magasra feljuttatni tüskét, azaz az adott vonal feletti 5. és magasabb sorokban levõ lyukak mindig üresen maradnak (ez John Conway egy észrevétele).

  A fenti feladatokkal kapcsolatban megfogalmaztunk egy-egy lehetetlenségi állítást. De hogyan lehet ezeket igazolni? Például az 1. feladatnál elvben végignézhetnénk az összes lehetséges rajzolási módot, és megállapíthatnánk, hogy egyik sem jó. Bár ez az adott feladatnál lehetséges, bonyolultabb ábráknál ez nagyon idõigényes lehet. A 2. feladatban már reménytelen végigpróbálni az összes lehetséges helyreállítási próbálkozást azok nagy száma miatt. A 3. feladatnál pedig már a szóba jöhetõ kezdeti konfigurációk száma is végtelen (végtelen táblát feltételezve), így azok végigpróbálása szóba sem jöhet.

  De akkor hogyan lehet a fenti állításokat igazolni? Egyáltalán hogyan lehet igazolni azt, hogy valami lehetetlen, nem létezik, nincs?

  Sokszor ez nem is olyan nehéz. Például az 1. feladatnál vegyük észre, hogy a rajzolás során, ha egy csomópontba beérünk, akkor onnan tovább is megyünk, ezért a csomópontokban a vonalak párosával kell, hogy szerepeljenek; kivéve persze a kezdõ és végsõ csomópontot, ha azok nem ugyanazok, hiszen a kezdõ csomópontban az induló vonalnak, a végsõ csomópontban pedig az érkezõ vonalnak nincs párja. Tehát ha egy ábra lerajzolható a ceruza felemelése nélkül, akkor vagy minden csomópontban páros sok vonal találkozik, vagy pedig két csomópont kivételével igaz ez. Mármost az 1. ábrán van három olyan csomópont, ahol három vonal, és van egy olyan csomópont, ahol öt vonal találkozik, tehát ebben az ábrában kettõnél több olyan csomópont van, ahol páratlan sok vonal találkozik, ezért ez az ábra nem rajzolható le.

  A fenti megoldás teljesen univerzális, bármely (összefüggõ) ábra akkor rajzolható le a ceruza felemelése nélkül, ha legfeljebb két olyan csomópont van benne, amelyeknél páratlan sok vonal találkozik; sõt azt is megadja, hogy ha van két ilyen csomópont, akkor a rajzolást feltétlenül az egyiknél kell kezdeni.

A második feladatnál egy adott állásban írjuk fel a kis négyzetek számait a 7. ábrán látható sorrendben. Tehát amikor minden mezõ a helyén van, akkor így az

sorrend adódik, míg a feladatban szereplõ kiinduló állás sorrendje az

  Az 1–15 számok tetszõleges sorrendjében számoljuk meg, hogy hány olyan számpárt találunk, amelynél egy nagyobb szám egy kisebb szám elõtt áll, és nevezzük ezt a számot az adott sorrend indexének. Például S₁ sorrendnél ezek a számpárok a

  Így ennek a sorrendnek az indexe 12, míg az S₂ sorrend indexe 13 a további (2, 1) pár miatt. Most tekintsük, hogy mi történik egy csúsztatásnál! Ha vízszintesen csúsztatunk, akkor a számok sorrendje egyáltalán nem változik meg, míg ha egy függõleges csúsztatást hajtunk végre, akkor a csúsztatott szám 0, 2, 4 vagy 6 hellyel kerülhet elõrébb vagy hátrább. Könnyen látható, hogy eközben az index páros (pontosabban 0, 2, 4, 6) számmal változhat meg (például, ha a sorrend
..., a, b, x, y, z, u, c, d, ... volt, és ebbõl az ..., a, x, y, z, u, b, c, d, .... sorrend lett, akkor az index csak az {x,b}, {y,b}, {z,b}, {u,b} számpárok miatt változhat, és ezek miatt változik is, mert ha y < b, akkor a (b, y) párt számoltuk az elsõ sorrendnél, de nem számoltuk a másodiknál, míg ha b < y, akkor fordítva, az (y, b) párt számoltuk a második sorrendnél, de nem számoltuk az elsõnél. Tehát összességében négy hely átugrásakor az index 0-val, 2-vel vagy 4-gyel nõhet vagy csökkenhet). Mivel a kiindulási S₂ sorrend indexe páratlan, és, mint azt éppen láttuk, az index csak páros számmal változhat, azt kapjuk, hogy csúsztatásoknál az S₂ sorrendbõl indulva csak olyan sorrendek érhetõk el, amelyek indexe páratlan, így többek között az eredeti S₁ sorrend nem érhetõ el.

  Persze az teljesen érdektelen kérdés, hogy a 3. ábrán látható konfigurációból az eredeti (2. ábrán látható) konfiguráció visszakapható-e. Az igazán érdekes probléma az, hogy mely konfigurációkból kapható meg az eredeti, vagy másképpen fogalmazva az, hogy az eredetibõl kiindulva mely konfigurációk érhetõk el. A fenti gondolatmenet adja, hogy csak azok, amelyekhez rendelt sorrendben az index páros (hiszen az eredeti sorrend indexe páros), és megmutatható, hogy ez már meg is adja a pontos választ, mert a páros indexû konfigurációk mind meg is kaphatók. Így ahhoz, hogy eldöntsük, hogy egy tetszõlegesen összeállított kiindulási konfigurációból az eredeti visszaálítható-e, mindössze a hozzá rendelt sorrend indexét kell kiszámolnunk, és ha az páros, akkor az eredeti visszaállítható, ha pedig páratlan, akkor nem.

  A fenti megoldás a lehetetlenségi bizonyítások egy sokszor alkalmazható elemét tartalmazza, az ún. invariáns ötletet. Mint láttuk, az egyes konfigurációkhoz hozzárendeltük az indexet, pontosabban annak a paritását, és egy csúsztatás során ez a paritás nem változott, invariáns maradt. Ezért egy kiindulási konfigurációból csak olyan más konfigurációk kaphatók meg, amelyekhez rendelt paritás ugyanaz, mint a kiindulásinál, és ez azonnal adta, hogy az eredeti állapot visszaállítása lehetetlen.

  A harmadik feladat megoldása is egy ilyen jellegû ötlettel történhet, bár a megoldás jóval trükkösebb. Feltételezhetjük, hogy egy végtelen táblán játszunk, és az adott vonal felett az ötödik sorban kijelölünk egy O-val jelölt lyukat, ahova szeretnénk eljutni. Azt kell igazolni, hogy akármilyen konfigurációból indulunk is ki, amelyben a tüskék a vonalon vagy alatta vannak, ez nem lehetséges. Mármost a megoldás ötlete az alábbi: minden lyukhoz hozzárendelünk egy súlyt, és a tüskék egy tetszõleges állására összeadjuk azon lyukakhoz rendelt súlyokat, amelyekben tüske van; ez lesz az adott konfiguráció összsúlya. A súlyokat oly módon fogjuk megválasztani, hogy egy tüske átugrásánál az összsúly soha nem növekedhet, és még az is igaz lesz, hogy a vonalon ill. alatta levõ összes súly S összege ugyanaz lesz, mint az O lyukban levõ egyetlen súly nagysága. Ha mindez megvalósítható, akkor az O lyukba valóban nem juthatunk el, hiszen tetszõleges kezdeti konfigurációból indulunk is ki, annak összsúlya S-nél kisebb, így abból nem juthatunk el egy nagyobb összsúlyú konfigurációba, márpedig bármely konfiguráció, amely az O pontot tartalmazza, legalább S összsúlyú, hiszen már az O pont súlya is S.

  A kérdés tehát az, hogy hogyan helyezzük el a súlyokat. Legyen q a q²+q = 1 egyenlet pozitív megoldása, azaz legyen
q=(5–1)/2, és egy tetszõleges lyukhoz rendeljük hozzá a q^k súlyt, ahol k azt a számot jelöli, ahány lépést kell tennünk az adott lyuktól, hogy elérjünk az O lyukhoz (minden lépésben egyet léphetünk vízszintesen illetve függõlegesen, és emlékeztetünk arra, hogy pozitív k-ra q^k azt jelöli, hogy a q-t k-szor összeszorozzuk, míg q⁰=1). A 8. ábra mutatja az egyes lyukakhoz rendelt súlyokat.

 Könnyen látható, hogy egy tüske átugrása és levétele során a rendszer összsúlya nem nõhet. Ha például egy, az O-tól
k távolságra levõ tüskével ugorjuk át a mellette levõ tüskét, és ha ekkor közeledünk az O ponthoz, akkor eredetileg az ugró és az átugrott pontokban levõ tüskékhez rendelt súlyok összege q^k+q^k–1=q^k–2(q+q²) volt. Mármost az átugrás után e két tüske helyett egy tüskénk lesz az O ponttól k–2 távolságban, amelyhez rendelt súly q^k–2, ami a q²+q=1 egyenlõség miatt ugyanaz, mint az elõbbi összeg. Hasonlóan látható, hogy az összsúly soha nem nõhet, és persze vannak olyan ugrások (ha távolodunk O-tól), amelyeknél csökkenhet.

  Hogy a vonalon, ill. az alatta levõ lyukak összsúlyát kiszámíthassuk, fel kell használnunk a mértani sor összegképletét:
 

(1)

  Ezt a = q^j-vel alkalmazva látható, hogy bármelyik, a vonalon levõ, és O-tól j távolságra levõ lyuk, ill. az alatta, egy oszlopban levõ lyukak összsúlya q^j/(1–q)·j = =5-re csak egy ilyen oszlop van, de j=6, 7, ...-re két-két ilyen oszlop található szimmetrikusan az O oszlopának két oldalán, ezért végül kapjuk, hogy a vonalon és az alatta levõ lyukak összsúlya

Ez utóbbi összegre ismét alkalmazhatjuk az (1) képletet az a = 2 · q⁶/(1–q) választással, így végül a kérdéses összsúly

ahol az utolsó lépésben felhasználtuk, hogy q + 1 = 1/q és q² = 1–q. Tehát a kérdéses S összeg 1, ami pontosan az O lyukhoz rendelt súly, és éppen ezt kellett elérnünk.

  Ha valaki többet akar olvasni hasonló játékokról, annak javaslom Csákány Béla élvezetesen megírt könyvét: Diszkrét matematikai játékok (Polygon Kiadó, 1998).

Folytatás