\Question{Induction}
Prove the following identity for all positive integers $n$ and $k$.
\begin{eqnarray*}
\sum_{j=1}^n j(j + 1)(j + 2)\cdots(j + k - 1) = \frac{n(n + 1)(n + 2)\cdots (n + k)}{k + 1}
\end{eqnarray*}
\Question{Finite Number of Solutions}
Prove that for every positive integer $k$, the following is true:\begin{quote}For every real number $r>0$, there are only finitely many solutions in positive integers to
\begin{align*}
\frac{1}{n_1}+\cdots+\frac{1}{n_k}=r.
\end{align*}
\end{quote}In other words, there exists some number $m$ (that depends on $k$ and $r$) such that there are at most $m$ ways of choosing a positive integer $n_1$, and a (possibly different) positive integer $n_2$, etc., that satisfy the equation.
\Question{Induction with Two Directions}
Pacman is walking on an infinite 2D grid.
He starts at some location $(i, j) \in \N^2$ in the first quadrant,
and is constrained to stay in the first quadrant (say, by walls along the x and
y axes).
Every second he does one of the following (if possible):
\begin{enumerate}[(i)]
\item Walk one inch down, to $(i, j-1)$.
\item Walk one inch left, to $(i-1, j)$.
\end{enumerate}
For example, if he is at $(5, 0)$, his only option is to walk left to $(4, 0)$.
Prove that no matter how he walks, he will always reach $(0, 0)$ in finite time.
\Question{Stable Marriage}
Consider a set of four men and four women with the following preferences:
\begin{center}
\begin{tabular}{|c|c||c|c|}\hline
men&preferences&women & preferences \\
\hline
A& 1$>$2$>$3$>$4&1& D$>$A$>$B$>$C \\
\hline
B&1$>$3$>$2$>$4 &2& A$>$B$>$C$>$D \\
\hline
C&1$>$3$>$2$>$4 &3& A$>$B$>$C$>$D \\
\hline
D&3$>$1$>$2$>$4 &4& A$>$B$>$D$>$C \\
\hline
\end{tabular}
\end{center}
\begin{Parts}
\Part Run on this instance the stable matching algorithm presented in class. Show each stage of the algorithm, and give the resulting matching, expressed as $\{(M,W),\ldots\}$.
\Part We know that there can be no more than $n^2$ stages of the algorithm, because at least one woman is deleted from at least one list at each stage. Can you construct an instance with $n$ men and $n$ women so that at least $n^2/2$ stages are required?
\Part Suppose we relax the rules for the men, so that each
unpaired man proposes to the next woman on his list at a
time of his choice (some men might procrastinate for several
days, while others might propose and get rejected several times
in a single day). Can the order of the proposals change
the resulting pairing? Give an example of such a change or
prove that the pairing that results is the same.
\end{Parts}
\Question{The Better Stable Matching}
In this problem we examine a simple way to {\em merge} two different
solutions to a stable marriage problem.
Let $R$, $R'$ be two distinct stable matchings. Define the
new matching $R \land R'$ as follows:
\begin{quote}
For every man $m$, $m$'s date in $R \land R'$ is whichever is better
(according to $m$'s preference list) of his dates in $R$ and $R'$.
\end{quote}
Also, we will say that a man/woman \textit{prefers} a matching $R$
to a matching $R'$ if he/she prefers his/her date in $R$
to his/her date in $R'$. We will use the following example:
\begin{center}
\begin{tabular}{|c|c||c|c|}\hline
men&preferences& women & preferences \\
\hline
A& 1$>$2$>$3$>$4& 1 & D$>$C$>$B$>$A \\
\hline
B&2$>$1$>$4$>$3 & 2 & C$>$D$>$A$>$B \\
\hline
C&3$>$4$>$1$>$2 & 3 & B$>$A$>$D$>$C \\
\hline
D&4$>$3$>$2$>$1 & 4 & A$>$B$>$D$>$C \\
\hline
\end{tabular}
\end{center}
\begin{Parts}
\Part $R=\{(A,4),(B,3),(C,1),(D,2)\}$ and
$R'=\{(A,3),(B,4),(C,2),(D,1)\}$ are stable matchings for the
example given above. Calculate $R \land R'$
and show that it is also stable.
\Part Prove that, for any matchings $R,\,R'$,
no man prefers $R$ or $R'$ to $R \land R'$.
\Part Prove that, for any stable matchings $R,\,R'$
where $m$ and $w$ are dates in $R$ but not in $R'$, one of the following
holds:
\begin{quote}
$\bullet$ $m$ prefers $R$ to $R'$ and $w$ prefers $R'$ to $R$; or\\
$\bullet$ $m$ prefers $R'$ to $R$ and $w$ prefers $R$ to $R'$.
\end{quote}
[\textit{Hint}: Let $M$ and $W$ denote the sets of mens and women respectively
that prefer $R$ to $R'$, and $M'$ and $W'$ the sets of men and women that prefer $R'$ to $R$. Note that $|M|+|M'|=|W|+|W'|$. (Why is this?) Show that $|M| \leq |W'|$ and that $|M'| \leq |W|$. Deduce that $|M'|=|W|$ and $|M|=|W'|$. The claim should now follow quite easily.]
(You may assume this result in subsequent parts even if you don't prove it here.)
\Part Prove an interesting result: for any stable matchings $R,\,R'$, (i) $R \land R'$ is a matching [\textit{Hint}: use the results from (c)], and (ii) it is also stable.
\end{Parts}
\Question{Stable Matching for Classes!}
%From sp14
Let's consider the system for getting into classes. We are given $n$ students and $m$ discussion sections.
Each discussion section $u$ has some number, $q_u$ of seats,
and we assume that the total number of students is larger than the total number of seats
(i.e. $\sum_{u=1}^m{q_u} < n$).
Each student ranks the $m$ discussion sections in order of preference, and the instructor for each discussion ranks the $n$ students.
Our goal is to find an assignment of students to seats (one student per seat) that is \textit{stable}
in the following sense:
\begin{itemize}
\item There is no student-section pair $(s,u)$ such that $s$ prefers $u$ to her allocated discussion section
and the instructor for $u$ prefers $s$ to one of the students assigned to $u$.
(This is like the stability criterion for Stable Marriage:
it says there is no student-section pair that would like to change the assignment.)
\item There is no discussion section $u$ for which the instructor prefers some unassigned student $s$ to one of the students assigned to $u$.
(This extends the stability criterion to take account of the fact that
some students are not assigned to discussions.)
\end{itemize}
Note that this problem is almost the same as the Stable Marriage Problem, with two differences:
(i) there are more students than seats; and
(ii) each discussion section can have more than one seat.
\begin{Parts}
\Part Explain how to modify the propose-and-reject algorithm so that
it finds a stable assignment of students to seats.
[\textit{Hint}: What roles of students/instructors will be in the propose-and-reject algorithm? What does "women have men on a string" mean in this setting?]
\Part State a version of the Improvement Lemma (see Lecture Note 4)
that applies to your algorithm, and prove that it holds.
\Part Use your Improvement Lemma to give a proof that your algorithm terminates, that every seat is filled, and that the assignment your algorithm returns is stable.
\end{Parts}