\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  5B1118 Diskret Matematik \\
L\"osningar till Kontrollskrivning 4 \\
Mondag den 3 May, 2004 \\}
\end{center}

\vspace{.3in}
\begin{enumerate}
\item (3p) Betrakta f\"oljande funktion:
$$f:\nat\to\nat\;\;\; f(n)=n+(-1)^n$$
\begin{enumerate}
\item \"Ar $f$ injektiv?
\item \"Ar $f$ surjektiv?
\item \"Ar $f$ bijektiv?
\end{enumerate}
\vspace{.3in}
Man kan skriva $f$ som:
\[ f(n)=\left\{\begin{array}{cc}
n+1& \text{ om }n\text{ \"ar j\"amn};\\
n-1&\text{ om }n\text{ \"ar odd}
\end{array}
\right. \]
$f(0)=1$ och $0$ \"ar det enda tal s{\aa} att $f(0)=1$.
\begin{enumerate}
\item  Antag att det finns $n_1,n_2\in\nat$ s{\aa} att $f(n_1)-f(n_2)$. Vi ska visa att $n_1=n_2$.
\begin{itemize}
\item Om $n_1$ \"ar j\"amn och $n_2$ \"ar odd (eller viceversa) d{\aa}
$f(n_1)-f(n_2)$ betyder att $n_1+1=n_2-1$, dvs $n_1=n_2-2$. Men detta \"ar omojligt n\"ar $n_1$ \"ar j\"amn och $n_2$ \"ar odd. Man avslutar d{\aa} att om $f(n_1)-f(n_2)$ s{\aa} m{\aa}ste b\aa da $n_1,n_2$ vara j\"amna eller odda.
\item  Om $n_1,n_2$ \"ar j\"amna d{\aa} $f(n_1)-f(n_2)$ ger $n_1+1=n_2+1$ och d{\aa} \"ar $n_1=n_2$.
\item Om $n_1,n_2$ \"ar odda d{\aa} $f(n_1)-f(n_2)$ ger $n_1-1=n_2-1$ och d{\aa} \"ar $n_1=n_2$.
\end{itemize}
\item   Vi m\aa ste visa att varje $m\in\nat$ kan skrivas som $m=n+(-1)^n$ f\"or n\aa gon $n\in\nat$.
\begin{itemize}
\item Om $m$ \"ar j\"amn d{\aa} \"ar $m+1$ odd och $f(m+1)=(m+1)+(-1)^{m+1}=m$.
S{\aa} $n=m+1$.
\item  Om $m$ \"ar odd d{\aa} \"ar $m-1$ j\"amn och $f(m-1)=(m-1)+(-1)^{m-1}=m$.S{\aa} $n=m-1$
\item $f$ \"ar bijektiv.

\end{itemize}

\end{enumerate}

\vspace{.2in}

\item(3p) Betrakta f\"oljande m\"angd:
$$F(\real)=\{f:\real\to \real\}$$
och f\"oljande bin\"ara operation:
$$+:F(\real)\times F(\real)\to F(\real)$$
d\"ar $f+g$ defineras som funktionen $(f+g)(x)=f(x)+g(x)$ f\"or varje \\
$(f,g)\in F(\real)\times F(\real)$ och f\"or varje $x\in\real$.

 Visa att $(F(\real), +)$ \"ar en grupp.
\vspace{.2in}
\begin{itemize}
\item[(G1)] Vi ska visa att operationen \"ar associativ:
Det \"ar sant eftersom additionen \"ar associativ p{\aa} $\real$.
\item[(G2)] Vi ska hitta ett Identiteselemnt. Det \"ar functionen
$$0:\real\to \real\;\; 0(x)=0$$
Man ser att $(0+f)(x)=(f+0)(x)=f(x)+0(x)=f(x)+0=f(x)$ f\"or varje $f\in F(\real)$.
\item[(G3)] L\aa t $f\in F(\real)$, vi ska hitta det inverselemnt $(f)^{-1}$. Definera
$$(f)^{-1}(x)=-f(x)\;\; \text{ f\"or varje }x\in\real$$
Denna \"ar inverelemnt till $f$ eftersom
$$(f+(f)^{-1})(x)=((f)^{-1}+f)(x)=f(x)-f(x)=0$$
\end{itemize}



\item(3p) Betrakta f\"oljande permutationer $\sigma,\tau\in{\mathbb S}_8$:
$$\sigma=[35472816],\;\;\; \tau=[12436587]$$
\begin{enumerate}
\item Skriv $\sigma,\tau$ p{\aa} cykelform.
\item Best\"am $\sigma^{-1}$.
\item Best\"am $\tau\circ\sigma^{-1}$
\end{enumerate} 
\vspace{.2in}
\begin{enumerate}
\item $\sigma=(1347)(25)(68), \pi=(1)(2)(34)(56)(78)$
\item $\sigma^{-1}=(1743)(52)(86)$.
\item p{\aa} enradform \"ar  $\sigma^{-1}=[75132846]$. Det f\"oljer att, under
  $\tau\circ\sigma^{-1}$ g\aa r 
$$1\to 7\to 8, 2\to 5\to 6, ...$$
$$\tau\circ\sigma^{-1}=[86142735]=(1852673)(4)$$
\end{enumerate}


\end{enumerate}


\end{document}