Kezdőlap


Feladat:	N.63	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Burcsi Péter , Gyarmati Katalin , Szádeczky-Kardoss Szabolcs
Füzet:	1996/január, 36 - 38. oldal		PDF \| MathML
Témakör(ök):	Sakk, Kombinációk, Nehéz feladat
Hivatkozás(ok):	Feladatok: 1995/március: N.63

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

$n = 1$ -re 1-féle eljutás van, $1 < 9^{1}$ .
Rendeljünk minden úthoz egy betűsort a következők alapján: Az első betű J (jobb) vagy L (le) aszerint, hogy a bástya merre indul el. A következők pedig: T (tovább), ha megállás nélkül áthalad az adott mezőn, J vagy L, ha megáll és jobbra, illetve lefelé halad tovább.
Nyilván így különböző ,,eljutásokhoz'' különböző betűsort rendeltünk. A betűsorok hossza $2 n - 2$ , így a különböző betűsorok száma $2 \cdot 3^{2 n - 3} < 9^{n}$ . Ezzel a feladat első részét beláttuk.
Tekintsük az összes $k \times l$ -es táblát, ahol $k + l = 2 n$ . Legyen egy $k \times l$ -es táblán az eljutások szám $N_{k, l}$ . Ekkor $\sum_{k + l = 2 n}^{} N_{k, l} = 2 \cdot 3^{2 n - 3}$ , mivel egy‐egy értelmű megfeleltetés van az ilyen utak és betűsorok között. Azt szeretnénk belátni, hogy a $k \times l$ -es téglalapok közül a négyzetben lehetséges a legtöbb féle út. Ha ez teljesül, akkor a 9 nem helyettesíthető kisebb számmal, mert a különböző méretű táblák száma $2 n - 1$ , így ekkor a négyzeten legalább $\frac{2 \cdot 3^{2 n - 3}}{2 n - 1}$ eljutás van, és tetszőleges $c < 9$ szám esetén ‐ ha az $n$ elég nagy ‐ $\frac{2 \cdot 3^{2 n - 3}}{2 n - 1} > c^{n}$ .
Egy $k \times l$ -es táblán 2-féle eljutás van aszerint, hogy az irányváltoztatások száma páros vagy páratlan.
Legyen először az irányváltoztatások száma $2 m - 1$ ( $m \geq 1$ egész). Ha jobbra indulok: a jobbra megtett szakaszok száma $m$ , hosszaik összege nyilván $k - 1$ . Ismert, hogy a $k - 1$ szám $(\binom{k - 2}{m - 1})$ -féleképpen bontható fel $m$ pozitív egész összegére (ha a sorrend is számít). Hasonló módon a lefelé megtett szakaszokra $(\binom{l - 2}{m - 1})$ -et kapunk. Így ennyi irányváltoztatás mellett az útvonalak száma $(\binom{k - 2}{m - 1}) (\binom{l - 2}{m - 1})$ . Azonban különbséget kell tennünk két útvonal között aszerint is, hogy hol állunk meg. Az útvonal $k + l - 2$ hosszú, az elején és az irányváltoztatásoknál nincs választási lehetőség, a maradék $(k + l - 2) - 1 - (2 m - 1) = k + l - 2 - 2 m$ mezőnél eldönthetjük, hogy megállunk, vagy megállás nélkül továbbhaladunk.
Tehát a lehetőségek száma $(\binom{k - 2}{m - 1}) (\binom{l - 2}{m - 1}) \cdot 2^{k + l - 2 - 2 m}$ .
Ugyanezt kapjuk, ha a bástya lefelé indul el, tehát a lehetőségek száma összesen (rögzített $m$ esetén) $(\binom{k - 2}{m - 1}) (\binom{l - 2}{m - 1}) \cdot 2^{k + l - 1 - 2 m}$ .
Most legyen az irányváltozások száma $2 m$ . Ha jobbra indul, akkor az előzőekhez hasonlóan $m + 1$ vízszintes és $m$ függőleges szakasz van, és hogy megállunk-e, azt $(k + l - 2) - 1 - 2 m = k + l - 3 - 2 m$ mezőnél dönthetjük el, így a lehetőségek száma $(\binom{k - 2}{m}) (\binom{l - 2}{m - 1}) \cdot 2^{k + l - 3 - 2 m}$ . Hasonló módon, ha lefelé indul el, akkor a lehetőségek száma $(\binom{k - 2}{m - 1}) (\binom{l - 2}{m}) \cdot 2^{k + l - 3 - 2 m}$ .
Elég bebizonyítani, hogy a négyzetnél van a legtöbb lehetőség, tehát elég bebizonyítani, hogy minden $m$ -re

