Matematická olympiáda – kategorie P

Zadání úloh ústředního kola (1. soutěžní den) 48. ročníku

Řešení programátorské úlohy P-III-1 musí obsahovat popis použitého algoritmu, zdůvodnění jeho správnosti, diskusi o efektivitě zvoleného řešení (tzn. posouzení časových a paměťových nároků programu) a program zapsaný v jazyce Pascal nebo C. V úloze P-III-3 místo programu uveďte schéma navrženého algoritmu.

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

Jednou z metod šifrování zpráv je použití šifrovací mřížky. Šifrovací mřížka je čtverec rozdělený na 2N x 2N čtvercových políček, přičemž N² zvolených políček je vyříznuto. Při šifrování mřížku položíme na čtvercovou tabulku stejných rozměrů (2N x 2N políček) a do každého výřezu zapíšeme jeden znak zprávy. Postupujeme při tom po řádcích shora dolů a v každém řádku zleva doprava. Tento postup ještě třikrát zopakujeme s mřížkou otočenou o 90^o, 180^o a 270^o ve směru hodinových ručiček. Zašifrovaná zpráva se získá přečtením zaplněné tabulky po řádcích. Aby bylo možné používat danou mřížku k šifrování, každé políčko v tabulce musí být odkryto popsaným způsobem právě jednou.

Máme dány dvě šifrovací mřížky stejné velikosti 2N x 2N. Tyto mřížky budeme používat na šifrování znakových řetězců délky 4N², přičemž jednotlivé znaky řetězců jsou ze speciální abecedy tvořené K znaky. Někdy se stane, že po zašifrování řetězce jednou z mřížek dostaneme původní řetězec. V tom případě použijeme k šifrování druhou mřížku. Otázkou zůstává, kolik existuje takových řetězců, které nelze změnit zašifrováním pomocí ani jedné z daných mřížek.

Navrhněte algoritmus, který dostane na vstupu čísla N, K a dvě šifrovací mřížky velikosti 2N x 2N. Pro tato vstupní data algoritmus určí počet různých řetězců délky 4N², které jsou tvořeny pouze znaky z K-prvkové abecedy a které po zašifrování první mřížkou i po zašifrování druhou mřížkou zůstanou nezměněné.

Příklad

Vstup: N=2, K=2

1	1	0	0
1	1	0	0
0	0	0	0
0	0	0	0

1	1	0	0
1	0	1	0
0	0	0	0
0	0	0	0

Výstup: 16
(Pro abecedu obsahující písmena a a b je příkladem takového řetězce abababbbbbbbbbbb.)

P-III-2 Hra se zápalkami

Dva hráči hrají následující hru: Na začátku hry jsou dány dvě hromádky zápalek -- na první hromádce je a a na druhé b zápalek (a, b > 0). Dále jsou dána dvě celá kladná čísla p, q (p < q). V jednom tahu musí hráč odebrat z jedné z těchto hromádek buď p nebo q zápalek (tak, aby na hromádce zůstal nezáporný počet zápalek). Hráči se postupně střídají ve svých tazích. Prohrává hráč, který je na tahu, ale nemůže žádný tah provést (tzn. když je na každé z hromádek méně než p zápalek).

Určete, pro které čtveřice hodnot a, b, p, q existuje vítězná strategie pro hráče, který táhne jako první. Své tvrzení dokažte.

P-III-3 Markovovy algoritmy

1. Sestrojte schéma Markovova algoritmu nad abecedou T={1}, který pro kladné celé číslo zapsané ve stejném tvaru jako v př. 3 studijního textu spočítá dolní celou část jeho dvojkového logaritmu. Výsledek bude zapsán rovněž ve stejném tvaru. Pro vstupní hodnotu nula není algoritmus přípustný.

   Poznámka: Dvojkový logaritmus kladného čísla x (v matematice zapisujeme jako log₂x) je roven takovému číslu y, pro které platí 2^y=x. Dolní celá část dvojkového logaritmu kladného celého čísla x (zapisujeme jako [log₂ x]) je rovna největšímu celému číslu y takovému, že 2^y <= x. Platí tedy [log₂ 1]=0, [log₂ 2]=1, [log₂ 3]=1, [log₂ 4]=2, [log₂ 5]=2 atd.

   Příklady výpočtu

   Vstup	Výsledek
   1	algoritmus není přípustný
   11	1
   111	11
   1111	11
   11111	111
   111111	111

