% LaTex2e
\documentclass[12pt]{article}
\usepackage{amssymb,latexsym}

%\usepackage{anysize}
%\marginsize{left}{right}{top}{bottom}
%\marginsize{1.25cm}{1.25cm}{1.75cm}{2.5cm} % this cuts off page numbers
%\marginsize{4cm}{4cm}{2cm}{3cm}

\pagestyle{myheadings}
\def\header{{\hfill Final Exam  \hfill A. Miller \hfill Fall 2010
                                       \hfill Math 475\hfill}}
\markboth\header\header

\newcount\probno
\newcount\total
\newwrite\examTBLFile

\probno=0

\def\message{$\;\;\;$ Show all of your work.
Circle your answer. \par\bigskip}
\def\message{}

\def\nextpage{\vfill \newpage}
\def\nextpage{\par\bigskip}

\def\prob{\advance\probno by 1 
    \nextpage
    \noindent\the\probno .
    }

\newwrite\ans
\immediate\openout\ans=answers
\outer\def\answer{\par\medbreak
  \immediate\write\ans{}
  \immediate\write\ans{\string\bigskip \the\probno . }
  \copytoblankline}
\outer\def\answerx{\par\medbreak
  \immediate\write\ans{}
  \immediate\write\ans{\string\bigskip \the\probno . }
  \copytoblankline}
\outer\def\putanswer{\par\medbreak
  \immediate\write\ans{}
  \copytoblankline}
\def\copytoblankline{\begingroup\setupcopy\copyans}
\def\setupcopy{\def\do##1{\catcode`##1=12}\dospecials
     \catcode`\|=12\obeylines}
{\obeylines \gdef\copyans#1
  {\def\next{#1}%
  \ifx\next\empty\let\next=\endgroup%
  \else\immediate\write\ans{\next}\let\next=\copyans\fi\next}}
\def\printanswers{\newpage\begin{center} Answers \end{center}
    \immediate\closeout\ans\input answers}

%\def\answer{\par\bigskip\bigskip\bigskip\noindent \par\bigskip
% Answer: \par\bigskip\bigskip}
% \outer\def\answer{ {\par\bigskip Circle your answer.} \par\medbreak

\newenvironment{enum}
{\begin{list}{(\alph{enumi})}
{\usecounter{enumi}\setlength{\rightmargin}{\leftmargin}}}
{\end{list}}

\newenvironment{Enum}
{\begin{list}{(\Alph{enumi})}
{\usecounter{enumi}\setlength{\rightmargin}{\leftmargin}}}
{\end{list}}

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

\def\mcomb(#1,#2,#3,#4){
\left(
\begin{array}{c}
#1 \\
#2,#3,#4 
\end{array}
\right)
}

\def\su{\subseteq}

\begin{document}


Do any {\bf five} of the following problems.   Do not hand in this sheet.
Do not hand in more than five problems.

Clearly state your assumptions
before trying to prove something.  State definitions clearly before
using them in your proof. Define your notation before you use it.
Do not assume what you are supposed to prove and then use that in your proof.
Do both directions of an ``if and only if'' proof.

\prob
(a) How many subsets $A\su\{1,2,\ldots,20\}$ are there
of size six?

(b) How many subsets $A\su\{1,2,\ldots,20\}$ are there
of size six which do not contain a pair of
successive integers?  Equivalently $|A|=6$ and for
every $x,y\in A$ if $|x-y|\leq 1$ then $x=y$.

(c) How many subsets $A\su\{1,2,\ldots,20\}$ are there
of size six $|A|=6$ such that for every $x,y\in A$ if
$|x-y|\leq 2$ then $x=y$?

\prob 
Show that if the edges of complete graph on 17 vertices
are colored with three colors, then there three vertices 
such that the three edges connecting them have the same color.
You may use without proof that $r(3,3)=6$.

\prob % 4-44 p.123
Let $A_1,A_2,\ldots, A_n$ be a partition of a set $X$.
Define the relation $R$ on $X$ by $x R y$ iff $x$ and $y$ 
there is a $k$ with $1\leq k\leq n$ such that $x\in A_k$ and
$y\in A_k$.  Prove that $R$ is an
equivalence relation.

\prob % 5-30 p.158
Prove that the only antichain of size 6 in the partial order
of all subsets of $\{1,2,3,4\}$ ordered by inclusion is the antichain
of all 2-element subsets of $\{1,2,3,4\}$.

\prob % 6-16 p.199
Prove that
$$n!=\sum_{k=0}^n \comb(n,k)D_{n-k}$$

\prob % 7-3 p.258
Prove
the following about the Fibonacci numbers:

  
%  (a) $f_n$ is even if and only if $n$ is divisible by $3$.
%  (b) $f_n$ is divisible by 3 if and only if $n$ is divisible by $4$.
%  (c) 

$f_n$ is divisible by 4 if and only if $n$ is divisible by $6$.

\prob % 8-13 p. 317
Prove that the number of onto functions from an $n$-set to a $k$-set
is $k!\;S(n,k)$.

\def\aa{{\mathcal A}}
\prob % 9-9
Let $\aa=(A_1,A_2,\ldots,A_n)$ be a family of sets with an SDR.  Let
$x$ be an element of $A_1$.   Prove that there is an SDR containing
$x$.  Show by example that it may not be possible to find an SDR in
which $x$ represents $A_1$.

% \printanswers

\end{document}



