Ész Ventura: Így kellett összehajtogatni a Qubit betűit

Az előző bélyeghajtogatós feladványban szabadon lehetett választani a Qubit betűi közül. Természetesen a b betű és a t betű volt a legkönnyebb, ezt is választotta mindenki, aki nem programot írt a feladat megoldására. Ezeket nézzük most meg, hogy hányféleképpen lehet összehajtani.

B betű

A b betű lényegében egy 2x2-es négyzetből és még egy hozzá kapcsolódó bélyegből áll. Nézzük először külön a 2x2-es négyzetet, hogy ezt hányféleképpen lehet összehajtani. Ez az ún. térképhajtogatás problémája, a Wikipédián találunk is róla cikket, amiből kiderül, hogy egy 2x2-es térképet nyolcféleképpen lehet összehajtogatni. A lehetséges hajtogatásokat alább láthatjuk, de miért lehetünk biztosak abban, hogy tényleg csak ezek lehetségesek?

Tegyük fel, hogy a térképünk bal-alsó sarka kék, bal-fölső sarka piros, jobb-fölső sarka sárga, jobb-alsó sarka pedig zöld. Legyen továbbá az összehajtogatott stócban a kék sarok mindig színével fölfele, és forgassuk úgy a stócot, hogy a kék semelyik szomszédjával sem érintkező sarka mutasson felénk. Ezt a négy színt elvileg 4·3·2 = 24 különböző sorrendben tehetnénk egymásra, ha nem lennének egymással összeragasztva. Egy színsorrend mindig egyértelműen meghatározza azt, hogy az egyes rétegek melyik élük mentén melyik másik réteggel kéne összeragasztva legyenek, mert a kékből kiindulva ez egyértelműen végigkövethető. A kérdés tehát csak az, hogy a lehetséges 24 esetből melyek valósíthatók meg fizikailag is, ezt pedig könnyedén végig lehet nézni.

Egyébként vegyük észre, hogy csak azok nem valósíthatók meg, ahol egymással szemközti sarkok közvetlenül egymás mellé kerülnének. Hajtsatok ketté egy papírlapot vízszintesen és függőlegesen is, majd próbáljátok meg úgy összehajtani, hogy két szemközti negyed közvetlenül egymás mellé kerüljön. Rá fogtok jönni, hogy miért nem megy. Ezt kivéve viszont minden más megy, amikor a szomszédos sarkok szomszédos rétegek is lesznek, ahogy a fenti ábrán is láthatjátok. És azért van pontosan nyolc eset, mert négyféle színnel kezdhetünk mégpedig óra mutató járásával egyező, vagy ellentétes irányba.

Bár a 2x2-es eset viszonylag egyszerűenek tűnik, itt is fellép a kombinatorikus robbanás, 3x3-as térképnek már 1368 lehetséges hajtogatása van. A probléma pedig legalább olyan nehéz, mint a bélyegsor hajtogatás, 7x7-es térkép a legnagyobb, amely hajtogatásainak a száma jelenleg ismert, lásd a sorozatok internetes enciklopédiájában.

Illusztráció: Gáspár Merse Előd

No de térjünk rá arra a kis fityegő bélyegre, ami még lelóg a 2x2-es négyzetről a b betű esetén. Lényegében mindegy, hogy merre lóg ki az az egy bélyeg, ezért az általánosság megszorítása nélkül feltehetjük, hogy ez mondjuk a kékhez kapcsolódik balra. Ha megnézzük a fenti nyolc stócot, akkor láthatjuk, hogy ezekben mind közös az, hogy a felénk eső két szél egyikén sincs perforáció, tehát a kék réteg akárhol is van a róla balra fityegő bélyeg bármelyik két szomszédos réteg közé behajtható, vagy a legaljára, vagy a legtetejére is akár. Ez összesen öt lehetőség mind a nyolc esetben, tehát a b-betű 40 féleképpen hajtogatható össze egy stóccá. 

T betű

Azt már láttuk, hogy az i betűt hat féle módon lehet összehajtogatni. A t betű olyan mint az i betű, csak van az egyik végén két oldalra egy-egy fityegő része. Ezeket a fityegő bélyegeket az i betű összehajtogatása után egymástól függetlenül behajthatjuk a stóc bármelyik résbe, vagy legalulra, vagy legfölülre. Ez összesen négy hely. Mármost lehetséges az, hogy mindkét bélyeget ugyanoda hajtjuk be, ez négy hely, de a két bélyegnek kétféle sorrendje lehet, tehát ez összesen nyolc lehetőség. Vagy lehet az, hogy különböző helyekre hajtjuk őket, ez 4·3 = 12 lehetőség. Így összesen 8+12 = 20 lehetőség van az i betű mind a hat hajtogatása esetén, vagyis összesen 120 féleképpen hajthatjuk össze a T-betűt.