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. □