6. Kadekto Musel Stáť vzorové riešenie

Všimnime si, že zakaždým sa vymieňajú iba susední pán a dáma. Vzájomné poradie dám sa nemení. Preto si môžeme očíslovať dámy celými číslami od \(1\) do \(d\) (vrátane), kde \(d\) je počet dám v rade, v poradí, v akom stoja v rade. Toto číslovanie sa zachová počas celého procesu. Ako druhé vypozorujme, že v danej chvíli (na danom začiatku minúty) sa dáma posúva dopredu práve vtedy, ak na začiatku tohto pohybu stál bezprostredne pred ňou pán.

Keď si skúsime simulovať správanie sa radu pre nejaké počiatočné rozostavenia dám a pánov, uvidíme, že prvá dáma sa od začiatku hýbe dopredu, až kým nepredbehne všetkých pánov. Druhá dáma môže byť blokovaná prvou, ale iba raz, lebo potom sa už za prvú dámu dostane každú minútu jeden pán, ale druhá každú minútu predbehne iba jedného, čiže prvú dobehne až na začiatku radu. Podobne tretia dáma môže byť na začiatku blokovaná, ale iba v prvých dvoch minútach… Vo všeobecnosti: Každá dáma počká najviac toľko minút, koľko je pred ňou dám. Za tento čas sa práve toľko pánov (ak sme nenarazili na začiatok radu) dostane do priestoru medzi ňou a prvou dámou. Odvtedy už má vždy koho predbiehať. Na základe takýchto experimentov už sformulujeme pomocné tvrdenie, ktorého dôkazom úlohu vyriešime.

Matematickou indukciou¹ teda dokážme, že \(k\)-ta dáma v rade (pre všetky čísla dám \(k\)) vždy, keď už prešlo aspoň \(k-1\) minút, sa bude nachádzať bezprostredne za pánom (alebo, ekvivalentne, sa pohne) alebo pred všetkými pánmi.

Pre \(k=1\) prvá dáma vždy, keď už prešlo aspoň \(0\) minút (táto podmienka je splnená pri každej príležitosti na pohyb), sa má pohnúť alebo stáť na čele radu. Keďže pred ňou nestojí ani jedna dáma, akonáhle sa pred ňou niekto nachádza, musí sa hneď pred ňou nachádzať pán. Tým je tento prípad dokázaný.

Keď už máme za sebou aspoň \(k-1\) minút, pri predchádzajúcom pohybe už prešlo aspoň \(k-2\) minút, takže z indukčného predpokladu pri predchádzajúcom pohybe sa dáma číslo \(k-1\) pohla alebo sa pred ňou už nenachádzal pán. Ak sa pohla, bezprostredne za ňu sa dostal pán, čo znamená, že medzi ňou a dámou číslo \(k\) je aspoň jeden pán. Ak sa pred dámou \(k-1\) už nenachádza pán, buď sa nenachádza ani pred \(k\)-tou, alebo sa opäť nejaký nachádza medzi nimi. Odtiaľ bezprostredne pred \(k\)-tou dámou stojí pán, čo sme chceli. Dokázali sme tvrdenie pre \(k\).

Z tohto plynie, že posledná dáma číslo \(d\) sa pohne zakaždým, keď prešlo aspoň \(d-1\) minút a pred ňou je ešte nejaký pán. Ak sa po \(29\) minútach pred ňou ešte nachádza nejaký pán, musel sa tam nachádzať nejaký aj vždy dovtedy (počet pánov pred ňou nemôže vzrásť, páni sa posúvajú iba za ňu), čo znamená, že na začiatku každej minúty od \(d\)-tej po dvadsiatu deviatu vrátane sa dáma pohla. To sa ale musela pohnúť \(30-d\) ráz, čo je spor, pretože v rade stojí celkovo iba \(30-d\) pánov a potom, čo ju každý pustil pred seba, už pred ňou nemôže byť ani jeden. To znamená, že všetci sa nachádzajú za ňou (a za všetkými ostatnými dámami) a dokázali sme tvrdenie zo zadania dokonca pre \(29\) minút.

Pravdaže, tým ho máme dokázané aj pre požadovaných \(30\), pretože posledný pohyb cieľový stav už nezvráti (ba čo viac, na začiatku tridsiatej minúty sa neudeje ani jedna výmena).