10. Kúzlo Mága Šuma vzorové riešenie

K tejto úlohe máme videonávod.

Najskôr si ujasníme, čo od nás vlastne chce zadanie a zavedieme si pár pojmov na jednoduchší popis. Počiatočná konfigurácia kariet je určená tým, aké číslo je na každej karte. Spolu máme \(2021\) možností pre každú z \(k\) kariet, teda \(2021^k\) konfigurácií. Biely Šum uvidí karty po tom, čo Bizón nechal otočenú len jednu z nich. Takúto situáciu budeme volať náhľad \((a, x)\), keď jediná viditeľná karta je na pozícii \(a\) a má číslo \(x\). Šum si v takejto situácii musí byť istý, aké číslo má nejaká iná karta. Ak by si bol istý viacerými inými kartami, môže si dopredu vrámci stratégie určiť pre každý náhľad len jednu takúto kartu, ktorú víťazoslávne otočí. Takže Šum sa riadi pravidlami \((a, x) \rightarrow (b, y)\), čo znamená, že pri náhľade \((a, x)\) otočí kartu na pozícii \(b\) a tá má číslo \(y\). Z vyššie uvedeného vyplýva, že pre každý náhľad máme len jedno pravidlo. Súbor všetkých týchto pravidiel budeme volať stratégia. Stratégia je úspešná, keď pre každú konfiguráciu dokáže Bizón pripraviť taký náhľad, aby Šumovo pravidlo fungovalo, to znamená, že každá konfigurácia obsahuje dvojicu kariet \((a, x), (b, y)\) takú, že \((a, x) \rightarrow (b, y)\) je pravidlo z našej stratégie.

Rozdeľme si konfigurácie do skupín podľa toho, ktoré pravidlo v každej z nich môžeme použiť. Pre každý náhľad máme jedno pravidlo a počet možných náhľadov je \(2021k\), takže najviac \(2021k\) pravidiel, a teda aj toľko skupín. Koľko je konfigurácií v jednej skupine, ktorá je daná pravidlom \((a, x)\rightarrow(b, y)\)? Na pozícii \(a\) musí byť číslo \(x\) a na pozícii \(b\) číslo \(y\). Na ostatných \(k-2\) pozíciách môže byť ľubovoľné číslo, čo dáva \(2021^{k-2}\) možností. Vo všetkých skupinách spolu máme najviac \(2021k \cdot 2021^{k-2}\) konfigurácií, ale aby bola stratégia úspešná, každá konfigurácia musí byť v niektorej skupine, takže \[\begin{aligned} 2021k \cdot 2021^{k-2} &\geq 2021^k, \qquad (1) \\ k &\geq 2021.\end{aligned}\]

Dostali sme, že \(k \geq 2021\), takže pre menšie \(k\) nemôže existovať úspešná stratégia. Po chvíľke skúšania a hrania sa objavíme, že pre \(k \geq 2022\) existuje pekná jednoduchá stratégia. Bizón si len pozrie číslo \(2022.\) karty, ktoré bude chcieť prezradiť Šumovi. Následne ho zakóduje pomocou prvých \(2021\) kariet, a to tak, že nechá otočenú toľkú kartu, aké číslo je na \(2022.\) karte. V reči pravidiel nám stačia pravidlá \((a, *) \rightarrow (2022, a)\), pre každú pozíciu \(a\), pričom \(*\) môže byť hocijaké číslo. Šum uhádne, že na \(2022.\) karte je číslo \(a\).

Prípad \(k=2021\) vyzerá ťažšie. V dokázanej nerovnosti \((1)\) by musela nastať rovnosť. V takomto prípade sa oplatí uvažovať aké podmienky a obmedzenia by musela spĺňať naša stratégia, aby mohla nastať rovnosť. Pri takomto postupe buď zistíme, že všetky obmedzenia sa nedajú splniť a prídeme k sporu, alebo nám obmedzenia povedia ako bude vyzerať výsledná stratégia.

