Matematická olympiáda – kategorie P

Řešení úloh oblastního kola 48. ročníku

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

Při šifrování libovolného textu pomocí šifrovací mřížky se pouze mění pořadí jednotlivých písmen v textu. Pro danou mřížku velikosti 2N x 2N a pro i z {1,2,...,(2N)²} označme symbolem f(i) číslo pozice, na kterou se dostane i-tý znak vstupního textu po zašifrování. Například pro mřížku uvedenou v zadání se text abcd zašifruje na dacb, takže f(1)=2 (neboť první písmeno a se dostalo na druhé místo), f(2)=4, f(3)=3 a f(4)=1. Zobrazení f je vlastně permutací prvků {1,2,...,(2N)²}.

Dále označme f^j(i) číslo pozice, na níž se dostane i-tý znak vstupního textu po j-násobném zašifrování. V našem příkladě po dvou zašifrováních dostáváme text bdca, tedy například f²(1)=4. Je zřejmé, že f^j můžeme definovat také rekurzívně: f⁰(i)=i a f^j+1(i)=f(f^j(i)).

Je zřejmé, že najdeme-li takové j, že f^j(i)=i pro každé i=1,2,..., (2N)², po j-násobném zašifrování textu danou mřížkou vždy dostaneme původní text. Důležité je uvědomit si, že pokud naopak existuje i takové, že f^j(i)\ne i, pak existuje nezašifrovaný text, který se po j-násobném zašifrování změní - stačí zvolit nějaký text, v němž jsou na pozicích i a f(i) různá písmena. Z uvedené úvahy vyplývá, že hledané číslo k bude nejmenší takové kladné číslo, že pro všechna i platí f^k(i)=i. Toto číslo nazýváme řádem permutace f.

Nyní musíme zjistit, jak lze určit řád permutace. Zvolíme si nějaké i a budeme pozorovat, na která políčka se dostane i-tý znak původního textu, když ho budeme opakovaně šifrovat danou mřížkou, tj. zkoumáme posloupnost f⁰(i), f¹(i), f²(i), f³(i), ... Jelikož všechny hodnoty v této posloupnosti jsou z rozsahu {1,2,... , (2N)²}, musí existovat čísla a, b taková, že a < b a f^a(i)=f^b(i). Zvolme a a b s touto vlastností tak, aby b bylo nejmenší možné.

Sporem snadno dokážeme, že a=0. V opačném případě by totiž platilo, že f(f^a-1(i))=f(f^b-1(i)). Současně ale f^a-1(i) <> f^b-1(i) (neboť b je nejmenší takové, že f^a(i)=f^b(i)). Zobrazení f by tedy pro dva různé vstupy (f^a-1(i) a f^b-1(i)) nabývalo stejné hodnoty, což nemůže nastat (dvě různá písmena se nemohou zapsat do téhož políčka).

Dokázali jsme tedy, že a=0. Co to ale znamená? i-té písmeno se při opakovaném šifrování nejprve dostane na navzájem různé pozice f¹(i), ..., f^b-1(i) a po b opakováních se vrátí zpět na pozici i. Celý tento cyklus délky b se bude stále opakovat, tzn. písmeno i se bude nacházet na místě i po 0, b, 2b, 3b, ... opakováních šifrování.

Vezměme nyní některou jinou pozici z cyklu: l=f^j(i). Vidíme, že f^u(l)=f^u(f^j(i))=f^u+j(i), tedy l bude procházet přes stejné pozice jako i, jenom v jiném pořadí. Lehce ověříme, že l-tý znak se dostane na svoje původní místo právě tehdy, když je počet opakování násobkem čísla b. Množina pozic {1,..., (2N)²} se nám tedy rozpadá na disjunktní cykly, přičemž prvky nacházející se v jednom cyklu si při každém opakování šifrování navzájem cyklicky vyměňují pozice.

Představme si, že pro každé i známe hodnotu b_i, která určuje, po kolika opakováních šifrování se i znovu dostane na svoje místo. Platí, že f^j(i)=i právě tehdy, když j je násobkem čísla b_i. My hledáme nejmenší k takové, že pro všechna i bude platit f^k(i)=i. Hledané číslo k bude proto nejmenším společným násobkem čísel b_i pro i prvkem {1,..., (2N)²}. Jelikož pro prvky, které patří do jednoho cyklu, je hodnota b_i stejná, stačí do nejmenšího společného násobku zahrnout po jednom b_i z každého cyklu.

