Két megoldással vagyok adós. Az előző heti húsvéti feladvány azonban úgy tűnik, kifogott még a leglelkesebb Ész Ventura-olvasókon is, ezért meghosszabbítom a beküldési határidőt április 15-ig. Ennek nyilván az is oka, hogy a legtöbb Ész Ventura-fejtörő eddig olyan volt, amin lehetett gondolkodni akár utazás közben is, ezen viszont csak úgy lehet effektíven töprengeni, ha színesben kinyomtatjuk a tojásokat. Ennek ellenére biztatok mindenkit, hogy gondolkozzon rajta akár a monitor előtt, mert nem olyan nehéz, ha adok némi segítséget. A legfontosabb segítség, hogy előbb fel kéne ismerni, mi a közös az összes tojásban, utána lehet a kakukktojást megtalálni. Adok továbbá két távoli asszociációs segítséget is: számítógépes program, Kétfarkú Kutya Párt.

Ezután térjünk rá a két héttel ezelőtti feladvány megoldására, azaz nézzük a Nagymánya-tévnyomat darabolásait. Nem véletlen egyébként, hogy ennek a feladványnak a megoldásáért négy koponya járt az ötből. Azért nem öt, mert különösebben nem volt nehéz, viszont bíbelődni kellett vele, leszámolni a lehetőségeket, miközben türelmesnek és figyelmesnek kellett lenni, nehogy kimaradjon valami. Volt az olvasók között olyan, aki el is küldött melegebb éghajlatra, megjegyezve, hogy ehhez neki nincs türelme. Valóban ehhez nem kreativitásra volt elsősorban szükség, mégis lesz tanulsága ennek a példának, sőt direkt választottam ilyen idegölő feladatot, mert pont ilyenre volt szükségem ahhoz, hogy demonstrálni tudjam, miért is van szükség a kombinatorikára a számítástudományban, ahogy arról a feladat bevezetőjében is már beszéltem.

Miért volt nehéz a leszámolás?

Kezdjük először egy könyebb verzióval, amikor csak egyetlen bélyeget akarunk eltávolítani az ívről úgy, hogy a maradék összefüggő maradjon. Ennek igen egyszerű és könnyen átlátható a megoldása, összesen két bélyeg van, amihez nem nyúlhatunk, ezeket jelöltem piros színnel az alábbi ábrán. Ha két bélyeget szeretnénk eltávolítani úgy, hogy összefüggők legyenek, akkor vagy egymás mellett vagy egymás alatt kell legyenek, és összesen 25 lehetőség van, hogy a maradék is összefüggő maradjon, csak az alábbi párok nem jók: FG, XY, FO, GP, HR, IS, JT, MX, NY, ezek ugyanis kettévágják az ívet.

Ahogy növekszik az eltávolítandó bélyegek száma, elvileg egyre többféle kombinációban állhatnak egymáshoz képest összefüggő módon. Ha öt bélyeget akarunk eltávolítani, akkor az ún. pentominókat kell tekintenünk, amikből tizenkétféle létezik, de jelen esetben mindegyiknek az elforgatott és tükrözött verzióit is számba kell vennünk. Ez pentominónként legrosszabb esetben nyolc lehetőség, de a szimmetriával rendelkező pentominóknál kevesebb. Az U alakú például tengelyesen szimmetrikus, azért csak négy különböző állása van, a plusz jelre emlékeztető pentominónak pedig csak egy lehetséges állása van.

A fentiekből azonban nem mindegyik jöhet szóba, hiszen olyan is van ezek között, amelyik bele sem fér a háromsoros bélyegívbe, például az álló L betű túl magas hozzá. Ezért írtam, hogy csak elvileg nő a lehetőségek száma. Ezen kívül meg kell nézni, hogy amik beleférnek, hányféle helyre tehetők az íven belül, és ezek közül mely pozíciók olyanok, hogy az eltávolítás után a maradék összefüggő marad.

