Diskreetti matematiikka, kevät 2012

Harjoitus 1 (viikko 16)

1. Osoita induktiolla n:n suhteen seuraavat kaavat oikeaksi

a) 1 + 3 + 5 + … + (2n – 1) = n²

b)

2. Olkoon A = {0, 1, 2}´{0, 1, 2}. Piirrä Hasse-kaavio järjestysrelaatiosta R Í A ´ A, missä

(r, s) R (r’, s’) jos ja vain jos r £ r’ ja s £ s’.

(Tässä relaatio £ on kokonaislukujen tavanomainen järjestys.)

3. Kuvaile yleisesti järjestettyjen joukkojen

a) (P({1, 2, …, n}), Í) ja

b) ({2, 3, 4, …, n}, |)

rakennetta. (Merkintä ” Í” on joukkojen sisältymisrelaatio ja merkintä “|” tarkoittaa tässä kokonaislukujen jaollisuusrelaatiota: m|n, jos m on n:n tekijä.) Mitkä ovat järjestyksen minimialkiot? Mitkä ovat annetun alkion välittömät seuraajat? Miten pitkä voi kummassakin järjestyksessä olla maksimaalisen pitkä ketju, so. täydellisesti järjestetty alkiojono?

4. Osoita, että missä tahansa n > 1 henkilön ryhmässä on ainakin kaksi jäsentä, jotka ovat tuttuja tasan yhtä monen ryhmään kuuluvan henkilön kanssa. Omaa itseä ei lueta tuttujen joukkoon, ja tuttavuusrelaatio on symmetrinen, niin että jos a on b:n tuttu, niin myös b on a:n tuttu.

5. Ajanhetkellä 0 sijaitsee x-akselin origossa hiukkanen, joka jakaantuu kahteen akselia pitkin vastakkaisiin suuntiin sinkoavaan hiukkaseen. Ehdittyään sekunnin kuluttua yhden yksikön päähän origosta hiukkaset pysähtyvät ja hajoavat samalla tavalla vastakkaisiin suuntiin sinkoaviin neljään hiukkaseen, jotka taas pysähtyvät sekunnin kuluttua yhden yksikön päähän lähtöpisteistään jne. Samaan pisteeseen pysähtyvät hiukkaset annihiloivat toisensa niin, että mitään ei jää jäljelle. Kuinka monta hiukkasta systeemissä on ajanhetkellä 2¹¹ + 1 ?