\documentclass[12pt]{article}
\usepackage{amsmath}

\input{macros-course}

\def\brule#1{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}

\newcommand{\solution}[1]{}
%%  \newcommand{\solution}[1]{\smallskip \textbf{Solution:} #1}

\newcommand{\pts}[1]{\relax[#1 pts]\enskip\ignorespaces}

\makeatletter
\renewcommand\theenumi{\@alph\c@enumi}
\renewcommand\theenumii{\@roman\c@enumii}

\renewcommand\labelenumi{\theenumi)}
\renewcommand\labelenumii{\theenumii)}

\def\ps@myheadings{%
    \let\@oddfoot\@empty\let\@evenfoot\@empty
    \def\@evenhead{\thepage\hfil\slshape\leftmark}%
    \def\@oddhead{\rlap{\slshape\rightmark}\hfil\thepage\hfil \llap{Name:\brule{2in}}}%
    \let\@mkboth\@gobbletwo
    \let\sectionmark\@gobble
    \let\subsectionmark\@gobble
    }

\makeatother

\newcommand{\bij}{\mathop{\mbox{\rm bij}}}

\begin{document}

\handout{q2}{Extra Q2 probs}{3/11 23:45}

\begin{problems}

\problem\pts{15} \emph{Pigeonhole Principle. (Amit)}  Prove that in any set of 52
integers, there must be two integers with the property that either their
sum or their difference is divisible by 100.

\solution{The 52 integers are the pigeons.  There are 51 holes, each
labelled with one or two integers from 0 to 99 as follows:
\[\begin{array}{|c|c|c|c|c|c|}
0 & 1,99 & 2,98 & \dots & 49,51 & 50
\end{array}\]
Place each pigeon, $n$, into the hole which has a label equal to $n \bmod 100$.

Now two pigeons must be in the same hole.  If these two have different
remainders $\mod 100$, then their sum is divisible by 100; otherwise their
difference is divisible by 100.}

\problem\pts{15} \emph{Pigeonhole Principle?? (Amit)} Prove that in any set
of $n+1$ positive integers $\leq 2n$, there are two consecutive integers.

\solution{I'm doubtful about this problem: seems easier to prove by
induction, and then there's no need for the Pigeonhole Principle.  I
couldn't find a Pigeonhole argument which didn't still require an
induction anyway.}


\problem\pts{20} \emph{Countability (Zully idea)}
\bparts
\ppart\pts{8} Prove that the set, I, of \emph{strictly increasing} functions from
$\naturals$ to $\naturals$ is uncountable.

\ppart\pts{12} Prove that the set, N, of \emph{nonincreasing} functions from
$\naturals$ to $\naturals$ is countable.

\solution{Seems too hard; needs a hint at least.

For $f: \naturals \to \naturals$, let
\[
\mbox{steps}_f ::= \set{(0,f(0))} \cup \set{(n+1,f(n+1)) \mid f(n) > f(n+1)}
\]
If $f \in N$, then $\mbox{steps}_f$ is finite and uniquely determines $f$.
So mapping $f$ to $\mbox{steps}_f$ defines an injection from $N$ to finite
sequences of elements in $\naturals \times \naturals$.  Code any finite
sequence $(n_0,n_1),(n_2,n_3),\dots, (n_{2k},n_{2k+1})$ as the number
$\prod_{i=0}^{2k+1} {p_i}^{n_i}$ where $p_i$ is the $i$th largest prime
number.  This coding defines an injection from such finite sequences into
$\naturals$.  Hence there is an injection from N into $\naturals$, which
we know implies that N is countable.}
\eparts



\problem\pts{20} \emph{Bijections} 
Prove that there is a bijection between the half-open unit interval
$[0,1)$ and the set $\naturals \rightarrow \set{0,1}$ of 0-1-valued
functions on the natural numbers.  You may cite without proof any of the
results from class or notes.

\solution{The correspondence between a function $f\in \naturals
\rightarrow \set{0,1}$ and the set $f^{-1}(1) ::= \set{n \in \naturals
\mid f(n) = 1}$ is obviously a bijection between $\naturals \rightarrow
\set{0,1}$ and $P(\naturals)$.  But we know from notes and problem set
that
\[P(\nats) \bij \reals \bij [0,1].\]
But $[0,1)$ and $[0,1]$ are infinite sets which differ by only one point,
and so have a bijection between them.}


\problem\pts{20} \emph{Linear Recurrences. (Matt)} 
Solve the linear recurrence
\[
T(n) = 3T(n-1) - 4T(n-3) + 6
\]
subject to the initial conditions $T(0) = 11, T(1) = 6, T(2) = 28$.

\solution{
(a)  Solve the homogeneous equation.

The characteristic equation of the homogeneous part is $x^3 -3x^2+4=0$
which has -1 as a root and 2 as a double root.  So
\[
T(n) = a 2^n + b n 2^n + c (-1)^n,
\]
for any constants $a,b,c$.

(b) Obtain the particular solution.  $T(n) \equiv 3.$

(c) Now, solve the recurrence by adding the homogeneous solution to the
   particular solution and solving for the base cases.
\[
T(n) = a 2^n + b n 2^n + c (-1)^n + 3
\]
where $a = 3, b = 1, c = 5$.}

\problem\pts{15} \emph{Permutations and Combinations.  (Mike)}
\[
k \binom{n}{k} = n \binom{n-1}{k-1}
\]

\bparts
\ppart\pts{5} Prove this equation algebraically.

\ppart\pts{10} Now give a combinatorial argument proving this equation.
That is, describe two different procedures for counting the same things,
where the lefthand side of the equation clearly describes the number of
outcomes of the first procedure and the righthand side the number of
outcomes of the second procedure.

\solution{Two ways to choose a committee of $k$ out of $n$ and a committee
chair:
\begin{enumerate}
\item The LHS corresponds to choosing the committee of $k$ and then
choosing a chair among the $k$.
\item The RHS corresponds to choosing one of the $n$ to be the chair, and
then choosing the remaining $k-1$
committee members from the remaining $n-1$ people.
\end{enumerate}
}

\eparts

\end{problems}

\end{document}
