Zadanie

Sultánovi sa už z úloh zatmieval mozog, niekde pri dvadsiatej hádanke ich už aj prestal počítať. Nevládal. Bol porazený. Vedel, že sa už nikdy odtiaľto nedostane a bez jeho velenia turecké vojská isto prehrajú bitku pri Moháči. A králik? Ten sa bavil. S potmehúdskym úškrnom vyčaroval na stôl balíček matgických kariet a povedal:

,,Tu máš balík \(52\) matgických kariet, ktoré som ti práve náhodne pootáčal tvárou nahor alebo tvárou nadol1. V jednom kroku smieš rozdeliť tento balík, jednu časť otočiť naopak a umiestniť ju späť na druhú časť. Moja otázka znie: ,Vieš otočiť všetky karty lícom nahor bez ohľadu na to, ako som ich otočil?‘ ‘‘

  1. Karty pritom naďalej ostali v balíku.↩

Zadanie tejto úlohy sa dalo pochopiť dvoma spôsobmi. Nebolo v ňom jasne povedané, či vidíme otočenie všetkých kariet v balíčku alebo len jednej karty navrchu.

Ak otočenie kariet na začiatku nevidíme, tak si ho vieme zistiť napríklad takto:

Otočenie \(i\)-tej karty zistíme tak, že prvých \(i\) kariet v balíčku otočíme. Teraz máme \(i\)-tu kartu navrchu balíčka a vidíme jej otočenie. Potom otočíme všetkých \(i\) kariet naspäť.

Potom vieme pokračovať postupom, ako keby sme karty videli, ktorý ilustrujeme nižšie. Preto veríme, že vám táto nejasnosť v zadaní nespôsobila problémy.

Riešenie (podľa Martina Štepánka)

Niekoľko kariet na vrchu (aspoň \(1\)) je otočených rovnako. Ak nie je rovnako otočený celý balíček, je priamo pod nimi niekoľko (tiež aspoň \(1\)) kariet otočených opačne (inak by patrili k pôvodným kartám). Ak tieto rovnaké karty zoberieme, otočíme opačne a položíme naspäť, tak budú stále na vrchu kôpky, ale otočené rovnako ako tie karty tesne pod nimi. To znamená, že počet kariet na vrchu, ktoré sú otočené rovnako, sa pri každom takomto kroku zväčší. Preto sa opakovaním tohto kroku napokon dostaneme až na koniec balíčka.

Potom je buď úloha splnená a karty sú lícom nahor, alebo sú všetky lícom nadol a celý balíček ešte raz otočíme.

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ť.