Matematická olympiáda – kategorie P

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

P-III-1 Šifrovací mřížka

Úlohu přetransformujeme na jednoduchou úlohu z teorie grafů. Vytvoříme graf G, jehož vrcholy budou čísla 1,2,...,4N² a mezi vrcholy i a j povede hrana právě tehdy, pokud se písmeno, které bylo v původním textu na pozici i, přemístí po zašifrování jednou nebo druhou mřížkou na pozici j, nebo naopak, pokud se písmeno z původní pozice j může dostat zašifrováním pomocí některé z mřížek na pozici i.

Označme nyní symbolem P počet komponent souvislosti grafu G. Dokážeme, že počet řetězců, které se po zašifrování oběma mřížkami nezmění, je K^P (K je počet znaků abecedy).

Mějme libovolný text t, který se po zašifrování jednou i druhou mřížkou nezmění. Označme t_i znak, který je v textu t na i-té pozici. Nejprve si uvědomme, že jsou-li vrcholy i a j v grafu G spojeny hranou, potom platí t_i=t_j. To vyplývá z konstrukce grafu G - jestliže písmeno t_i přejde po zašifrování jednou nebo druhou mřížkou na pozici j, musí být stejné jako písmeno, které bylo na pozici j v původním textu t (jinak by se text změnil). Podobně můžeme postupovat v případě, že naopak t_j se šifrováním dostane na pozici i.

Rozšířením této úvahy zjistíme, že pro libovolné dva vrcholy i a j nacházející se v téže komponentě souvislosti platí, že t_i=t_j. Jsou-li totiž i a j v téže komponentě, spojuje je nějaká cesta. Každé dva po sobě jdoucí vrcholy na této cestě jsou spojeny hranou, a proto na jim odpovídajících pozicích v t musí být stejné znaky. Využitím tranzitivity rovnosti (jestliže t_a=t_b a t_b=t_c, pak také t_a=t_c) dostaneme z těchto rovností i rovnost pro koncové vrcholy cesty (t_i=t_j).

Dokázali jsme tedy, že pokud se t nezmění zašifrováním pomocí ani jedné z mřížek, na všech pozicích z jedné komponenty souvislosti jsou stejná písmena. Nyní dokážeme, že pokud naopak na všech pozicích z jedné komponenty souvislosti jsou stejná písmena, pak text t bude mít po zašifrování jednou i druhou mřížkou na pozicích z této komponenty původní hodnoty. Mějme tedy vrchol i z naší komponenty. Na pozici i však po zašifrování libovolnou z mřížek vždy přejdou pouze znaky z pozic spojených s i hranou a ty jsou v téže komponentě a mají tedy stejnou hodnotu.

Vidíme, že t se nezmění zašifrováním právě tehdy, když jsou v každé komponentě souvislosti na všech pozicích stejné znaky. Každá z komponent může mít přiřazen jeden z K znaků, přičemž znaky můžeme komponentám přiřazovat nezávisle, celkový počet možností je proto K^P.

Algoritmus řešení úlohy je tedy jednoduchý. Na základě mřížek (simulací šifrování) sestavíme graf G a pomocí prohledávání do šířky nebo do hloubky zjistíme počet jeho komponent souvislosti P. Potom stačí umocnit K na P. Graf G má 4N² vrcholů, přičemž každý jeho vrchol má stupeň nejvýše 4. Celkový počet hran v grafu je tedy nejvýše 8N². Časová složitost prohledávání grafu a také celková složitost algoritmu je proto O(N²). Paměťová složitost je také O(N²).

