Ész Ventura: Kevesebb mint egyévnyi szenvedés a mellékhelységben!

A megkeseredett WC-burkoló burkolási problémájában az volt a kérdés, hogy hány különböző módon lehet leburkolni az 1 négyzetméter alapterületű mellékhelységet 20 cm és 40 cm oldalélű négyzet alakú padlólapokkal, vagyis hány napig dolgozik még a munkáját megunt WC-burkoló.

Legyen a kisebb padlólap egységnyi élű. Ekkor az a kérdés, hogy egy 5x5-ös négyzetet hányféleképpen lehet lefedni hézag- és átfedésmentesen 1x1-es és 2x2-es csempéket használva. A feladatot általános 5xn-es helységre oldjuk meg Dévai Gergely megoldónk által felírt rekurziós összefüggések segítségével. A még általánosabb nxm lefedések száma egyébként ismert az irodalomból is (Mathar, 2016).

Jelölje f(n) az 5xn méretű padló lefedéseinek számát, és próbáljunk meg rekurziós képletet felírni f(n)-re. Három eset van:

(1) Azok az lefedések, amelykben az n-edik sor csupa kis csempéből áll, megfeleltethetők az 5x(n-1) méretű padló lefedéseinek, vagyis ezek száma f(n-1).

(2) Azok a lefedések, amelyeknek az n-edik (legalsó) sora két nagy csempét is tartalmaz (pontosabban mindkettőnek a felét), három csoportba oszthatók a nagy csempék elhelyezkedése szerint, lásd az alábbi ábra fölső sorát. Bármelyik kombináció esetén igaz az, hogy az (n-1)-edik sorban már csak egy kis csempe fér el a két nagy mellett, ezért a lefedések mindhárom esetben megfeleltethetők az 5x(n-2)-es lefedéseknek. Az utolsó sorban (a szaggatott vonal alatt) két nagy csempét is részben tartalmazó lefedések száma tehát összesen 3·f(n-2) lesz.

(3) Vannak még azok a lefedések, amelyekben az n-edik (legalsó) sorban pontosan egy nagy csempe (fele) található. Ebben az esetben a nagy csempe négy féle pozícióban lehet, lásd az alábbi ábra alsó sorát. Ha a nagy csempe az egyik szélen van, akkor a lefedések száma legyen g(n-1). A szimmetria miatt mindegy, hogy melyik szélen van. Ha valamelyik középső pozícióban, akkor az ehhez tartozó lefedések száma legyen h(n-1). g(n) tehát annak a száma, hogy hányféleképpen csempézhatő le egy olyan 5xn-be beleférő terület, aminek az alsó széle olyan alakú, mint a bal alsó mintázat fölső széle, h(n) pedig ugyanez a mellette lévő mintázatra vonatkoztatva. Összességében tehát az ebbe a kategóriába eső, azaz a szaggatott vonal alatt pontosan egy nagy csempe felét tartalmazó 5xn-es lefedések száma 2·g(n-1) + 2·h(n-1) lesz.

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

Azt kaptuk tehát, hogy f(n) = f(n-1) + 3·f(n-2) + 2·g(n-1) + 2·h(n-1). A minket érdeklő f(n) függvényen kívül viszont bevezettünk két másikat: g(n)-t és h(n)-t, ezért most azokra is fel kell még írnunk rekurziós összefüggéseket.

Ha megnézzük, hogy az utolsó két sorban elhelyezkedő nagy csempe milyen pozíciókban enged meg egy másik nagy csempét az utolsó előtti sorban, akkor az alábbi rekurziós összefüggéseket írhatjuk még fel: g(n) = f(n-1) + g(n-1) + h(n-1), illetve h(n) = f(n-1) + g(n-1), ahol az f-es tagok annak felelnek meg, hogy a szóban forgó nagy csempe soraiban nincsen másik nagy csempe.

Ha most megnézzük mi a helyzet akkor, ha csak egy vagy két sor van, akkor megállapíthatjuk, hogy f(1) = 1, f(2) = 8, g(1) = 1, g(2) = 3, h(1) = 1, h(2) = 2. Ezek után pedig már használhatjuk a rekurziós összefüggéseket, amiből némi számolás után az fog adódni, hogy f(5) = 314, illetve f(10) = 221799. A WC-burkoló tehát egy évnél kevesebbet kell még dolgozzon, de a haladó kérdés esetében ez már emberöltőnél is több.

A hírekről sok helyen tájékozódhatsz. A Qubit krízisben és békeidőben is arra törekszik, hogy az események mögött álló mélyebb összefüggéseket is megértsük – szigorúan a modern tudomány szemszögéből, több mint 100 tudós-szerzőnk és szakértő újságíróink révén. Ez nekünk sokba kerül, de reméljük, nektek is sokat ér.
Támogasd a Qubit fennmaradását!