Zadanie

Agenti C. S. I. Žilina vypočúvajú ťažkého zločinca, ktorý im nechce nič prezradiť. Preto si na pomoc zavolali Mr. Mira. Všetko, čo Mr. Miro potrebuje, je psychicky zničiť zločinca nasledujúcou hrou.

Zločinec si tajne myslí $8$ políčok na šachovnici $8 \times 8$, pričom žiadne dve neležia v rovnakom riadku ani v rovnakom stĺpci. Potom má Mr. Miro sériu pokusov. Jeden pokus spočíva v tom, že Mr. Miro umiestni $8$ veží na šachovnicu tak, aby sa žiadne dve neohrozovali. Následne zločinec ukáže, ktoré z veží sa nachádzajú na políčkach, na ktoré myslí. Ak zločinec ukáže na párny1 počet veží, tak Mr. Miro vyhráva. V opačnom prípade sa veže odstránia zo šachovnice a Mr. Miro má ďalší pokus. Určte najmenší počet pokusov, po ktorých vie Mr. Miro určite vyhrať.

  1. Nula je párne číslo. ↩

V prvom rade je dobré uvedomiť si, o čo komu ide. Mr. Miro chce vyhrať, nie uhádnuť políčka, na ktoré zločinec myslí. Podarí sa mu to, ak uhádne párny počet veží. V prvom pokuse Mr. Miro tipne hocijakých 8 políčok. Môže tak trafiť:

  1. párny počet veží – \(0\), \(2\), \(4\), \(6\), \(8\) – vtedy vyhráva a hra končí;
  2. nepárny počet veží – \(1\), \(3\), \(5\) – pripočíta sa mu jeden pokus a pokračuje ďalej.

Všimnite si, že \(7\) veží trafiť nemôže, pretože potom má posledná veža vždy už len jedno políčko voľné, teda je jednoznačne určená.

Pozrime sa na prípady, keď nevyhrá hneď a poďme za radom.

  • Mr. Miro trafil \(1\) vežu. Mr. Miro už vie o siedmych „zlých“ políčkach, takže stačí, že jednu vežu zmení tak, aby ju neuhádol a vyhrá, pretože trafí 0. Teda využije informáciu o tom, kde sa zločincove políčka určite nenachádzajú. Problémom je, že nemôže presunúť len jednu vežu, pretože by ohrozovala inú. Stačí však, keď ohrozenú vežu posunie do riadka (resp. stĺpca), v ktorom predtým bola uhádnutá veža (viď obrázok). Tým pádom uhádne 0 veží a vyhrá. Prečo sa nesnažil uhádnuť napr. 2 veže namiesto žiadnej, je jasné – nemusí uspieť. Na druhej strane, s touto stratégiou určite vyhrá už po druhom pokuse.

  • Mr. Miro uhádne \(3\) alebo \(5\) veží. V tom prípade je postup rovnaký. Presunie jednu z uhádnutých veží na políčko, kde určite neuhádne, a tú, ktorú bude táto veža ohrozovať posunie tak, ako je spomenuté vyššie. Z nepárneho počtu uhádnutých veží sa stane párny a Mr. Miro vyhráva.

Odpoveď je teda v každom prípade: Mr. Miro určite vyhrá na druhý pokus.

Pre úplnosť riešenia treba ešte dodať, prečo Mr. Miro nevie vyhrať na menej ťahov. Prečo? No Mr. Miro nevie vyhrať na jeden ťah preto, lebo po prvom ťahu sa mu vždy môže stať, že trafí nepárny počet políčok, ako to bolo spomínané na začiatku.

  1. Nula je párne číslo.↩

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