next up previous
Next: About this document Up: No Title Previous: No Title

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ö:

    displaymath41

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

  4. Hyperkuutioverkon tex2html_wrap_inline47 solmuina ovat kaikki n-bittiset binäärijonot tex2html_wrap_inline51 , 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 tex2html_wrap_inline57 .
    2. Millä n:n arvoilla verkko tex2html_wrap_inline47 sisältää Eulerin kierroksen?
    3. Mikä on verkon tex2html_wrap_inline47 väriluku? (Perusteltu vastaus.)
    4. Osoita, että jos tex2html_wrap_inline65 , niin verkko tex2html_wrap_inline47 ei ole planaarinen. (Bonustehtävä +3 p.: Osoita, että verkko tex2html_wrap_inline47 on planaarinen, jos ja vain jos tex2html_wrap_inline71 .)
  5. Todista induktiolla n:n suhteen, että jokainen edellisen tehtävän mukainen hyperkuutioverkko tex2html_wrap_inline47 , tex2html_wrap_inline77 , sisältää Hamiltonin syklin. (Ohje: Oleta induktiivisesti, että verkko tex2html_wrap_inline47 sisältää Hamiltonin polun solmusta tex2html_wrap_inline81 solmuun tex2html_wrap_inline83 . Totea, että kahdesta tällaisesta polusta voidaan yhdistää verkon tex2html_wrap_inline85 samanmuotoinen Hamiltonin polku tex2html_wrap_inline87 .) Piirrä em. konstruktion mukaiset verkkojen tex2html_wrap_inline57 ja tex2html_wrap_inline91 Hamiltonin syklit.

    (Huomautus: Hyperkuution tex2html_wrap_inline47 Hamiltonin syklit vastaavat kokonaislukujen 0, ..., tex2html_wrap_inline95 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ä.



Pekka Orponen
Wed Jan 26 16:10:35 EET 2000