MAT282 Johdatus diskreettiin matematiikkaan
2. välikoe ke 24.11.1999 klo 8-11

1. Tiedekunnassa on dekaani ja yhdeksän muuta professoria: biologit M, A ja T, fyysikot R ja P, kemistit V ja J sekä matemaatikot K ja O. Dekaanin pitää muodostaa professoreista kehittämiskeskusteluja varten ryhmiä. Kussakin ryhmässä voi olla useita professoreita, kuitenkin seuraavin rajoituksin: kahta saman oppiaineen professoria ei voi sijoittaa samaan ryhmään; professorit V ja T tulee sijoittaa eri ryhmiin, samoin kuin professorit R ja M; professori A on ainoa biologi jonka voi sijoittaa samaan ryhmään kummankaan matemaatikon kanssa. Kukin kehittämiskeskustelu kestää tunnin. Muodosta dekaanin avuksi jokin professoreiden ryhmittely, jota käyttäen hän selviää keskusteluista mahdollisimman nopeasti. Montako tuntia vähintään tarvitaan?
2. Dominopelin nappula on kahteen neliöön jaettu suorakaide, jonka molemmissa puoliskoissa on nollasta kuuteen ``silmää''. Jos pelistä jätetään pois nappulat, joiden puoliskojen silmämäärä on sama, ja sovitaan että nappulan suunnistuksella ei ole väliä, huomataan että dominonappulat vastaavat täsmälleen kahden alkion joukkoja , missä , . Osoita, että näin saatavat dominonappulaa voidaan asettaa dominopelin sääntöjen mukaiseksi renkaaksi, jossa kahden toisiaan koskettavan nappulan vastinpuoliskoissa on aina sama silmäluku. Esimerkiksi oheisessa kuvassa on toistensa naapureiksi laillisesti asetetut dominonappulat ja .

   (Vihje: Tarkastele verkkoa .)

3. Kaikkien 15 EU-maan pääministerit saapuvat Jyväskylään huippukokoukseen tapaamaan 15:ta Jyvässeudun merkittävää kunnallista vaikuttajaa. Kukin pääministeri saa nimetä kolme vaikuttajaa, joiden kanssa hän haluaisi neuvotella. Osoita, että mikäli kenellekään jyvässeutulaiselle ei tule enempää kuin kolme neuvottelupyyntöä (tällöin itse asiassa jokaiselle tulee tasan kolme), kaikki toivotut tapaamiset voidaan järjestää kolmessa peräkkäisessä vaiheessa, joissa kussakin käydään 15 pareittaista neuvottelua EU:n ja Jyvässeudun edustajien kesken.
4. Tarkastellaan viisinkertaista toistokoodia , jossa yksibittinen viesti koodataan viisibittiseksi jonoksi c(b) = bbbbb.
   1. Muodosta koodin koodisanat ja tarkistusmatriisi. Montako virhettä koodi korjaa lähimmän naapurin periaatteella?
   2. Määritä koodin teho (engl. rate), ja osoita että koodi on itse asiassa täydellinen (engl. perfect), so. omassa luokassaan maksimaalisen tehokas.
   3. Määritä todennäköisyys, että koodia käyttäen koodattu viestisana b = 0 välittyy virheettömästi kanavassa BSC(0.05), kun vastaanottaja käyttää lähimmän naapurin dekoodausmenetelmää. (Lisätieto niille, joiden todennäköisyyslaskennan taidot ovat ruosteessa: ns. binomijakauman mukainen todennäköisyys sille, että n-bittisessä viestissä sattuu tasan e virhettä on , kun yksittäisen virheen todennäköisyys on p. Jos sinulla ei ole laskinta, myös symbolimuotoinen virhetodennäköisyyden kaava kelpaa vastaukseksi.)

Pisteytys: kukin tehtävä á 9 pistettä, yhteensä 36 pistettä.