program P_III_1; const max=50; {maximalni rozmer mrizky} type pole=array [1..max,1..max] of boolean; var mrizka,pom:pole; {pole s mrizkou: true - vyrez, false - papir} hrany:array [1..max*max,1..4] of integer; {hrany grafu} byl:array [1..max*max] of boolean; {zda jsme jiz prohledli dany vrchol} n,k:integer; {rozmer mrizky, pocet pismen abecedy} vys:longint; {vysledek} i,j:integer; procedure nacti_mrizku; {do pole "mrizka" nacte mrizku ze vstupu} var i,j,pom:integer; begin for i:=1 to n do for j:=1 to n do begin read(pom); if pom=0 then mrizka[i,j]:=false else mrizka[i,j]:=true; end; end; procedure otoc; {pomoci pomocneho pole "pom" otoci pole "mrizka" o 90 stupnu ve smeru hodinovych rucicek} var i,j:integer; begin for i:=1 to n do for j:=1 to n do pom[i,j]:=false; for i:=1 to n do for j:=1 to n do if mrizka[i,j] then pom[j,n-i+1]:=true; mrizka:=pom; end; procedure vytvor_hranu(z,k:integer); {do pole "hrany[z]" prida cislo "k" na prvni nulove (volne) misto} var i:integer; begin i:=1; while hrany[z,i] <> 0 do i:=i+1; hrany[z,i]:=k; end; procedure pridej_hrany; var i,j,otoceni,pozice,kam:integer; begin {postupne simulujeme sifrovani - pro kazdou pozici ve vstupnim textu zjistime, kam se zapise, a pridame odpovidajici hranu do grafu} pozice:=1; {pozice ve vstupnim textu} for otoceni:=1 to 4 do begin for i:=1 to n do for j:=1 to n do if mrizka[i,j] then begin {nasli jsme otvor} kam:=(i-1)*n+j; {kam se zapise znak na aktualni pozici} vytvor_hranu(pozice,kam); {pridame hranu} vytvor_hranu(kam,pozice); pozice:=pozice+1; end; otoc; {otoceni mrizky o 90 stupnu} end; end; procedure prohledej(vrchol:integer); {prohledavani grafu do hloubky, v poli "byl" znaci navstivene vrcholy} var i:integer; begin if not byl[vrchol] then begin byl[vrchol]:=true; for i:=1 to 4 do prohledej(hrany[vrchol,i]); end; end; function urci_vysledek:longint; {pocita pocet komponent a urci celkovy vysledek} var i:integer; v:longint; begin v:=1; {vysledek pro nula komponent} for i:=1 to n*n do byl[i]:=false; for i:=1 to n*n do if not byl[i] then begin {dosud nenavstiveny vrchol - prohledame jeho komponentu a vysledek vynasobime cislem "k"} prohledej(i); v:=v*k; end; urci_vysledek:=v; {"v" je nyni rovno "k" na pocet komponent} end; begin readln(n,k); n:=n*2; {n je delka strany} for i:=1 to n*n do {nulovani hran} for j:=1 to 4 do hrany[i,j]:=0; {zpracovani prvni mrizky:} nacti_mrizku; pridej_hrany; {zpracovani druhe mrizky:} nacti_mrizku; pridej_hrany; {vypocet vysledku:} vys:=urci_vysledek; writeln('Pocet textu, ktere se nezmeni, je ',vys,'.'); end.

P-III-2 Hra se zápalkami

Pozici hry, kdy na první hromádce zbývá x a na druhé y zápalek, budeme značit (x,y). Hra tedy začíná v pozici (a,b) a končí v okamžiku, kdy se poprvé dostane do stavu (x,y) pro nějaká x, y taková, že x < p a y < p.

Tahem rozumíme dvojici čísel (t,u) z množiny M={(p,0), (q,0), (0,p), (0,q)}. Vykonáme-li v pozici (x,y) tah (t,u), hra přejde do pozice (x-t,y-u). V pozici (x,y) je přípustné provést tah (t,u) právě tehdy, je-li t <= x a u<= y.

O pozici (x,y) řekneme, že je vyhraná, jestliže v ní existuje vítězná herní strategie pro hráče, který je právě na tahu. V opačném případě označujeme pozici jako prohranou.

Ve vyhrané pozici musí existovat alespoň jeden přípustný tah, který hru převede do prohrané pozice (tento tah je pak součástí vítězné herní strategie). Naopak, libovolný tah přípustný v prohrané pozici musí vést do nějaké pozice vyhrané (ať táhne soupeř jakkoliv, opět budeme mít k dispozici tah vedoucí k výhře).

