|
Feladat: |
B.4928 |
Korcsoport: 16-17 |
Nehézségi fok: nehéz |
Megoldó(k): |
Biczó Benedek , Busa 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örffy Á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 Máté , Tóth Balázs , Weisz Máté , Zsigri Bálint |
Füzet: |
2018/szeptember,
350 - 351. oldal |
PDF | MathML |
Témakör(ök): |
Feladat, Fagráfok, erdők, faváz, Kombinatorikai leszámolási problémák |
Hivatkozás(ok): | Feladatok: 2018/január: B.4928 |
|
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. Írjuk rá minden ágra (és a törzsre), hogy hány gyermeke van. Legyen egy ág (vagy a törzs), aminek gyereke van. Legyen az gyermekeire írt számok maximuma. Legyen az gyermekein nem szereplő, -nál kisebb pozitív egész számok maximuma. A biztosan létezik, mert az 1 nem szerepelhet az ágakon. Ekkor a szerepel valamelyik gyerekén. Ha , akkor , ezért a szerepel valamelyik gyermekén. Ez ellentmondás, ezért . Így a mind szerepelnek gyermekein. A testvéreknek különböző számú gyermeke van, ezért ezekből pontosan egy van. Így gyermekeinek a száma , tehát . Tehát az gyermekeire írt számok a . Vegyünk fel az ágak között egy irányított gráfot, ahol kétféle él van: az egyik fajta egy ,,függőleges'' él, amely egy feliratú ágtól az feliratú gyermekéhez vezet, a másik fajta egy ,,vízszintes'' él, amely egy feliratú ágtól az feliratú testvéréhez vezet, ha . Látható, hogy a gráfban minden ághoz pontosan egyféleképpen lehet eljutni a fa törzsétől, mert egy ágtól az összes gyermekéhez pontosan egyféleképpen lehet eljutni. Az összes ágtól pontosan egy függőleges és pontosan egy vízszintes él indul, kivéve a -es ágakat, ahonnan csak függőleges él indul. Az láb magasan induló ágak száma megegyezik az láb magasan induló -es ágak számával, mert minden ágnak pontosan egy -es gyermeke van. Válasszunk ki egy láb magasan induló -es ágat. -hez létezik pontosan egy útvonal a gráfban, ami a fa törzsétől indul. Nevezzük a és jelekből álló véges sorozatokat sorozatnak. Az útvonalat leírhatjuk egy sorozattal, ahol a függőleges élet jelent, a pedig vízszintes élet. Az így kapott -sorozat egyértelműen meghatározza -et. Látható, hogy egy esetén eggyel nő a jelenlegi ágra írt szám, és a esetén eggyel csökken, ahogy a sorozat alapján haladunk a gráfban. Az útvonal első és utolsó ágán is a szerepel, ezért a -ok és -ok száma megegyezik. Az -hez tartozó sorozat darab jelet tartalmaz, mert a függőleges élekkel egy lábbal nő a magasság, a vízszintes éleknél nem változik. Így a -ok száma is . Nevezzünk egy darab jelet és darab jelet tartalmazó sorozatot jónak, ha az első tagja között legalább annyi van, mint mindegyik -re. Az útvonal összes ágán a szám legalább , és az első ágon a szám , ebből könnyen látható, hogy az -hez tartozó sorozat jó. Az is látható, hogy ha a sorozat jó, akkor nem fordulhat elő, hogy egy -es ágról egy vízszintes élen próbálunk továbblépni. Így a jó sorozatok száma megegyezik az láb magasan induló ágak számával. A jó sorozatokat úgy számolhatjuk meg, hogy az összes darab -t és darab -t tartalmazó sorozat számából levonjuk a nem jó sorozatok számát. Az összes ilyen sorozat száma . Vegyünk egy olyan sorozatot, ami nem jó. Van olyan minimális , amelyre teljesül, hogy az első tag között több van, mint . A minimalitás miatt az első között között legfeljebb annyi van, mint . Ez csak úgy lehet, ha az első tag között ugyanannyi van, mint , és az -edik tag . Változtassuk meg az -edik tag utáni összes tagot, ezt nevezzük módosított sorozatnak. Ha az -edik tagot is megváltotatnánk, akkor nyilván nem változna meg a -ok és -ok száma (mert egyenlőek). Így a módosított sorozatban darab van, és darab . Látható, hogy egy darab -t és darab -t tartalmazó sorozat esetén is van olyan , amire az első elem között több van, mint (mert az egész sorozatban is több van). Vegyük észre, hogy ha a minimális -edik tag után megváltoztatjuk az összes tagot, akkor visszakapjuk az eredeti sorozatot. Így a nem jó sorozatok száma megegyezik az darab -t és darab -t tartalmazó sorozatok számával, ami . Tehát az ágak száma: , ami az -edik Catalan-szám.
Gáspár Attila (Miskolc, Földes Ferenc Gimn., 12. évf.) dolgozata alapján
Megjegyzés. A helyes megoldást adó versenyzők többsége valamilyen ismert problémára visszavezetve eljutott oda, hogy az láb magasan kiinduló ágak száma az -edik Catalan-szám. Ezután ennek a kiszámítását már nem részletezte.
|
|