\documentclass {exam}
\pagestyle {headandfoot}
\lfoot {\oddeven {}{Page \thepage \space of \numpages }}
\cfoot {}
\rfoot {\oddeven {Page \thepage \space of \numpages }{}}
\begin {document}
\noindent \textbf{MATH 112}\hfill
\textbf{Week 3 homework}\hfill
\textbf{Due 2003 August 20}
\vskip 12pt plus 4pt minus 4pt
\begin {questions}
\question
Suppose that you're picking out an outfit for the day.
You can choose the green pants, the blue pants, or the black pants:
$3$ possible choices of pants.
You can also choose
the green shirt, the blue shirt, the white shirt, or the grey shirt:
$4$ possible choices of shirt.
But you know that mixing a green item with a blue item will look bad.
Does the product rule for counting directly apply
to tell you how many different outfits you could wear?
If not, how can you figure this number out anyway?
%
\question
Suppose that you know the sum rule for only $2$ options.
Use induction to prove that the sum rule also holds
for any natural number $k \ge 2$ of options.
[Hint: \textsl{Break up\/ $n + 1$ options
into\/ $n$ options and\/ $1$ option.}]
%
\question \relax [\textsl {Binomial theorem.}]
This question explains why the binomial coefficients are called that.
Use induction to prove
that $$(x + y)^{n} = \sum_{i=0}^{n} {n \choose i} x^{i} y^{n-i}\mbox{.}$$
(The formula `$x + y$' is a \textbf{binomial}.)
%
\question
Prove that if $n$ is a natural number,
then $${2n \choose 2} = 2{n \choose 2} + n^{2}\mbox{:}$$
\begin {parts}
\part
using algebra
and the formula for the binomial coefficient in terms of factorials.
%
\part
using a combinatorial argument
applied to the meaning of the binomial coefficient in terms of sets.
%
\end {parts}
\question
Let $A$ and $B$ be sets of sizes $m$ and $n$, respectively.
\begin {parts}
\part Give a formula for the number of functions from $A$ to $B$.
Briefly explain why it's correct.
%
\part Give a formula for the number of one-to-one functions from $A$ to $B$.
Briefly explain why it's correct.
%
\part Give a formula for the number of invertible functions from $A$ to $B$.
Briefly explain why it's correct.
%
\end {parts}
\question
Prove that if $n$, $r$, and $k$ are natural numbers, with $k \le r \le n $,
then $${n \choose r}{r \choose k}
= {n \choose k}{n - k \choose r - k}\mbox{.}$$
%
\question
How many different strings can be made
by rearranging the letters in the word `MISSISSIPPI'?
[Hint: \textsl {Don't solve this problem by listing them all!\/}]
%
\question
\begin {parts}
\part
A bookshelf contains $12$ books in a row.
How many ways can you choose $5$ of these books
subject to the condition that you never choose a pair of books
that are right next to each other on the shelf.
%
\part
Generalise this to the case of $n$ books on the shelf and choosing $k$ books.
Given a value of $n$, what condition on $k$ is necessary
so that the answer doesn't just come out to zero?
%
\end {parts}
\question
A hideous alien being with $3$ feet is searching for socks in the dark.
The monster has $27$ black socks, $33$ grey socks, and $12$ navy blue socks.
How many socks must it pull out of the drawer
to be sure that it has $3$ socks of the same colour?
%
\question
Consider a Cartesian plane (that is, with coordinates)
and a pentagon in it whose vertices all have integer coordinates.
Show that there is a pair of distinct vertices
such that the midpoint of the line joining these two vertices
also has integer coordinates.
%
\end {questions}
\end {document}
