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ž N2 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 90o, 180o a 270o 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 4N2, 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 4N2, 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

1100
1100
0000
0000

1100
1010
0000
0000

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 log2x) je roven takovému číslu y, pro které platí 2y=x. Dolní celá část dvojkového logaritmu kladného celého čísla x (zapisujeme jako [log2 x]) je rovna největšímu celému číslu y takovému, že 2y <= x. Platí tedy [log2 1]=0, [log2 2]=1, [log2 3]=1, [log2 4]=2, [log2 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={a0,a1,..., an} 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
P1 -> (.)Q1
P2 -> (.)Q2
...
Pr -> (.)Qr
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 Pm ->(.)Qm (1 <= m <= r) takovou, že Pm je obsaženo v P. Provedeme substituci nejlevějšího výskytu slova Pm na Qm. Označme R1 slovo, které je výsledkem této substituce. Můžeme napsat A: P|-R1. Je-li Pm ->. Qm koncová formule substituce, činnost algoritmu A končí, jeho hodnotou je slovo R1 a píšeme A(P)=R1. Je-li Pm -> Qm obyčejná formule substituce, aplikujeme na R1 stejný postup, který jsme použili na slovo P. Tímto způsobem pokračujeme dále. Dostaneme posloupnost slov P,R1,...,Ri (i >= 1). Můžeme psát
A: P |- R1,...,|- Ri
nebo též zkráceně
A: P |-> Ri
Jestliže v určitém okamžiku nastane situace, že ani jedno ze slov P1,...,Pr není obsaženo v Ri, potom činnost algoritmu rovněž končí a Ri 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í:

Příklad 2

Nechť T={a0,a1,...,an}. Uvažujme schéma
a0 -> _
a1 -> _
...
an -> _
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:a1a3a0 |- a1a3 |- a3 |- _ nebo A:a1a3a0 |-> _, takže A(a1a3a0)=_.

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={a0,a1,...,an} je abeceda. Pro každé slovo P=aj0aj1...ajk v T (k >= 0, aji je prvkem T, i=0,1,...,n) je slovo P-1=ajk...aj1aj0 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{b1,b2}:
(a) b1b1->b2
(b) b2x->xb2 (x prvkem T)
(c) b2b1->b2
(d) b2->. _
(e) b1yx->x b1 y (x,y prvky T)
(f) _->b1

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