3. Kočiar Miesto Súpravy

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.