Rovnosť v \((1)\) nastane len vtedy, keď každá konfigurácia bude v niektorej skupine, a keď sme každú konfiguráciu započítali len raz, teda každá konfigurácia musí byť v práve jednej skupine. Ešte raz to isté v zelenom, žiadna konfigurácia nie je v dvoch skupinách, teda na žiadnu konfiguráciu sa nedajú použiť dve pravidlá.

V prvom rade si uvedomme, že v pravidle \((a, x) \rightarrow (b, y)\) sú pozície \(a, b\) rôzne, lebo Šum nemôže otočiť kartu, ktorá už je otočená. Urobíme zopár pozorovaní.

1. Nemôžeme mať dve pravidlá \((a, x)\rightarrow(b, y)\) a \((c, z)\rightarrow(d, w)\), kde všetky pozície \(a, b, c, d\) sú navzájom rôzne. Ak by sme mali, tak existuje konfigurácia, ktorá obsahuje na všetkých štyroch pozíciách príslušné karty \((a, x), (b, y), (c, z), (d, w)\) a spĺňa obe pravidlá.

2. Nemôžeme mať pravidlá \((a, x)\rightarrow(b, y)\) a \((b, y)\rightarrow(c, z)\), kde pozície \(a, c\) sú rôzne. V opačnom prípade máme konfiguráciu s kartami \((a, x), (b, y), (c, z)\) spĺňajúcu obe pravidlá.

3. Nemôžeme mať pravidlá \((a, x)\rightarrow(c, z)\) a \((b, y)\rightarrow(c, z)\), kde pozície \(a, b\) sú rôzne. Zdôvodnenie je rovnaké ako v predchádzajúcom bode.

4. Nemôžeme mať pravidlá \((a, x)\rightarrow(b, y)\) a \((b, y)\rightarrow(a, x)\). Znovu existuje konfigurácia, ktorá spĺňa obe pravidlá.

Aby nastala v \((1)\) rovnosť, pre každý možný vstup \((a, x)\) musíme mať nejaké pravidlo. BUNV ¹ predpokladajme, že pre vstup \((1, 1)\) máme pravidlo \(P=(1, 1) \rightarrow (2, 1)\). Podľa \(a)\) musí pravidlo pre každý vstup \((a, *), a\geq3\) ukazovať na pozíciu \(1\) alebo \(2\), aby sme nemali \(4\) rôzne pozície. Povedzme nech to je pre vstup \((3, 1)\) pozícia \(1\), máme pravidlo \(Q=(3, 1) \rightarrow (1, *)\). Teraz pre ľubovoľný vstup \((a, *), a \geq 4\) musí mať výstup pozíciu \(1\) alebo \(2\) kvôli \(P\) a zároveň pozíciu \(1\) alebo \(3\) kvôli \(Q\), takže jedine pozíciu \(1\).

Pozrime sa, ktoré pravidlá môžu mať výstup \((1, x)\) pre každé \(x\) od \(1\) do \(2021\). Podľa \(c)\) musia mať všetky takéto pravidlá rovnakú pozíciu na vstupe. Povieme, že táto pozícia na vstupe zaberá číslo \(x\) na výstupe. Uvažujeme pozície na vstupe od \(4\) do \(2021\), ktorých je \(2018\), aby pozícia na výstupe bola určite \(1\). Niektorá pozícia \(p\) zaberá najviac \(1\) výstup \((1, y)\), lebo pozícií je \(2018\) a výstupov najviac \(2021\). To znamená, že pre každý vstup \((p, *)\) máme pravidlo \((p, *) \rightarrow (1, y)\).

Nech pre vstup \((1, y)\) máme pravidlo \((1, y) \rightarrow (b, z)\). Podľa \(b)\) platí \(b=p\). Teraz máme dve pravidlá \[\begin{aligned} (1, y) \rightarrow (p, z), \\ (p, z) \rightarrow (1, y),\end{aligned}\] čo je spor s \(d)\). Takže pre \(k=2021\) neexistuje úspešná stratégia. Najmenšie vyhovujúce \(k\) je \(2022\).