Matematická olympiáda – kategorie P

Řešení úloh ústředního kola (2. soutěžní den) 46. ročníku

P-III-4

 Nejprve si všimněme, že stačí zabývat se hrou se čtyřmi kamínky. Ostatní případy totiž snadno převedeme na hru se čtyřmi kamínky následující úvahou. Je-li počet kamínků ve hře k, rozšíříme hrací plán doleva o 4-k políček, na něž umístíme kamínky, které se již ve hře samozřejmě nikdy nepohnou. Například pro hru se dvěma kamínky můžeme předpokládat, že hrací plán zahrnuje i políčka -2 a -1 a tato políčka jsou od začátku obsazená.

Zavedeme nyní hodnoty m a n, které budou charakterizovat jednotlivé situace hry. Číslo m udává vzájemnou vzdálenost prvního a druhého kamínku, zatímco číslo n určuje vzdálenost třetího a čtvrtého kamínku na hracím plánu. Formálně zapsáno, označíme-li si pozice kamínků x, y, u, v (kde x < y < u < v, přičemž např. pro hru se dvěma kamínky je x=-2, y=-1), pak platí m=y-x-1, n=v-u-1.

Dokážeme následující tvrzení:

  1. Je-li m různé od n, hráč na tahu může provést takový tah, kterým dostane svého soupeře do situace m=n.
  2. Je-li m=n, hráč na tahu nemůže zabránit výhře svého soupeře.
K důkazu prvního bodu tvrzení si stačí uvědomit, že hráč na tahu může vždy provést tah délky |m-n| buď kamínkem stojícím na pozici y (pokud m > n), nebo kamínkem na pozici v (pokud m < n). Druhý bod snadno dokážeme matematickou indukcí vzhledem k součtu S=x+y+u+v. Jsme-li v koncové situaci (tj. S=6 pro hru se čtyřmi kamínky), hráč na tahu jistě prohrál. Předpokládejme, že dokazované tvrzení platí pro všechny situace se součtem menším než S, a dokážeme jeho platnost i pro situace se součtem rovným S. Jelikož platí m=n, hráč na tahu musí svým tahem porušit platnost této podmínky. Druhý hráč může odpovědět tahem podle bodu 1. a tím opět hráče postavit do situace m=n, přičemž součet pozic kamínků se snížil a podle indukčního předpokladu hráč na tahu nemůže zabránit soupeřovi ve výhře.

Z dokázaných tvrzení vyplývá, že v situaci s různými hodnotami m, n má hráč na tahu jednoduchou vítěznou strategii, zatímco v situaci m=n nemůže vyhrát, pokud soupeř neudělá chybu. Napsat program hrající hru je pak již velmi snadné.

P-III-5

Situaci si můžeme reprezentovat grafem, jehož vrcholy jsou rozděleny do dvou disjunktních množin. V množině A budou vrcholy odpovídající pořadovým číslům dveří (tzn. číslům určujícím pořadí, v jakém mají být dveře otevřeny) a v množině B vrcholy odpovídající jednotlivým dveřím. Vrchol v z množiny A spojíme hranou s vrcholem u z množiny B v případě, že podle podmínek konkrétního zadání mohou být dveře u otevřeny jako v-té v pořadí. Jiné hrany v grafu nejsou. Párováním v grafu nazýváme takovou podmnožinu hran, že žádné dvě z nich nemají společný vrchol. Párování M pokrývá vrchol grafu w, pokud nějaká hrana z M vychází z vrcholu w. Naší úlohou tedy je nalézt párování, které bude pokrývat všechny vrcholy z množiny A. Jelikož množiny vrcholů A a B jsou stejně velké a hrany vedou pouze z A do B, bude takové párování pokrývat také všechny vrcholy množiny B.

Stupeň vrcholu v z množiny A může být 0, 1, 2 (pokud se k němu vztahuje nějaká podmínka) nebo n (pokud se na v žádná podmínka nevztahuje). Má-li některý vrchol stupeň 0, žádné řešení úlohy neexistuje. Pokud existuje v A vrchol v, z něhož vede jediná hrana (do vrcholu u), pak každé řešení úlohy musí obsahovat hranu vu. Odstraníme-li tedy z grafu vrcholy v, u a všechny hrany z nich vycházející, bude mít takto upravený graf stejný počet řešení jako graf původní (pokud definujeme, že graf s 0 vrcholy má jedno řešení). Takto můžeme postupně odstranit všechny vrcholy stupně 1 z množiny A, přičemž musíme dát pozor na to, že odstraněním jednoho takového vrcholu mohou vzniknout další.

