Matematická olympiáda – kategorie P

Zadání úloh oblastního kola 48. ročníku

Na vyřešení úloh oblastního kola MO kategorie P máte čtyři hodiny čistého času. Řešení každého příkladu musí obsahovat (není-li uvedeno v textu zadání něco jiného):

• popis řešení, tzn. popis použitého algoritmu, argumenty, které zdůvodňují správnost vašeho řešení, diskusi o efektivitě zvoleného algoritmu (jeho časové a paměťové nároky). Popis řešení musí být jasný a srozumitelný, aniž by bylo třeba nahlédnout do samotného programu.
• program: v úlohách P-II-1, P-II-2 a P-II-3 je třeba uvést dostatečně podrobný zápis algoritmu (nejlépe zdrojový text nejdůležitějších částí programu v jazyku Pascal nebo C). Ze zápisu můžete vynechat jednoduché technické operace, jako jsou vstupy, výstupy, implementace jednoduchých matematických vztahů apod. V úloze P-II-4 uveďte místo programu schéma navrženého algoritmu.

Hodnotí se nejen správnost programu, ale také kvalita popisu řešení a efektivita zvoleného algoritmu.

P-II-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ž smluvených N^2 políček je z tabulky vyříznutých. 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řitom 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 pohybu hodinových ručiček. Zašifrovaná zpráva se získá přečtením tabulky po řádcích. Aby byla daná mřížka použitelná pro šifrování, každá pozice v tabulce musí být odkryta popsaným způsobem právě jednou.

Tuto základní metodu šifrování můžeme použít i vícenásobně tak, že zašifrovaný text opakovaně zašifrujeme pomocí téže mřížky. V tomto případě si tedy uživatelé šifry musí zvolit nejen mřížku, ale také číslo k, které určuje počet opakování šifrovacího procesu. Pro některá čísla k se nám však může stát, že když zašifrujeme danou mřížkou libovolný text k-krát, dostaneme vždy původní text. Vaším úkolem je nalézt algoritmus, který pro zadanou šifrovací mřížku najde nejmenší k > 0 této vlastnosti.

Vstupem vašeho algoritmu bude číslo N a matice 2N x 2N obsahující nuly a jedničky, přičemž jedničky označují vyříznuté čtverečky a nuly nevyříznuté. Můžete předpokládat, že mřížka zadaná na vstupu je správná (tj. je použitelná pro šifrování). Pro tuto mřížku váš algoritmus nalezne nejmenší kladné číslo k takové, že z každého textu po k-násobném zašifrování dostaneme původní text.

Příklad

Uvažujme jednoduchou mřížku:

0	1
0	0

Správná odpověď zní k=3. Jestliže vezmeme například řetězec abcd, po prvním zašifrování dostaneme dacb, po druhém bdca a po třetím zašifrování opět původní abcd (abychom dokázali, že k=3, bylo by třeba ukázat, že pro každý vstupní řetězec dostaneme po třech opakováních původní řetězec).

P-II-2 Tajemný kryptogram

Popisovaný šifrovací systém vychází z reálného systému používaného během 1. světové války. Je dána tabulka č. 1, která má 6 řádků a 6 sloupců. V jednotlivých políčkách tabulky jsou zapsána písmena a číslice:

Tabulka č. 1
	A	D	F	V	M	X
A	Z	3	E	N	V	A
D	Y	C	X	J	P	Q
F	D	H	2	O	0	7
V	W	R	K	F	T	1
M	I	S	U	M	4	G
X	6	8	9	5	B	L

Z šifrovaného textu nejprve vytvoříme mezitext tak, že každý znak vstupního řetězce nahradíme dvojicí označující řádek a sloupec, kde se znak v tabulce nachází (například B nahradíme dvojicí XM). Mezitext potom zapíšeme po řádcích do druhé (tzv. permutační) tabulky. V záhlaví sloupců permutační tabulky se nacházejí navzájem různá písmena. Abecední pořadí těchto písmen potom určuje pořadí, v němž vypíšeme sloupce tabulky do zašifrovaného textu.

Jestliže například v záhlaví permutační tabulky máme postupně písmena V, Y, H, R, A a J a chceme zašifrovat text KRYPTOGRAFIE, dostaneme:

V	Y	H	R	A	J
V	F	V	D	D	A
D	M	V	M	F	V
M	X	V	D	A	X
V	V	M	A	A	F

Výsledný zašifrovaný text bude DFAAVVVMAVXFDMDAVDMVFMXV.

Byl nalezen dlouhý zašifrovaný text, přičemž je známa použitá šifrovací tabulka č. 1, není však známo záhlaví permutační tabulky. Dále byl nalezen dlouhý seznam obvykle používaných záhlaví permutační tabulky. Jednou z možností, jak zašifrovaný text rozšifrovat, je vyzkoušet postupně všechna obvykle používaná záhlaví a zjistit, pro která z nich dostaneme smysluplný text. Problém však spočívá v tom, že záhlaví je příliš mnoho, a proto je třeba některá z nich vyloučit pomocí počítače.

Soutěžní úloha

Napište algoritmus, který dostane na vstupu zašifrovaný text délky m a seznam k používaných záhlaví permutační tabulky (všechna záhlaví mají stejnou délku n, přičemž m je násobkem n). Algoritmus pro každé záhlaví zjistí a vypíše, zda je potenciálně smysluplné nebo ne. Šifrovací tabulka č. 1 je pevně dána a je součástí algoritmu.

Záhlaví označujeme jako potenciálně smysluplné, jestliže v textu, který dostaneme rozšifrováním pomocí tohoto záhlaví, počet dvojic po sobě následujících písmen typu souhláska-samohláska a samohláska-souhláska je aspoň trojnásobkem počtu dvojic typu samohláska-samohláska nebo souhláska-souhláska. Číslice se nepovažují za písmena. Například slovo LEPIDLO5 obsahuje pět dvojic první skupiny a jen jednu dvojici z druhé skupiny.

Pokuste se, aby váš algoritmus fungoval co nejrychleji za předpokladu, že počet záhlaví k je velmi velký (může být až 3 milióny) a délka zašifrovaného textu m je velká v porovnání s délkou jednotlivých záhlaví n (n je řádově 10, m řádově několik tisíc). Proveďte diskusi časové a paměťové složitosti vzhledem k parametrům m, n, k.

P-II-3 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 zápalek, na druhé je b zápalek (a,b > 0).

V jednom tahu může hráč odebrat z některé z těchto hromádek právě 2^k nebo 3^k zápalek, kde k je libovolné nezáporné celé číslo (na této hromádce zůstává nezáporný počet zápalek). Hráči se střídají v tazích. Prohrává hráč, který je na tahu, ale nemůže tah učinit.

Popište všechny dvojice čísel a,b, pro které existuje vítězná strategie pro hráče, který táhne jako první. Své tvrzení dokažte.

P-II-4 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.

Soutěžní úloha

Uvažujte zápis celých nezáporných čísel podle příkladu 3. Napište schéma algoritmu, který pro dvě přirozená čísla a,b (b > 0) určí hodnotu celočíselného podílu a div b. Čísla jsou na začátku činnosti algoritmu oddělena dvojtečkou. Zdůvodněte jeho správnost.

Příklad

A(11111:111)=111
A(1111:11)=1111
A(11111:1111)=11
Algoritmus není přípustný například pro slovo 1111:1.