Nejprve dokážeme následující větu:

Věta

Pozice (x,y) je vyhraná právě tehdy, když pozice (x₁,y₁) je vyhraná, kde x₁ a y₁ jsou zbytky po dělení čísel x,y číslem p+q.

Důkaz

Důkaz provedeme matematickou indukcí podle hodnoty x+y.

Pro x+y < p+q tvrzení zřejmě platí (x₁=x, y₁=y).

Nechť tvrzení platí pro všechna x,y taková, že x+y < s, kde s >= p+q. Nechť x,y jsou libovolná čísla taková, že x+y=s. Potom:

• Je-li pozice (x₁,y₁) vyhraná, pak nutně existuje tah (t,u) z M takový, že pozice (x₁-t,y₁-u) je prohraná (x₁-t >= 0, y₁-u >= 0). Protože ale (x-t)+(y-u) < s, podle indukčního předpokladu je také pozice (x-t,y-u) prohraná a tedy pozice (x,y) je vyhraná, neboť hráč na tahu v ní může provést vítězný tah (t,u).
• Je-li pozice (x₁,y₁) prohraná, sporem předpokládejme, že pozice (x,y) je vyhraná. Pak první hráč může svým tahem přejít k prohrané pozici. Bez újmy na obecnosti předpokládejme, že vítězný tah je odečtení čísla p od čísla x (další 3 možnosti lze prošetřit analogicky). Pak pozice (x-p,y) je prohraná. Označíme-li x₂ zbytek po dělení čísla x-p číslem p+q, podle indukčního předpokladu je pozice (x₂,y₁) prohraná. Je-li x₁ >= p, je (x₂,y₁)=(x₁-p,y₁), je-li x₁ < p, je (x₂,y₁)=(x₁+q,y₁).

V obou případech dostáváme spor, neboť zřejmě nemohou být současně prohrané pozice (x₁,y₁) a (x₁-p,y₁) ani (x₁,y₁) a (x₁+q,y₁).

Dále se budeme zabývat analýzou pozice (x,y) v případě, že x < p+q a y < p+q. Nejprve spočítáme paritu počtu tahů zbývajících do konce hry v pozici (x,0), kde 0 <= x < p+q:

• Je-li x < q, hráči pouze mohou odečítat hodnotu p a tedy provedou právě [x/p] tahů.
• Je-li x >= q, hráči mohou buď provést právě jeden tah (v případě, že odečtou číslo q), nebo provedou právě [x/p] tahů (v případě, že v prvním tahu odečtou číslo p, v dalších tazích mohou odečítat pouze číslo p a nikdy nemohou odečíst číslo q).

Tedy platí:

• Je-li [x/p] liché, hra má vždy lichý počet tahů.
• Je-li [x/p] sudé a x < q, hra má vždy sudý počet tahů.
• Je-li [x/p] sudé a x >= q, hra může mít sudý nebo lichý počet tahů, přičemž o tom rozhoduje první tah.

Nyní mějme obecnou počáteční pozici (a,b). Protože začínající hráč vyhrává hru právě tehdy, když celkový počet tahů je lichý, snadno ukážeme, že platí:

Věta

Pozice (a,b) je pro a < p+q, b < p+q prohraná právě tehdy, když nastane jedna z následujících dvou možností:

• [ a/p ], [ b/p ] jsou obě lichá čísla
• [ a/p ], [ b/p ] jsou obě sudá čísla [ a/q ] +[ b/q ] je sudé

Důkaz