2. Sestrojte schéma Markovova algoritmu nad abecedou T={0,1}, který je přípustný právě tehdy, je-li na vstupu binární zápis nezáporného celého čísla dělitelného třemi.

   Poznámka: Binárním zápisem celého čísla rozumíme zápis tohoto čísla ve dvojkové soustavě, tzn. pomocí cifer 0 a 1. Binární zápis kladného celého čísla začíná vždy cifrou 1, vedoucí nuly se nepřipouštějí. Binární zápis nuly je tvořen jediným symbolem 0.

   Příklady výpočtu

   	Výsledek	Zdůvodnění
   0	algoritmus je přípustný	číslo 0 je dělitelné 3
   1	algoritmus není přípustný	číslo 1 není dělitelné 3
   10	algoritmus není přípustný	číslo 2 není dělitelné 3
   11	algoritmus je přípustný	číslo 3 je dělitelné 3
   1100	algoritmus je přípustný	číslo 12 je dělitelné 3
   1101	algoritmus není přípustný	číslo 13 není dělitelné 3
   01100	algoritmus není přípustný	vedoucí nula není v zápisu čísla povolena

Studijní text k úloze P-III-3 - Markovovy algoritmy

Konečnou množinu symbolů T={a₀,a₁,..., a_n} nazveme abecedou. Prvky množiny T budeme nazývat znaky abecedy. Slovem P v abecedě T nazveme každou konečnou posloupnost znaků abecedy T. Prázdné slovo budeme označovat symbolem _. Algoritmem v abecedě T budeme rozumět funkci, jejíž definičním oborem je podmnožina slov v abecedě T a oborem hodnot je opět podmnožina slov v T. Nechť P je slovo v abecedě T. Řekneme, že algoritmus A je přípustný pro slovo P, právě když P je prvkem jeho definičního oboru. Většinu algoritmů je možno rozdělit na nějaké jednodušší kroky. Jeden ze způsobů navrhl v roce 1954 A. A. Markov. Základní operací je substituce jednoho slova za jiné. Výrazy P-> Q a P->^. Q, kde P a Q jsou slova v abecedě T, nazýváme formulemi substituce v abecedě T. Přitom předpokládáme, že šipka (->) a tečka (^.) nejsou prvky T. Některé ze slov P a Q může být i prázdné. Formuli P-> Q nazýváme obyčejnou a formuli P->^. Q nazýváme koncovou. Zápisem P->(^.)Q rozumíme buď formuli P-> Q, nebo P->^. Q. Konečný seznam formulí substituce v abecedě T
P₁ -> (^.)Q₁
P₂ -> (^.)Q₂
...
P_r -> (^.)Q_r
nazýváme schéma algoritmu A.

Řekneme, že slovo W je obsaženo ve slově Q, právě když existují taková slova U, V (mohou být i prázdná), že Q=UWV. Algoritmus A pracuje následujícím způsobem. Nechť je dáno slovo P v abecedě T. Ve schématu algoritmu A najdeme první formuli P_m ->(^.)Q_m (1 <= m <= r) takovou, že P_m je obsaženo v P. Provedeme substituci nejlevějšího výskytu slova P_m na Q_m. Označme R₁ slovo, které je výsledkem této substituce. Můžeme napsat A: P|-R₁. Je-li P_m ->^. Q_m koncová formule substituce, činnost algoritmu A končí, jeho hodnotou je slovo R₁ a píšeme A(P)=R₁. Je-li P_m -> Q_m obyčejná formule substituce, aplikujeme na R₁ stejný postup, který jsme použili na slovo P. Tímto způsobem pokračujeme dále. Dostaneme posloupnost slov P,R₁,...,R_i (i >= 1). Můžeme psát
A: P |- R₁,...,|- R_i
nebo též zkráceně
A: P |-> R_i
Jestliže v určitém okamžiku nastane situace, že ani jedno ze slov P₁,...,P_r není obsaženo v R_i, potom činnost algoritmu rovněž končí a R_i je hodnotou algoritmu A. Může se ovšem stát, že popsaný postup nikdy nekončí. V takovém případě řekneme, že algoritmus není přípustný pro slovo P.

