MAT282 Johdatus diskreettiin matematiikkaan (3 ov)
Loppukoe ke 26.1.2000 klo 8-12

1. Monellako tavalla 6 identtistä palloa voidaan värittää kolmella värillä? Entä jos pallot ovat toisistaan erottuvia (esim. erikokoisia)? Moniko värityksistä sisältää kaikkien kolmen värisiä palloja, kun pallot ovat (a) identtisiä (b) erottuvia?
2. Valtakunnallisessa ``Sinnustako Presidentti?'' -kilpailussa arvioitiin kilpailijoiden kyvykkyyttä asteikolla 0-6 neljässä lajissa (ulkopolitiikka, sisäpolitiikka, arvomaailma ja ruoanlaitto). Päästäkseen finaaliin kilpailijan tuli saada vähintään yksi piste joka lajista, sekä yhteensä vähintään 17 pistettä 24 mahdollisesta. Monellako eri tavalla vaaditun pistemäärän voi saavuttaa?
3. Ratkaise rekursioyhtälö:

   

   (Vihje: Tarkastele lukujen sijaan niiden 2-kantaisia logaritmeja .)

4. Hyperkuutioverkon solmuina ovat kaikki n-bittiset binäärijonot , ja solmujen u ja v välillä on kaari, jos ja vain jos niiden Hamming-etäisyys on tasan 1 (so. solmuja vastaavat bittijonot eroavat toisistaan tasan yhdessä kohden).
   1. Piirrä verkko .
   2. Millä n:n arvoilla verkko sisältää Eulerin kierroksen?
   3. Mikä on verkon väriluku? (Perusteltu vastaus.)
   4. Osoita, että jos , niin verkko ei ole planaarinen. (Bonustehtävä +3 p.: Osoita, että verkko on planaarinen, jos ja vain jos .)
5. Todista induktiolla n:n suhteen, että jokainen edellisen tehtävän mukainen hyperkuutioverkko , , sisältää Hamiltonin syklin. (Ohje: Oleta induktiivisesti, että verkko sisältää Hamiltonin polun solmusta solmuun . Totea, että kahdesta tällaisesta polusta voidaan yhdistää verkon samanmuotoinen Hamiltonin polku .) Piirrä em. konstruktion mukaiset verkkojen ja Hamiltonin syklit.

   (Huomautus: Hyperkuution Hamiltonin syklit vastaavat kokonaislukujen 0, ..., ns. syklisiä Gray-koodeja, joissa kahden peräkkäisen luvun binääriesitykset poikkeavat aina vain yhdessä bitissä.)

Pisteytys: Kukin tehtävä 12 pistettä, yhteensä 60 pistettä.