% 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 Midterm 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#1{\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)
}
\begin{document}

\bigskip

\begin{center}
Instructions
\end{center}

No notes, no books, no calculators, no cell phones, no pagers,
no electronic devices of any kind.

In problems 2 and 3 you do not need to simplify your answer.


\par\vskip .25in
\begin{center}
Name\makebox[3in]{\hrulefill} \\
\end{center}

\bigskip

%\setcounter{page}{0}
%\newpage


\def\nextpage{\par\bigskip}
\prob{20} Given the inversion sequence $(2,4,2,1,1,0)$, construct
the permutation of $\{1,2,3,4,5,6\}$ which it corresponds to.

\answer 641352

\def\nextpage{\vfill \newpage}
\prob{20}
There are 20 balls to be put into 6 numbered buckets.

\bigskip
(1) How many are possible if the balls are distinguishable,
i.e., the balls are numbered 1 thru 20?

\vfill
(2) How many ways are possible if the balls are indistinguishable?

\vfill
(3) How many ways are possible if the balls are indistinguishable
and each bucket must get at least two balls?
\vfill

\answer (1) $6^{20}$ (2) $\comb(25,5)$ (3) $\comb(13,5)$

\prob{20}
(a) How many ways are there to divide 12 people into 3 groups,
one each of size 3, 4, and 5?

\vfill
(b) Suppose two of the people, Alice and Barbara,
want to be in different groups.
Then how many ways can it be done?
\vfill

\answer (a) $\mcomb(12,3,4,5)$ (b) 
$\mcomb(12,3,4,5)-\left[\mcomb(10,1,4,5)+\mcomb(10,3,2,5)+
\mcomb(10,3,4,3)\right]$

\prob{20} Let $n>1$ be an integer.
Prove that given $n+1$ integers there must be two
of them whose difference is divisible by $n$.

\def\mod{\mbox{ mod }}
\answer Recall that $r = a \mod n$ is the remainder after
dividing the integer $a$ by $n$.  Equivalently, 
$$r=a\mod n \;\;\;\;\;\;\mbox{ iff }\;\;\;\;\;\; 
0\leq r<n \mbox { and }\exists q\in{\mathbb Z}\;\; a=qn+r$$
Now suppose we are given a set $A$ of integers with $|A|=n+1$.
Since there are only
$n$ possible remainders $0,1,\ldots, n-1$ by the Pidgeon Hole Principle there
must be distinct integers $a,b\in A$ such that
$$ a \mod n=b \mod n=r.$$  
But then
$a=qn+r$ and $b=\hat{q}n+r$ for some integers $q$ and $\hat{q}$ and
so $$a-b=(q-\hat{q})\;n$$ is divisible by $n$.

\prob{20}
Let $W$ be the set of all words of length three which contain
only the letters $a$, $b$, and $c$.
Define the binary relation $E$ on $W$ by

\bigskip
$w_1 \;E\; w_2$ $\;\;\;$ iff  $\;\;\;$ $w_1$ and $w_2$ contain
                          the same number of $a$'s, same number
\par \hspace{1.2in}      of  $b$'s, and the same number of $c$'s.

\bigskip

\begin{enum}

\item Prove that $E$ is an equivalence relation.

\item What is the equivalence class containing the word abc ?

\item How many equivalence classes are there?

Hint: List a representative of each class.
\end{enum}

\def\sp{$\;\;\;$}

\answer (1) State the definitions of reflexive, symmetric, and
transitive and note the $E$ has each of these properties.
\par (2) abc   acb   bac   bca   cab   cba
\par (3) There are 10.  A list of representatives would be
\par abc  \sp aab   aac  \sp bba   bbc \sp  cca   ccb  \sp  aaa   bbb   ccc




\printanswers

\end{document}



