next up previous
Next: Tästä dokumentista ... Up: harj2 Previous: harj2

Johdatus diskreettiin matematiikkaan, syksy 2000
Harjoitus 2, 3.-5.10.


  1. Todista seuraavat väitteet:
    1. Kaikki luonnollisten lukujen joukon ${\mathbf N}$ osajoukot ovat joko äärellisiä tai numeroituvasti äärettömiä.
    2. Karteesinen tulo ${\mathbf N}\times{\mathbf N}$ on numeroituvasti ääretön. (Vihje: Ajattele parit $(m,n) \in {\mathbf N}\times{\mathbf N}$ sijoitetuksi kaksiulotteiseen taulukkoon. Numeroi taulukon alkiot vasemmalta alhaalta oikealle ylös suuntautuvin vinorivein.) Huom.: Tuloksesta seuraa helposti, että myös rationaalilukujen joukko ${\mathbf Q}$ on numeroituvasti ääretön.

  2. 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. (Vihje: Kyyhkyslakkaperiaate.)

  3. Korttipakassa on 52 korttia, jotka jakautuvat neljään ``maahan'' (hertta, ruutu, risti, pata). Kuhunkin maahan kuuluvat kortit on numeroitu 1,...,13.
    1. Montako erilaista viiden kortin ``pokerikättä'' (viiden kortin osajoukkoa) pakan korteista voidaan muodostaa? (Jos sinulla ei ole laskinta, kaava riittää vastaukseksi.)
    2. Monellako tavalla korteista voidaan muodostaa viiden kortin ``väri'', so. viiden kortin osajoukko jonka kaikki kortit ovat keskenään samaa maata?
    3. Monellako tavalla korteista voidaan muodostaa ``täyskäsi'', so. viiden kortin osajoukko joka koostuu ``kolmosista'' (kolme keskenään samanarvoista korttia) ja ``parista'' (kaksi keskenään samanarvoista korttia)? (Sama kortti ei tietenkään täyskädessä voi kuulua sekä kolmosiin että pariin.)

  4. Todista seuraavat binomikertoimien ominaisuudet:
    1. ${{n}\choose{k}} = \frac{n-k+1}{k}{{n}\choose{k-1}}, %%\qquad
\mbox{ kun } 1 \leq k \leq n.$ Päättele tästä, että binomikertoimet ovat $k$:n suhteen kasvavia ( ${{n}\choose{k-1}} < {{n}\choose{k}}$), kun $k \leq n/2$, ja väheneviä ( ${{n}\choose{k}} > {{n}\choose{k+1}}$), kun $k \geq n/2$.
    2. Vahvista Pascalin kaava ${{n}\choose{k}} = {{n-1}\choose{k-1}} + {{n-1}\choose{k}}, %%\qquad
\mbox{ kun } 1 \leq k \leq n,$ suoraan binomikertoimien aritmeettisesta määritelmästä laskemalla.
    3. $\sum_{i=0}^r {{n+i}\choose{n}} = {{n+r+1}\choose{n+1}},$ induktiolla $r$:n suhteen. Mikä tuttu kaava tästä saadaan $n$:n arvolla 1? Keksitkö yhtälölle myös kombinatorisen todistuksen?

  5. Arvioi ``keskimmäisen'' binomikertoimen ${{2n}\choose{n}}$ suuruutta käyttäen kertomafunktiolle Stirlingin approksimaatiota: $n! \sim \sqrt{2\pi n}(n/e)^n$.

  6. Luonnolliset luvut $m$ ja $n$ ovat pareittain jaottomia, jos niillä ei ole yhteisiä tekijöitä, so. jos niiden suurin yhteinen tekijä on $\mbox{syt}(m,n)=1$. Ns. Eulerin funktio $\phi$ ilmaisee annettua lukua $n$ pienempien, $n$:n kanssa pareittain jaottomien lukujen määrän, so. $\phi(n) =
\vert\{m \in {\bf N} : 1 \leq m \leq n, \mbox{syt}(m,n) = 1\}\vert.$ (Siten esim. $\phi(5) = 4$, $\phi(6) = 2$.) Totea seulayhtälöä käyttämällä että jos luvun $n$ eri alkutekijät ovat $p_1$, $p_2$,..., $p_k$, niin

    \begin{displaymath}\phi(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots
(1-\frac{1}{p_k}).\end{displaymath}


next up previous
Next: Tästä dokumentista ... Up: harj2 Previous: harj2
Pekka Orponen 2000-10-05