A B. 5296. feladat (2023. február)

B. 5296. Hány különböző lépéssorozattal juthat el egy bástya a \(\displaystyle 8\times 8\)-as sakktábla bal alsó sarkából a jobb felső sarkába, ha felváltva lép jobbra és felfelé, továbbá először jobbra lép és utoljára felfelé?

Javasolta: Hujter Bálint (Budapest)

(4 pont)

A beküldési határidő 2023. március 10-én LEJÁRT.

1. megoldás. A bástya mozgását kódoljuk egy \(\displaystyle \{\rightarrow,\uparrow\}\)-sorozattal a következő módon. Ha egy lépésben jobbra (felfelé) lép \(\displaystyle k\) mezőt, akkor leírunk \(\displaystyle k\) darab \(\displaystyle \rightarrow\) jelet (\(\displaystyle \uparrow\) jelet). Világos, hogy különböző lépéssorozatokhoz különböző \(\displaystyle \{\rightarrow,\uparrow\}\)-sorozat tartozik.

Mivel a bal alsó sarokból a jobb felsőbe kell eljutnia a bástyának, ezért az így kapott sorozat 14 hosszú lesz, és hét-hét \(\displaystyle \rightarrow\), illetve \(\displaystyle \uparrow\) jelből áll. Jobbra lép először és utoljára felfelé, ezért az első jel \(\displaystyle \rightarrow\), az utolsó pedig \(\displaystyle \uparrow\).

Megmutatjuk, hogy minden ilyen \(\displaystyle \{\rightarrow,\uparrow\}\)-sorozatot meg is kapunk a bástya egy lépéssorozatánál. Tekintsünk egy 14 hosszú, \(\displaystyle \{\rightarrow,\uparrow\}\)-sorozatot, mely hét-hét \(\displaystyle \rightarrow\), illetve \(\displaystyle \uparrow\) jelből áll, \(\displaystyle \rightarrow\)-val kezdődik, \(\displaystyle \uparrow\)-vel végződik. Mivel felváltva lép jobbra és felfelé, így az első lépése olyan hosszúságú jobbra, ahány egymást követő \(\displaystyle \rightarrow\) jellel kezdődik a sorozat (az első \(\displaystyle \uparrow\) előtt). Ezután felfelé lép, éspedig olyan hosszút, ahány \(\displaystyle \uparrow\) jel következik egymás után. És így tovább...

Tehát a lépéssorozatok száma az olyan 14 hosszú \(\displaystyle \{\rightarrow,\uparrow\}\)-sorozatok száma, amik hét-hét \(\displaystyle \rightarrow\), illetve \(\displaystyle \uparrow\) jelből állnak, \(\displaystyle \rightarrow\)-val kezdődnek, \(\displaystyle \uparrow\)-val végződnek. Vagyis a középső 12 helyen kell kiválasztani 6 helyet, ahova \(\displaystyle \rightarrow\) kerül, így a lépéssorozatok száma \(\displaystyle \binom{12}{6}=924\).

2. megoldás. Mivel a bástyának összesen hetet kell jobbra és hetet felfelé elmozdulnia, ezért a jobbra lépések \(\displaystyle k\) számára \(\displaystyle 1\leq k\leq 7\) teljesül. Mivel jobbra indul és felfelé lép utoljára, ezért a felfelé lépések száma szintén \(\displaystyle k\). A lépéssorozatot már egyértelműen meghatározza, hogy sorrendben mi a \(\displaystyle k\) darab jobbra lépés hossza és sorrendben mi a \(\displaystyle k\) darab felfelé lépés hossza. Világos, hogy a két esetben ugyanaz a lehetőségek száma, éspedig az \(\displaystyle a_1+a_2+\dots+a_k=7\) egyenlet pozitív egész megoldásainak száma. (Hiszen mindegyik jobbra lépésnél legalább egyet haladnunk kell jobbra, összesen pedig hetet.)