Algoritmus bude pracovat následovně: Nejprve simulací šifrovacího procesu zjistíme hodnoty f(i) (v programu jsou uloženy v poli |perm|). Toto je možné provést v čase O(N²). Potom pro jedno i z každého cyklu určíme hodnotu b_i (v programu proměnná |delka|) a z těchto hodnot přímo spočítáme nejmenší společný násobek. Nejmenší společný násobek dvou čísel x,y zjišťujeme vydělením jejich součinu jejich největším společným dělitelem spočteným pomocí Eukleidova algoritmu v čase O(min(x,y)). Jelikož y postupně prochází přes všechny délky cyklů b_i a jejich součet je O(N²) (každý prvek patří do jednoho cyklu), je celkový čas strávený výpočty největších společných dělitelů taktéž O(N²). Zbývá popsat, jak určíme hodnoty b_i pro jednotlivá i: jednoduše budeme procházet po prvcích cyklu i, f(i), f²(i), ... , dokud nenajdeme f^j(i)=i. V tuto chvíli známe b_i=j. Přitom si budeme v poli zaznamenávat, přes které prvky jsme v cyklu prošli. Hodnotu b_i počítáme jen pro taková i, pro která ještě nemáme zaznamenáno, že již byla v některém cyklu navštívena. Tím si zajistíme, že při výpočtu všech potřebných hodnot b_i procházíme každým cyklem právě jednou - pokud později přijdeme k jinému prvku již zpracovaného cyklu, neprocházíme tímto cyklem znovu. Časová složitost této části programu je omezena součtem délek cyklů na O(N²). Celý program tedy má dohromady časovou i paměťovou složitost O(N²).

program P_II_1; const max=80; {maximální rozměr mřížky} var mrizka,mrizka2:array [1..max,1..max] of boolean; {pole s mřížkou: true - výřez, false - papír} a:array [1..max,1..max] of integer; {kam se zapíše které písmeno ze vstupu} perm:array [1..max*max] of integer; {kam přejde které písmeno ze vstupu} byl:array [1..max*max] of boolean; {zda jsme uz prošli cyklus obsahující dané číslo} n:integer; {rozměr mřížky} k:longint; {výsledek} procedure nacti; {do pole mrizka načte šifrovací mřížku a do proměnné n počet jejích řádků resp. sloupců} var t:text; i,j,pom:integer; begin assign(t,'p_ii_1.in'); reset(t); readln(t,n); n:=n*2; for i:=1 to n do for j:=1 to n do begin read(t,pom); mrizka[i,j] := (pom<>0); end; close(t); end; procedure otoc; {pomocí pomocného pole mrizka2 otočí pole mrizka o 90 stupňů ve směru hodinových ručiček} var i,j:integer; begin mrizka2:=mrizka; for i:=1 to n do for j:=1 to n do mrizka[i,j]:=mrizka2[j,n-i+1]; end; procedure vytvor_permutaci; var i,j,otoceni,cislo:integer; begin {nejprve zaplníme pole a čísly 1..n*n - v a[i,j] bude číslo l právě tehdy, když l-tý znak vstupního řetězce se při šifrování zapíše na pozici a[i,j]} cislo:=1; {které číslo budeme zapisovat} 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 {našli jsme otvor} a[i,j]:=cislo; cislo:=cislo+1; end; otoc; {otočení mřížky o 90 stupňů} end; {nyní vložíme do pole perm[i] dané číslo j právě tehdy, když ve výsledném textu bude i-té písmeno původního textu na j-tém místě} cislo:=1; for i:=1 to n do for j:=1 to n do begin perm[a[i,j]]:=cislo; cislo:=cislo+1; end end; function nsn(a,b:longint):longint; {vypočítá nejmenší společný násobek čísel a,b} var c,aa,bb:longint; begin {nejprve NSD pomocí Eukleidova algoritmu} aa:=a; bb:=b; while bb>0 do begin c:= aa mod bb; aa:=bb; bb:=c; end; {aa je nyní NSD čísel a,b} nsn:=(a div aa)*b; end; procedure spocitej_rad; {výpočet řádu permutace - výsledného čísla k} var i,j,delka:integer; begin for i:=1 to n*n do byl[i]:=false; k:=1; for i:=1 to n*n do begin if not byl[i] then begin {projdeme cyklus obsahující i a zjistíme jeho délku} j:=i; delka:=0; while not byl[j] do begin byl[j]:=true; j:=perm[j]; delka:=delka+1; end; {while} {k je nsn všech délek cyklů} k:=nsn(k,delka); end; {if} end; {for i} end; begin nacti; vytvor_permutaci; spocitej_rad; writeln('Po ',k,' šifrováních dostaneme vždy původní slovo.'); end.