Láthatjuk, hogy a leszámolgatást nem tudjuk megúszni, és ennek alapvetően két oka van. Az egyik, hogy sokféle pentominó van, a másik, hogy a teljes bélyegív alakja szabálytalan. Ha a bélyegív alakja szabályos lenne, például téglalap alakú, akkor egy adott pentominó alakzatra meg lehetne adni egy képlettel a téglalap oldalhosszainak függvényében általánosan is, hogy hányféleképpen lehet eltávolítani azt a pentominót a téglalapból úgy, hogy összefüggő maradjon a téglalap maradéka. A kombinatorika tipikusan ilyen általánosabb jellegű képletek levezetésével foglalkozik, nem arról szól, hogy kézzel számlálgassunk egy speciális szituációban. Ha saját magunknak kell számolgatni, azt igyekszünk megúszni és számítógépekre bízni. Jelen esetben még éppen akadtak olyanok, akiknek volt türelme kézzel leszámolgatni, direkt ilyen feladványt tűztem ki. Ha azonban a bélyegív sokkal több bélyeget tartalmazott volna, és az alakja még sokkal bonyolultabb, akkor ez már reménytelen lett volna. És van még egy indok, amiért érdemes az ilyesmit a számítógépekre bízni, nevezetesen az, hogy elkerüljük a tévedés lehetőségét, nehogy valamint kihagyjunk vagy többször számoljunk figyelmetlenségből.

Kombinatorikus robbanás!

Ha azt tekintjük, hogy 24 bélyegből hányféleképpen lehet tetszőleges módon kiválasztani 5-öt, az több mint 42 ezer lehetőség. De ha kikötjük az 5 bélyeg összefüggőségét, és figyelembe vesszük a bélyegív alakját is, akkor a lehetőségek száma 282-re csökken, és ez még végignézhető egyesével. Aki türelmesen végignézte, az 45-öt találhatott ezek között, amiknél a maradék is összefüggő, tehát megfelel a feladat feltételeinek. Ha viszont megnöveljük a probléma nagyságát, és egy 100-as ívből szeretnénk 10-et kiválasztani, akkor a lehetőségek száma 17310309456440 lesz (17 billió). A 10-es poliominók száma 4655, ennyiféle alakzatot kéne végignézni a fenti 12 helyett. A kombinatorikában gyakran fellép ez a drasztikus növekedés, amire azt szokás mondani, hogy kombinatorikusan felrobban a lehetőségek száma.

Azt láttuk tehát, hogy a kitűzött feladat kézzel is megoldható még, ezt sokan meg is tették, viszont programot is lehet írni rá, voltak, akik így jártak el. Azt is megjegyeztük, hogy szabályos (például téglalap alakú) bélyegív esetén a kombinatorika segíthet. Viszont azt is meg szeretném mutatni, hogy a kombinatorikára program írása során is szükség van általában, és ez ezen a példán szépen bemutatható. Ehhez először is beszélnünk kell arról, hogy mi egy számítógépes program. Itt a Qubiten is sok szó esett már programozásról Kálmán László jóvoltából, és példák is voltak leginkább a programozástechnikai részre koncentrálva. A program lényege azonban az algoritmus, és ha valami szépséget találhatunk a programozásban, akkor az minden bizonnyal azokhoz a matematikai trükkökhöz és megoldásokhoz köthető elsősorban, amiket alkalmaznunk kell az algoritmusban. Erről még nem igazán esett szó a programozási cikksorozatban, márpedig itt jön a képbe például a kombinatorika.

Meg kell mondani a gépnek, hogy mit csináljon

Számítógép segítségével sokkal több dolgot ellenőrizhetünk könnyedén, mint amennyit egy ember sorra tud venni, csak meg kell mondani a számítógépnek, hogy mit csináljon. Ezt azonban pontosan meg kell tervezni, és erre szolgál az algoritmus. Ahogyan mi végignéznénk az eseteket, ha lenne rá időnk, úgy a számítógépes program számára is előre meg kell terveznünk a lépések sorozatát. Ezen lépések közben persze adódhatnak feltételes elágazások, de mindenre gondolnunk kell előre, hogy beavatkozás nélkül végig tudjon futni a program. És van még egy dolog, amit meg kell tennünk: formalizálni a feladat szempontjából releváns tulajdonságokat. Ha például ránézünk egy bélyegívre, akkor mindenféle tudatos gondolkodás nélkül a percepciónk alapján viszonylag automatikusan látjuk, hogy összefüggő-e vagy sem. Ezzel szemben a számítógépet nem tudjuk megkérdezni arról, hogy összefüggő-e valami, hanem definiálnunk kell formálisan, hogy mit nevezünk összefüggőnek, és utána azt valahogyan tesztelnünk kell – ez is az algoritmus része kell legyen. Az összefüggőséget például megvizsgálhatja úgy a program, hogy kiindul egy tetszőleges bélyegből, ami része az alakzatnak és veszi annak a szomszédait, majd annak is a szomszédait és így tovább, végül pedig ellenőrzi, hogy minden bélyeghez eljutott-e, ami a halmaz része.

