Zadanie
František sa mu chce poďakovať, a tak ho pozve k nemu domov do kráľovského paláca. Zavedie ho ku kočiaru, kde sa Krtko začudovane opýta: „A veď keď si hovoril, že tento hrad je až vo vedľajšom meste, tak nepôjdeme radšej vlakom? Nebude to rýchlejšie a pohodlnejšie?“ „Vlakom?“ začudovane sa opýta František, „Čo to je? Ako to funguje?“ „Tak tu mi vlak nehrozí…“ Krtko si smutne povzdychol a podujal sa Františkovi vysvetľovať, čo to ten vlak je.
Na železničnej stanici v Krtkovom meste majú dve slepé koľaje, ktoré sa na jednom konci spájajú do jednej, kadiaľ pokračuje trať von z mesta. Na prvej koľaji stojí súprava vlaku pozostávajúca z rušňa a \(n\) navzájom rozlíšiteľných vagónov. V jednom kroku môžu železničiari spraviť nasledovný proces:
rozpoja súpravu na 1. koľaji na ľubovoľnom mieste,
rušeň odtiahne vagóny, ktoré ostali za ním zapojené, von z mesta,
rušeň zacúva na 2. koľaj a tým odtlačí vagóny, ktoré boli odtiahnuté von z mesta, pričom ak sa na 2. koľaji už nachádzajú vagóny, tak ich k nim pripojí,
pokiaľ ešte na 1. koľaji ostali vagóny, rušeň odpoja od všetkých vagónov na 2. koľaji a vráti sa naspäť na 1. koľaj, kde ho pripoja na vagóny.
Tento proces železničiari ľubovoľne opakujú, dokým všetky vagóny neskončia na 2. koľaji.
Koľko rôznych súprav možno týmto spôsobom zložiť?
Napríklad ak na začiatku boli na 1. koľaji za rušňom vozne 1, 2, 3, tak železničiari mohli napríklad najskôr rozpojiť súpravu medzi vozňami 2 a 3, potom odtiahnuť vozne 1 a 2 von z mesta a následne ich presunúť na 2. koľaj. Rušeň sa potom vráti na prvú koľaj, pripojí sa k nemu vozeň číslo \(3\), vyjdú von z mesta a potom prejdú na druhú koľaj. Na konci tak budú na druhej koľaji za rušňom vozne v poradí 3, 1, 2.
Pozrime sa, ako nakoniec vyzeralo každé preusporiadanie celej súpravy. Vždy ho vieme popísať iba miestami, na ktorých sa rozhodnú pôvodnú súpravu rozpojiť. Všetko ostatné je jednoznačné, postupne odoberú odpojený kus súpravy a preradia ho na druhú koľaj, ako sa píše v zadaní.
Medzi každými dvoma z \(n\) vagónov môžu súpravu buď rozpojiť alebo nerozpojiť, nie je to nijak ovplyvnené tým, či už súpravu rozpojili na inom mieste. Počet možností, ako to urobiť, teda bude \(2^{n-1}\), lebo počet miest medzi vagónmi je \(n-1\) a každé má \(2\) možnosti.
Teraz už len treba ukázať, že nám z dvoch iných porozpájaní nemôže na konci vzniknúť rovnaká súprava. To overíme ľahko – pozrieme sa na nejaké miesto, kde sa dve porozpájania líšia, teda v jednom sme tam súpravu rozpojili a v jednom nie. Dva vagóny, ktoré sú priamo pri takomto mieste, ostanú v prípade nerozpojenia vzájonme v pôvodnom poradí, no v prípade rozpojenia sa do novej súpravy dostane najprv vagón ktorý bol bližšie k lokomotíve, teda potom bude z tých dvoch bližšie k mestu.
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.