Problem B. 5296. (February 2023)

B. 5296. A rook is moving from the bottom left corner of a \(\displaystyle 8\times 8\) chessboard to the top right corner. It starts by moving to the right, then up, and so on, right and up alternatingly. How many different sequences of moves are there?

Proposed by B. Hujter, Budapest

(4 pont)

Deadline expired on March 10, 2023.

Sorry, the solution is available only in Hungarian. Google translation

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.

Statistics:

132 students sent a solution.
4 points:	103 students.
3 points:	1 student.
2 points:	11 students.
1 point:	7 students.
0 point:	4 students.
Unfair, not evaluated:	2 solutionss.

Problems in Mathematics of KöMaL, February 2023