8. Kompetitívna Majestátna Súťaž vzorové riešenie

Keď si bežný riešiteľ (alebo opravovateľ) prečíta zadanie typu „všetky dvojice hrali proti sebe práve raz“, mali by mu hneď napadnúť turnajové grafy (tournament graph¹). Keby sme nemali takýto čudný bodovací systém, už by sme boli dosť šťastní. Keby sme vyhodnocovali zápasy na konci turnaja (tak, že každá výhra dáva toľko bodov, koľkokrát sme prehrali), vtedy by sme mohli body počítať celkom ľahko, iba vynásobením počtu výhier a prehier pre dané družstvo. To by sme hneď mali pozorovanie, že každé družstvo buď vyhralo \(k\) hier a prehralo \(2n-1-k\) zápasov, alebo prehralo \(k\) a vyhralo \(2n-1-k\). Ale tu sa skóre určuje úplne iným spôsobom, táto úvaha nám nepomohla.

Ľahké začínajúce pozorovania

Poďme sa teraz pozrieť, čo je toto za bodovací systém. Môžeme sa napríklad spýtať, či družstvá silné v normálnom živote (napr. Bayern Mníchov v Lige Majstrov v ročníku 2019/2020) sú silné aj v tomto bodovacom systéme: Prídeme na to, že ono to tak vôbec nie je, pretože samé výhry znamenajú 0 bodov. Taktiež si môžeme všimnúť, že aj keď dva tímy vyhrali rovnako veľa zápasov, ak tím \(A\) vyhral prvých \(k\) zápasov, tak ten má \(0\) bodov, a \(B\), ktorý vyhral posledných \(k\), má \(k(2n-1-k)\) bodov. Takže počet výhier nám o skóre nehovorí nič.

Ešte predtým, než sa začneme zaoberať nejakými ozajstnými turnajmi, poďme si tipnúť, čo by sme vlastne chceli dokázať. Keby sme chceli ukázať pre nejaké \(n\), že to nejde, tak by sme mali nájsť nejaký hrozne silný invariant, ktorý sa nám popasuje s hrozne veľa možnosťami. Treba si všimnúť, že nevieme nič o tom, kto kedy hral. Nemôžeme voľne predpokladať, že každý tím má odohratých v istom čase zhruba rovnako veľa zápasov, a dokonca zápasy sú asymetrické v zmysle, že nejaký tím môže výhrou získať oveľa viac bodov ako ten druhý. Teda ukázať niečo také, že niečo sa nedá, vyzerá byť skoro nemožné.

Na druhú stranu v prípade kladnej odpovede máme ľahšiu prácu, treba nájsť jeden rozpis zápasov, kde všetci majú rovnaké skóre. A vyššie sme videli, že máme relatívne veľké množstvo volieb. Tak pokúsme sa o nájdenie vhodnej konštrukcie v malých prípadoch a možno uvidíme niečo, čo by mohlo fungovať aj pre väčšie čísla.

Základná konštrukcia

Najprv sa pozrime, ako sa dobre počíta skóre pre daný tím a ako sa z tohto počítania dá pripraviť vhodný rozpis zápasov. Tak daný tím odohral \(2n-1\) zápasov, niektoré vyhral, niektoré nie. Môžeme ich chronologicky po sebe napísať, ako postupnosť výhier (\(W\) – win) a prehier (\(L\) – loss). Napríklad, ak niekto vyhral prvé \(2\) zápasy, potom prehral a vyhral a znovu prehral, tak postupnosť tímu je \(WWLWL\). Tu sa skóre počíta celkom jednoducho: treba spočítať pre všetky \(W\), koľko je pred nimi \(L\). Každý tím má teda nejakú takúto postupnosť a chceme tieto postupnosti napísať do tabuľky tak, aby sme po riadkoch s vynechaním prázdnych políčok dostali postupnosť daného tímu. Tiež chceme, aby každý stĺpec reprezentoval jeden zápas. Teda v každom stĺpci by sme mali mať práve jedno \(W\) a jedno \(L\) a ináč prázdne políčka. Toto bude nejaký úplný rozpis turnaja. Môžeme si rozmyslieť, že tabuľka by mala mať \(2n\) riadkov a \(\binom{2n}{2}\) stĺpcov.

Tak poďme na to pre \(n=2\) (\(4\) tímy). Aby niekto mal nenulové skóre, musí mať aj prehru, aj výhru a všetci musia hrať \(3\) zápasy. Tak po chvíľke hrania si uvedomíme, že maximum dosiahnuteľných bodov je \(2\) a dá sa dosiahnuť postupnosťami \(LLW\) a \(LWW\). Hneď si ale vieme povedať, že takýto turnaj sa nám nájsť určite nepodarí, pretože všetci musia začať prehrou, teda chronologicky prvý zápas nemal kto vyhrať. Zostáva iba prípad, keď všetci získajú práve 1 bod. Toto je možné iba postupnosťami \(WLW\) a \(LWL\) (ľahko si vieme rozmyslieť, že tieto postupnosti sú dobré, \(WWW\) a \(LLL\) dávajú \(0\), \(LLW\) a \(LWW\) sme pozerali, dávajú \(2\) body, \(WLL\) a \(WWL\) dávajú tiež \(0\) bodov a dokopy je \(8\) rôznych postupností). Takže aby sme mali rovnaký počet výhier a prehier, \(2\) tímy mali postupnosť \(WLW\) a \(2\) tímy \(LWL\). To sa dá spraviť napríklad takto:

