Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?
A régi honlapot akarom!!! :-)

A B. 4920. feladat (2017. december)

B. 4920. Hányféleképpen lehet \(\displaystyle 1\times2\)-es dominókkal átfedés és hézag nélkül lefedni a \(\displaystyle 8\times8\)-as sakktábla körül felvett 2 egység szélességű szegélyt? (Az ábrán látható két lefedést különbözőnek tekintjük.)

Javasolta: Róka Sándor (Nyíregyháza)

(6 pont)

A beküldési határidő 2018. január 10-én LEJÁRT.


Megoldás. A megoldás során felhasználjuk azt a jól ismert állítást, hogy egy \(\displaystyle 2\times n\)-es téglalapot \(\displaystyle 1\times 2\)-es dominókkal \(\displaystyle F_{n+1}\)-féleképpen lehet hézagmentesen és átfedések nélkül lefedni, vagyis parkettázni, ahol \(\displaystyle F_{n+1}\) a Fibonacci-sorozat \(\displaystyle (n+1)\)-edik tagja. (A Fibonacci-sorozatot az \(\displaystyle F_0=0,F_1=1\), és \(\displaystyle n\geq 2\)-re \(\displaystyle F_n=F_{n-1}+F_{n-2}\) rekurzió határozza meg. A hivatkozott állítás indukcióval könnyen igazolható. Ha \(\displaystyle n=1\), akkor valóban \(\displaystyle F_2=1\) lehetőség, ha pedig \(\displaystyle n=2\), akkor valóban \(\displaystyle F_3=2\) lehetőség van. Ha most \(\displaystyle n\geq 3\), akkor a \(\displaystyle 2\times n\)-es táblázat bal szélén vagy egy függőlegesen álló dominó van, és ezesetben a tőle jobbra lévő \(\displaystyle 2\times (n-1)\)-es részt kell lefednünk, ami \(\displaystyle F_n\)-féleképpen tehető meg, vagy pedig két vízszintesen álló dominó van egymás alatt a bal szélén, és ekkor a tőlük jobbra lévő \(\displaystyle 2\times (n-2)\)-es részt kell lefednünk, ami \(\displaystyle F_{n-1}\)-féleképpen tehető meg. így a lehetőségek száma valóban \(\displaystyle F_{n}+F_{n-1}=F_{n+1}\).)

Először tekintsük azokat a parkettázásokat, amikor a bal felső mezőt egy vízszintesen álló dominó fedi le. Világos, hogy így a parkettázások felét fogjuk megszámolni (a bal felső és a jobb alsó sarkot összekötő átlóra tükrözve kapjuk ezekből azokat, melyeknél a bal felső mezőt függőlegesen álló dominó fedi).

Ha a bal felső \(\displaystyle 2\times 2\)-es négyzet jobb szélén lévő piros vonal egy dominót kettévág, akkor a fedés onnan egyértelműen folytatható, és befejezhető az 1. ábra szerint.

Tegyük most fel, hogy a bal felső \(\displaystyle 2\times 2\)-es rész jobb szélén lévő piros vonal nem vág ketté dominót. Két esetet különböztetünk meg aszerint, hogy a jobb alsó sarkot vízszintes vagy függőleges dominó fedi.

1. eset. Tegyük fel először, hogy vízszintes. Ekkor a jobb alsó \(\displaystyle 2\times 2\)-es négyzet bal szélén lévő piros vonal sem vág ketté dominót, hiszen különben az 1. ábra szerinti parkettázást kapnánk. A bal alsó \(\displaystyle 2\times 2\)-es négyzet felső oldalán lévő vonal

vagy nem vág ketté dominót (2. ábra),

vagy kettőt is kettévág (3. ábra),

hiszen a vonal feletti \(\displaystyle 9\times 2\)-es részt különben nem lehetne lefedni. Utóbbi esetben a bal alsó sarkot egy vízszintes dominónak kell fednie. Az első esetben egy \(\displaystyle 9\times 2\)-es és egy \(\displaystyle 2\times 10\)-es részt kell lefedni dominókkal, ez \(\displaystyle F_{10}F_{11}\)-féleképpen tehető meg. A második esetben pedig egy \(\displaystyle 8\times 2\)-es és egy \(\displaystyle 2\times 8\)-as téglalapot kell lefedni dominókkal, ez \(\displaystyle F_{9}^2\)-féleképpen tehető meg. Az ábra szimmetriáját kihasználva a felső és jobb oldali sáv által alkotott L alakú rész lefedésére ugyanennyi, vagyis \(\displaystyle F_{10}F_{11}+F_{9}^2\) féle lehetőség van. összesen tehát az 1. esetben a parkettázások száma \(\displaystyle (F_{10}F_{11}+F_{9}^2)^2\).

2. eset. Most tegyük fel, hogy a jobb alsó sarkot függőleges dominó fedi. A jobb alsó \(\displaystyle 2\times 2\)-es négyzet felső oldala nem vághat ketté dominót, mert akkor a fedés egyértelmű befejezésében a bal felső sarkot is függőleges dominónak kellene fednie. Tehát ismét kialakul két L alakú sáv, ahol az 1. esetben látott esetszétválasztáshoz hasonlóan megszámolhatjuk a fedéseket. Az alsó L fedésére \(\displaystyle F_{10}F_{12}+F_9F_{10}\) lehetőség van (4. és 5. ábra szerinti esetek alapján), a felső L fedésére pedig \(\displaystyle F_{11}F_{9}+F_9F_8\). így a 2. esetben a lehetőségek száma \(\displaystyle (F_{10}F_{12}+F_9F_{10})(F_{11}F_{9}+F_9F_8)\).

Tehát feltéve, hogy a bal felső sarkot vízszintes dominó fedi, a lehetőségek száma \(\displaystyle 1+(F_{10}F_{11}+F_{9}^2)^2+(F_{10}F_{12})(F_{11}F_{9}+F_9F_8)\), így a feladat kérdésére a válasz ennek kétszerese, vagyis:

\(\displaystyle 2(1+(F_{10}F_{11}+F_{9}^2)^2+(F_{10}F_{12}+F_9F_{10})(F_{11}F_{9}+F_9F_8))=146458404.\)

Megjegyzés. A válasz \(\displaystyle 4(2F_{10}^2+1)^2\) alakban is írható.


Statisztika:

A B. 4920. feladat értékelése még nem fejeződött be.


A KöMaL 2017. decemberi matematika feladatai