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