P-II-2 Tajemný kryptogram

Nejprve trochu terminologie: nezašifrovaný text budeme nazývat zprávou (skládá se ze znaků), zatímco text zašifrovaný kryptogramem (složeným ze symbolů). Zadaný kryptogram délky m můžeme rozložit na n sloupců o d=m/n symbolech, j-tý symbol v i-tém sloupci označíme t_ij posloupnost symbolů t_ij pro pevné j nazveme j-tým řádkem kryptogramu. Klíč K_i (1 <= i <= n) ovlivňuje pouze pořadí, v jakém se sloupce zapisují, takže pro všechny klíče se řádky skládají z těchže symbolů, pouze v jiném pořadí, které popíšeme permutací k_i (k_i=j <- sloupec přijatý jako j-tý v pořadí má být zapsán do tabulky jako i-tý). Dále nechť d(x,y) je znak vzniklý dekódováním dvojice po sobě jdoucích symbolů x,y.

Přiřadíme-li každé dvojici znaků a,b váhu w(a,b) tak, že všechny dvojice souhláska-samohláska a samohláska-souhláska dostanou váhu 1, dvojice souhláska-souhláska a samohláska-samohláska váhu -3 a ostatní dvojice váhu 0, pak jsou potenciálně smysluplné právě ty klíče, které dají zprávy, v nichž je celková váha všech dvojic sousedních znaků nezáporná. Jinými slovy, pro dekódovanou zprávu a_i musí vyjít W = w(a₁,a₂)+...+w(a_m/2-1,a_m/2) >= 0.

