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

Hogy lehet, hogy nem lehet?

Hogy lehet, hogy nem lehet?

Kiss, Emil


Mindig lenyűgöztek az olyan eredmények, amelyek azt állítják, hogy valamit, amit szeretnénk, nem lehet megcsinálni. Nem azért, mert ügyetlenek, lusták, vagy tudatlanok vagyunk, hanem mert vitathatatlanul bebizonyítható, hogy a dolog elvileg is lehetetlen. Ilyen eredményekhez vezethetnek például a következő problémák.

  • Lehet-e örökmozgót építeni?

  • Mely csomókat nem lehet kibogozni?

  • Lehet-e egy sík papírlapból gömböt hajtogatni?

  • Át lehet-e darabolni egymásba két adott testet?

  • Milyen számítógépet lehet építeni adott alkatrészekből?

  • Szerkeszthető-e szabályos hétszög körzővel és vonalzóval?

  • Milyen egyenletekre nincs megoldóképlet?

  • Milyen minták nem tekerhetők ki a Rubik-kockán?

  • Van-e olyan állítás, amit sem bizonyítani, sem megcáfolni nem lehet?

Az első probléma kilóg a sorból, hiszen ez nem „elméleti” kérdés. A fizikai kísérleteknek kell eldönteniük, hogy az energiamegmaradás törvénye igaz-e. De ha igaz, akkor már bizonyítható, hogy örökmozgó nem építhető. A „lehetetlenségi” matematikai bizonyításokban legtöbbször mi magunk „teremtjük meg” az „energia” fogalmát úgy, hogy a vizsgált rendszer (például a bűvös kocka) állapotaihoz egy alkalmas mennyiséget rendelünk, ami a megengedett átalakítások során nem változik, invariáns marad. A rendszer ekkor biztosan nem mehet át az egyik „energiaszintről” egy másikra.

Az ilyen bizonyítások bonyolultak lehetnek: szerepet játszhat bennük a logika, az algebra, a geometria, a kombinatorika, az algoritmuselmélet, sőt még a valószínűségszámítás is. A fenti kérdések mindegyikét nem is fogjuk megvizsgálni. Ebben az írásban, amely maga is mozaik, a személyes ízlésem szerint válogattam, algebrai problémák között. Hallani fogunk kártyakeverési eljárásokról, szavak átalakításának problémájáról, de a klasszifikáció híres tételéről is, aminek a bizonyítása több, mint tízezer oldal!

Elsősorban mesélni szeretnék, végig arra törekedtem, hogy a fő gondolatokat tolmácsoljam, és elkerüljem a nehéz bizonyításokat. Aki a részletekre kíváncsi, elmélyedhet az irodalomjegyzékben szereplő művekben, aki pedig az agyát akarja tornáztatni, az több Feladatot is találhat a cikkben, némelyikük embert próbáló. Ezek megoldásvázlata az utolsó fejezetben szerepel. A Kérdéseknél érdemes egy pillanatra megállni és elgondolkozni, hogy jobban megértsük a választ, ami a szövegben következik.

1. Szóproblémák

A bergengócok nyelvében mindössze két hang szerepel: g és u . A nyelvtani szabályok is nagyon egyszerűek. Ha egy szóban két g szerepel egymás után, akkor azok kitörölhetők a szó értelmének megváltozása nélkül. Hasonlóképpen kitörölhető három egymás utáni u is. Végül ha egy szóban előfordul u g , akkor ez helyettesíthető g u u -val. Mindegyik átalakítási szabály meg is fordítható, tehát például bármelyik szóba bárhová beírható két egymás utáni g betű.

1.1. Kérdés. Hány különböző értelmű szó lehet ebben a nyelvben legfeljebb?

Könnyű meggondolni, hogy az utolsó átalakítási szabály segítségével a g betűket a szó elejére, az u betűket a szó végére csoportosíthatjuk át. Ha ez megtörtént, akkor a „felesleges” g és u betűket kitörölhetjük az első két szabály segítségével. A következő szavak maradnak meg: g u , g u u , g , u , u u , és az üres szó, amiben egyáltalán nincs betű (ezt kapjuk például, ha u u u -ból, vagy g g -ből indulunk ki). Tehát legfeljebb hat különböző értelmű szó lehet a nyelvben, de esetleg még kevesebb akkor, ha a felsorolt hat szó között is vannak még olyanok, amik egymásba átalakíthatók.

