A B. 5272. feladat (2022. november)

B. 5272. Egy bolha a koordinátarendszer $\displaystyle (a,b)$ pontjából indul, ahol $\displaystyle a$, $\displaystyle b$ pozitív egészek. Egy-egy ugrással balra vagy lefele mozog egységnyit. Addig ugrál, amíg el nem éri az $\displaystyle x$ vagy az $\displaystyle y$ tengelyt. A lehetséges ugrássorozatok hányadrésze végződik az $\displaystyle x$ tengelyen?

Melján Dávid (Kecskemét) ötletéből

(4 pont)

A beküldési határidő 2022. december 12-én LEJÁRT.

1. megoldás. Ha a bolha előbb az $\displaystyle x$ tengelyt éri el, méghozzá a $\displaystyle (k,0)$ pontban, akkor oda a $\displaystyle (k,1)$ pontból érkezett. Amíg az $\displaystyle (a,b)$ pontból a $\displaystyle (k,1)$ pontba eljutott, összesen $\displaystyle a-k$ db balra és $\displaystyle b-1$ db lefele ugrást végzett. Ilyen ugrássorozatból $\displaystyle \binom{a+b-k-1}{b-1}$-féle van (hiszen az $\displaystyle a+b-k-1$ db egymást követő ugrás közül szabadon kiválaszthatok $\displaystyle b-1$ db lefele irányulót).

Így az $\displaystyle x$ tengelyen végződő ugrássorozatok száma:

$\displaystyle \binom{a+b-2}{b-1} + \binom{a+b-3}{b-1} + \binom{a+b-4}{b-1} + \ldots + \binom{b}{b-1} + \binom{b-1}{b-1}.$

A Pascal-háromszög közismert ,,zokniszabálya'' (ld. pl.  https://en.wikipedia.org/wiki/ Hockey-stick_identity) szerint ezek összege:

$\displaystyle \binom{a+b-1}{b}.$

,,Szimmetrikusan'' ugyanezt elmondhatjuk az $\displaystyle y$ tengelyen végződő ugrássorozatok számáról, amelyre így $\displaystyle \binom{a+b-1}{a}$ adódik. Ezen két érték aránya:

$\displaystyle \frac{\binom{a+b-1}{b}}{\binom{a+b-1}{a}} = \frac{\frac{(a+b-1)!}{(a-1)! \cdot b!}}{\frac{(a+b-1)!}{a! (b-1)!}} = \frac{\frac1{b}}{\frac1{a}} = \frac{a}{b}.$

Tehát a lehetséges ugrássorozatok $\displaystyle \dfrac{a}{a+b}$ része végződik az $\displaystyle x$ tengelyen.

2. megoldás. Utasítsuk a bolhát, hogy miután elérte valamelyik tengelyt, onnan még egyenesen ugráljon el az origóba. Így a bolha összességében egy $\displaystyle (a,b)$-ből $\displaystyle (0,0)$-ba vezető balra/le ugrássorozatot végez, ezt nevezzük teljes útvonalnak.

Minden teljes útvonal eléri előbb-utóbb valamelyik tengelyt és a teljes útvonalból egyértelműen rekonstruálható az első tengelyelérésig történő szakasz. Tehát a teljes útvonalak kölcsönösen egyértelműen megfeleltethetők az első tengelyelérésig tartó útvonalaknak.

Teljes útvonalból $\displaystyle \binom{a+b}{a}$ különböző van, és ezek közül éppen azok érik el előbb az $\displaystyle x$ tengelyt, mint az $\displaystyle y$ tengelyt, amelyek az $\displaystyle (1,0)$ pontból érkeznek az origóba. Az $\displaystyle (a,b)$-ből az $\displaystyle (1,0)$ pontba balra/le lépésekkel $\displaystyle \binom{a+b-1}{a-1}$-féleképpen lehet eljutni, így a keresett arány:

$\displaystyle \frac{\binom{a+b-1}{a-1}}{\binom{a+b}{a}} = \frac{a}{a+b}.$

Statisztika:

128 dolgozat érkezett.
4 pontot kapott:	55 versenyző.
3 pontot kapott:	21 versenyző.
2 pontot kapott:	24 versenyző.
1 pontot kapott:	5 versenyző.
0 pontot kapott:	16 versenyző.
Nem versenyszerű:	4 dolgozat.
Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt:	1 dolgozat.

A KöMaL 2022. novemberi matematika feladatai