Rozebereme 9 možností podle toho, jakou z podmínek A, B, C splňují čísla a, b. Nesplňuje-li žádné z čísel a, b podmínku C, výsledek nezáleží na hře hráčů a zřejmě sudý počet tahů nastane právě tehdy, když buď obě splňují A, nebo obě splňují B. Splňuje-li právě jedno z čísel a, b podmínku C, první hráč toto číslo může vhodně snížit tak, aby vyhrál, neboť počet tahů druhým číslem je pevně určen. Konečně, splňují-li obě čísla podmínku C, vyhrává druhý hráč, neboť po libovolném tahu prvního hráče může druhý hráč s nepoužitým číslem provést stejnou operaci a tím dosáhnout sudého počtu tahů. Tedy pozice (a,b) je prohraná, splňují-li čísla a, b stejnou podmínku A, B nebo C, což dává ihned dokazované tvrzení.

Z dokázaných vět přímo plyne:

Startegie

Pro libovolná a, b celá nezáporná je pozice (a,b) prohraná, právě tehdy, když nastává právě jedna z možností

• [ a₁/p], [ b₁/p] jsou obě lichá
• [ a₁/p], [ b₁/p] jsou obě sudá a [ a₁/q]+[ b₁/q] je sudé

kde a₁, b₁ jsou zbytky po dělení čísel a,b číslem p+q.

P-III-3 Markovovy algoritmy

Úloha a

