\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


\begin{problem}
  Let $x$ be a string of characters.  In this question, we consider
  the reverse of a string, which we write $r(x)$.  For example, if $x
  = 10110$, then $r(x) = 01101$.  \bparts \ppart Give a recursive
  definition of $r(x)$, the reverse of a string.  \ppart Use your
  recursive definition in part (a) to prove that for any two strings,
  $x,y$:
  $$r(xy) = r(y)r(x).$$
  \eparts
\end{problem}

\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.  See
    Figure \ref{fig:koch} below.
    \begin{figure}[h]
      \centering
      \includegraphics[width=3.0in]{koch}
      \caption{Recursive case of Koch snowflake definition} \label{fig:koch}
    \end{figure}
    
    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}

\begin{problem}
  Recall the matching problem with $n$ boys and $n$ girls.  We know
  from the notes that the matching algorithm is boy-optimal.  In this
  problem, we further explore the notion of boy and girl optimal.

  \bparts 
  
  \ppart Suppose that one boy, Ben Bitdiddle, is completely
  undesirable -- that is, he is at the bottom of the preference list
  of every girl.  Is it possible that Ben ends up matched with the
  girl at the top of his preference list?  Prove your claim.
  
  \ppart Now, consider the reverse scenario -- that some girl is
  completely undesirable, i.e. at the bottom of the preference list of
  every boy.  Is it possible that she ends up matched with the boy at
  the top of his preference list?  Prove your claim.

  \eparts

\end{problem}

\begin{problem}
  
  In the previous problem, we considered the situation that somebody
  completely undesirable is paired with his or her first choice.  In
  this problem, we explore whether or not everybody can be paired with
  a slightly undesirable person.
  
  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{itemize}
  \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{itemize}

  \bparts
  \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.

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

\ppart
Use your invariant to prove the theorem.
\eparts

% \solnospace{
% \medskip
% %\textbf{Solution:}
% Our invariant is 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.  }

% \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{document}
