Diskreetit rakenteet (ITK015)

4. DEMORATKAISUT

1. Jäännösluokkarengas Z5 koostuu alkiojoukosta {0, 1, 2, 3, 4} =

{[0]5, [1]5, [2]5, [3]5, [4]5}, missä

[0]5 = {..-10, -5, 0, 5, 10, 15, ...}

[1]5 = {...-9, -4, 1, 6, 11, 16, ...}

[2]5 = {...-8, -3, 2, 7, 12, 17, ...}

[3]5 = {...-7, -2, 3, 8, 13, 18, ...}

[4]5 = {...-8, -1, 4, 9, 14, 19, ...}

---

[5]5 = [0]5

Saadaan seuraavanlaiset totuustaulut:

Esimerkiksi [2]5 + [3]5 = [0]5 sillä jos otetaan kummastakin alkiojoukosta [2]5 ja [3]5 satunnainen luku esim. 7 ja 8 niin saadaan 7 + 8 = 15, joka kuuluu alkiojoukkoon [0]5. Edelleen [2]5 x [3]5 = [1]5 sillä jos otetaan kummastakin alkiojoukosta [2]5 ja [3]5 satunnainen luku esim. 2 ja 3 niin saadaan 2 x 3 = 6, joka kuuluu alkiojoukkoon [1]5.

2.

220 = 1048576 eli 220 º 48576 (mod 106)

240 = 485762 = 2 359 627 776.

250 = 210 240, joten kerrotaan viimeiset 6 numeroa luvulla 210 = 1042 => 642 842 624. Viimeiset kuusi numeroa ovat haetut.

3. Ohessa kuva jäännösluokkarenkaasta Z18. Yliviivatut eivät ole kääntyviä alkioita koska syt (x, 18) ­ 1. Poistetaan siis kaikki parilliset ja 3:lla jaolliset luvut.

Tarkastellaan jäljelle jääviä alkioita. Alkion 0 viereiset alkiot ovat aina itsensä käänteisalkioita sillä 1•1 º 1 ja 17•17 = (-1) • (-1) º1. Samoin huomataan, että 17•17 = 289 = 1 + 288 = 1 + 16•18.

Riittää siis tarkastella enää alkioita 5, 7, 11 ja 13. Kun tarkastellaan lukuja k•18 + 1 (k = 1, 2, ...) niin saadaan 19, 37, 55, 73, 91, joista ensimmäiset jaolliset luvut ovat 55 ja 91. Näistä 55 = 5•11 ja 91 = 7•13 eli tässä ovat haetut lukuparit eli 5•11 º 1 (mod 18) ja 7•13 º 1 (mod 18).

4. Sanassa prstzmrzlinakrk on 15 kirjainta, jotka voidaan näin järjestää 15! eri tavalla. Edelleen sanassa on r-kirjaimia 3 kpl sekä z- ja k-kirjaimia kumpaakin 2 kpl. Sana pysyy samana vaikka esimerkiksi z-kirjainten paikkoja vaihdetaankin. Näin voidaan tehdä 3! = 1á2•3 = 6:lla eri tavalla. Erilaisia sanoja syntyy näin siis 15!/2!2!3! kpl. (Tämä "Sana"koostuu slovakinkielisistä sanoista "prst" = sormi, "krk" = kurkku ja "zmrzlina" = jäätelö).

5. Kuuden joukosta voidaan poimia kaksi alkiota 6!/2!(6-2)! = 6!/2!4! = 15 eri tavalla.

Sama voidaan merkitä lyhyesti:

6. a) Kertoimet saadaan suoraan Pascalin kolmiosta seuraavasti.

(x + y)2 = x2 + 2xy + y2 ja (x + y)3 = x3 + 3x2y + 3xy2 + y3, missä kertoimet

1, 2, 1 ja 1, 3, 3, 1 saadaan Pascalin kolmion toiselta ja kolmannelta riviltä.

Jos y = 1 niin saadaan (x + 1)2 = x2 + 2x + 1 ja (x + 1)3 = x3 + 3x2 + 3x + 1.

Potenssit 9 ja 10 saadaan kirjoittamalla Pascalin kolmio auki näille riveille asti tai sitten huomioimalla, että kaikki kertoimet ovat muotoa:

Saadaan:

(x + 1)10 = x10 + 10x9 + 45x8+ 120x7 + 210x6 + 252x5 + 210x4 + 120x3 + 45x2 + 10x + 1

(x + 1)9 = x9 + 9x8 + 36x7+ 84x6 + 126x5 + 126x4 + 84x3 + 36x2 + 9x + 1

Jolloin:

(x + 1)10 (x + 1)9 = x10 + 9x9 + 36x8+ 84x7 + 126x6 + 126x5 + 84x4 + 36x3 + 9x2 + x

b)Tämä tehtävä siirtyi 5. demoihin.

7. Vastaukset lyhyesti: a) (4 1 3 2 5), b) (3 1 2 4 5).

a) p1p2p3(x) = p1(p2(p3(x))), jolloin otetaan ensin permutaatio p3, josta edelleen p2 ja siitä p1. Graafisessa esityksessä nähdään permutaatiokuvaukset ja lopullinen tulos löydetään seuraamalla kutakin "lankaa". Näin esimerkiksi 5 kuvautuu ensin luvuksi 2 p3:n mukaan, luku 2 luvuksi 3 p2:n mukaan ja luku 3 taas luvuksi 5 p1:n mukaan. Näin luku 5 loppujen lopuksi kuvautuu tässä kertolaskussa 5:ksi. Kuva alla:

b) Lasketaan yhdistetyn p1p2p3 kuvauksen permutaatio p1p3p2 eli siis p1p3p2(x) = p1(p3(p2(x))), jolloin otetaan ensin permutaatio p2, josta edelleen p3 ja siitä p1. (Huom! Tehtävässä on käytetty hieman epäortodoksista merkintätapaa, joka saattaa tulkinnanvarainen!) Graafisessa esityksessä nähdään permutaatiokuvaukset ja lopullinen tulos on alla: