Problem B. 4928. (January 2018)
B. 4928. The trunk of an ever-growing tree forks in two at a height of one foot. In the following, the term branch will refer to a section between two joints, with no further joint along its length. Every branch of the ever-growing tree is straight, and terminates one foot higher than its lower end. The branches starting from the upper end of the branch are considered the children of the branch, also called the siblings of each other. Every branch of the tree has at least two children. If a branch does not have exactly two children then it has a sibling with exactly two children. Siblings always have different numbers of children. If a branch has more than two children then it has a sibling with one fewer children. How many branches start from joints at a height of \(\displaystyle n\) feet?
Proposed by M. E. Gáspár, Budapest
(6 pont)
Deadline expired on February 12, 2018.
Sorry, the solution is available only in Hungarian. Google translation
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}\).
Statistics:
56 students sent a solution. 6 points: 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 points: Beke Csongor, Csaplár Viktor, Szabó 417 Dávid. 4 points: 2 students. 3 points: 6 students. 2 points: 5 students. 1 point: 14 students. 0 point: 2 students.
Problems in Mathematics of KöMaL, January 2018