Az algoritmus tervezése során több dologra is figyelni kell ahhoz, hogy ténylegesen meg tudjuk oldani a problémát. Bár a számítógép gyorsabb, mint az ember, a fent említett exponenciális ütemű kombinatorikus robbanás egy programnak is gondot okozhat, ezért fontos, hogy a lépéseinket úgy tervezzük meg, hogy a végén eljussunk a megoldásig, de ne tegyünk sokkal több lépést, mint amire szükség van. Csinálhatnánk például azt, hogy tekintjük az összes bélyegkombinációt az íven az összefüggőségtől függetlenül, majd mindegyikre megvizsgáljuk az összefüggőséget, és amelyik nem összefüggő, azt elfelejtjük. A fentiekben láttuk azonban, hogy egy 100-as ív esetén így könnyedén csillagászati számú lépést kell végezni, ami még egy számítógépnek is sok lehet. Ehelyett az a praktikusabb megoldás, hogy eleve csak az összefüggő lehetőségeken megyünk végig, vagyis először legeneráljuk a poliominókat, majd azokat végigscanneljük az íven.

Ezekben a részproblémákban mind-mind használjuk a kombinatorikát. Használjuk annak megbecslésénél, hogy egyáltalán a tervezett megoldás hány lépésből fog állni. Használjuk ott, hogy az egyes lépésekben hány esetet kell megvizsgálni. És használjuk ott is, hogy egy adott lépés vizsgálatával mikor nem kell fölöslegesen tovább foglalkoznunk. Vegyük továbbá észre, hogy ez teljesen általános, nem csak erre a bélyeges feladatra vonatkozik, hanem szinte bármilyen számítógépes programra, amit arra készítettek, hogy az ember helyett nézzen végig eseteket, például akkor, amikor a Google útvonaltervezője meghatározza nekünk a leggyorsabb vagy legrövidebb útvonalat.

A helyes megoldások

A konkrét algoritmust a mi esetünkre nem fogom most leírni, csak érzékeltetni szerettem volna a programozástól távolabb állók számára is a kombinatorika fontosságát ezen a területen, és azt hogy a programozás nem csak kulimunka, hanem matematikát és kreatív gondolkodást is igényel. Különben is az a szép, hogy rengetegféleképpen le lehet programozni ezt a feladatot. Meg lehet például oldani a fentebb vázolt módon, amikor tetszőleges számú bélyegre végigpróbálgatjuk szisztematikusan a lehetőségeket. De azt is lehet, hogy megoldjuk először egy, majd két bélyegre a problémát, ahogy az elején tettük, a nagyobb számok vizsgálatánál pedig mindig visszavezetjük az eggyel kisebbre. Ehhez az kell, hogy a korábbi megoldásokat ne csak leszámoljuk, hanem el is tároljuk a konkrét pozíciókat. Ekkor ugyanis elég mindig azt vizsgálni, hogy az egyes korábbi megoldásokhoz hogyan lehet még egy bélyeget hozzávenni úgy, hogy szomszédos legyen vele, és a maradék is összefüggő maradjon. Továbbá arra kell még vigyázni, hogy ilyen módon nehogy kétszer számoljunk valamit, ami többféleképpen is kijöhet.

Egyébként a megoldások számai a Nagymánya-tévnyomatra a következők. Egy bélyegre 22, kettőre 25, háromra 36, négyre 42, ötre 45, hatra 50, hétre 53, nyolcra 56, kilencre 57, tízre 60, tizenegyre 63, tizenkettőre 64. E fölött pedig nem kell külön megadnunk, mert ugyanezek jönnek visszafele, hiszen 13-ra például nyilvánvalóan megegyezik a 24-13=11-re adott megoldással, hiszen a kivágott rész és a maradék komplementerek/kiegészítő részek és mindkettő összefüggő. Egyébként öt bélyegre a konkrét lehetőségeket lásd az animáción, amit Békési István megoldónknak köszönhetünk: