\bigskip
\textit{\textbf{Note:} This homework consists of two parts. The first part (questions 1-5) will be graded and will determine your score for this homework. The second part (questions 6-8) will be graded if you submit them, but will not affect your homework score in any way. You are strongly advised to attempt all the questions in the first part. You should attempt the problems in the second part only if you are interested and have time to spare.}
\rule{6in}{2px}
\section*{Part 1: Required Problems}
\bigskip
\Question{Induction}
Prove the following using induction:
\begin{Parts}
\Part For all natural numbers $n$, $\dfrac{n^3}{3}+\dfrac{n^2}{2}+\dfrac{n}{6}$ is a natural number.
% \nosolspace{2cm}
\Part Let a and b be integers with $a\ne b$. For all natural numbers $n\ge1$, $(a^n-b^n)$ is divisible by $(a-b)$.
% \nosolspace{2cm}
\Part For all natural numbers $n$, $(2n)!\le 2^{2n}(n!)^2$. [Note that 0! is defined to be 1.]
% \nosolspace{2cm}
\end{Parts}
\Question{Make It Stronger}
Let $x\ge 1$ be a real number. Use induction to prove that for all positive integers $n$, all of the entries in the matrix \[\begin{pmatrix}1&x\\0&1\end{pmatrix}^n\] are $\le xn$. (Hint 1: Find a way to strengthen the inductive hypothesis! Hint 2: Try writing out the first few powers.)
\Question{Strong Induction}
Use strong induction to show that for all natural numbers $n$ there exist natural numbers $x$, $y$, and $z$ such that $6^n = x^2+y^2+z^2$.
\Question{Long Courtship}
\begin{Parts}
\Part Run the traditional (i.e., male optimal) propose-and-reject algorithm on the following example:
\noindent \begin{center}
\begin{tabular}{|c|c|}
\hline
Man & Preference List\tabularnewline
\hline
\hline
$1$ & $A>B>C>D$\tabularnewline
\hline
$2$ & $B>C>A>D$\tabularnewline
\hline
$3$ & $C>A>B>D$\tabularnewline
\hline
$4$ & $A>B>C>D$\tabularnewline
\hline
\end{tabular}\qquad{}%
\begin{tabular}{|c|c|}
\hline
Woman & Preference List\tabularnewline
\hline
\hline
$A$ & $2>3>4>1$\tabularnewline
\hline
$B$ & $3>4>1>2$\tabularnewline
\hline
$C$ & $4>1>2>3$\tabularnewline
\hline
$D$ & $1>2>3>4$\tabularnewline
\hline
\end{tabular}
\par\end{center}
State what happens on every day in a table.
\Part We know from the notes on the stable marriage algorithm (Lemma 4.1) that the propose-and-reject algorithm must terminate after at most $n^2$ days. This is in fact the maximum number of proposals before the algorithm halts since each man has $n$ women in his list to propose and there are $n$ men who have such a list. Knowing this, prove a sharper bound showing that the algorithm must terminate after at most $n(n-1) + 1$ proposals.
\Part Is the instance in part (a) a worst-case instance for n=4, in the sense that it requires the maximum possible number of proposals?
\end{Parts}
\Question{The Ranking List}
Now that you have practiced the basic algorithm, let's study the stable marriage problem a little bit quantitavely. Here we define the following notation: on day $j$, let $P_j(M)$ be the rank of the woman that man $M$ proposes to (where the first woman on his list has rank $1$ and the last has rank $n$). Also, let $R_j(W)$ be the total number of men that woman $W$ has rejected up through day $j-1$ (i.e.\ not including the proposals on day $j$). Answer the following questions using the notation above.
\begin{Parts}
\Part Prove or disprove the following claim: $\sum_M P_j(M) - \sum_W R_j(W)$ is independent of $j$. If it is true, also give the value of $\sum_M P_j(M) - \sum_W R_j(W)$. The notation, $\sum_M$ and $\sum_W$, simply means that we are summing over all men and all women.
\nosolspace{0.8in}
\Part Prove or disprove the following claim: one of the \textbf{men or women} must be matched to someone who is ranked in the top half of their preference list. You may assume that $n$ is even.
\nosolspace{0.5in}
\end{Parts}
\bigskip
\textit{\textbf{Note:} This concludes the first part of the homework. The problems below are optional, will not affect your score, and should be attempted only if you have time to spare.}
\rule{6in}{2px}
\bigskip
\section*{Part 2: Optional Problems}
\bigskip
\Question{Trinomials}
Use induction to prove that for all natural numbers $n$, we have the following expansion:
$$
(a+b+c)^n = \sum_{i+j+l=n}\dfrac{n!}{i!j!l!}a^ib^jc^l, \qquad \text{where} \qquad 0\le i,j,l\le n, \quad i,j,l\in\N.$$
\Question{Airport}
Suppose that there are $2n+1$ airports where $n$ is a positive integer. The distances between any two airports are all different. For each airport, there is exactly one airplane departing from it, and heading towards the closest airport. Prove by induction that there is an airport which none of the airplanes are heading towards.
\Question{A Better Stable Pairing}
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 pairings. Define the
new pairing $R \land R'$ as follows:
\begin{quote}
For every man $m$, $m$'s partner in $R \land R'$ is whichever is better
(according to $m$'s preference list) of his partners in $R$ and $R'$.
\end{quote}
Also, we will say that a man/woman \textit{prefers} a pairing $R$
to a pairing $R'$ if he/she prefers his/her partner in $R$
to his/her partner 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 pairings for the
example given above. Calculate $R \land R'$
and show that it is also stable.
\Part Prove that, for any pairings $R,\,R'$,
no man prefers $R$ or $R'$ to $R \land R'$.
\Part Prove that, for any stable pairings $R,\,R'$
where $m$ and $w$ are partners 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 men 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 the next part even if you don't prove it here.)
\Part Prove an interesting result: for any stable pairings $R,\,R'$, (i) $R \land R'$ is a pairing [\textit{Hint}: use the results from (c)], and (ii) it is also stable.
\end{Parts}