Például nem lehetséges-e az, hogy a g és u szavak is egymásba alakíthatók? Mivel beírni is szabad betűket, egy ilyen átalakítás-sorozat nagyon sok lépésből is állhatna, miközben a szereplő szavak hossza is esetleg több millió betűsre nő. A lehetséges átalakítások száma végtelen, az összeset nem tudjuk végigszámolni. Ez tehát az első példánk, amikor azt kell bizonyítani, hogy valamit nem lehet megcsinálni!

Mi itt a jó „energiafogalom”? A második és a harmadik átalakítási szabály egyáltalán nem változtatja meg a szóban szereplő g betűk számát, az első szabály pedig kettővel csökkenti, vagy növeli. Ha tehát a g szóból indulunk ki, akkor bárhogyan is alkalmazzuk szabályainkat, a kapott szavakban mindig páratlan sok g betű lesz. A végeredmény tehát soha nem lehet u , amiben páros sok (nulla darab) g szerepel.

Lássuk be, hogy a felsorolt hat szó közül semelyik kettő sem alakítható egymásba! Most is egy invariánst keresünk, azaz szavak egy „tulajdonságát”, ami nem változik meg az átalakítások során. Ez bonyolultabb tulajdonság lesz, mint a g betűk számának paritása volt: minden szóhoz egy geometriai transzformációt rendelünk.

Legyen A B C egy szabályos háromszög. Ennek sok szimmetriája van, például tükrözések és forgatások. Ezekkel a transzformációkkal szeretnénk számolni, méghozzá minél gyorsabban, azaz lehetőleg formális szabályok szerint. Jelölje G az A B oldal felező merőlegesére való tükrözést, és U a háromszög középpontja körül való 120 fokos forgatást. Az U transzformáció tehát az A csúcsot B -be, B -t C -be, C -t A -ba viszi.

Ha több ilyen transzformációt egymás után elvégzünk, újra a háromszög valamelyik szimmetriáját kapjuk. Például mi lesz az eredmény, ha először U -t, azután G -t alkalmazzuk? Mivel G ( U ( A ) ) = G ( B ) = A , és G ( U ( B ) ) = G ( C ) = C , az eredmény, amit U G -vel jelölünk, a B C oldal felező merőlegesére való tükrözés. Könnyen kiszámolhatjuk, azt is, hogy G U U (azaz ha először G -t alkalmazzuk, majd U -t kétszer), szintén ugyanez a tükrözés lesz.

A kapott U G = G U U összefüggés nagyon hasonlít a szóproblémánkban látott u g - g u u átalakítási szabályra. Vegyük észre, hogy a G és U transzformációk a másik két szabályt is teljesítik, hiszen ha G -t kétszer, vagy U -t háromszor alkalmazzuk, akkor mindkét esetben a helybenhagyást kapjuk.

Most már könnyű belátni, hogy a felsorolt hat szó közül semelyik kettő sem alakítható egymásba. Ha adott egy u és g betűkből álló tetszőleges szó, akkor írjunk mindegyik kisbetű helyére nagybetűt. Így egy geometriai transzformációt kapunk. Láttuk, hogy az átalakítási szabályok alkalmazásakor ez a transzformáció nem változik meg, ezért ha két szó egymásba alakítható, akkor ugyanaz a transzformáció tartozik hozzájuk. A felsorolt hat szónak azonban hat különböző transzformáció felel meg (az üres szónak a helybenhagyás, u -nak és u u -nak a két 120 fokos forgatás, g -nek, g u -nak és g u u -nak a három tengelyes tükrözés), ezért e szavak közül semelyik kettő sem alakítható egymásba.

1.2. Feladat. Módosítsuk átalakítási szabályainkat úgy, hogy nem három, hanem n darab egymás melletti u legyen kihúzható, és u g - g u u , ahol n - 1 darab u szerepel. Hány különböző értelmű szó írható fel ebben az esetben?

1.3. Feladat. Hány különböző értelmű szó írható fel akkor, ha a szabályok a következők: öt egymás melletti g , három egymás melletti u húzható ki, és még azt is tudjuk, hogy u g - g u u ?

Most azt fogjuk megvizsgálni, hogy fel tudunk-e sok olyan szót írni, amelyek „nagyon nem periodikusak”. Ismét egy könnyű, játékos kérdéssel kezdjük, de most már megoldatlan, sőt megold hatatlan problémákhoz is el fogunk jutni.

1.4. Kérdés. A Szűkszavú Emberek Országában annyira bűnnek számít a fecsegés, hogy ha egy szóban egymás mellett két egyforma rész van, akkor a két rész együtt kihúzható a szó értelmének megváltozása nélkül. Hány különböző értelmű szó írható fel, ha az ábécé m betűből áll?

