A B. 4928. feladat (2018. január)

B. 4928. Az égig érő fa törzse egy láb magasan kétfelé ágazik. A továbbiakban ágnak két elágazás közti részt tekintünk, amin nincs további elágazás. Az égig érő fa minden ága egyenes és egy lábbal magasabban végződik, mint a talajhoz közelebbi vége. Egy ág gyermekeinek tekintjük az ág magasabban lévő végéből kiinduló ágakat, amiket egyúttal egymás testvéreinek is nevezünk. Az égig érő fa minden ágának van legalább két gyermeke, és ha nem pont két gyermeke van, akkor van olyan testvére, akinek pontosan két gyereke van. A testvéreknek mindig különböző számú gyerekük van. Ha egy ágnak több, mint két gyereke van, akkor van olyan testvére, akinek pontosan eggyel kevesebb gyereke van, mint neki. Hány ág indul ki az \(\displaystyle n\) láb magasan lévő elágazásokból?

Javasolta: Gáspár Merse Előd (Budapest)

(6 pont)

A beküldési határidő 2018. február 12-én LEJÁRT.

Megoldás. Azt fogjuk igazolni, hogy az \(\displaystyle n\) magasságban lévő elágazások száma az \(\displaystyle n\)-edik Catalan-szám, vagyis \(\displaystyle C_{n}=\frac{\binom{2n}{n}}{n+1}\). Tehát az \(\displaystyle n\) láb magasan lévő elágazásokból \(\displaystyle C_{n+1}=\frac{\binom{2n+2}{n+1}}{n+2}\) ág indul (felfelé), hiszen \(\displaystyle n+1\) láb magasan ennyi elágazás van.

Ehhez felhasználjuk a Catalan-számok azon definícióját, mely szerint \(\displaystyle C_{n}\) azt adja meg, hogy \(\displaystyle (0,0)\)-ból hányféleképpen juthatunk el \(\displaystyle (n,n)\)-be úgy, hogy minden lépésben 1-et jobbra (tehát \(\displaystyle (a,b)\)-ből \(\displaystyle (a+1,b)\)-be) vagy 1-et felfelé (tehát \(\displaystyle (a,b)\)-ből \(\displaystyle (a,b+1)\)-be) lépünk, és a lépegetés során nem járunk olyan pontban, melynek első koordinátája nagyobb a másodiknál (tehát végig az \(\displaystyle y=x\) egyenes alatt maradunk, megengedve azt, hogy erre az egyenesre rálépjünk). Az ilyen utakat hívjuk szabályos utaknak.

Mindezt úgy fogjuk igazolni, hogy megadunk egy bijekciót a szabályos \(\displaystyle (0,0)-(n,n)\) utak és az égig érő fa gyökeréből az \(\displaystyle n\) magasságban lévő elágazásaiba vezető utak között. A fa minden elágazásába írjunk 1-gyel kisebb számot, mint ahány gyereke van. (Tehát az 1 láb magasan lévő elágazásba 1-et írunk, ennek egyik gyerekéhez 1-et, a másikhoz 2-t, stb.) Ha egy elágazásba az \(\displaystyle m\) számot írtuk (vagyis \(\displaystyle m+1\) gyereke van), akkor a szabályok szerint a gyerekeibe írt számok: \(\displaystyle 1,2,\dots,m+1\). Vegyünk egy utat a fa gyökeréből valamelyik \(\displaystyle n\) magasan lévő elágazásába, és az út során látott számok legyenek \(\displaystyle a_1,a_2,\dots,a_n\). Ehhez rendeljük hozzá azt a \(\displaystyle (0,0)\)-ból \(\displaystyle (n,n)\)-be vezető utat, amely az \(\displaystyle x=i\) egyenletű függőleges egyenesre először az \(\displaystyle (i,i-a_i)\) pontban lép rá (az \(\displaystyle (i-1,i-a_i)\) pontból érkezve) minden \(\displaystyle 1\leq i\leq n\) esetén. Megmutatjuk, hogy minden lehetséges \(\displaystyle a_1,a_2,\dots,a_n\) sorozathoz (amit egy \(\displaystyle n\) magasságban lévő elágazásig lépegetve kaptunk az égig érő fánál) tartozik pontosan egy szabályos út. Az 1 magasan lévő elágazásnak 2 gyereke van, ezért \(\displaystyle a_1=1\), tehát az \(\displaystyle x=1\) egyenesre \(\displaystyle (1,0)\)-ban érkezünk (a \(\displaystyle (0,0)\)-ból). Az \(\displaystyle x=2\) egyenesre \(\displaystyle (2,2-a_2)\)-ben kell megérkeznünk, ami vagy \(\displaystyle (2,1)\) vagy \(\displaystyle (2,0)\). Tehát \(\displaystyle (1,0)\)-ból vagy rögtön jobbra lépünk, vagy először egyet felfelé, majd egyet jobbra. Most nézzük meg általánosan: tegyük fel, hogy már beláttuk, hogy \(\displaystyle (i,i-a_i)\)-ig létezik pontosan egy megfelelő út, belátjuk, hogy ennek pontosan egy olyan szabályos folytatása van, amelyen az \(\displaystyle x=i+1\) egyenesre \(\displaystyle (i+1,i+1-a_{i+1})\)-ben érkezünk meg. Tekintsük azt az elágazást, amelyben \(\displaystyle a_i\) szerepel. Ennek a gyerekeiben lévő számok \(\displaystyle 1,2,\dots,a_i+1\), vagyis \(\displaystyle a_{i+1}\) értéke ezen számok közül kerülhet ki. Így \(\displaystyle (i+1,i+1-a_{i+1})\) értéke \(\displaystyle (i+1,i),(i+1,i-1),\dots,(i-a_i)\) lehet. Ez azt jelenti, hogy \(\displaystyle (i,i-a_i)\)-ből először felfelé kell lépnünk \(\displaystyle a_i+1-a_{i+1}\)-et, majd jobbra egyet. Mivel \(\displaystyle 0\leq a_i+1-a_{i+1}\) és \(\displaystyle (i-a_i)+(a_i+1-a_{i+1})=i+1-a_{i+1}\leq i\), ezért ez szabályos folytatása az útnak. Mindezt így folytatva végül eljutunk \(\displaystyle (n,n-a_n)\)-be, ahonnan felfele haladva juthatunk el \(\displaystyle (n,n)\)-be. Tehát az égig érő fa minden \(\displaystyle n\) magasságban lévő elágazásához tartozik egy szabályos út \(\displaystyle (0,0)\)-ból \(\displaystyle (n,n)\)-be.

