\documentclass[11pt]{article}
\usepackage{header}
%%% Change these %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def
\title{HW 2}
\def
\due{Friday, September 9 at 10PM}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\maketitle
\fontsize{12}{15}
\selectfont
\begin{Questions}
\Question{\bf Sundry}
Before you start your homework, write down your team. Who else did you work with on this homework? List names and email addresses. (In case of hw party, you can also just describe the group.) How did you work on this homework? Working in groups of 3-5 will earn credit for your "Sundry" grade.
%%% Include questions here %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Question (5 points) Prove that
$1^3 + 2^3 + 3^3 +
\dots + n^3 = (1 + 2 + 3 +
\dots + n)^2$
for all integers $n>0$.
\Question{\bf A Tricky Game} (10 points)
\begin{Parts}
\Part (10 points) CS 70 course staff invite you to play a game: Suppose there are $n^2$ coins in a $n
\times n$ grid ($n > 0$), each with their heads side up. In each move, you can pick one of the $n$ rows or columns and flip over all of the coins in that row or column. However, you are not allowed to re-arrange them in any other way. You have an unlimited number of moves. If you happen to reach a configuration where there is exactly one coin with its tails side up, you will get an extra credit. Are you able to win this game? Does that apply to all $n$? Prove your answer.
\Part (Optional) Now, suppose we change the rules: If the number of ``tails'' is between 1 and $n-1$, you win. Are you able to win this game? Does that apply to all $n$? Prove your answer.
\end{Parts}
\Question{\bf Making big rocks into little rocks} (10 pts)
\\
One day, you find a shady-looking flyer on Sproul that advertises an
undergraduate research position in the Stanford geology
department. After you make your way down to the Farm, Dr. Hoover, the
professor in charge, hands you the following assignment to keep you
busy for the first year, complaining that none of the Stanford
undergrads have been able to help him:
You are given a single large pile of pebbles to start with. Every day,
you have pick one pile of pebbles and split it into two smaller piles
any way you wish. Then, you have to count the number of pebbles in
each of the two new piles you just created ($k$ and $m$), and write
down the product $k
\times m$ in your lab notebook. Of course, over
time, you end up with more and more piles which get smaller and
smaller. You get to stop when each pebble is in its own pile. Once you
stop, add up all the numbers you wrote down and report them to Dr.
Hoover. The following figure shows an example of the process.
\includegraphics[width=15cm]{resources/figures/pile-splitting}
Convince Dr. Hoover (and his funding agency) that this
\footnote{The
research assignment, not this homework problem!}
is a pointless
exercise: no matter how you split the piles, your answer will come
out to $n(n-1)/2$, where $n$ is the number of pebbles in the original
pile (which you can just count on the first day).
\Question (10 points)
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 $
\frac{1}{n_1}
+
\cdots+
\frac{1}{n_k}
=r$.
\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{\bf Be a Judge} (15 points)
For each of the following statements about the traditional stable marriage algorithm with men proposing, indicate whether the statement is True or False and justify your answer with a short 2-3 line explanation:
\begin{Parts}
\Part (3 points) In a stable marriage algorithm execution which takes $n$ days, there is a woman who did not receive a proposal on the $(n-1)$th day.
\Part (3 points) There is a set of preferences for $n$ men and $n$ women,
such that in a stable marriage algorithm execution every man ends up with his
least preferred woman.
\Part (3 points) In a stable marriage instance, if man~$M$ and woman~$W$ each put each
other at the top of their respective preference lists, then $M$ must be paired with~$W$
in every stable pairing.
\Part (3 points) In a stable marriage instance with at least two men and two women,
if man~$M$ and woman~$W$ each put each
other at the bottom of their respective preference lists, then $M$ cannot
be paired with~$W$ in any stable pairing.
\Part (3 points) For every~$n>1$, there is a stable marriage instance with $n$ men and
$n$~women which has an unstable pairing in which every unmatched
man-woman pair is a rogue couple.
\end{Parts}
\Question{\bf Stable Marriage} (18 points)
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 (3 points) 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 (5 points) 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 $c
\cdot{\em general pattern} n^2$ stages are required for some respectably large constant $c$? (We are looking for a
here, one that results in $c
\cdot n^2$ stages for any $n$.)
\Part (10 points) 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{\bf Combining Stable Marriages} (18 points)
In this problem we examine a simple way to
{\em combine}
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'$ is 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 (3 points) $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 (5 points) Prove that, for any matchings $R,
\,R'$,
no man prefers $R$ or $R'$ to $R
\land R'$.
\Part (5 points) 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}
[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'|$, where $|S|$ denotes the size of set $S$. (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 (5 points) Prove an interesting result: for any stable matchings $R,
\,R'$, (i) $R
\land[Hint: use the results from (c)] R'$ is a matching
, and (ii) it is also stable.
\end{Parts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{Questions}
\end{document}