\parskip=10 pt \def\ra{\rightarrow} \def\la{\leftarrow} \def\lra{\leftrightarrow}
\def\frac#1#2{{{#1}\over{#2}}}
\def\bin#1#2{\pmatrix{#1\cr #2\cr}}
\magnification=\magstep 1 \centerline{Final Exam math 302, Spring 1996, (front page)}
Work all the problems. There are problems on the back page as well. 

\item{1.} Let the universe of discourse be the nonnegative integers. First, restate the following proposition in direct and simple English:
\itemitem{} $\forall n\exists a\exists b\exists c\exists d[a^2+b^2+c^2+d^2=n]$.
\itemitem{}Next, prove that the statement is true at least with respect to integers between 90 and 95. (In fact it's true in general, but the proof requires concepts beyond the scope of this course.)

\item{2.} A jury pool contains 10 men and 10 women. A jury contains 12 people. What is the probability, if the jurors are selected at random, that the jury chosen will contain 6 men and 6 women?

\item{3.} Suppose $U$ has 100 elements, and $A$, $B$ and $C$ are subsets of $U$. If $A$ has 90, $B$ has 85, and $C$ has 80 elements, what is the minimum possible value for the number of elements in $A\cap B\cap C$?

\item{4.} Both  parts of this question have to do with the binomial theorem.
\itemitem{(a)} State the binomial theorem, if possible in the formal language of quantifiers, sigma notation and so on. A full statement in careful (legal-style) English will also do.
\itemitem{(b)} What can you conclude about $\bin{4n}{0}-\bin{4n}{2}+\bin{4n}{4}-\dots$ from setting $x=1$ and $y=i$ in the binomial theorem expansion of $(x+y)^{4n}$? Make a guess, and for extra points, prove it. 

\item{5.} A function $f$ from $Z$ to $Z$ is termed `happy' if $\forall n[f(n+1)-f(n)>f(n)-f(n-1)]$. Here, $Z$ denotes the positive and negative integers, as well as zero.
\itemitem{(a)}Give an example of a happy function and prove that it is happy.  
\itemitem{(b)} Can there be a happy function from $Z$ to $Z$ which is one-to-one?

\item{6.} Consider the  set $S$ of all functions  from $\{1,2,3,4,5,6,7,8\}$ into 
$\{1,2,3,4\}$.
\itemitem{(a)} How many elements are there in $S$?
\itemitem{(b)} How many of these are onto?
\itemitem{(c)} How many are there for which $f(n)\le f(n+1)$ for $1\le n\le 7$?\vfill\eject

\item{7.} Prove by induction that for all positive integers $n$, $$1+x+x^2+\dots+x^n=\frac{1-x^{n+1}}{1-x}$$ if $x\ne 1$.
\itemitem{(b)} For extra points, find the  formula for $1+2x+3x^2+\dots+nx^{n-1}$. You don't have to prove this one, but you should check it. 

\item{8.} Give formal, exact definitions of each of the following, and following the definition, an example of each:
\itemitem{(a)} An antisymmetric relation.
\itemitem{(b)} An equivalence relation.
\itemitem{(c)} $f(n)\in O(g(n))$.

\item{9.} A scheme has been put forward for a recursive multiplication algorithm. In this scheme, the time (in CPU cycles) required to complete the multiplication of 2 numbers of $n$ digits length each is given by $T(n)=6T(\lfloor n/3\rfloor)+n$, with $T(0)=1$. 
\itemitem{(a)} How many clock cycles does it take to multiply two 9-digit numbers using this algorithm? 
\itemitem{(b)} What is the asymptotic growth rate of the number of CPU cycles required to execute this algorithm, in terms of the number of digits in the numbers being multiplied? \bye