\documentclass[12pt,twoside]{article}   
\usepackage{latex-macros/course}% !! Use the macros

\renewcommand{\reading}{Notes for
\href{http://theory.csail.mit.edu/classes/6.042/spring06/ln4.pdf}{Week4}}

\begin{document}
\problemset{3}                 % !! Start the problem set with its number


%%%%%%%%%%%%
%% Problem 1
%%%%%%%%%%%%
\begin{problem}
  Consider the following recursive definition of the
  set $S$ of binary strings.
  \begin{itemize}
  \item $\lambda, 0,1 \in S$.
  \item If $s \in S$, then $0s0$ and $1s1 \in S$.
  \end{itemize}
  \bparts
  \ppart What common property do all elements of $S$ have?
  \ppart Prove your claim in part (a) by structural induction.
  \eparts
\end{problem}

%%%%%%%%%%%%
%% Problem 2
%%%%%%%%%%%%
\begin{problem}
  Fractals are yet another example of a mathematical object that can
  be defined recursively.  In this problem, we consider the Koch
  snowflake.  Any Koch snowflake can be constructed by the following
  recursive definition.
  \begin{itemize}
  \item Base Case: An equilateral triangle is a Koch snowflake.
  \item Recursive case: Let $K$ be a Koch snowflake, and let $l$ be a
    line segment on the snowflake.  Remove the middle third of $l$,
    and replace it with two line segments of the same length as is
    done below:

    The resulting figure is also a Koch snowflake.
  \end{itemize}
  
  Prove by structural induction that the area inside any Koch
  snowflake is of the form $q\sqrt{3}$, where $q$ is a rational
  number.

\end{problem}

%%%%%%%%%%%%
%% Problem 2
%%%%%%%%%%%%
\begin{problem}
  
\end{problem}

%%%%%%%%%%%%
%% Problem 3
%%%%%%%%%%%%
\begin{problem}

\end{problem}

%%%%%%%%%%%%
%% Problem 4
%%%%%%%%%%%%
\begin{problem}
\end{problem}

%%%%%%%%%%%%
%% Problem 5
%%%%%%%%%%%%
\begin{problem}  
\end{problem}

%%%%%%%%%%%%
%% Problem 6
%%%%%%%%%%%%
\begin{problem}
\end{problem}

%%%%%%%%%%%%
%% Problem 7
%%%%%%%%%%%%
\begin{problem}
  
  Consider an instance of the matching problem with $n$ boys and $n$
  girls.  Call a person {\em unlucky} if he or she is matched up with
  one of his or her $\floor{\frac{n}{2}}$ last choices.  In this
  problem, we will prove the following:
 
  {\bf Theorem} The matching algorithm from class never produces a
  matching in which every person is unlucky.

Fix an execution of the matching algorithm.  Define the variables 
$B_i, G_i, i \in \{ 1, 2, \ldots, n \}$ as follows:
\begin{description}
\item $B_i = j$ if the $i$-th boy is currently courting the $j$-th girl
on his list
\item $G_i$ is the number of boys that the $i$-th girl has rejected.
\end{description}

\ppart
Show that $\sum_{i=1} ^n B_i - \sum_{i=1} ^n G_i$ is preserved at each
step of the matching algorithm.

\solnospace{
\medskip
%\textbf{Solution:}

Let $S = \sum_{i=1} ^n B_i - \sum_{i=1} ^n G_i$.  We must prove that
this quantity remains constant after any transition.

Let's consider an arbitrary girl $g_j$ at some step $t$:
\begin{itemize}

\item If $g_j$ has no suitors, $G_j$ remain the same, and no $B_i$ is
involved here.  So $S$ is preserved in this case.

\item If $g_j$ has at least one suitor, then let $k$ be the number of
suitors she has.  Then she rejects the $k-1$ boys she likes least and
tells the boy she likes most to come back the next day.  So that $G_j$
increases by $k-1$ while $k-1$ $B_i$s increase by $1$ (for the rejected
boys) and one $B_i$ remains constant (for the accepted boy).  Overall,
S is preserved in this case as well.
\end{itemize}

Since this is true for an arbitrary girl, it is true for all girls at
step $t$. Each boy is courting exactly one girl, so that if we
consider all girls along with their suitors, we are automatically
considering all boys.

%Let $S = \sum_{i=1} ^n B_i - \sum_{i=1} ^n G_i$.  Suppose that at step
%$t$, boy $b_i$ proposes to girl $g_j$.  There are three possible outcomes:
%
%If $g_j$ has not had any previous proposals, she must accept.  In this
%case, none of the $B_i$s and none of the $G_j$s change, so $S$ is preserved.
%
%If $g_j$ rejects, then $G_j$ increases by 1, $B_i$ increases by 1, and
%the other $B$s and $G$s remain the same.  $S$ is preserved again.
%
%If $g_j$ accepts $b_i$ because she likes him better than her current
%mate $b_{i'}$, then $G_j$ increases by 1, $B_{i'}$ increases by 1, and
%the other $B$s and $G$s remain the same.  $S$ is preserved in this case
%as well.
}

\ppart
Formulate an invariant that you can use to prove the theorem, and 
show that your invariant is correct.

\solnospace{
\medskip
%\textbf{Solution:}
Our invariantis that the value of $S$ is always equal to the number of
boys (or girls); $P : S = n$.  In the initial state, this is true
because everyone is courting the first girl on their list.  From part
(a) it follows that all transitions preserve the truth value of $P$.
Therefore $P$ is an invariant.  }

\ppart
Use your invariant to prove the theorem.

\solnospace{
\medskip
%\textbf{Solution:}
We prove the statement by contradiction.  Consider a match M in which
every person is unlucky.  Then, in the final state:
\begin{description}
\item For every $i \in \{ 1, \ldots, n \}$,
$B_i \geq n + 1 - \floor{\frac{n}{2}}$ ($B_i$ is matched with a girl
ranked between $n + 1 - \floor{\frac{n}{2}}$ and $n +1 - 1 =n$), and
\item For every $i \in \{ 1, \ldots, n \}$,
$G_i \leq \floor{\frac{n}{2}} - 1$, ($G_i$ has rejected less than
$\floor{\frac{n}{2}}$ boys, otherwise she would be matched with one
{\em not} within her last $\floor{\frac{n}{2}}$ choices.
\end{description}

\begin{eqnarray*}
\sum_{i=1} ^n B_i - \sum_{i=1} ^n G_i & = & 
\sum_{i=1} ^n B_i - G_i \\
& \geq & \sum_{i=1} ^n \left(n + 1 - \floor{\frac{n}{2}}\right) - \left(\floor{\f
rac{n}{2}} - 1\right) \\
& = & \sum_{i=1} ^n 2 + 2 \left(\frac{n}{2} - \floor{\frac{n}{2}}\right)
\end{eqnarray*}

Since $(\frac{n}{2} - \floor{\frac{n}{2}}) \geq 0$, it follows that 
$\sum_{i=1} ^n B_i - \sum_{i=1} ^n G_i \geq 2n$. \\ This
violates the invariant $P$.
}


\end{problem}

\end{problem}

\end{document}
