\Question{Hit or Miss?}
State which of the proofs below is correct or incorrect.
For the incorrect ones, please explain clearly where the logical error in the proof lies.
Simply saying that the claim or the induction hypothesis is false is \emph{not} a valid explanation of what is wrong with the proof.
You do not need to elaborate if you think the proof is correct.
\begin{Parts}
\Part
\textbf{Claim:} For all positive numbers $n \in \mathbb{R}$, $n^2 \ge n$.
\begin{proof}
The proof will be by induction on $n$. \\
\emph{Base Case:} $1^2 \ge 1$. It is true for $n=1$. \\
\emph{Inductive Hypothesis:} Assume that $n^2 \ge n$. \\
\emph{Inductive Step:} We must prove that $(n+1)^2 \ge n+1$.
Starting from the left hand side,
\begin{align*}
(n+1)^2 &= n^2+2n+1 \\
&\ge n+1.
\end{align*}
Therefore, the statement is true.
\end{proof}
\Part
\textbf{Claim:} For all negative integers $n$, $(-1) + (-3) + \cdots + (2n+1) = -n^2$.
\begin{proof}
The proof will be by induction on $n$. \\
\emph{Base Case:} $-1 = -(-1)^2$. It is true for $n=-1$. \\
\emph{Inductive Hypothesis:} Assume that $(-1) + (-3) + \cdots + (2n+1) = -n^2$. \\
\emph{Inductive Step:} We need to prove that the statement is also true for $n-1$ if it is true for $n$, that is,
$(-1) + (-3) + \cdots + (2(n-1)+1) = -(n-1)^2$. Starting from the left hand side,
\begin{align*}
(-1) + (-3) + \cdots + (2(n-1)+1)
&= ((-1) + (-3) + \cdots + (2n+1))+(2(n-1)+1) \\
&= -n^2 + (2(n-1)+1) \quad \text{(Inductive Hypothesis)}\\
&= -n^2 + 2n - 1 \\
&= -(n^2 - 2n + 1) \\
&= -(n-1)^2.
\end{align*}
Therefore, the statement is true.
\end{proof}
% \Part
% \textbf{Claim:} For all positive integers $n$, $\sum\limits_{i=0}^n 2^{-i} \le 2$.
% \begin{proof}
% We will prove a stronger statement, that is, $\sum\limits_{i=0}^n 2^{-i} = 2-2^{-n}$, by induction on $n$. \\
% \emph{Base Case:} $n=1 \le 2-1$. It is true for $n=1$. \\
% \emph{Inductive Hypothesis:} Assume that $\sum\limits_{i=0}^n 2^{-i} = 2-2^{-n}$. \\
% \emph{Inductive Step:} We must show that $\sum\limits_{i=0}^{n+1} 2^{-i} = 2-2^{-(n+1)}$. Starting from the left hand side,
% \begin{align*}
% \sum\limits_{i=0}^{n+1} 2^{-i}
% &= \sum\limits_{i=0}^{n} 2^{-i} + 2^{-(n+1)} \\
% &= (2-2^{-n})+2^{-(n+1)} \quad\text{(Inductive Hypothesis)} \\
% &= 2-2^{-(n+1)}.
% \end{align*}
% Since $\sum\limits_{i=0}^n 2^{-i} = 2-2^{-n} \le 2$, the claim is true.
% \end{proof}
\Part
\textbf{Claim:} For all nonnegative integers $n$, $2n=0$.
\begin{proof}
We will prove by strong induction on $n$. \\
\emph{Base Case:} $2 \times 0 = 0$. It is true for $n=0$. \\
\emph{Inductive Hypothesis:} Assume that $2k=0$ for all $0 \le k \le n$. \\
\emph{Inductive Step:} We must show that $2(n+1)=0$. Write $n+1 = a+b$ where $0 < a,b \le n$.
From the inductive hypothesis, we know $2a = 0$ and $2b=0$, therefore,
\begin{align*}
2(n+1) = 2(a+b) = 2a + 2b = 0+0 =0.
\end{align*}
The statement is true.
\end{proof}
% \Part
% \textbf{Claim:} Every positive integer $n\ge2$ has a unique prime factorization. \\
% In other words, let $2 \le p_1, p_2, \hdots, p_i \le n$ be all prime numbers that divide $n$,
% there is only one unique way to write $n$ as a product of primes,
% \begin{align*}
% n = p_1^{d_1} \cdot p_2^{d_2} \dotsm p_i^{d_i},
% \end{align*}
% where $d_1, d_2, \hdots, d_i \in \mathbb{N}$.
% \begin{proof}
% We will prove by strong induction on $n$. \\
% \emph{Base Case:} 2 is a prime itself. It is true for $n=2$. \\
% \emph{Inductive Hypothesis:} Assume that the statement is true for all $2 \le k \le n$. \\
% \emph{Inductive Step:} We must prove that the statement is true for $n+1$.
% If $n+1$ is prime, then it itself is a unique prime factorization.
% Otherwise, $n+1$ can be written as $x \times y$ where $2 \le x,y \le n$.
% From the inductive hypothesis, both $x$ and $y$ have unique prime factorizations.
% The product of unique prime factorizations is unique, therefore, $n+1$ has a unique prime factorization.
% \end{proof}
\end{Parts}
\Question{A Coin Game}
Your "friend" Stanley Ford suggests you play the following game with him. You each start with a single stack of $n$ coins. On each of your turns, you select one of your stacks of coins (that has at least two coins) and split it into two stacks, each with at least one coin. Your score for that turn is the product of the sizes of the two resulting stacks (for example, if you split a stack of 5 coins into a stack of 3 coins and a stack of 2 coins, your score would be $3 \cdot 2 = 6$). You continue taking turns until all your stacks have only one coin in them. Stan then plays the same game with his stack of $n$ coins, and whoever ends up with the largest total score over all their turns wins.
Prove that no matter how you choose to split the stacks, your total score will always be $\frac{n(n - 1)}{2}$. (This means that you and Stan will end up with the same score no matter what happens, so the game is rather pointless.)
\Question{Grid Induction}
Pacman is walking on an infinite 2D grid.
He starts at some location $(i, j) \in \mathbb{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 step down, to $(i, j-1)$.
\item Walk one step 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)$; if Pacman is instead at $(3, 2)$, he could walk either to $(2, 2)$ or $(3, 1)$.
Prove by induction that no matter how he walks, he will always reach $(0, 0)$ in finite time. (\textit{Hint}: Try starting Pacman at a few small points like $(2, 1)$ and looking all the different paths he could take to reach $(0, 0)$. Do you notice a pattern?)
\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 day 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$ days for the algorithm to terminate, because at least one woman is deleted from at least one list on each day. Can you construct an instance (a set of preference lists) with $n$ men and $n$ women so that at least $n^2/2$ days 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). Prove that this modification will not change what pairing the algorithm outputs.
\end{Parts}
\Question{Optimal Partners}
In the notes, we proved that the Stable Marriage Algorithm always outputs the male-optimal pairing. However, we never explicitly showed why it is guaranteed that putting every man with his best choice results in a pairing at all. Prove by contradiction that no two men can have the same optimal partner. (Note: your proof should not rely on the fact that the Stable Marriage Algorithm outputs the male-optimal pairing.)
\Question{Examples or It's Impossible}Determine if each of the situations below is possible with the traditional propose-and-reject algorithm.
If so, give an example with at least $3$ men and $3$ women. Otherwise, give a brief proof as to why it's impossible.
\begin{Parts}
\Part Every man gets his first choice.
\Part Every woman gets her first choice, even though her first choice does not prefer her the most.
\Part Every woman gets her last choice.
\Part Every man gets his last choice.
\Part A man who is second on every woman's list gets his last choice.
\end{Parts}