Diskreetit rakenteet (ITK015)

5. DEMORATKAISUJA

1. Lasketaan p1-1p2-1p3-1

Lasketaan (p1p2p3)-1:

2. p1 = (1 2 3 5 4), p2 = (1 5 4 2 3), p3 = (2 5) (3 4) , p1p2 = (4 5 2 3 1) p1p2p3 = (1 4 2).

Alla kolme kiertoa myös graafisesti kuvattuna:

3. a) p= (1 3 9) (2 8 6) (5 7) b) Kolme kiertoa voidaan järjestää 6:lla (3!) eri tavalla.

Kiertoa (4) ei ole tarpeen huomioida. Tehtävän asettelussa ilmaisulla "erilaista tuloa" tarkoitettiin nimenomaan tulojärjestystä.

Jos tehtävä halutaan ymmärtää niin, että erilainen tulo tarkoittaa eri tulontekijöitä niin haetaan yllämainituille kierroille kaikki erilaiset yhdistelmät. Tällöin olisi tutkittava montako yhden, kahden, kolmen tai neljän kierron joukkoa syntyy. Tämä olisi aivan erilainen tehtävä ja tuloksena saataisiin kombinaatioiden summa S C(4,k), kun k=1,2,3 tai 4 eli C(4,1) + C(4.2) + C(4,3) + C(4,4) = 4 + 6 + 4 + 1 = 15. Jos itsekierto (4) jätetään pois niin saataisiin C(3,1) + C(3,2) + C(3,3) = = 3 + 3 + 1 = 9.

4. "Pulunkoloperiaate" = Pigeonhole Principle.

a) Arpakuutio on saatava 7:ään eri asentoon eli sitä pitää kääntää 6 kertaa.

b) Voi olla enintään 29 jos oletetaan nimen voivan alkaa jollain suomalaisilla aakkosilla (28) tai W:llä. Jos halutaan olla varmoja, että kaikkien nimet alkavat eri kirjaimella niin oppilaita voi kuitenkin olla vain yksi, jos opiskelijoita olisi kaksi niin nimet voisivat jo alkaa samalla kirjaimella.

c) 77 + 20 - 15 = 82 eli teen ja kahvinjuojien unioni.

5. a) P = 0 (eli P = 1 x 1/3 x 1/3 x 0 x 0).

b)

= 7!/5!2! = 21.

Mikäli katsotaan olevan merkitystä ruoan valinnan järjestyksellä niin tehtävän asettelu muuttuisi ja saataisiin tulokseksi 3x3x3x3x3 =35 =243

c) P = 3x(1/3)5 = 1/81 = 0.012345679012...

6. a) 9 voidaan valita 11:n joukosta 11!/9!2! = 55 tavalla.

b) Jos valittavana olevia kukkia olisi rajaton määrä niin voitaisiin huomioida kaikki kukkakombinaatiot ja laskettaisiin kuten tehtävä

5. b): 9 + 3 -1 = 11 => 11!/9!2! = 55.

Nyt on kuitenkin 9 kukkaa valittavana vain 11:n joukosta, jolloin vaihtoehtojen määrä riippuu siitä kuinka paljon eri kukkia laatikossa on. Ainoastaan se on tiedossa, että jokaista kukkaa on ainakin 1 kappale. Ulkopuolelle nipun jää siis aina 2 kukkaa, jotka voivat olla joko samaa lajia (joita on 3) tai jokin kolmesta yhdistelmästä: Ruusu & Neilikka, Neilikka & Orvokki tai Orvokki & Ruusu. Siis:

A: Jos jokaista kukkaa on laatikossa ainakin 2 kpl on vaihtoehtoja 6 kpl

B: Jos jotain kukkalajia (esim. orvokkia) on vain 1 kpl on vaihtoehtoja 5 kpl.

C: Jos kahta kukkaa on vain 1 kpl on vaihtoehtoja 4 kpl.

Vaihtoehdot kuvina alla: