Zadanie

Počas dlhých zimných večerov hrajú Jožo s Kikou cez videohovor zaujímavú hru. Kika zamieša balík \(52\) kariet a uloží karty do kruhu lícom nahor, pričom jedno miesto v kruhu nechá prázdne. Jožo, ktorý na karty nevidí (keďže Kika si omylom zabudla odlepiť pásku z kamery), jednu menuje. Ak táto karta susedí s prázdnym miestom, Kika posunie kartu na prázdne miesto, bez toho, aby to povedala Jožovi. Ináč sa nič nestane. Potom Jožo menuje ďalšiu kartu atď. toľkokrát, koľko chce, kým nepovie „KMS“.

  1. Môže Jožo zaručiť, že po vyrieknutí „KMS“ nie je žiadna karta na svojom pôvodnom mieste?
  2. Môže Jožo zaručiť, že po vyrieknutí „KMS“ nesusedí piková dáma s prázdnym miestom?

Časť a)

Časť a) je jednoduchá, stačí si zvoliť ľubovoľné pevné poradie kariet a povedať ho \(52\)-krát (napr. Srdce 2, Srdce 3, …, Srdce Eso, Piko 2, …, Káro Eso), spolu \(2704\) slov. Čo sa stane? Prázdne miesto sa bude pohybovať stále jedným smerom a obkrúži takto celý kruh (možno niekoľko krát). Určite nemôže zmeniť smer, pretože ak sme akurát vyslovili kartu vedľa voľného miesta a presunuli ju tam, vyslovíme všetky ostatné karty skôr ako ju vyslovíme znova, teda už sa na to voľné miesto presunula iná karta v rovnakom smere.

  • Každá karta sa posunie aspoň raz, pretože prázdne miesto sa posunie každé kolo aspoň raz, teda spolu aspoň \(52\)-krát v jednom smere, teda sa posunie o celý kruh, a to znamená že sme sa s každou kartou posunuli aspoň raz.

  • Žiadna karta sa nevráti na svoje pôvodné miesto, keďže jednu kartu vyslovíme práve \(52\)-krát, a na vrátenie sa v smere hod. ručičiek potrebuje \(53\) presunov (keďže kruh je tvorený \(53\) miestami, jedno je voľné).

Preto žiadna karta neostane na svojom mieste.

Časť b)

Predstavme si poskladaný kruh a všetky možné polohy prázdneho miesta, teda kruh so \(104\) miestami a každé druhé je prázdne. Značí to, že na začiatku môže byť prázdne miesto medzi ľubovoľnými dvoma kartami. Jožo teraz povie jednu kartu. Kde môže byť prázdne miesto teraz? Nič sa nezmení s kartami a miestami mimo nej, jedine sa niečo stane s dvoma susediacimi. Čo sa ale stane? Ak je prázdne miesto napravo od vyslovenej karty, presunie sa od nej naľavo. Ak je prázdne miesto naľavo, presunie sa napravo. Teda po vyslovení nejakej karty môžu byť prázdne miesta stále na ľubovoľnom mieste. Pre každý krok teda platí, že prázdne miesto môže byť pri ľubovoľnej karte. Preto neexistuje žiadna postupnosť kariet taká, aby bolo zaručené že pri pikovej dáme nebude prázdne miesto.

Iné riešenie časti b)

Ďalej značíme \(S+[t_1, ..., t_n]\) stav kariet, do ktorého sa dostaneme zo stavu \(S\) po vykonaní postupnosti ťahov \(t_1, ... t_n\). Jožova sekvencia kariet musí byť univerzálna pre všetky začiatočné rozostavenia kariet. Pre spor teda predpokladajme, že taká existuje, označme ju \(k_1,\, \dots,\, k_n\). Uvažujme ľubovoľné konečné rozostavenie kariet také, pre ktoré Jožo prehrá, a označme ho \(P\). Spravme reverznú sekvenciu ťahov, t. j. \(k_n, \dots, k_1\) a začnime hru v takomto začiatočnom rozostavení kariet \(P+ [k_n, \dots, k_1]\). Keďže po dvoch vysloveniach rovnakej karty sa karta posunie tam a späť (prípadne sa nepohne vôbec) nič to nezmení. Jožo teraz povie jeho sekvenciu a stane sa toto: \(P+[k_n, \dots, k_2, k_1, k_1, k_2, \dots, k_n]=P+[k_n, \dots, k_2, k_2, \dots, k_n]=\dots=P+[k_n, k_n]=P\) Teda na konci ostane práve prehrávajúce rozpoloženie kariet. Preto neexistuje univerzálna sekvencia kariet zaručujúca prázdne miesto pri dá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ť.