Druhá písemná zkouška MB204 5.6.2013
1. Mějme kongruenci 963 -x = 2766 (mod 1716). Pomocí kritéria, udávajícího řešitelnost (a počet řešení) lineární kongruence, určete počet řešení této kongruence a pak kongruenci vyřešte.
Řešení. 963 = 32.107, 2766 = 2.3.461, 1716 = 22.3.11.13 (963,1716) = 3|2766. Soustava má právě tři řešení modulo 1716. Najdeme x — 4t + 2at = 2 mod 11a t = 2 mod 13, což dává x = 10 mod 4.11.13 = 572, neboli xlj2,3 = 10, 582,1154 mod 1716. ' ' □
2. Určete cr"1 a cr2013, kde '1   2   3   4   5   6 7
(a) a = [4   5   7   6   1   2   3 j v gmpě Permutací (s7'°)-
(b) o = [4]n v grupě (Z*,-).
Řešení, (a) a = (1,4,6,2,5) o (3,7), cr"1 = (1,5,2,6,4) o (3,7), cr5 = 1     cr2013 =
cr3 = (1,2, 4, 5, 6) o (3, 7). (b) 45 = 1 mod 11 =^> c^1 = 44 = 3 mod 11 a cr2013 = 420i3 =43 = 9 mod n □
3. Sedmibitovou zprávu a$ai... ae, chápanou jako ao+a±x+- ■ -+a,QXe, kódujeme polynomiálním kódem generovaným polynomem x4 + x3 + 1.
• (a) Zakódujte zprávu 1101011.
• (b) Obdrželi jste kód 01001011101. Jaká byla posílaná zpráva, když budete předpokládat, že došlo k chybě na maximálně jednom bitu?
• (c) Jaká byla zpráva v (b), pokud předpokládáme, že došlo k chybě právě na dvou bitech?
Řešení, (a) x4 = x3 + 1, x5 = x3 + x + 1, x7 = x2 + x + 1 x9 = x2 + 1, x10 = x3 + x 1 + x + x3 + x5 + x6 x4 + x5 + x7 + x9 + x10 + x3 + 1 + x3 + x + 1 + x2 + x + 1 + x2 + 1 + x3 + x = x3 + x4 + x5 + x7 + x9 + x10 + x3 + x. Kód je tedy 01011101011. (b) x + x4 + x6 + x7 + xs + x10 dává po dělení x4 + x3 + 1 zbytek x2 + x + 1 = x7. Došlo tedy k chybě na osmém bitu a původní zpráva byla 1010101. (c) Buď nastala chyba na druhém a desátém bitu (x + x9 = x2 + x + 1), nebo na čtvrtém a sedmém (x3 +2ľ6 = 2ľ2 + 2ľ + l) nebo pátém a devátém (x4 + xs = x2 + x + í). V prvním případě byla zpráva 00001011111, ve druhém 01011010101, ve třetím 01000011001.
□
4. Bankomat vydává bankovky v hodnotě 200, 500 a 1 000 korun. Kolika způsoby mohu vybrat 7 000 korun? Ukažte řešení pomocí vytvořující funkce.
Řešení. Úlohu můžeme přeformulovat jako hledání počtu celočíselných řešení
2a + 56+ 10c =70;    a, b, c > 0. To je také rovno koeficientu u x70 v funkce
G(x) = (1 + x2 + x4 + • • • )(1 + x5 + x10 + • • • )(1 + x10 + x20 + • • •) Tato funkce je rovna
G(X) " 1 - x2 1 - x5 1 - x10
a protože
í-x10     .      , í-x10
1 + x5 a-- = 1 + x2 + x4 + x6 + x8,
1 — x5 ' 1 — X
můžeme ji upravit do tvaru
, . _ (1 + x2 + x4 + X6 + X8)(í + X5) [X)~ (1-xiO)3
i
Podle binomické věty máme
(i-xio)3 = ^(-i)fef ,3Vofe
fe=0
a tedy
~3Vofe
G(x) = (1 + x2 + x4 + x5 + xe + x7 + xs + x9 + x11 + x13) ^(-l)fe I
fe=0
Mocninu x70 dostaneme jediným způsobem a to jako 7.10 + 0, tj. koeficient u x70 je
70i-/ ^       ^~3^     /3 + 7- 1\ 9.
□