\documentclass[12pt]{article}
\usepackage{amssymb,latexsym,epsfig,anysize}

\pagestyle{empty}
\def\arrow{\to}
%\input macros

\def\fillin{\par\noindent
answer:$\underline{\phantom{AAAAAAAAAAAAAAAA}}$
\par\noindent}
\def\rvec#1{\stackrel{\rightarrow}{#1}}
\def\lvec#1{\stackrel{\leftarrow}{#1}}

\newcounter{xprobno}
\newcommand{\xprob}[1]{\addtocounter{xprobno}{1}
   \par\vspace{.25in}\noindent\thexprobno . \marginpar{(#1 points)} }

\begin{document}

\begin{flushright}
  A. Miller\\
  M475 Final Exam \\
  December 20, 1993
\end{flushright}

\bigskip

\begin{center}
  Keep this sheet.   Show all your work and explain your answers.
\end{center}

\bigskip

%%%%%%%%%%%%%%%%%%%%%%%%%% chapter 5
\def\comb#1#2{\left(
              \begin{array}{c}
              #1 \\ #2
              \end{array}\right) }



%%%% chapter 2
\xprob{10} Of 400 employees at a factory, all worked
for three, four, or five days during a certain week
(including Sunday).  Show that at least 5 of the
employees must have been present on exactly the same days.

%%% chapter 3
\xprob{10} What is the largest power of ten which divides the
number $30!\;$?

%%% chapter 4

\xprob{10} What are the mobile integers in
$\lvec{6}\;\lvec{5}\;\rvec{3}\;
\lvec{1}\;\rvec{2}\;\lvec{4}\;\rvec{7}\;$?

What is the are the next three permutations after it
 (including the arrows)?


%%%%%%%%%%%%%%%%%%%%%% chapter 5

%\xprob{10} Evaluate the sum $\sum^n_{k=0} (-1)^k 10^k$.

%%%%%%%%%%%%%%%%%%%%%%%%%% chapter 6

\xprob{10}
Let the set $X$ be the set of all positive integers
less than or equal to 1000
which are divisible by 3, 4, or 5.   What is $|X|$?

%%%%%%%%%%%% chapter 7

\xprob{10} Let $h_{n+1}=h_n+6h_{n-1}$ and $h_0=2$ and $h_1=1$.
Find a formula for $h_n$.



%%%%%%%%%%% chapter 8


\def\rmand{\mbox{ and }}

\xprob{10} How many paths are there from $(0,0,0)$ to $(5,5,7)$
if each move is one of the following:
\begin{itemize}
  \item $(x,y,z)\arrow (x+1,y,z)$, or
  \item $(x,y,z)\arrow (x,y+1,z)$, or
  \item $(x,y,z)\arrow (x,y,z+1)$.
\end{itemize}
{\bf And} at all times we have $x\leq y$?




\def\cycle#1#2{\left[
              \begin{array}{c}
              #1 \\ #2
              \end{array}\right] }


%\xprob{10} Let $\cycle nm=s(n,m)$ be the Stirling numbers of the
%first kind, i.e., the number of permutations
%of an $n$-element set which have exactly $m$ cycles.
%These satisfy the identity:
%$$ \cycle{n+1}m=\cycle n{m-1} + n\cycle nm \rmand
%\cycle n1=(n-1)!,\; \cycle nn=1.$$
%Show that
%$$x(x+1)(x+2)\ldots(x+n-1)=\sum_{m=1}^{n}\cycle nm x^m.$$

%%%%%%% chapter 9

\newpage

\xprob{10}

$A_1=\{a,b\}$

$A_2=\{a,b,c,d\}$

$A_3=\{d,e,f\}$

$A_4=\{b,c\}$

$A_5=\{a,c\}$

$A_6=\{a,b,c\}$

Does the sequence $\langle A_1,A_2,A_3,A_4,A_5,A_6\rangle$ have a
system of distinct representatives (SDR)?  If so, what is it?
If not, show why not.

\xprob{10} Let $(V,E)$ be a bipartite graph. Hence
$V$ is the disjoint union of two sets $A$ and $B$ so that
no two vertices in $A$ are adjacent and no two vertices in $B$ are
adjacent.  Suppose
$p$ is a positive integer such that
every vertex of $A$ has degree $\geq p$ and every vertex of $B$ has
degree $\leq p$.  Prove that $|A|\leq |B|$.


%%%%% chapter 11-12

\xprob{10} Suppose $G=(V,E)$ is a graph such that
$|V|=n$ and
$$|E| > \comb{n-1}{2}.$$
Show that for any two distinct
vertices $u,v\in V$, either $u$ and $v$ are adjacent or there
exists a vertex $w\in V$ such that  $w$ is adjacent to both
$u$ and $v$.


%\xprob{10} Suppose twelve people are at a dinner party in which every
%person knows at least six others. Prove that all twelve can be
%seated at a circular table in such a way that each person is
%acquanted with the persons sitting on either side.  Give an example
%to show that this may not be possible if every person knows only
%five others.

%\xprob{10}
%Show that if one edge is removed from the graph $K_{3,3}$ the resulting
%graph is planar.

%\xprob{10}
%What is the smallest integer k such that the graph below
%can be colored with $k$ colors?  Be sure and prove that
%it cannot be colored with fewer colors.

\xprob{10} Do {\bf one} of the following:
\begin{enumerate}
    \item  Prove Euler's formula: $|V|+|F|-|E|=2$.
    \item  Prove that the graph $K_5$ is not planar.
    \item  Prove that the graph $K_{3,3}$ is not planar.
\end{enumerate}
If you do (2) or (3) you may assume (1) without proof.




\end{document}