8. Kto Má Sušičku? vzorové riešenie

Môžeme si všimnúť, že nejaké dva stavy sú ekvivalentné s daným stavom \(S\), ak sú ekvivalentné aj navzájom. Vyplýva to z toho dôvodu, že ak sú nejaké stavy \(U,V\) oba ekvivalentné so stavom \(S\), tak existuje konečná postupnosť krokov, ktoré prenášajú \(U\) na \(V\), menovite tie, ktoré prenesú \(U\) na \(S\) a následne ťahy prenášajúce \(S\) na \(V\). To je dokopy konečne veľa krokov. Tým sme toto tvrdenie ukázali. Dodáme, že hocijaký stav je ekvivalentný sám so sebou.

Teraz ak uvažujeme všetky možné stavy, tak vlastne chceme spočítať, že koľko existuje rôznych skupín navzájom ekvivalentných stavov. Predstavme si to ako vyberanie jednej skupiny po druhej: Vyberieme si zatiaľ nevybraný stav a aj všetky ekvivalentné s ním (toto celé nazveme ako jeden ťah). Skončíme, keď sme vybrali všetky stavy. Uvedomme si, že počet takýchto ťahov je práve odpoveďou na našu otázku: stavy z dvoch rôznych ťahov musia byť neekvivalentné, pretože inak by boli vybrané v rovnakom kroku. ¹

Takže ideme si určiť počet všetkých takýchto skupín/tried pre dané \(n\)-ká.

Pre nepárne \(n\) bude odpoveďou \(2\), pretože si vieme zadefinovať invariant, ktorý nám určuje dve rôzne triedy: a to je parita počtu mokrých (\(M\)) ľudí. Tieto triedy sú naozaj neprázdne, pretože stavy všetci \(M\) resp. všetci \(S\) sú v jednej resp. druhej triede. Teda treba nám ukázať bez ujmy na všeobecnosť, že ak máme nepárny počet ľudí a nepárny počet \(M\) (mokrých) ľudí, tak sa vieme dostať do stavu; hocijaké rozdelenie s nepárnym počtom mokrých ľudí. Tak poďme na to.

Skupinu vedľa seba stojacich ľudí s rovnakou suchosťou/mokrosťou nazveme sekvencia (kľudne aj veľkosti \(1\)). Ľahko si všimneme, že buď je sekvencia celá kružnica, alebo vedľa nej sa nachádzajú dve sekvencie s opačnou suchosťou/mokrosťou, (ak máme len \(2\) sekvencie, tak je len jeden sused). Teda máme buď \(1\)-nu alebo párny počet sekvencií, teda musia sa striedať. Ale dokopy je nepárny počet ľudí, teda niekde v nejakej sekvencií je párny počet ľudí. V tejto párnej sekvencii si vedia v niekoľko krokoch všetci zmeniť ich suchosť/mokrosť triviálnym spôsobom. A teraz si všimnime, že sa buď spravila jedna veľká sekvencia a kvôli invariante sme sa nutne dostali do stavu všetci mokrý, alebo sme prepojili nejaké \(2\) sekvencie toho druhého typu, čím sme zmenšili počet sekvencií o \(2\). Teda vždy si môžeme niekoľkými krokmi znížiť počet sekvencií. Teda vieme sa dostať k jednej sekvencii. Preto sú naozaj všetky začínajúce stavy s nepárnym \(M\) v rovnakej triede. Rovnako sa ukáže, že všetky stavy s nepárnym \(S\) sú v rovnakej triede. A keďže máme možnosť voľby nepárne \(M\) alebo nepárne \(S\), tak máme počet tried naozaj \(2\).

Prejdime teraz k párnym \(n\)-kám. Tu po chvíli uvažovania malých prípadov si hneď môžeme všimnúť, že tých tried môže byť kľudne viac, napríklad pre \(n=2\) máme \(3\) rôzne triedy, pre \(n=4\) až \(5\) tried. Môžeme si všimnúť, že invariant z predošlého prípadu tu funguje tiež, avšak existujú stavy, ktoré majú rovnakú hodnotu podľa tohto invariantu, ale nie sú ekvivalentné. Tiež nám nefunguje úvaha z predošlej časti, čo nám zagarantovala, že môžeme znižovať počet sekvencií (nemusí nutne existovať sekvencia párnej dĺžky).