Stačí tedy nadále uvažovat případ, že n > 1 a každý vrchol množiny A má stupeň alespoň 2. Nechť A' je podmnožina množiny A obsahující pouze vrcholy stupně 2 a nechť G' je podgraf původního grafu G s vrcholy z množin A' a B a se všemi hranami grafu G, které vedou z A' do B. Existuje-li párování pokrývající všechny vrcholy množiny A', pak existuje také párování pokrývající všechny prvky množiny A, neboť na vrcholy z množiny A \ A' se nevztahuje žádná podmínka a proto je můžeme libovolně spárovat se zbývajícími vrcholy z množiny B. Zároveň platí, že je-li množina A \ A' větší než jednoprvková, úloha má více řešení. Pokud je počet prvků v A \ A' 0 nebo 1, pak má úloha tolik řešení, kolik existuje párování v G' pokrývajících množinu A'.

Zbývá tedy již jen vyřešit problém, kolik existuje v grafu G' párování pokrývajících množinu A'. Je-li množina A' prázdná, existuje jediné párování požadovaných vlastností, v opačném případě naopak nemůže existovat jediné takové párování. Nechť existuje nějaké párování pokrývající množinu A'. Vytvoříme cestu obsahující střídavě hrany obsažené v párování a hrany, které v párování nejsou. Začneme v nějakém vrcholu v0 z B pokrytém párováním a z tohoto vrcholu budeme pokračovat po hraně obsažené v párování do vrcholu v1 z A'. Odtud můžeme pokračovat jedině po druhé hraně vedoucí z v1 do nějakého vrcholu v2 v B. Odtud znovu po hraně z párování, atd. Skončíme ve chvíli, když přijdeme do vrcholu v z množiny B, který má stupeň 1, nebo když se vrátíme do některého vrcholu, v němž jsme již byli. V prvním případě je možné vytvořit nové párování tak, že hrany ležící na cestě, které v původním párování nebyly, do párování zařadíme, a naopak odstraníme z něj ty hrany na cestě, které původně v párování byly. Ve druhém případě část cesty tvoří kružnici a na této kružnici také můžeme vyměnit hrany stejným způsobem a získat tak nové párování. Pokud tedy existuje aspoň jedno párování pokrývající množinu A', pak existují jistě aspoň dvě.

V případě neprázdné množiny A' stačí tudíž zjistit, zda vůbec nějaké pokrývající párování existuje. Jestliže v B existuje vrchol u, který je spojen hranou pouze s jediným vrcholem v z A', pak platí: existuje-li párování pokrývající A', musí existovat také párování pokrývající A' a obsahující hranu vu. Důvod je zřejmý - stačí vzít libovolné párování pokrývající A', odstranit z něj hranu obsahující v a přidat do něj hranu vu. Můžeme tedy odstranit z grafu vrcholy v a u a všechny hrany z nich vedoucí a dále postupně odstraňovat další vrcholy množiny B spojené s jediným vrcholem množiny A' (opět nám odstraněním jednoho mohou vzniknout další takové vrcholy).

Nechť A" je množina vrcholů obsahující ty vrcholy z A', které nebyly z grafu odstraněny výše popsaným procesem. Nechť B" je podmnožina množiny B obsahující vrcholy, které jsou spojeny hranou s nějakým vrcholem z A". Protože jsme již odstranili vrcholy spojené s jediným vrcholem z A', každý vrchol z B" je spojen s aspoň dvěma vrcholy z A". Současně platí, že každý vrchol z A" je spojen s právě dvěma vrcholy z B". Počet hran vedoucích z A" do B" musí být stejný jako počet hran vedoucích z B" do A". Proto je nutně |A"| >= |B"|. Pokud |A"| > |B"|, jistě neexistuje párování pokrývající množinu A". Pokud |A"| = |B"|, pak každý vrchol množiny B" má stupeň 2. Nechť G" je podgraf grafu G' s vrcholy z A" a B" a se všemi hranami grafu G', které vedou z A" do B". Všechny komponenty souvislosti grafu G" jsou tedy kružnice, v nichž se střídají vrcholy z A" a B". Párování v tomto grafu vytvoříme jednoduše tak, že na každé takovéto kružnici střídavě vždy jednu hranu zařadíme do párování a druhou ne.

Na základě provedených úvah je již snadné napsat program, který řeší úlohu v čase O(n). Ke každému vrcholu si budeme pamatovat seznam hran, které z něj vycházejí. Vrcholů, na něž se nevztahuje žádná podmínka, může být až O(n), přičemž z každého vychází n hran. Již jenom vytvoření takovéto struktury by vyžadovalo čas O(n2). U těchto vrcholů si proto nebudeme pamatovat seznam hran, ale pouze jejich počet. Každá hrana je zaznamenána ve dvou seznamech (pro oba své koncové vrcholy). Pokud oba tyto výskyty propojíme, budeme moci v čase O(1) vynechat hranu z obou seznamů. Potom již jenom sledujeme jednotlivé podmínky uvedené v předcházejících úvahách a když je třeba, odstraňujeme vrcholy stupně 1 (udržujeme si zásobník nalezených a dosud nezpracovaných vrcholů stupně 1). Z grafu můžeme odstranit nejvýše O(n) hran, každou v čase O(1), takže celý algoritmus má lineární časovou složitost.