Uvažme nejprve jednodušší případ, kdy n je sudé. Tehdy každý řádek kryptogramu po zpětném přeházení podle klíče odpovídá celému počtu znaků, takže vyjde:
W= SUMA_{1 <= j <= d, 1<= i <= n-3, i liché} ( d(t_k(i)j,t_k(i+1)j)+ d(t_k(i+2)j,t_k(i+3)j) )+ SUMA_{1 <= j <= d-1} ( d(t_k(n-1)j,t_k(n)j)+ d(t_k(1)j+1,t_k(2)j+1) )
My si ovšem můžeme předpočítat hodnoty vah za všechny dvojice znaků vzniklé z každé čtveřice sloupců a analogické hodnoty pro "posunuté" dvojice na rozhraní řádků:
C_ijkl=SUMA_{1 <= z <= d} w(d(t_iz,t_jz),d(t_kz,t_lz))
C^*_ijkl=SUMA_{1 <= z <= d-1} w(d(t_iz,t_jz),d(t_k,z+1,t_l,z+1))
(to zvládneme v čase O(n⁴d)) a z těchto hodnot pak snadno v čase O(n) získáme W:
W=C^*_{k(n-1),k(n),k(1),k(2)}+ SUMA_{1 <= i <= n-3, i liché} C_{k(i),k(i+1),k(i+2),k(i+3)}
Pro liché n se navíc musíme umět vyrovnat s tím, že rozhraní mezi lichými a sudými řádky kryptogramu půlí nikoliv dvojici, nýbrž dokonce znak, zatímco zbylá rozhraní jsou v půli dvojice. Proto musíme zpracovávat zvlášť sudé a liché řádky a dva různé typy přechodů přes okraj. Předpočítáme si proto obecnější hodnoty C^pq_ijkl odpovídající celkové váze dvojic vzniklých ze čtveřice sloupců i,j,k,l na sudých (p=0) resp. lichých (p=1) řádcích s posunutím přes okraj daným počtem symbolů q přesahujících do dalšího řádku (q=0 pro vnitřní dvojice, q=2 odpovídá C^* pro sudé n, q=1 a q=3 jsou přechody s půlenými znaky pro liché n). Tyto hodnoty spočteme opět v čase O(n⁴d) dle vztahu:
C^pq_ijkl= SUMA_{1 <= z <= d, z má stejnou paritu jako p} w(d(T^0q_izT^1q_jz, d(T^2q_kzT^3q_lz), kde T^aq_ij=t_ij pro a < 4 - q, =t_i,j+1 pro a >= 4 - q
Z těchto hodnot v čase O(n) spočteme W pro libovolný klíč K, a sice jak pro sudé, tak pro liché n.

Výsledná časová složitost algoritmu tedy je O(n⁴d+kn)= O(n³m+kn), paměťová O(n⁴+m).

Program pracuje přesně podle tohoto algoritmu, pouze si do tabulky doplní "poposlední" řádek zaplněný neplatnými znaky, aby se vyhnul ošetřování přesahů z posledního řádku.

P-II-3 Hra se zápalkami

Všimněme si, že hráč může odebrat v jednom tahu 1, 2, 3 nebo 4 zápalky, ale nikdy nemůže odebrat 5k zápalek (kde k je libovolné přirozené číslo) - žádné z čísel 2^k ani 3^k totiž není násobkem pěti. Dokážeme, že vítězná strategie existuje pro začínajícího hráče právě tehdy, když číslo a-b není dělitelné pěti. Tvrzení dokážeme matematickou indukcí podle celkového počtu zápalek zbývajících na hromádkách, tzn. podle hodnoty a+b:

Pro a+b=0 (tj. a=b=0) začínající hráč nemůže provést žádný tah a prohrál, tedy tvrzení platí.

Předpokládejme, že tvrzení platí pro libovolná celá nezáporná čísla a, b taková, že a+b < s, kde s je dané přirozené číslo. Nechť nyní a, b jsou libovolná celá nezáporná čísla taková, že a+b=s.

Je-li číslo a-b dělitelné pěti, bez újmy na obecnosti předpokládejme, že první hráč odebral z první hromádky x zápalek. Protože podle úvodní úvahy není číslo x dělitelné číslem 5, není ani číslo (a-x)-b dělitelné pěti. Protože ale (a-x)+b=a+b-x < s, podle indukčního předpokladu ve vzniklé pozici existuje vítězná strategie pro hráče, který je právě na tahu, tím je však druhý hráč. Vidíme tedy, že neexistuje vítězná strategie pro začínajícího hráče, což jsme měli dokázat.
Není-li číslo a-b dělitelné pěti, předpokládejme, že a > b (případ a < b se řeší analogicky záměnou a, b). Označme x zbytek po dělení čísla a-b číslem 5 (zřejmě 1 <= x <= 4). Číslo (a-x)-b je jistě dělitelné pěti a také a-x >= b >= 0. Odebere-li začínající hráč z první hromádky x zápalek, což může podle úvodní úvahy, vznikne pozice, ve které podle indukčního předpokladu existuje vítězná strategie pro hráče, který právě není na tahu. Tím je však hráč, který zahajoval hru. Existuje tedy vítězná strategie pro začínajícího hráče, což jsme měli dokázat.

P-II-4 Markovovy algoritmy

Algoritmus celočíselného dělení dvou celých nezáporných čísel zapsaných v unární soustavě je založen na postupném odčítání dělitele od dělence. Nejprve zkontrolujeme, zda zadaná vstupní data (dvojice čísel) nepředstavují dělení nulou -- v takovém případě nebude algoritmus pro tato data přípustný a uměle docílíme zacyklení výpočtu. V opačném případě odebereme ze zápisu každého z čísel jeden znak 1, aby počet jedniček v zápisu čísla odpovídal hodnotě tohoto čísla. Následuje vlastní odčítání: z dělence postupně odebereme tolik znaků 1, kolik jich je obsaženo v děliteli, poté (pokud se nám to podaří) si do výsledku připíšeme jednu čárku. To opakujeme tak dlouho, dokud se celý dělenec nezruší. Pak už stačí jen smazat dělitele a počet čárek zapsaných do výsledku určuje hodnotu hledaného celočíselného podílu. Stačí už jen přepsat zaznamenané čárky na znaky 1 a jeden znak 1 ještě připojit, aby byl zápis výsledku v požadovaném tvaru v unární číselné soustavě.

Popsaný postup realizuje následující schéma Markovova algoritmu. Schéma používá pomocné symboly z abecedy {a,b,c,d,e,f,g}.
(1) 1:11 -> b1
(2) : -> :
(3) 1b1 -> bc
(4) c1 -> 1c
(5) bc -> dce
(6) ec -> ce
(7) e -> fa
(8) cf -> f1
(9) df -> b
(10) b1 -> g
(11) g1 -> g
(12) gc -> g
(13) ga -> 1g
(14) g -> 1
V úvodní formuli (1) se zjišťuje, zda se nejedná o dělení nulou. Pokud ne, provede se zároveň odstranění "nadbytečných" znaků 1 z dělence i dělitele a oddělovací dvojtečka se změní na znak b (aby se tato formule nemohla při výpočtu uplatnit vícekrát). Pokud vstupní data představovala dělení nulou, formule (1) se neuplatní a výpočet přejde na formuli (2), která zajistí zacyklení výpočtu pro takto nepřípustná data.

Formule (3) a (4) zajišťují jedno odečtení dělitele od dělence. Pomocí (3) se postupně z dělence odstraňují jednotlivé znaky 1 a za každý z nich je jeden znak 1 z dělitele dočasně přeznačen na symbol c (jako příznak, že už byl použit). Souběžně s tím je pomocí (4) zajištěno přesouvání 1 před c v rámci dělitele. Postupně prováděné odčítání skončí buď tím, že dojdou jedničky v děliteli nebo tím, že dojdou jedničky v dělenci (případně v obou zároveň).

Jestliže se podařilo odečíst od dělence celého dělitele, uplatní se formule (5) a následně se zrealizuje celý blok výpočtu pomocí (5)-(9). Ten slouží k připsání jedničky do výsledného podílu. Podíl je vytvářen ve zpracovávaném slově na konci, ve slově bezprostředně následuje za dělitelem. Aby se snadno odlišil, je zatím vytvářen pomocí symbolů a. Ve formuli (5) je oddělovací znak b dočasně změněn na d (aby se tato formule neuplatnila opakovaně) a zároveň je "vyslán" symbol e, aby pomocí (6) přešel na konec dělitele. Tam formule (7) připíše do výsledku jeden symbol a, zároveň přitom změní e na f. Symbol f postupuje pomocí (8) zpět doleva a cestou přeznačuje znaky c v děliteli opět na 1, aby byl dělitel připraven na další kolo odčítání. Po průchodu celým dělitelem je f zrušen a přitom se oddělovač d změní zpátky na b. Slovo je tak připraveno k zahájení dalšího odčítání pomocí (3).

Pokud jsme při odčítání neodečetli celého dělitele a v dělenci již "došly" jedničky, proces odčítání představovaný formulemi (3)-(4) se zastaví a (5) se neuplatní. Výpočet tedy přejde na "ukončovací" blok formulí (10)-(14). V něm je nejprve oddělovací symbol b, který nyní stojí na začátku slova, změněn na g. Ten pak postupně smaže celého dělitele, který může být v dané chvíli tvořen zčásti symboly 1 a zčásti symboly c (11)-(12). Dále pomocí formule (13) přeměníme znaky a ve výsledném podílu na 1 a nakonec pomocí (14) ještě jednu poslední jedničku do podílu připíšeme a g zrušíme.

Časová složitost: Uvažujme podíl m:n. Bloky Markovova algoritmu (1)-(2) a (10)-(14) se provádějí pouze jednou. Formule (3) se vykoná celkem m-krát, pro každý její výpočet se (4) provede (n-1)-krát. Formule (5) se provádí (m/n)-krát, po každém jejím provedení následuje zhruba 2n kroků (6)-(9). Časově nejnáročnější je tedy opakovaně provádění (4), které určuje výslednou časovou složitost navrženého algoritmu O(mn).