Tegyük fel először, hogy két betűnk van: b és c . Vegyük észre, hogy

b c - b ( b c b c ) c = ( b b ) c b ( c c ) - c b .

Tehát összegyűjthetjük a b betűket a szó baloldalán, a c betűket a jobboldalon, és ezért legfeljebb négy szó lehet: b , c , b c és az üres szó. A paritásos trükkel beláthatjuk, hogy ezek nem alakíthatók egymásba. Ez a gondolatmenet könnyen általánosítható, és akkor kiderül, hogy m darab betű esetén a szavak száma 2 m lesz (tehát véges sok).

1.5. Feladat. Az Engedékenyebb Szűkszavú Emberek Országában az a szabály, hogy ha egy szóban egymás mellett két egyforma rész van, akkor az egyik kihúzható a szó értelmének megváltozása nélkül (tehát például a b a c - a b a a c , a b a c a b a c , a b a b a c ; ezt a szabályt is megfordíthatónak értelmezzük). Mutassuk meg, hogy – véges sok féle betűt használva – csak véges sok különböző jelentésű szót lehet felírni.

Most próbáljuk meg a szűkszavúság követelményét másképp gyengíteni. Legyen a szabályunk az, hogy ha egy szóban egymás mellett n egyforma rész van, akkor ez az n rész együtt kihúzható. Ez a Burnside-tól származó problémakör nagyon fontos a csoportelméletben.

1.6. Feladat. Mutassuk meg, hogy n = 3 és véges sok betű esetén csak véges sok különböző jelentésű szót lehet felírni.

A szavak száma n = 4 és n = 6 esetében is véges (ha véges sok betűt használunk). Megváltozik azonban a helyzet, ha n értéke nagy. Novikov és Adjan híres eredménye (bonyolult és hosszú bizonyítással), hogy ha n páratlan, és legalább 665, akkor a kapott szavak száma már két betű esetében is végtelen. Az n = 5 eset mindmáig megoldatlan, még két betű esetében is.

1.7. Probléma. Ha két betűből álló szavakat tekintünk, és öt egymás melletti egyforma rész húzható ki, véges sok különböző jelentésű szót lehet-e felírni?

Ahhoz, hogy egy ilyen problémán gondolkozni tudjunk, gyorsan meg kellene tudni válaszolnunk bármely két szóról, hogy egymásba alakíthatóak-e, vagy sem. Ahelyett, hogy minden szópár esetében külön trükköt keresgélnénk, jó lenne írni erre egy számítógépes programot. Döbbenetes felfedezés, hogy ilyen program nem írható! Sőt nemcsak általában nincs olyan program, ami beolvassa az átalakítási szabályokat, és eldönti az általunk megadott szópárokról, hogy egymásba alakíthatóak-e, hanem már olyan programot sem lehet írni, ami konkrétan az alábbi szabályrendszer esetében működik. Legyenek a betűk a , e , i , o , u , a szabályok pedig: a i - i a ; a o - o a ; e i - i e ; e o - o e ; a o a i - a e a i ; u i a - a u ; u o e - e u .

Mit jelent az, hogy ez a szóprobléma általában nem oldható meg? Valaki hoz két szót (például u o e i a és e a u ), és megkérdezi, hogy ezek egymásba alakíthatóak-e. A világ matematikusai összeülnek, és egyiküknek sikerül megoldania a problémát: megadja az átalakítást. Ezután jön másvalaki két újabb szóval (mondjuk i a a a és e e o i ). Egy másik matematikus idővel felfedezi azt a trükköt, ami mutatja, hogy ezek nem alakíthatók egymásba. De ha valaki egy harmadik szópárral rukkol elő, akkor jó eséllyel megint újra kell kezdeni a gondolkodást, soha nem lesz olyan ötlet, ami az összes szópárt egyszerre elintézi. (A kép azért nem teljesen fekete: vannak híres eljárások, például a Knuth-Bendix algoritmus, amik intelligensen keresnek, és sok szópár esetében sikeresen eldöntik a problémát.)

Annak a precíz bizonyításához, hogy ilyen program nem létezik, elvileg az összes lehetséges (végtelen sok) programot át kellene tudnunk tekinteni. Ez a probléma szerkezetében hasonló ahhoz, amit már megoldottunk (amikor rögzített szópár esetén az összes lehetséges szó-átalakításokat kellett volna áttekinteni). Mindehhez pontosan meg kell fogalmazni azt, hogy mit is értünk programon. Ezek a kérdések már a logikához tartoznak, és tárgyalásuk túl messzire vezetne. Valamennyit azért még fogunk beszélni róluk a következő fejezetben.