\begin{matrix} (\binom{k - 2}{m - 1}) (\binom{l - 2}{m - 1}) \cdot 2^{k + l - 2 - 2 m} \leq (\binom{n - 2}{m - 1}) (\binom{n - 2}{m - 1}) 2^{n + n - 2 - 2 m}, \end{matrix}

illetve

\begin{matrix} \begin{matrix} ((\binom{k - 2}{m}) (\binom{l - 2}{m - 1}) + (\binom{k - 2}{m - 1}) (\binom{l - 2}{m})) \cdot 2^{k + l - 3 - 2 m} \leq \\ \leq (2 \cdot (\binom{n - 2}{m}) (\binom{n - 2}{m - 1})) \cdot 2^{n + m - 3 - 2 m} . \end{matrix} \end{matrix}

Mivel

k + l = n + n

, azért elég bebizonyítani, hogy

\begin{matrix} \begin{matrix} (\binom{k - 2}{m - 1}) (\binom{l - 2}{m - 1}) & \leq {(\binom{n - 2}{m - 1})}^{2} és & (1) \\ (\binom{k - 2}{m}) (\binom{l - 2}{m - 1}) + (\binom{k - 2}{m - 1}) (\binom{l - 2}{m}) & \leq 2 \cdot (\binom{n - 2}{m}) (\binom{n - 2}{m - 1}) & (2) \end{matrix} \end{matrix}

A számtani‐mértani közép egyenlőtlensége alapján

k l \leq {(\frac{k + l}{2})}^{2}

, így minden

c

-re

\begin{matrix} k l - c (k + l) + c^{2} \leq {(\frac{k + l}{2})}^{2} - c (k + l) + c^{2}, \end{matrix}

azaz

(k - c) (l - c) \leq {(\frac{k + l}{2} - c)}^{2}

. Így

\begin{matrix} \prod_{c = 2}^{m} (k - c) (l - c) \leq \prod_{c = 2}^{m} {(n - c)}^{2}, \end{matrix}

azaz

\begin{matrix} \begin{matrix} (k - 2) (k - 3) ... (k - 2 - m + 2) \cdot (l - 2) (l - 3) ... (l - 2 - m + 2) \leq \\ \leq (n - 2) (n - 3) ... (n - 2 - m + 2) . \end{matrix} \end{matrix}

Mindkét oldalt elosztva

{((m - 1)!)}^{2}

-nel, éppen az (1) egyenlőtlenséget kapjuk.
Az (1) mindkét oldalát megszorozva

\frac{k - m - 1}{m} + \frac{l - m - 1}{m} = 2 \cdot \frac{n - m - 1}{m}

-mel:

\begin{matrix} \begin{matrix} (\binom{k - 2}{m - 1}) \cdot \frac{k - m - 1}{m} (\binom{l - 2}{m - 1}) + (\binom{k - 2}{m - 1}) (\binom{l - 2}{m - 1}) \cdot \frac{l - m - 1}{m} \leq \\ \leq 2 (\binom{n - 2}{m - 1}) (\binom{n - 2}{m - 1}) \cdot \frac{n - m - 1}{m}, \\ (\binom{k - 2}{m}) (\binom{l - 2}{m - 1}) + (\binom{k - 2}{m - 1}) (\binom{l - 2}{m}) \leq 2 (\binom{n - 2}{m - 1}) (\binom{n - 2}{m}) . \end{matrix} \end{matrix}

Ezt akartuk bizonyítani.

Burcsi Péter (Pápa, Türr I. Gimn., III. o.t.)