A bizonyítás befejezéséhez elég megmutatnunk, hogy minden \(\displaystyle (0,0)\)-ból \(\displaystyle (n,n)\)-be vezető szabályos utat pontosan egy (\(\displaystyle n\) magasságban lévő) elágazáshoz rendeltünk hozzá. Vegyünk egy szabályos utat. Az \(\displaystyle a_1,a_2,\dots,a_n\) számokat definiáljuk úgy, hogy \(\displaystyle a_i\) azt mondja meg, hány egységgel az \(\displaystyle (i,i)\) pont alatt lépünk először az \(\displaystyle x=i\) egyenesre. Világos, hogy a kiválasztott szabályos utunkat csak ahhoz az elágazáshoz rendelhettük, ami az \(\displaystyle a_1,a_2,\dots,a_n\) sorozatot határozza meg, és az is világos, hogy ilyen elágazás legfeljebb egy van (hiszen a testvéreknek mindig különböző számú gyereke van). Azt kell tehát ellenőrizni, hogy létezik-e ilyen elágazás. Az \(\displaystyle x=1\) egyenesre csak \(\displaystyle (1,0)\)-ban érkezhetünk, így \(\displaystyle a_1=1\). Az 1 láb magasan lévő egyetlen elágazásban tényleg 1 szerepel, így el tudunk indulni. Tegyük fel, hogy az \(\displaystyle a_1,\dots,a_i\) sorozatot már megtaláltuk, vagyis egy olyan \(\displaystyle i\) magasan lévő elágazásban vagyunk, ahová \(\displaystyle a_i\)-t írtunk, és az idáig vezető úton éppen az \(\displaystyle a_1,\dots,a_i\) számokat láttuk ebben a sorrendben. Ennek az elágazásnak \(\displaystyle a_i+1\) gyereke van, az ezekbe írt számok tehát \(\displaystyle 1,2,\dots,a_i+1\). Azt kell belátnunk tehát, hogy \(\displaystyle 1\leq a_{i+1}\leq a_i+1\). Az alsó becslés világos, hiszen az \(\displaystyle x=i\) egyenes legmagasabban lévő, de még nem az \(\displaystyle x=y\) egyenes fölé eső pontja \(\displaystyle (i,i)\), vagyis az \(\displaystyle x=i+1\) egyenesre \(\displaystyle (i+1,i)\)-ben, vagy ez alatt érkezhetünk meg. Az \(\displaystyle x=i\) egyenesre \(\displaystyle (i,i-a_i)\)-ben érkeztünk meg, így ennél alacsonyabban lévő pontjába az \(\displaystyle x=i+1\) egyenesnek sem érkezhetünk, azaz \(\displaystyle i-a_i\leq i+1-a_{i+1}\), és mi éppen ezt akartuk igazolni.

Ezzel beláttuk, hogy a fenti hozzárendelés bijekció, így az \(\displaystyle n\) magasan lévő elágazásokból induló ágak száma éppen az \(\displaystyle n+1\)-edik Catalan-szám, vagyis \(\displaystyle C_{n+1}=\frac{\binom{2n+2}{n+1}}{n+2}\).

Statisztika:

56 dolgozat érkezett.
6 pontot kapott:	Biczó Benedek, Busa 423 Máté, Daróczi Sándor, Deák Bence, Dobák Dániel, Döbröntei Dávid Bence, Füredi Erik Benjámin, Gáspár Attila, Győrffi Ádám György, Győrffy Ágoston, Győrffy Johanna, Hegedűs Dániel, Hervay Bence, Janzer Orsolya Lili, Kerekes Anna, Molnár Bálint, Nagy Nándor, Noszály Áron, Póta Balázs, Schifferer András, Soós 314 Máté, Tóth 827 Balázs, Weisz Máté, Zsigri Bálint.
5 pontot kapott:	Beke Csongor, Csaplár Viktor, Szabó 417 Dávid.
4 pontot kapott:	2 versenyző.
3 pontot kapott:	6 versenyző.
2 pontot kapott:	5 versenyző.
1 pontot kapott:	14 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2018. januári matematika feladatai