1. b₀1 -> 1b₀
2. b₀ -> }
3. {11 -> 1{
4. {1 -> {
5. {} -> |}1
6. 1| -> |1
7. |} -> ^._
8. | -> {
9. 11 -> {1b₀
10. 1 -> 1
Jestliže vstupní slovo obsahuje jedinou jedničku reprezentující hodnotu nula, bude se provádět opakovaně formule 10 a dojde k zacyklení výpočtu (algoritmus je pro nulu nepřípustný).
Je-li na vstupu kladné číslo N (zapsané jako N+1 jedniček), vykoná se nejprve formule 9, kterou se na začátek slova umístí závorka { a odstraní se jedna nadbytečná jednička používaná ve zvoleném kódování čísel. Opakovaným prováděním formule 1 se pak přemístí pomocný symbol b₀ na pravý okraj slova, kde se formulí 2 přemění na závorku }. Po použití trojice pravidel 9, 1, 2 bude tedy vstupní slovo převedeno na tvar {11111111} (N jedniček v závorkách).

Následně se vždy opakováním formule 3 vydělí číslo dvěma, pomocí pravidla 4 se případně odstraní zbývající lichá jednička a použitím 5 se přičte jedna jednička do výsledku, který je vytvářen na pravém okraji slova za znakem }. Formule 6 a 8 pak zajistí obnovení situace před dalším dělením. Po dosažení nulového výsledku dělení se uplatní pravidlo 7, které smaže zbývající pomocné symboly a výpočet ukončí.

Popsaný algoritmus je založen na skutečnosti, že dolní celá část dvojkového logaritmu čísla N udává, kolikrát můžeme číslo opakovaně celočíselně vydělit dvěma, než dostaneme nulový výsledek. Formule 6 se uplatní i v případě nulového podílu a připíše jednu 1 k výsledku - ve výsledku se proto objeví vždy o jednu 1 více, než kolik je správná hodnota dvojkového logaritmu. To však přesně odpovídá zvolenému kódování čísel.

Přípravná fáze výpočtu uvedeného algoritmu (použití formulí 9, 1 a 2) se provádí pouze jednou a představuje pro vstupní hodnotu N provedení O(N) kroků výpočtu. Poté (formule 3-8) se (log₂N)-krát opakuje dělení čísla dvěma. Při prvním dělení se provede maximálně N+4 kroků ( (N/2)-krát pravidlo 3, (N/2)-krát pravidlo 6, ostatní se vykonají pouze jednou), při druhém N/2+4 kroků výpočtu, při třetím N/4+4, atd. Celková doba výpočtu navrženého Markovova algoritmu vyjádřená počtem vykonaných kroků je tedy shora omezena O(N) + N + N/2 + N/4 + N/8 + ... + 1 + 4 log₂ N. Součet geometrické řady 1/2 + 1/4 + 1/8 + ... se blíží hodnotě 1, celkem se proto vykoná O(O(N)+N+log N)=O(N) kroků výpočtu.

Úloha b

1. X01 -> X01
2. X00 -> X00
3. X0 ->^._
4. X1 -> B
5. A0 -> A
6. A1 -> B
7. B0 -> C
8. B1 -> A
9. C0 -> B
10. C1 -> C
11. A ->^._
12. B -> B
13. C -> C
14. _ -> X
Formule 14 nejprve umístí na začátek vstupního slova pomocný symbol X. Podle začátku zadaného slova se pak provede jedna z formulí 1-4. Binární zápis čísla nemůže začínat nulou a přitom obsahovat více než jednu cifru - v takovém případě se uplatní pravidlo 1 nebo 2 a dojde k zacyklení výpočtu nad nepřípustným vstupem. Obsahuje-li vstupní slovo jedinou nulu, zajistí pravidlo 3 ukončení výpočtu - algoritmus je přípustný, neboť nula je beze zbytku dělitelná třemi. Konečně začíná-li binární zápis čísla cifrou 1, je tato cifra nahrazena pomocným symbolem B a výpočet pokračuje v další části schématu.

Formule 5-10 provádějí jednoduchou analýzu zadaného řetězce, který obsahuje kladné celé číslo korektně zapsané ve dvojkové soustavě. Číslo zpracováváme zleva doprava cifru po cifře a sledujeme, jaký zbytek po dělení třemi dává číslo představované již zpracovanými dvojkovými číslicemi. Podle hodnoty tohoto zbytku měníme pomocný symbol na A, B nebo C (A pro zbytek 0, B pro zbytek 1, C pro zbytek 2). Formule 4 odebrala z dvojkového zápisu čísla vedoucí jedničku a pomocný symbol nastavila na B, neboť číslo jedna dává po dělení třemi zbytek 1.

Máme-li již přečtenu z levé strany vstupního řetězce skupinu dvojkových cifer představující nějaké číslo v, můžeme rozlišit tři případy podle zbytku po dělení čísla v třemi:

• v je beze zbytku dělitelné třemi (stav A)
  • přidáme-li k jeho dvojkovému zápisu cifru 0, dostaneme hodnotu 2v, která je rovněž dělitelná třemi (formule 5)
  • přidáme-li k jeho dvojkovému zápisu cifru 1, dostaneme hodnotu 2v+1, která dává při dělení třemi zbytek 1 (formule 6)
• v dává po dělení třemi zbytek 1, je tedy tvaru v=3k+1 (stav B)
  • přidáme-li k jeho dvojkovému zápisu cifru 0, dostaneme hodnotu 2v=6k+2, která dává při dělení třemi zbytek 2 (formule 7)
  • přidáme-li k jeho dvojkovému zápisu cifru 1, dostaneme hodnotu 2v+1=6k+3, která je beze zbytku dělitelná třemi (formule 8)
• v dává po dělení třemi zbytek 2, je tedy tvaru v=3k+2 (stav C)
  • přidáme-li k jeho dvojkovému zápisu cifru 0, dostaneme hodnotu 2v=6k+4, která dává při dělení třemi zbytek 1 (formule 9)
  • přidáme-li k jeho dvojkovému zápisu cifru 1, dostaneme hodnotu 2v+1=6k+5, která dává při dělení třemi zbytek 2 (formule 10)

Po zpracování celého vstupního slova určuje poslední pomocný symbol, jaký je výsledný zbytek po celočíselném dělení zadaného čísla třemi. Je-li výsledným symbolem A, zadané číslo bylo dělitelné třemi a formule 11 proto výpočet úspěšně ukončí. V případě symbolů B a C se jednalo o dvojkový zápis čísla, které nebylo dělitelné třemi - pomocí pravidla 12 nebo 13 se tedy zajistí zacyklení výpočtu nad nepřípustným vstupním slovem.

Celý výpočet má zjevně lineární časovou složitost vzhledem k délce zadaného vstupního slova, pro přípustné vstupní hodnoty je počet vykonaných kroků přímo úměrný počtu číslic zkoumaného čísla.