Zadanie
Mišovia kúpili chlieb. Keďže ši ho Mišovia nezvládli nakrájať v šupermarkete, tak ši ho mušia teda nakrájať nožom. Nôž je tupý a Mišovia šmatlaví, takže žiadne dva krajce chleba nemajú rovnakú výšku ani rovnakú hrúbku. Nech \(n \geq 2\) je celé číšlo označujúce počet krajcov chleba. Mišo ich uložil do chlebníka od najnižšieho po najvyšší zľava doprava. Každú minútu Mišovia vezmú nejaké dva šušedné krajce také, že ľavý krajec je širší a nižší než pravý, a vymenia ich.
Mišovia odmietli ješť chlieb, pokým nebude zoradený podľa hrúbky. Dokážte, že bez ohľadu na to, aké ťahy robia Mišovia, po konečnom počte minút nebudú môcť špraviť žiadny ďalší ťah a krajce budú vtedy zoradené vzoštupne podľa hrúbky zľava doprava.
Vieme, že Mišovia budú robiť ťahy, kým budú môcť. Tiež vieme, že máme konečný počet krajcov chleba a konečný počet spôsobov, ako ich usporiadať. Ďalej je isté, že ak sa raz dva chleby vymenia, už nikdy sa nebudú môcť vymeniť nazad (chlieb sa ocitne napravo od krajca, ktorý je vyšší). Preto sa nám nikdy nezopakuje usporiadanie chlebov, a keďže usporiadaní je konečný počet, tak po konečnom počte ťahov Mišovia musia skončiť.
Uvažujme najužší krajec, označme ho \(K\). Čo ak by sme nikdy nepohli chlebom \(K\)? Je len konečný počet výmen, ktoré môžeme urobiť bez toho, aby sme pohli \(K\). Pokiaľ \(K\) nie je celkom vľavo, určite sa teda dostaneme do situácie, kedy nebudeme môcť pohnúť žiadnym krajcom okrem tohto. V takejto situácii budú určite všetky chleby naľavo od \(K\) nižšie (tak boli rozostavené na začiatku) aj širšie (pretože \(K\) je najužší). Teda určite vieme posunúť \(K\) doľava a je to jediný ťah, ktorý vieme spraviť, takže ním musíme pohnúť. Pokiaľ stále nie je najviac vľavo, ako sa len dá, môžeme túto úvahu zopakovať. Opäť bude možný len konečný počet ťahov bez pohnutia \(K\) a potom týmto krajcom určite budeme musieť pohnúť. Pokiaľ sa \(K\) dostalo na najľavejšiu pozíciu, tak nám zostáva usporiadať už len \(n-1\) krajcov.
V tomto bode môžeme sledovať pozície nového \(K_1\), čo je nový najužší krajec. Tento časom stretne rovnaký osud a niekedy sa bude musieť dostať na druhú najľavejšiu pozíciu. Ak tento postup zopakujeme \(n-1\) krát, určite usporiadame všetky krajce podľa hrúbky za konečný počet minút a žiaden ďalší ťah už nebude možné urobiť.
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ť.