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

\begin{document}

\title{General Mathematics and Computational Science I}
\author{Final Exam}
\date{December 16, 2005}
\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}

% \newpage


\begin{enumerate}

\item Let $A$ be a set with a finite number of elements.
\begin{enumerate}
\item Let $a \in A$.  Are there more subsets of $A$ that contain $a$
or subsets of $A$ that do not contain $a$?
\item If $X \subset A$, and $X$ contains at least two elements, are
there more subsets of $A$ that contain $X$, or subsets of $A$ that do
not contain $X$?
\end{enumerate}
Explain your answer in each case.
\hfill (5+5)

\item Recall from class that the rational numbers $\mathbb{Q}$
are defined as equivalence classes of tuples
\[
  \{ [a/b] \colon a, b \in \mathbb{Z}, b \neq 0 \}
\]
with respect to the relation
\begin{equation*}
  \tag{*}
  [a/b] \sim [c/d] \quad \text{if } ad=bc \,.
\end{equation*}

Further, recall that $\mathbb{Q}$ can be ordered as follows.  A
rational number $[a/b]\in \mathbb{Q}$, is \emph{positive} if $ab>0$
and \emph{negative} if $ab<0$.  Then, for rationals $x=[a/b]$ and
$y=[c/d]$, we define $x>y$ if $x-y>0$.

\begin{enumerate}
\item Verify that (*) defines an equivalence relation.

\item Prove, using the above definition of ordering, that for any
ordered pair $x,y \in \mathbb{Q}$ with $x<y$ there exists $z\in
\mathbb{Q}$ with $x<z<y$.
\end{enumerate}
\hfill (5+5)


\item Let $a_n$ denote the sequence of Fibonacci numbers, i.e.
\begin{gather*}
  a_{n+1} = a_n + a_{n-1} \,, \\
  a_0 = a_1 = 1 \,.
\end{gather*}
Prove, by induction, that
\begin{gather*}
  a_0 + a_2 + \dots + a_{2n} = a_{2n+1} \,.
\end{gather*}
\hfill(10)

\item A combination lock has a five digit key; a digit can be any of
the numbers $0, \dots, 9$.  What is the number of possible
combinations if the digits must be in an increasing sequence?
\hfill(10)

\item Use the arithmetic-geometric mean inequality to find the radius
of a cylinder with prescribed surface area and the largest possible
volume.

\emph{Hints:} The volume and the surface area of a cylinder of height
$h$ and radius $r$ are given by $V=\pi h r^2$ and $S=2 \pi r^2 + 2 \pi
r h$, respectively.  Eliminate $h$.
\hfill(10)


\item 
\begin{enumerate}
\item Solve the following linear programming problem using the simplex
method.

Maximize
$
  z = 4 \, x_1 + x_2
$
subject to 
\begin{gather*}
  x_1 + x_2 \leq 4 \,, \\
  x_2 \leq 3 \,, \\
  3 \, x_1 + x_2 \leq 9 \,, \\
  x_i \geq 0 \text{ for } i=1,2 \,.
\end{gather*}

\item Sketch the feasible region, the level lines of the objective
function, and the location of the optimal point found in (a).
\end{enumerate}
\hfill(10+10)



\item Consider a Kac ring with $N$ sites occupied by $B$ black and $W$
white balls.  Each edge between neighboring sites carries a marker
with probability $\mu$.  When the ring makes one turn, a ball just in
front of a marker changes color.

Give an expression for the probability that all balls turn white after
the first turn.  What happens for $N$ large?
\hfill(10)


\item If $W(B)$ denotes the number of possible ways that the sites of
the Kac ring can be occupied by $B$ black balls, define the entropy of
the ring by
\begin{gather*}
  S = \ln W(B) \,.
\end{gather*}

Show that when you double the number of sites, keeping the ratio of
black balls constant, the entropy doubles in the limit of large $N$.

\emph{Hint:} Use Stirling's formula,
\begin{gather*}
  n! \sim \sqrt{2 \pi n} \, n^n \, e^{-n} \,.
\end{gather*}
\hfill(10)

\end{enumerate}



\end{document}
