\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.\\

 Augusti, 2004 }
\end{center}

\vspace{.3in}

\begin{itemize}
%\item {\it Skrivtid:} {\bf 8:00-13:00.}
\item {\it Till{\aa}tna hj\"alpmedel: Minir\"aknare med sifferdisplay.}
\item {\it V\"al motiverade svar kr\"avs!}
\item {\it F\"or godk\"ant (=Betyg 3) fordras minst 18 po\"ang, f\"or betyg 4 minst 23 po\"ang och f\"or betyg 5 minst 30 po\"ang.}
\end{itemize}

\vspace{.4in}

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

\vspace{.3in}

\begin{enumerate}
\item (3p) Visa med hj\"alp av induktion att:
$$n^2-2n-1>0\text{ f\"or } n\geq 3$$

Satsen \"ar sant f\"or $n=3$: $9-6-1>0$.

Antag att satsen g\"aller f\"or varje $3\leq n\leq k$ och visa att satsen \"ar sant f\"or $n=k+1$.
$$(k+1)^2-2(k+1)-1=[k^2-2k-1]+[2k-1]>0+5>0$$
\vspace{.4in}

 \item (3p) Best\"am talet $x$ om
$$\sum_{i=0}^{30}{30\choose i}7^i=x^{90}.$$
Enligt binomialsatsen:
$$(7+1)^{30}=\sum_{i=0}^{30}{30\choose i}7^i$$
Man ska l\"osa $8^{30}=x^{90}=(x^3)^{30}$.
Det f\"oljer att $x^3=8$ och s{\aa} $x=2$.


\vspace{.4in}

\item(3p) Best\"am om grafer $G_1,G_2$ med f\"oljande incidensmatriser \"ar isomorfa.
\[ A_{G_1}=\left( \begin{array}{ccccc}
1&0&0&0&0\\
0&1&1&0&0\\
0&0&1&1&0\\
0&0&0&1&1\\
1&1&0&0&1
\end{array} \right)\]
\vspace{.4in}
\[ A_{G_2}=\left( \begin{array}{ccccc}
1&0&0&0&1\\
0&1&1&0&0\\
0&0&1&1&0\\
0&0&0&1&1\\
1&1&0&0&0
\end{array} \right)\]

$G_1$ har en nod med grad $3$ och alla noder i $G_2$ har grad $2$.
Grafer kan inte vara isomorfa.
\item(3p) Betrakta de f\"oljande permutationer $\sigma,\tau\in{\mathbb S}_7$:
$$\sigma=[3547216],\;\;\; \tau=[1243657]$$

\begin{enumerate}
\item $\sigma=(13476)(25)$, $\tau=(34)(56)$.
\item $\sigma^{-1}=(16743)(25)$.
\item $\tau\circ\sigma^{-1}=(152673)$
\end{enumerate}


\vspace{.4in}

\item(3p) Skriv checkmatrisen av en kod av l\"angd $15$ som r\"attar precis ett fel. 

$ 15=2^4-1$, s{\aa} kan man skriva en Hamming kod med $r=4$. Matrisen $M$ har $4$ rader och $15$ kolumner, som best\aa r av alla ickenoll sekvenser av $4$ element i $\zed_2$:
\[ M=\left[ \begin{array}{ccccccccccccccc}
1&0&0&1&0&1&1&0&0&0&1&1&0&1&1\\
0&1&0&1&0&0&0&1&1&0&1&1&1&0&1\\
0&0&1&0&0&1&0&1&0&1&1&1&1&1&0\\
0&0&0&0&1&0&1&0&1&1&1&0&1&1&1
\end{array} \right]\]
\vspace{.7in}

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

\vspace{.4in}

\item(5p) L{\aa}t $S=\{a\in\real\text{ s{\aa} att }a\neq -1\}$. Betrakta den f\"oljande operationen $*$:
$$a*b=a+b+ab$$
\begin{enumerate}
\item Visa att $*$ \"ar en bin\"ara operation p{\aa} $S$.
Man ska visa att $a*b\in S$ f\"or alla $a,b\in S$.
$a*b\in\real$ och $a*b\neq -1$. Om $a*b=a+b+ab=-1$ d{\aa} g\"aller
$a*b=a+b+ab+1=(b+1)(a+1)=0$. Det f\"oljer att $a=-1$ eller $b=-1$ som \"ar om\"ojligt, $a,b\in S$.

\item Visa att $(S,*)$ \"ar en grupp.
\begin{itemize}
\item (G1) $$(a*b)*c=(a+b+ab)+c+(a+b+ab)c=a+b+c+ab+ac+bc+abc$$
$$a*(b+c)=a+(c+b+cb)+a(c+b+cb)=a+b+c+ab+ac+bc+abc$$
\item (G2) identitetet \"ar $0$:
$$0*a=a*0=a+0+a\cdot 0=a$$
\item (G3) inversen av elemntet $a$ \"ar ett element $x$ s{\aa} att
$$a*x=x*a=a+x+ax=0$$
Det f\"oljer att $x=\frac{-a}{a+1}\neq -1$, dvs $x\in S$.
\end{itemize}}

\item Best\"am l\"osningen av $2*x*3=7$ i $S$.
\end{enumerate}
$$2*x*3=(2+x+2x)*3=2+x+2x+3+6+3x+6x=7$$
Man ska l\"osa ekvationen $12x+4=0$. L\"osningar \"ar $x=-\frac{1}{3}$.

\vspace{.3in}

\item(5p) Best\"am antalet $6$ siffriga j\"amna heltal  om ingen siffra f\"orekommer mer \"an en g\aa ng.

J\"amna heltal slutar med en j\"amn siffra, $0,2,4,6,8$.
Vi ska ber\"akna antalet s\"att att v\"alja $6$ siffror, utan upprepning n\"ar 
\begin{itemize}
\item f\"orsta siffran kan v\"aljas bland $1,...,9$
\item f\"oljande $4$  kan v\"aljas bland  $0$ och $9$  
\item sista kan v\"aljas bland $0,2,4,6,8$.
\end{itemize}
Det \"ar l\"attare att dela upp alternativen i tv{\aa} grupper:
\begin{enumerate}
\item heltal som slutar  med $0$
\item heltal d\"ar sista siffran \"ar skild fr\aa n $0$.
\end{enumerate}
 Enligt multiplikations principen  finns det
$9\cdot 8\cdot 7\cdot 6\cdot 5=15120$ element i f\"orsta gruppen.

F\"or att ber\"akna antalet element i andra gruppen b\"orjar vi p{\aa} sista siffran (d\"ar vi har 4 olika alternativ) och sedan forts\"atter vi fr\aa n f\"orsta siffran. S{\aa} det finns
$4\cdot 8\cdot 8\cdot 7\cdot 6\cdot 5= 53760$ m\aa nga alternativ.

Totalt har vi $53760+15120$

\vspace{.3in}

\item(5p) Hur m\aa nga permutationer av siffrorna $0,1,2,3,4,5,6,7,8,9$ b\"orjar med en trea eller slutar med an sjua?

L\aa t $A=\{\sigma\in{\mathBbb S}_{10}\text{ som b\"orjar med en trea }\}$ och $B=\{\sigma\in{\mathBbb S}_{10}\text{ som  slutar med an sjua }\}$.

Vi ska r\"akna kardilalitetet av unionen:
$$|A\cup B|=|A|+|B|-|A\cap B|$$

$|A|=|B|=9!$ och $|A\cap B|=8!$

Svaret \"ar $9!+9!-8!=685440$.

\vspace{.3in}

\item(5p) Betrakta de f\"oljande funktioner $f,g:\real\to\real$:
$$f(x)=103x+173,\;\;g(x)=ax+b$$
d\"ar $a,b\in\zed$. Best\"am alla v\"arden p{\aa} $a$ och $b$ f\"or vilka:
$$f\circ g=g\circ f$$

$$f\circ g=103(ax+b)+173=g\circ f=a(103x+173)+b$$
Det f\"oljer att $103ax+103b+173=103ax+173a+b$, s{\aa}:
$$173a-102b=173$$

En l\"osning \"ar $(a,b)=(1,0)$.
Den $mcm(102,173)=173\cdot 102$.
Det f\"oljer att den allm\"anna l\"osning blir:
$(a,b)=(1+102k, 173k)$ d\"ar $k\in\zed$.

\end{enumerate}


\end{document}