\[\begin{bmatrix} W & L & & & W &\\ L & & W & & & L\\ & W & & L & & W\\ & & L & W & L & \end{bmatrix}\]

Takže pre \(n=2\) to ide.

Rekurentný krok

Z tejto konštrukcie by sme si mohli zobrať so sebou nejaké nápady. Napríklad ten so striedajúcimi postupnosťami vyzerá dosť dobre. Chceme ukázať, že naše dve striedavé postupnosti dĺžky \(2n-1\) (\(WLW\dots LW\) a \(LWL\dots WL\)) majú vždy rovnakú hodnotu. A ono to platí triviálne, pretože \(W\) na začiatku postupnosti pripočíta \(0\) bodov a \(L\) na konci tiež, a keď tie zmažeme z oboch postupností, dostávame tú istú postupnosť (\(LWLW\dots LW\)) dĺžky \(2n-2\). Ak už máme konštrukciu pre \(n\), ľahko spravíme konštrukciu pre \(n+1\). Treba iba spraviť niečo nasledovného typu: na začiatku turnaja prídu \(2\) tímy, rýchlo zahrajú všetky svoje zápasy a potom odídu. Potom zvyšných \(2n\) tímov hrá už len medzi sebou ako v turnaji pre \(n\). Treba dať pozor na to, aby sa pre nikoho nepokazilo striedanie výhier a prehier, ale ide to dosť priamočiaro.

Chceme pridať \(2\) tímy (budeme ich nazývať \(A\) a \(B\) a staré tímy si pomenujme \(1,\,2,\,\dots,\,2n\)) tak, aby sme konštrukciu pre \(n\) nijak nepokazili. Asi najjednoduchší spôsob je, že na začiatok turnaja si dáme všetky zápasy \(A\) s očíslovanými tímami. Chceme to spraviť tak, aby postupnosť tímu \(A\) bola striedavá, aby aj oni nahrali toľko bodov, ako ostatní. Takže nech hrá \(A\) s tímami v poradí \(1,\,2,\,\dots,\,2n\) tak, aby jeho postupnosť začínala s \(W\) (teda tím \(A\) porazil práve tímy s nepárnym číslom). Po týchto \(2n\) zápasoch si tím \(B\) zahrá \(2n\) zápasov proti očíslovaným tímom tak, že prehrá práve proti tímom s nepárnym číslom. Potom si ešte zahrajú medzi sebou zápas \(A\) a \(B\) tak, že vyhrá \(A\). Teraz nám zostávajú iba zápasy medzi tímami s číslami. Chceme to zorganizovať tak, aby všetky postupnosti boli striedavé, teda aby tento menší turnaj začínali prehrou tímy s nepárnym číslom. Môžeme si všimnúť, že v prípade \(2\) tímov a rovnako tu pre \(n+1\) tímov, vďaka rozpisu prvých \(4n+1\) zápasov platí, že ak zoradíme tímy v poradí \((A,1,\dots, 2n,B)\), tak prvé hry tímov končili \(W,L,W,\dots L\), takže ak z konštrukcie pre \(n\) vymeníme všetky \(W\) na \(L\) a naopak, dostaneme taký podrozpis turnaja pre \(n+1\), čo po spojení s prvými \(4n+1\) zápasmi dáva pre všetky tímy vhodnú striedavú postupnosť. Pre ilustráciu pre \(n=3\) viď rozpis.

\[\begin{bmatrix} W & L & W & L & & & & & W & & & & & & \\ L & & & & W & & & & & \color{red} L & \color{red} W & & & \color{red} L & \\ & W & & & & L & & & & \color{red} W & & \color{red} L & & & \color{red} W\\ & & L & & & & W & & & & \color{red} L & & \color{red} W & & \color{red} L\\ & & & W & & & & L & & & & \color{red} W & \color{red} L & \color{red} W & \\ & & & & L & W & L & W & L & & & & & & \end{bmatrix}\]

Týmto sme si ukázali jednoduchú metódu na rekurentnú výrobu správneho rozpisu (správnosť sme si ukázali tým, že sme si ukázali, že striedavou postupnosťou všetky tímy získajú rovnaký počet bodov) pre všetky \(n\geq 2\). Odpoveďou teda je, že taký turnaj sa mohol odohrať pre všetky \(n\geq 2\).