Egy ilyen megoldásnak viszont kölcsönösen egyértelműen megfeleltethetők az \(\displaystyle \{1,2,3,4,5,6\}\) halmaz \(\displaystyle k-1\) elemű részhalmazai. Nevezetesen, az \(\displaystyle a_1+a_2+\dots+a_k=7\) megoldáshoz rendeljük hozzá az \(\displaystyle \{a_1,a_1+a_2,\dots,a_1+a_2+\dots +a_{k-1}\}\) halmazt. Így az egyenlet megoldásainak száma \(\displaystyle \binom{6}{k-1}\).

Tehát a lépéssorozatok száma \(\displaystyle \sum\limits_{k=1}^7 \binom{6}{k-1}^2\). Ezt egyrészt numerikusan is kiszámíthatjuk, megkapva a 924-es végeredményt, másrészt a

\(\displaystyle \sum\limits_{k=1}^7 \binom{6}{k-1}^2=\sum\limits_{i=0}^6 \binom{6}{i}\cdot\binom{6}{6-i}\)

felírás mutatja, hogy az összeg \(\displaystyle \binom{12}{6}\)-tal egyenlő, hiszen ha \(\displaystyle A\) és \(\displaystyle B\) két diszjunkt 6-elemű halmaz, akkor az \(\displaystyle A\cup B\) 12-elemű halmaz 6-elemű \(\displaystyle C\) részhalmazait úgy is összeszámolhatjuk, hogy aszerint csoportosítjuk őket, mekkora \(\displaystyle A\cap C\) mérete. Ha \(\displaystyle |A\cap C|=i\), akkor \(\displaystyle |B\cap C|=6-i\), és így \(\displaystyle C\)-re \(\displaystyle \binom{6}{i}\cdot\binom{6}{6-i}\) féle lehetőség van, ezt kell összegezni \(\displaystyle 0\leq i\leq 6\)-ra.

3. megoldás. Tekintsük azokat a mezőket, ahol minden második lépés után van a bástya. Ez mezők egy olyan sorozata, ahol a következő mindig jobbra-felfele helyezkedik el az előzőhöz képest. Egy ilyen mezősorozatot röviden hívjunk jobbra-fel sorozatnak. A sorozatban szereplő legelső mező a bal alsó sarok, a legutolsó pedig a jobb felső sarok. Ezek a lépéssorozatot egyértelműen meghatározzák, hiszen az ilyen mezőből jobbra mindig annyit lép a bástya, hogy a jobbra-fel sorozatban szereplő következő mező oszlopába kerüljön. Számozzuk meg a sorokat és az oszlopokat a bal alsó saroktól kezdve 1-től 8-ig és \(\displaystyle 1\leq k,\ell\leq 8\) esetén jelölje \(\displaystyle a_{k,\ell}\) azt, hogy a bal alsó sarokból hány jobbra-fel sorozattal juthatunk el a \(\displaystyle k\)-adik sor \(\displaystyle \ell\)-edik mezőjébe. A \(\displaystyle (k,\ell)\)-ben végződő jobbra-fel sorozat utolsó mezője egy olyan \(\displaystyle (i,j)\) mező lehet, melyre \(\displaystyle i<k\) és \(\displaystyle j<\ell\). Így \(\displaystyle a_{k,\ell}\)-re a következő rekurzív képlet adható:

\(\displaystyle a_{k,\ell}=\sum\limits_{\substack{1\leq i<k,\\1\leq j<\ell}}a_{i,j}.\)

(Speciálisan, ha \(\displaystyle k=1\) vagy \(\displaystyle \ell=1\), akkor ez egy üres összeg és \(\displaystyle a_{k,\ell}=0\).)

A rekurzió alapján a \(\displaystyle 8\times 8\)-as sakktábla mezőibe beírva az \(\displaystyle a_{k,\ell}\) értékeket könnyen kiszámolhatjuk, a mezőket alulról felfelé, balról jobbra haladva töltve ki: minden mezőbe a tőle balra-lefelé lévő mezőkben lévő számok összegét kell írni:

Így a lépéssorozatok száma 924.

Statisztika:

132 dolgozat érkezett.
4 pontot kapott:	103 versenyző.
3 pontot kapott:	1 versenyző.
2 pontot kapott:	11 versenyző.
1 pontot kapott:	7 versenyző.
0 pontot kapott:	4 versenyző.
Nem versenyszerű:	2 dolgozat.

A KöMaL 2023. februári matematika feladatai