Potrebujeme si teda nájsť nejaký jemnejší invariant, ktorý lepšie rozdeľuje prípady. Všimnime si, že vieme ofarbiť všetkých ľudí v kruhu striedavo (Párnou farbou (\(P\)) a Nepárnou farbou (\(N\))). Pri každom kroku zmení stav práve jeden z oboch frakcií, a to ešte z rovnakého stavu na ten druhý. Nasledovný invariant je nádejný: rozdiel počtu \(M\) vo frakciách \(N\) a \(P\) sa nemení. (Treba to myslieť tak, že ak na začiatku je päť mokrých vo frakcii \(N\) a traja mokrí vo frakcii \(P\), tak hodnota stavu je \(5-3=2\), a ak na začiatku sú traja mokrí vo frakcii \(N\) a päť mokrých vo frakcii \(P\), tak hodnota stavu je \(3-5=-2\).) To nám napovedá o tom, že ak \(n=2k\), tak maximálna hodnota tohto invariantu je \(k\) a minimálna \(-k\), čo zodpovedá \(2k+1=n+1\) rôznym triedam. (Všimnime si, že prípady \(n=2, 4\) nám naozaj dávali tento výsledok). Nejaký člen každej triedy sa dá ľahko skonštruovať – ak chceme rozdiel \(0\), tak dáme všetkých na \(M\); a keď má byť rozdiel \(\pm i\), tak okrem \(1\leq i\leq k\) členov tej správnej frakcie dáme všetkých ostatných na \(S\) a tých \(i\) na \(M\). Takže aspoň \(n+1\) rôznych tried už máme. Teraz treba ukázať, že tento invariant je presný, teda rovnakú hodnotu majú práve ekvivalentné stavy. Poďme si to teda ukázať.

Znova máme niekoľko sekvencií. Ak máme iba jednu, tak máme zjavne hodnotu \(0\) v invariante. Ak nie, tak máme párny počet sekvencií v striedavom poradí. Teraz ak máme sekvenciu párnej dĺžky, tak ju môžeme kľudne eliminovať. Dostávame sa teda do stavu, kde každá sekvencia je nepárnej dĺžky (alebo znova máme iba jednu sekvenciu a sme v prípade \(0\)). Teraz teda máme niekoľko nepárnych sekvencií. Tak nech sa nejaká daná sekvencia Mokrých začína s členom vo frakcii \(N\) (môžeme si to povedať bez ujmy na všeobecnosť, pretože výmenou písmeniek \(N\) a \(P\) dostaneme práve dôkaz pre ten druhý prípad). Tak táto sekvencia sa aj nutne končí s členom vo frakcii \(N\). Teda susediaca sekvencia Suchých sa začína aj skončí členom vo frakcii \(P\). Teda znova ďalšia sekvencia Mokrých sa začína a končí členom vo frakcií \(N\), atď. Vieme teda, že v každej sekvencii Mokrých je o jedna viac členov \(N\) ako \(P\). To teda znamená, že ak sme v začínajúcom stave mali hodnotu invarianty \(+i\), tak teraz máme \(i\) sekvencií Mokrých. Teraz tieto si vieme triviálne zredukovať na sekvencie dĺžky \(1\). A potom tieto jednotky si vieme o \(2\) posúvať, až kým sa nedostaneme do stavu, že všetci Mokrí ľudia stoja na políčkach \(1,3,\cdots 2i-1\). Toto vieme spraviť, pretože keď máme už iba \(i\) ľudí v stave Mokrých, tak oni nutne stoje na pozíciách \(N\) (vďaka invariantu). Tak nech je \(x\) najmenšie z políčok \(1,3,\cdots 2i-1\), kde ešte nestojí človek v stave M. Tak si zoberme človeka Mokrého stavu (na pozícii \(y\)) pri sekvencii, v ktorej je toto \(x\), a postupne si Mokrého môžeme posúvať o \(2\) (triviálne si premeníme \(2\) Suché členy vedľa nášho Mokrého \(y\) na Mokrých a potom si zmeníme \(y\) a toho prostredného na Suchých). Takto sa z každého stavu s hodnotou \(i\) vieme dostať do jedného daného stavu (opísané vyššie), to teda znamená, že náš invariant je naozaj presný. Teda pre párne \(n\) máme \(n+1\) možností.

Odpoveď. Pre nepárne \(n\) je počet tried \(2\), pre párne \(n\) je táto hodnota \(n+1\).