\documentclass[12pt]{amsart} 
\usepackage[dvips]{graphics, color}
\theoremstyle{plain}

\newtheorem{theorem}{Theorem}[section]
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\theoremstyle{lemma}
\newtheorem{lemma}[theorem]{Lemma}
\theoremstyle{exempel}
\newtheorem{exempel}[theorem]{Exempel}
\theoremstyle{corollary}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{proposition}
\newtheorem{proposition}[theorem]{{Proposition}}
\theoremstyle{clam}
\newtheorem{clam}[theorem]{Claim}
\theoremstyle{conjecture}
\newtheorem{con}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{re}[theorem]{{Remark}}
\newtheorem{no}[theorem]{Notation}



\newtheorem{quest}[theorem]{Question}

\newtheorem{problem}[theorem]{Problem}





\newtheorem{worning}[theorem]{{\rm W\sc orning}}

\newtheorem{para}[theorem]{}

\newtheorem{examp}[theorem]{Example}

\newtheorem{exercise}[theorem]{Exercise}

\newcommand\pn[1]{{\mathbb P}^{#1}}
\newcommand\cal[1]{\mathcal {#1}}
\newcommand\cL{\mathcal L}
\newcommand\cZ{\mathcal Z}
\newcommand\cO[1]{\cal{O}_{\cal{{#1}}}}
\newcommand\X[1]{X^{[{#1}]}}
\newcommand\zed{{\mathbb Z}}
\newcommand\nat{{\mathbb N}}
\newcommand\rat{{\mathbb Q}}
\newcommand\real{{\mathbb R}}
%\newcommand\a{{\aa}}
\textwidth16cm
\textheight20cm
\oddsidemargin-0.3cm
\evensidemargin0.4cm
%\pagestyle{plain} 
\newtheorem{Definition}{\sf Definition}
\begin{document}
{\sf KTH Matematik}
\begin{center} 
 {\bf Tentamen i 5B1118 Diskret Matematik 5p.\\

 24 Maj, 2004 }
\end{center}


\vspace{.4in}

\begin{center}
{\bf DEL A}, 3p per uppgift.
\end{center}

\vspace{.3in}

\begin{enumerate}
\item (3p) Hitta alla positiva heltal $m,n$ som uppfyller
$$15m+30n=45$$

Kan dela ekvationen med $5$ och l\"osa 
$$3m+6n=9$$

$sgd(3,6)=3$ och $3=6-3$. Det betyder at $3\cdot 6-3\cdot 3=9$ och \"ar d\"arf\"or $(m,n)=(-3,3)$ EN l\"osning. Man ska hitta den alm\"anna l\"osningen.
$lcm(3,6)=6$ och $6=2\cdot 3$.
$$3\cdot 6-3\cdot 3+k(2\cdot 3-6)=3\cdot(-3 +2k)+6\cdot(3-k)=9$$
Alla l\"osningar till ekvationen skrivas som $(m,n)=(2k-3, 3-k)$ f\"or $k\in\zed.$
Vi vill ha att 
\begin{itemize}
\item $2k-3>0$, dvs $k>\frac{3}{2}$ och eftersom $k\in\zed$ \"ar $k\geq 2$
\item $3-k>0$, dvs $k<3$.
\end{itemize}
Det finns en positiv l\"osning ($k=2$)  $(m,n)=(1, 1)$.
\vspace{.4in}

\item(3p) Hur m\aa nga arrangemang av bokst\"averna i ordet MATEMATIK finns det? Hur m\aa nga av dessa  inneh\aa ller inte sekvensen ``AA''?

Ordet matematik har tv{\aa} M,  tv{\aa} A och  tv{\aa} T. Antalet arrangemang
\"ar allts{\aa}
$${9\choose{2,2,2}}=\frac{9!}{2\cdot 2\cdot 2}=\frac{362880}{8}=45360$$

Antalet arrangemang som inneh\aa ller AA kan man best\"amma genom att r\"akna antalet arrangemang av bokst\"averna i MTMTIK$\Box$, d\"ar $\Box=$AA.
Det \"ar: $${8\choose{2,2}}=\frac{8!}{ 2\cdot 2}=\frac{40320}{4}=10080$$

Arrangemang som inneh\aa ller inte AA \"ar allts{\aa} $45360-10080=35280$
\vspace{.4in}

\item(3p) L\aa t $G=(V,E)$ vara en enkel graf. Best\"am $|V|$ om $G$ har $12$ kanter och varje nod har grad $4$. Rita en geometrisk representation av $G$.

Enligt formulan
$$2|E|=\sum_{v\in V} deg(v)$$
\"ar $24=|V|\cdot 4$ och d\"arf\"or $|V|=6.$



\vspace{.4in}

\item(3p) Betrakta funktionen:
$$f:\zed_+\times \zed_+\to \rat_+;\;\;\;f(m,n)=\frac{m}{n}$$
\begin{enumerate}
\item \"Ar $f$ surjektiv?

Varje positvt rationalt tal kan skrivas som $\frac{m}{n}$, d\"ar $m,n\in\zed_+$. Det visar att $f$ \"ar surjektiv.
\item \"Ar $f$ bijektiv?
Funktionen $f$ \"ar inte injektiv. Man har, till exempel att:
$$f(2,4)=f(1,2)=1/2$$
Det visar att funktionen \"ar INTE bijektiv.
\end{enumerate}

\vspace{.4in}

\item(3p) Givet ett RSA-system med krypteringsnyckel $n=77$ och $e=7$.
Dekryptera meddelandet $3$.

$n=11\cdot 7$, $m=10\cdot 6=60$. Vi ska hitta $d$ s{\aa} att $7d\equiv_{60} 1$.
Eftersom $(60,7)$ \"ar relativt prima, Euklides algoritm ger
$$1=2\cdot 60-17\cdot 7\equiv_{60}-17\cdot 7 $$
Det f\"oljer att $d=-17\equiv_{60} 43$.

Meddelandet $3$ dekrypteras som $3^{43}$, mod $77$.

$3^4=81\equiv_{77} 4\;\;\; 3^8\equiv_{77}16\;\; 3^{16}\equiv_{77}256\equiv_{77} 25\;\; 3^{32}\equiv_{77}625\equiv_{77} 9$

svaret blir $3^{32}\cdot 3^8\cdot 3^3\equiv_{77} 38$


\vspace{.7in}

\begin{center}
{\bf DEL B}, 5p per uppgift.
\end{center}

\vspace{.6in}

\item(5p) Betrackta  den fullst\"andiga bipartita grafen $K_{m,n}$.\footnote{ Grafen har $m+n$ noder, uppdelad i tv{\aa} m\"angder $V_1,V_2$ med $m$ respektive $n$ element, d\"ar kanter f\"orbinder varje nod i $V_1$ med varje nod i $V_2$, men inga kanter g\aa r mellan tv{\aa} noder i $V_1$ och inga  mellan tv{\aa} noder i $V_2$} 

\begin{enumerate}
\item For vilka v\"arden p{\aa} $m$ och $n$ \"ar $K_{m,n}$ en Eulergraf?
den fullst\"andiga bipartita grafen $K_{m,n}$ \"ar en graf utan isolerade noder, s{\aa} $K_{m,n}$ \"ar en Eulergraf om och endast om den \"ar sammanh\"angande och varje nod har j\"amn grad.

L\aa t $w,v$ vara tv{\aa} noder i $K_{m,n}$. Om $v\in V_1,w\in V_2$ (eller viceversa) d{\aa} finns det en kant mellan dem.
Om $v,w\in V_1$ (eller $v,w\in V_2$) d{\aa} kan man  v\"alja en nod $x\in V_2$
och kanter $vxw$ f\"or att g{\aa} fr\aa n $v$ till $w$. Det visar att  $K_{m,n}$ \"ar sammanh\"angande f\"or varje $m,n$.

Varje nod i $V_1$ har grad $|V_2|=n$ och varje nod i $V_2$ har grad $|V_1|=m$.

Allts{\aa} \"ar $K_{m,n}$ en Eulergraf om och endast om \"ar $m$ och $n$ j\"amna.
\item V\"alj ett par  $m,n$ s\aa dan att $K_{m,n}$  \"ar en Eulergraf och rita en Eulerkrets.

Man kan v\"alja till exempel $K_{2,2}$.

\item Finns det n\aa got par $m,n$ s{\aa}dan att $K_{m,n}$ inte \"ar en Eulergraf, men har en Eulerv\"ag?

$K_{m,n}$ \"ar en Eulergraf om och endast om h\"ogst tv{\aa} noder har udda grader.
Det f\"oljer att f\"or varje udda positivt heltal $n$ \"ar $K_{2,n}$ inte  en Eulergraf men har en Eulerv\"ag 

\end{enumerate}
\vspace{.4in}

\item(5p) Visa att om $a,b\in\zed_n$ \"ar inverterbara\footnote{ Med avseende p{\aa} multiplicationen. } d{\aa} \"ar $ab$ och $b^{-1}$ inverterbara. ( $b^{-1}$ betecknar multiplikativa inversen av $b$).

L\aa t $G=\{0\neq  a\in\zed_{32}\text{ s\aa dan att } a\text{ \"ar inverterbart} \}$.
\"Ar $(G,\cdot)$ en grupp? (multiplicationen $\cdot$ \"ar  multiplicationen modulo 32).

Ett element $a\in\zed_n$ \"ar inverterbart om och endast om $sgd(a,n)=1$, dvs $a$ och $n$ \"ar relativt prima.

Antag att $a,b\in\zed_n$ \"ar inverterbara, dvs $sgd(a,n)=1$ och $sgd(b,n)=1$.
Om $sgd(ab,n)=c$ d{\aa} g\"aller att $c$ delar $n$ och $c$ delar $ab$.
Det f\"oljer att $c$ delar $n$ och $c$ delar minst en mellan $a$ och $b$.
Men det betyder att $c$ delar $sgd(a,n)=1$ eller  $c$ delar $sgd(b,n)=1$ och
d{\aa} \"ar $c=1$. Det visar att $ab$ \"ar inverterbar.

Alternativt ska man visa att det finns en multipilkativa invers f\"or $ab$, dvs
ett element $c$ s\aa dan att $ac=ca=1$.
L\aa t $a^{-1}, b^{-1}$ vara de multiplikativa inverserna av respektive $a,b$ d{\aa} \"ar $ b^{-1}a^{-1}$ den  multiplikativa inversen till $ab$ .

Det \"ar klart att $b$ \"ar den multiplikativa inversen av $b^{-1}$.

$sgd(a,32)=1$ f\"or varje udda heltal $a$. Det f\"oljer att

$$G=\{[1],[3],[5],[7],[9],[11],[13],[15],[17],[19],[21],[23],[25],[27],[29],[31]\}   $$

Aftersom $ab$ \"ar inverterbart f\"or varje $a,b\in\zed_{32}$ \"ar multiplicationen en bin\"ar operation.
Den \"ar associativ f\"or att operationen \"ar associativ p{\aa} $\zed_{32}$.
Identitetelementet \"ar $[1]$.
Eftersom $a^{-1}$ \"ar inverterbar f\"or varje inverterbart element $a$ har varje element i $G$ en invers.
Det visar att $(G,\cdot)$ \"ar en grupp.
\vspace{.4in}

\item(5p) Visa att grupperna $(\zed_4,+)$ och $(\zed_2\times\zed_2,+)$ \"ar inte isomorfa.

$(\zed_4,+)$ \"ar en cyklisk grupp av kardinalitet $4$. Elementen $[1]$ har ordningen $ord([1])=4$. Om det finns en isomorfi $\phi$ mellan  $(\zed_4,+)$ och $(\zed_2\times\zed_2,+)$ d{\aa} m{\aa}ste $ord(\phi([1])=4$. Men det finns inget element i $(\zed_2\times\zed_2,+)$ med ordningen $4$.

$$ord(1,1)=ord(1,0)=ord(0,1)=2$$

\vspace{.4in}

\item(5p) Best\"am antalet permutationer $\sigma\in{\Bbb S}_5$ som uppfyller:
$$\sigma\neq id\text{ och }\sigma^2=id.$$

En permutation $\sigma\neq id$ av $5$ element kan ha en av f\"oljande typer:
$$ [1,1,1,2], [1,1,3], [1,2,2], [1,4], [2,3],[5]$$

Ordningen av en $k$-cykel \"ar $k$ s{\aa} bara permutaioner av typer
$$[1,1,1,2], [1,2,2]$$
\"ar s{\aa} att $\sigma^2=id.$

Antalet permutaioner av typ $[1,1,1,2]$ \"er lika med antalet $2$-cyklar i ${\Bbb S}_5$, som \"ar ${5\choose 2}=10$.

Antalet permutaioner av typ $[1,2,2]$ \"ar $\frac{1}{2}{5\choose 2}\cdot 3=15$ (f\"or varje val av en $2$-cykel det finns  tre olika s\"att att v\"alja ett element och en annan $2$-cykel. S{\aa} d\"ar dubbelr\"aknar man varje tv{\aa}-cyckel s{\aa} ska man dela med tv{\aa}).

Totalt finns det $25$ stycker  permutationer $\sigma\in{\Bbb S}_5$ som uppfyller:
$$\sigma\neq id\text{ och }\sigma^2=id.$$

\end{enumerate}


\end{document}