MAT282 Johdatus diskreettiin matematiikkaan (3 ov)
Loppukoe ke 13.6.2001 klo 12-16

1. Järvi-Suomen yliopiston Kombinaatioteknologian tiedekunnassa on viisi vakinaista professoria, jotka tiedekunnan organisaatiouudistuksen yhteydessä uudelleensijoitellaan tiedekunnan kolmeen laitokseen niin, että kullekin laitokselle tulee vähintään yksi vakinainen professori. Monellako tavalla sijoittelu voidaan tehdä, kun professorit ovat (a) keskenään identtisiä, (b) toisistaan erottuvia? (Laitokset ovat kummassakin tapauksessa ei-identtisiä.)

2. Kuvassa 1 on kokonaisluvut $1,\dots,5$ sijoitettu ympyrän kehälle niin, että kukin luku esiintyy toisen naapurina tasan yhden kerran. Osoita, että tällainen kokonaislukujen $1,\dots,n$ sijoittelu on mahdollinen aina ja vain kun $n$ on pariton. (Vihje: Tarkastele verkkoa $K_n$.)

   Kuva 1: Lukuympyrä

   

3. Vuoden 2003 eduskuntavaalien jälkeen koottavaan laajapohjaiseen Kansalliseen Konsensushallitukseen nimitetään kaikkiaan 18 ministeriä viidestä suurimmasta puolueesta. Monellako tavalla hallitus voidaan koota, kun kustakin puolueesta halutaan mukaan vähintään kaksi, mutta enintään viisi ministeriä? (Ministeripaikat ja saman puolueen ministerit ovat keskenään samanveroisia; vain lukumäärillä on merkitystä.)

4. Ratkaise rekursioyhtälö:
   
   $$\left\{\begin{array}{l} a_1 = 0,\\ a_n = 3\cdot2^{n-1} - a_{n-1}, \quad n \geq 2. \end{array}\right.$$
   
   

5. Tunnetussa susi, lammas ja kaalinpää -ongelmassa miehen pitää kuljettaa mainitut kolme hahmoa veneellä joen yli, mutta veneeseen mahtuu miehen kanssa yhtä aikaa vain yksi kuljetettava. Sutta ja lammasta ei saa jättää kahdestaan samalle rannalle, samoin kuin ei lammasta ja kaalinpäätä. Mallinna ongelma verkkoteoreettisesti ja määritä tältä pohjalta, montako kertaa mies vähintään joutuu soutamaan joen poikki, sekä montako erilaista ``minimisouturatkaisua'' hänellä on valittavanaan. (Huom. 1. Myös paluusoudut lasketaan mukaan ylityksiin, joten tarvittavien ylitysten määrä on triviaalisti ainakin seitsemän. Huom. 2. Esitettävän ratkaisun täytyy perustua muodostettuun ongelman verkkomalliin. Toisiinsa liittymätön verkko ja ``intuitiivinen'' ratkaisu eivät kelpaa vastaukseksi.)

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