\documentclass[12pt]{article}
\usepackage{ccfonts,euler}
\usepackage{fullpage,amsmath,amsfonts,graphicx}

\begin{document}

\title{General Mathematics and Computational Science I}
\author{Midterm I}
\date{October 4, 2007}
\maketitle

% \vspace*{\fill}
% {\baselineskip=40pt
% \begin{tabbing}
% Student ID Number: \= \kill
% Last Name: \> \rule[-2pt]{10cm}{0.3pt} \\
% First Name:  \> \rule[-2pt]{10cm}{0.3pt} \\
% Signature: \> \rule[-2pt]{10cm}{0.3pt} \\
% %Code: \> \fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% %\fbox{\rule{0pt}{1.5em}\rule{1.5ex}{0pt}}
% \end{tabbing}}


% \vspace*{\fill}


\def\N{{\mathbb N}}

\begin{enumerate}

\item Prove, by induction, that $2^{2n}-1$ is divisible by $3$ for
  every $n \in \N$.
\hfill(8)

\item Consider the game where $n$ balls are arranged along a chain;
  $k$ balls are white and the remaining $n-k$ balls are black.  You
  cannot remove a black ball.  When removing a white ball, the chain
  breaks into two pieces and the former neighbors of the removed ball
  change their color.

It is sometimes, but not always, possible to remove all balls
following these rules.  The following example shows a case where it
can be done. 
\begin{center}
\includegraphics[width=9cm]{balls}
\end{center}
\begin{enumerate}
\item Conjecture a condition which ensures that all balls can be
  removed in accordance with the rules above.

\item Prove, by induction or otherwise, that your condition is
  sufficient.

\item Prove, by induction or otherwise, that your condition is
  necessary. 

\end{enumerate}
\hfill(3+3+3)

\item For $a,b \in \mathbb{Z}$, define $a \sim b$ if and only if
  $\lvert a\rvert^2=\lvert b \rvert^2$.

  Check whether this relation is an equivalence relation, i.e.\ check
  whether it is reflexive, symmetric, and transitive.  If a property
  holds, prove that it does.  If a property does not hold, give a
  counter example.
\hfill(8)

\item Let $(\N,s,1)$ be a set with successor map $s$ and distinguished
  element $1$ satisfying the Peano axioms, and let $(\N',s',1')$ be a
  different set with its own successor map $s'$ and distinguished
  element $1'$ also satisfying the Peano axioms.

Assume that $\Phi \colon \N \to \N'$ is a map with $\Phi(1)=1'$ and
$\Phi(s(n))=s'(\Phi(n))$ for every $n\in\N$.  Prove that $\Phi$ is
surjective.
\hfill(8)

\item In how many different ways can 5 boys and 5 girls sit in (a) a
  row and (b) a circle so that no boy sits next to a boy and no girl
  sits next to a girl?
\hfill(6+3)

\item Show that 
\[
  \binom{n}{k} \binom{n-k}{j} = \binom{n}{j} \binom{n-j}{k} \,.
\]
\hfill(8)
\end{enumerate}


\end{document}
