Harjoitus 6 (17.10.2007)

1.9
Luvun n aito jakaja on kokonaisluku m (1 < m < n), jolla luku n on jaollinen. Kuinka monta aitoa jakajaa on luvulla 441000?

1.10
Kuinka monta aitoa jakajaa on kokonaisluvulla N, joka voidaan esittää alkulukujen tulona seuraavasti:
N = p₁^n₁ * p₂^n₂ * ... * p_k^n_k

1.11
Kuinka monella tavalla luku 441000 voidaan ilmoittaa kahden kokonaisluvun tulona (m > 1, n > 1) niin, että lukujen m ja n ainoa yhteinen jakaja on 1. (Toisin sanoen luvut m ja n ovat suhteellisia alkulukuja.)

1.12
Yleistä tehtävän 1.11 tulos osoittamalla, että tehtävän 1.10 kokonaisluku voidaan jakaa 2^{k - 1} - 1 tavalla kahden suhteellisen alkuluvun tuloksi (m > 1, n > 1).

1.13
Binääriluku muodostuu nollista ja ykkösistä, esim. 01001 on binääriluku, jonka pituus on 5. Joukossa X on kaikki binääriluvut, joiden pituus on n. Vastaava n muuttujan Boolean-funktio on kuvaus joukosta X joukkoon Y = {0, 1}. Kuinka monta eri n muuttujan Boolean-funktiota on olemassa?

1.14
Tiettyjen Boolean-funktioiden arvo säilyy samana, kun funktiolle annettavan binääriluvun kaikki nollat muutetaan ykkösiksi ja päinvastoin. Esimerkiksi 6 muuttujan Boolean-funktiossa täytyy tällöin päteä mm. f(101101) = f(010010). Etsi kaikki mainitun ehdon täyttävät 2 muuttujan Boolean-funktiot.

1.15
Millä kaavalla voidaan laskea tehtävän 1.14 Boolean-funktioiden määrä, kun muuttujia onkin n kappaletta?

1.16
Kukkarossa on k erilaista kolikkoa, ja eri kolikoiden lukumäärät ovat n₁, n₂, ..., n_k. Kuinka monta erilaista kolikkojoukkoa, joissa on ainakin yksi kolikko, voidaan valita?

1.148
Todista seuraavat yhtäsuuruudet:
(a) S(n, 2) = 2^{n - 1} - 1
(b) S(n, n - 1) = C(n, 2)

1.162
Joukossa X on n alkiota. Osoita, että joukon X epätyhjien osajoukkojen ositusten yhteismäärä on B_{n + 1} - 1.