Kezdőlap


Feladat:	B.3963	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Barta Zsolt , Szalkai Balázs
Füzet:	2007/december, 536 - 537. oldal		PDF \| MathML
Témakör(ök):	Sakk, Mátrixjátékok, Kombinatorikai leszámolási problémák, Feladat
Hivatkozás(ok):	Feladatok: 2007/január: B.3963

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.

I. megoldás. Az, hogy át kell haladnunk a középső mezők valamelyikén, pontosan azt jelenti, hogy nem léphetünk az ábrán sötétre színezett mezőkre, mert így kikerülnénk a középső négy mezőt, hiszen csak jobbra vagy felfelé léphetünk.

A többi útvonal viszont mind áthalad a középső

2 \times 2

-es területen, tehát csak ezeket az útvonalakat kell összeszámolnunk.
A kiinduló mezőre egyféleképpen léphetünk. A többi mezőre pedig annyiféleképpen, amennyi a tőle balra lévő és alatta lévő mezőkre lépés lehetőségeinek összege, hiszen csak ezekről léphetünk rá.
Így minden mezőre beírhatjuk, hányféleképpen léphetünk oda. A jobb felső sarokba tehát 2450-féleképpen juthatunk. Ennyi a keresett útvonalak száma.

II. megoldás. Egy

a \times b

mezős ,,sakktáblán'' a bal alsó sarokból a jobb felsőbe vezető utak száma:

\begin{matrix} S (a; b) = (\binom{a + b - 2}{a - 1}), \end{matrix}

ugyanis

(a + b - 2)

-t lépünk, és ezek közül választhatunk

(a - 1)

jobbra lépést.

A középső négy mezőre beléphetünk az

A

C

vagy

B

mezőkön. Utóbbi két út szimmetrikus, tehát elegendő az egyiket vizsgálni, majd a kapott lépésszámot szorozni kettővel.
Az

A

mezőre

S (4; 4)

-féleképpen juthatunk. Utunkat az

A

mezőről egy

5 \times 5

-ös táblán folytathatjuk

S (5; 5)

-féleképpen.
A

C

mezőre csak a

P

mezőről léphetünk, úgy, hogy

A

-t ne érintsük. A

P

mezőre

S (3; 5)

-féleképpen juthatunk. A

C

mezőről tovább pedig

S (5; 4)

-féleképpen mehetünk a jobb felső sarokba.
A megfelelő útvonalak száma:

\begin{matrix} S (4; 4) \cdot S (5; 5) + 2 \cdot S (3; 5) \cdot S (5; 4) = (\binom{6}{3}) \cdot (\binom{8}{4}) + 2 (\binom{6}{2}) \cdot (\binom{7}{4}) = 2450. \end{matrix}