%\documentclass[12pt]{article}
\newcommand{\coursename}{DM527\xspace}
\newcommand{\coursenamel}{DM527 Matematiske redskaber i datalogi\xspace}
\newcommand{\courseurl}{http://imada.sdu.dk/~svalle/courses/dm527-2007}
\newcommand{\courseperiod}{E2007, 1. kvartal\xspace}
\newcommand{\mytitle}{Eksamensprojekt efteråret 2007\xspace}

\documentclass[12pt]{article}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[english,danish]{babel}
\setlength{\parindent}{0em}
\setlength{\parskip}{1ex plus .1ex minus .1ex}
\setlength{\itemsep}{0ex}
\usepackage{xspace}
\usepackage{a4wide}
\usepackage{graphicx}
\usepackage[osf]{mathpazo} % consider options: osf, sc

\def\N{\Bbb{N}}
\def\Q{\Bbb{Q}}

\def\Z{\Bbb{Z}}
\def\R{\Bbb{R}}



\renewcommand{\labelenumi}{\alph{enumi})}
\newcommand{\Xomit}[1]{}

\usepackage[%
  pdfauthor={Jens Svalgaard Kohrt},%
  pdftitle={\mytitle{}},%
  pdftex]{hyperref}

\begin{document}


\begin{tabular}{@{}l}
\href{http://imada.sdu.dk/}{IMADA} \\
\href{http://sdu.dk/}{SDU}
\end{tabular}
\hfill
\begin{tabular}{r@{}}
\courseperiod\\ % \today{} \\
\href{http://imada.sdu.dk/~svalle/}{Jens Svalgaard Kohrt}
\end{tabular}

\vspace{2ex}
\begin{center}{\LARGE 
    \href{\courseurl}{\coursenamel} \\
    % E07, 1st quarter --
    \mytitle}
\end{center}

\vspace{1ex}
\selectlanguage{danish}
\newcounter{antalopgaver}
\addtocounter{antalopgaver}{1}
\newcommand{\opgave}[1]{%
  \bigskip\subsection*{Opgave \theantalopgaver{} (#1 \%)}%
  \addtocounter{antalopgaver}{1}
}
\thispagestyle{empty}

\subsection*{Deadline og formalia}

Projektet skal indleveres til din instruktor senest 

\begin{center}
  fredag den 12. oktober 2007 klokken 12.16.
\end{center}

Husk, at dette er et eksamensprojekt! Dvs. du må ikke på nogen måde arbejde
sammen med andre. % Snyd kan medføre bortvisning fra alle danske universiteter!

Projektet består af 6 opgaver, hvoraf enkelte har flere delopgaver. For hver
opgave er angivet, hvor mange procent denne opgave tæller af den samlede
karakter. Bemærk at delopgaver ikke nødvendigvis vægtes lige højt. I alt
kommer 20\% af karakteren fra eksamensprojektet.

\emph{Bemærk:} I det følgende defineres $\N = \{1,2,3,\ldots\}$ og $\N_0 =
\{0\}\cup \N$.

\pagebreak

\opgave{8}
% ex. 3.7.28

\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{Setun-1}
\caption{\small Satun, 1958. En russisk computer, der som en af de eneste
  nogensinde brugte balanceret ternær repræsentation. Stort set alle computere
  lavet både før og efter Satun bruger binær repræsentation. Se mere på
  \href{http://en.wikipedia.org/wiki/Setun}{Wikipedia} eller på det online
  \href{http://ukrainiancomputing.org/PHOTOS/Setun-1.html}{ukrainske computer
    museum}. }
\end{center}
\end{figure}

Man kan vise, at ethvert heltal $n\in\Z$ kan repræsenteres unikt på formen
\[
   n = 3^k e_k  + 3^{k-1} e_{k-1} + \cdots + 3e_1 + e_0 
     = \sum_{i=0}^{k} 3^i e_i \,,
\]
hvor $e_i \in \{-1,0,1\}$ for $i =0, 1, \ldots, k$. Denne repræsentation
kaldes \emph{balanceret ternær}. Når man bruger balanceret ternær
repræsentation skrives $-1$ normalt som $\overline 1$, dvs. $1$ med en streg
ovenover.

Bruges balanceret ternær repræsentation skrives det decimale tal $5$ som
$1\overline{11}$, dvs.
\[ 
    5 = 3^2~1 + 3~(-1) + (-1) = 9 -3 -1 \,.
\]
Det decimale tal $-14$ skrives som $\overline1 111$ i balanceret ternær repræsentation.

\begin{enumerate}
\item Skriv følgende decimale tal i balanceret ternær repræsentation
\[
    2,~~ 18,~~ -89,~~ 120,~~ 121,~~ 122\,.
\]

\item Vis, at ethvert tal $n \in \N_0$ kan skrives i balanceret ternær
  repræsentation.

  Vink: Brug induktion over $n$. 

\item Brug resultatet fra b) til at vise, at ethvert tal $n\in\Z$ kan skrives
  i balanceret ternær repræsentation.
\end{enumerate}

\opgave{3}

For naturlige tal $x \in\N$ betragter vi de følgende åbne udsagn:
\begin{itemize}
\item $P(x) := x$ er et primtal.
\item $D(x,y) := x|y$.
\item $E(x) := x$ er et lige tal, dvs. $E(x) = D(2,x)$.
\end{itemize}


\begin{enumerate}
\item Betragt de to udsagn
  \[
    A \equiv \forall x \in\N: \forall y \in\N:~
    \left( P(x) \wedge E(x) \wedge E(y) \right) \Rightarrow D(x,y) \,,
  \]
  og
  \[
    B \equiv \forall x \in \N:~ \exists n \in\N:~
    P(x) \Rightarrow \sum_{i=1}^n i = n \,.
  \]
  
  Afgør for både $A$ og $B$, hvorvidt udsagnet er sandt eller falsk. Begrund
  dine svar.

\item Find negationerne af udsagnene i a). Disse skal udtrykkes kun ved hjælp
  af de logiske operationer $\wedge, \vee, \neg$ og kvantorerne $\exists$ og
  $\forall$. 

\end{enumerate}


\opgave{1}
% 
Vis at der for vilkårlige naturlige tal $m, n \in\N_o$, $m\le n$ gælder:
\[
  \sum_{i=m}^{n}i = \frac{n(n+1)-m(m-1)}{2}
\]


\opgave{3}
% 
Vis at der for alle naturlige tal $n \in \N_0$ gælder
\[
  n^2 \le 3^n
\]
% Vink: For ikke for små $n$ gælder $2n+1   < 2n^2$. Brug flere basistilfælde.
Vink: Hvis $n$ er stor nok, gælder $(n+1)^2 < 3n^2$. 

\opgave{3}

Brug den kinesiske restklassesætning til at finde det mindste naturlige tal $x
\in \N$, som opfylder følgende tre uligheder:
\[ 
\begin{array}{rrr}
   x &\equiv& 5  \pmod{13}
\\ x &\equiv& -2 \pmod{17}
\\ x &\equiv& 7  \pmod{32}
\end{array}
\]

\opgave{2}

Defin\'er følgende matrixer
\[
  A =
   \left[\begin{matrix}
     1 & 0 & 0 \\
     1 & 1 & 1
   \end{matrix} \right]\,, 
~~~~
  B =
   \left[\begin{matrix}
     -2 & 4 \\
     7  & 16 \\
     3  & -1 
   \end{matrix} \right]\,, 
~~~~
  C =
   \left[\begin{matrix}
     0 & 1 \\
     1 & 1 
   \end{matrix} \right] \,.
\]

\begin{enumerate}
\item Find følgende (husk mellemregninger) såfremt resultatet er defineret
\[
A+B,~~ A+B^t,~~ A A^t,~~ AC,~~ CA,~~ A\odot C ~~\text{og}~~ C \odot A
\]
\item Hvilke (hvis nogen) af $A$, $B$ og $C$ er symmetriske?
\end{enumerate}

\end{document}