Příklad 1

Nechť T={b,c}. Uvažujme schéma:
b -> ^. _
c -> c
normálního algoritmu A pro slovo P v abecedě T.

Výsledek činnosti algoritmu A je pro P následující:

• Je-li P prázdné slovo, je hodnota algoritmu rovněž prázdné slovo (A(_)= _).
• Obsahuje-li P aspoň jeden znak b, potom hodnotou algoritmu je slovo, které vznikne z P vynecháním nejlevějšího výskytu znaku b v P (např. A(cbcb)=ccb).
• Algoritmus není přípustný pro slova neobsahující znaky b.

Příklad 2

Nechť T={a₀,a₁,...,a_n}. Uvažujme schéma
a₀ -> _
a₁ -> _
...
a_n -> _
Takové schéma zapisujeme zkráceně ve tvaru:
x->_ (x prvkem T)
Při tomto zkráceném zápisu schématu předpokládáme, že odpovídající prvky seznamu mohou být zapsány v libovolném pořadí. Výsledkem algoritmu A je vždy prázdné slovo. Říkáme též, že A přepisuje libovolné slovo (v abecedě T) na prázdné slovo. Činnost tohoto algoritmu můžeme zapsat například ve tvaru A:a₁a₃a₀ |- a₁a₃ |- a₃ |- _ nebo A:a₁a₃a₀ |-> _, takže A(a₁a₃a₀)=_.

Příklad 3

Nechť T={1}. Definujme induktivně [0]=1 a [n+1]=[n]1, tj. [1]=11, [2]=111 atd. Slova [n] nazveme čísla.

Uvažujme schéma
_ ->^. 1
Pro libovolné slovo P v T platí zřejmě A(P)=1P, což můžeme zapsat ve tvaru A([n])=[n+1] pro libovolné přirozené číslo n. (Uvědomte si, že každé slovo P začíná prázdným slovem _, tj. P=_ P).

Abecedu B nazveme rozšířením abecedy T, je-li T podmnožinou B. V řadě případů je nutno při konstrukci schématu algoritmu v abecedě T použít mimo znaků abecedy T ještě další pomocné znaky. Pak řekneme, že jsme vytvořili schéma algoritmů nad abecedou T (tj. v nějaké abecedě B, která je rozšířením T).

Příklad 4

Nechť T={a₀,a₁,...,a_n} je abeceda. Pro každé slovo P=a_j0a_j1...a_jk v T (k >= 0, a_ji je prvkem T, i=0,1,...,n) je slovo P^-1=a_jk...a_j1a_j0 obrácením slova P. Sestrojte normální algoritmus A, který pro libovolné slovo P vytvoří jeho obrácení, tj. A(P)=P^-1.

Uvažujme zkrácené schéma algoritmu v abecedě B=TU{b₁,b₂}:
(a) b₁b₁->b₂
(b) b₂x->xb₂ (x prvkem T)
(c) b₂b₁->b₂
(d) b₂->^. _
(e) b₁yx->x b₁ y (x,y prvky T)
(f) _->b₁

• Na základě formule (f) dostaneme A:P |- b₁ P.
• Potom je aplikována v potřebném počtu opakování formule (e): A: P |- a_j1b₁ a_j0a_j2... a_jk |- a_j1a_j2b₁ a_j0 a_j3...a_jk |-> a_j1a_j2 ... a_jkb₁ a_j0.
• S opakováním předchozích dvou kroků postupně dostaneme
  A: P |-> a_j2a_j3... a_jkb₁ a_j1 b₁ a_j0 |-> b₁ a_jk b₁ a_j(k-1)...b₁ a_j1b₁ a_j0 |- |- b₁b₁ a_jk b₁ a_j(k-1)...b₁ a_j1 b₁ a_j0
  
• S pomocí (a) dále dostaneme A: P |-> b₂ a_jk b₁ a_j(k-1)...b₁ a_j1 b₁ a_j0, pomocí (b) a (c) a s posledním použitím (d) dostaneme A(P)=P^-1.

Tím jsme popsali činnost normálního algoritmu A nad abecedou T obracející slovo v abecedě T.