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

%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query

\newcommand{\SMU}{\textrm{BMU}}

\newcommand{\mfigure}[3]{\bigskip\centerline{\resizebox{#1}{#2}{\includegraphics{#3}}}\bigskip}

\instatements{
\renewcommand{\exampreamble}{   % !! renew \exampreamble 
  \textbf{Circle the name of your Tutorial Instructor}:
  \begin{center}
  \renewcommand{\arraystretch}{1.5}
  \begin{tabular}{lllll}
Ching & Christos & Grant & Paul & Zardosht
  \end{tabular}
  \end{center}
  \begin{itemize}
  \item 
  This quiz is \textbf{closed book}, but you may have one sheet of paper with
  notes on both sides.
  \item 
  There are 5 problems, each worth 20 points.  Total time is 80 minutes. 
  \item 
  Write your solutions in the space provided.  If you need more
  space, write on the back of the sheet containing the problem.
  Please keep your entire answer to a problem on that problem's page.
  \item 
  You may assume all of the results presented in class and in the
  assigned reading.
  \item  
  \textbf{Be neat and write legibly}.  You will be graded not only on
  the correctness of your answer, but also on the clarity with which
  you express it.
  \item 
  GOOD LUCK!
  \end{itemize}}}

\begin{document} 
\quiz{2}

\begin{examproblem}{20} \textbf{Structural Induction}

The set of binary strings that match up (\emph{\SMU}'s) is defined
inductively as follows:
\begin{itemize}

\item The empty string, $\lambda$, is in \SMU.  \qquad (\SMU-base)

\item If $s, t \in \SMU$, then $\mathtt{0} s \mathtt{1} t \in
\SMU$. \qquad (\SMU-ind)

\end{itemize}

In this problem we ask you to complete a proof by structural induction that
\SMU\ is closed under concatenation, that is
\begin{quote}
If $s,t \in \SMU$, then the string $st$ is in \SMU.
\end{quote}
The induction hypothesis will be
\[
P(r) \eqdef \quad \forall t' \in \SMU\, [rt' \in \SMU].
\]

\bparts

\ppart[5] Prove the base case of the structural induction.

\solution[\vspace{2.0in}]{
The base case is $P(\lambda)$, that is, 
$$
\forall t' \in \SMU\, [\lambda t' \in \SMU].
$$
Since $\lambda$ is the empty string, $\lambda t'$ is just $t'$.
Hence, $P(\lambda)$ is really
$$
\forall t' \in \SMU\, [t' \in \SMU],
$$
which is trivially true.}

\ppart[15] Below is a proof of the inductive step of the structural
induction, that is, a proof that if $r = \mathtt{0} s \mathtt{1} t$ for
$s,t \in \SMU$, then $P(r)$ holds.  Some possible justifications for lines
of the proof are listed on the next page.  Fill in the number of the
justification of the various lines of the proof where indicated.

\begin{proof}
Suppose $t'$ is some string in \SMU.  According to \brule{0.4in}, we must
prove that $rt' \in \SMU$.

\solution{\it The correct answer was ``(8): definition of $P(r)$'' and was
worth 3 points. Partial credit of 2 points was given to answer ``(4):
structural induction hypothesis for $r$'' ---a subtle difference, really.}

Then
\begin{align*}
t t' & \in \SMU & \text{(by \brule{0.4in})}.
\end{align*}

\solution{\it (1): structural induction hypothesis for $t$ \quad[3 points].}

Let $t'' \eqdef t t'$.  Now
\begin{align*}
rt' & = (\mathtt{0}s\mathtt{1}t) t' & \text{(by \brule{0.4in})}\\
\insolutions{\intertext{\solution{\it (5): definition of $r$ \quad[2 points].}}}
    & =  \mathtt{0}s\mathtt{1} (t t') & \text{(by \brule{0.4in})}\\
\insolutions{\intertext{\solution{\it (10): associativity of string concatenation \quad[2 points].}}}
    & = \mathtt{0}s\mathtt{1} t''  & \text{(by \brule{0.4in})}
\end{align*}
\solution{\it (7): definition of $t''$ \quad[2 points].}
Therefore, $rt' \in \SMU$ by \brule{0.4in}
\solution{\it (14) case (\SMU-ind) of the definition of \SMU \quad[3 points].}
\end{proof}

Justifications:

\begin{enumerate}

\item structural induction hypothesis for $t$.

\item structural induction hypothesis for $t'$.

\item structural induction hypothesis for $s$.

\item structural induction hypothesis for $r$.

\item definition of $r$.

\item definition of $t'$.

\item definition of $t''$.

\item definition of $P(r)$.

\item definition of $P(t')$.

\item associativity of string concatenation.

\item $\lambda \in \SMU$.

\item $\SMU =$ strings that ``count right''.

\item Case (\SMU-base) of the definition of \SMU.

\item Case (\SMU-ind) of the definition of \SMU.

\end{enumerate}

\eparts

\end{examproblem}

\instatements{\newpage}
\begin{examproblem}{20}

A deck of cards numbered $1,\dots, 2n$, where $n$ is a positive integer, is
shuffled and placed on a table.  The following actions are carried out:

(*) A card that is not at the bottom of the deck is picked.  Then,

\begin{enumerate}

\item if the card below the one picked has a lower number, then the
  positions in the deck of the two cards are switched, and step (*) is
  repeated.

\item if the card below the one picked has a higher number, then both
cards are removed from the deck and discarded. If there are still cards in
the deck, \emph{the deck is reshuffled} and step (*) is repeated.
Otherwise, the process is over.

\end{enumerate}

This process can be modelled as a state machine whose states describe the
situation when a card is about to be picked at step (*).  Namely, a state
will be the sequence $S$, of (the numbers of) the cards in the deck on the
table, from top to bottom.

\bparts

\ppart[3] What are the possible start states of the machine?

\solution[\vspace{1.0in}]{
Any sequence of the integers $1,\dots, 2n$.

\textbf{Grading Policy:} You received full credit if you conveyed that the
start states were all possible permutations of the sequence of integers
$1, \dots, 2n$.  You received no credit if you did not correctly identify
the start states.

You received 1 point if instead of a sequence of numbers, you used the
language ``cards,'' ``deck,'' \etc, to represent a state.  Remember that a
State Machine has no notion of what a ``card'' or ``deck'' is.
It is necessary to \emph{represent} of the idea behind a ``deck''
with a standard mathematical object such as a
sequence of numbers.

If you have any questions, or feel that your grade does not reflect this
grading policy, please contact TA Paul Youn at \texttt{youn@mit.edu}.}

\ppart[5] Transitions $S \longrightarrow S'$ corresponding to case~1
\iffalse when two cards are switched\fi can be specified by the conditions
that
\begin{quote}
there are numbers $k > l$ such that $S = S_1 k l S_2$, and $S' = S_1 l k
S_2$.
\end{quote}
Describe the conditions on $S$ and $S'$ that specify a transition $S
\longrightarrow S'$ corresponding to case~2.\iffalse when two cards are
removed from the deck.\fi


\solution[\vspace{4in}]{There are $k < l$ such that $S = S_1 k l S_2$,
and $S'$ is a sequence of the same numbers as are in the sequence
$S_1S_2$.

\emph{Common Mistakes}: Some students simply wrote that $S'=S_1S_2$, 
which ignores the reshuffling of the deck following case 2. This
reshuffling aspect is the main part of the problem. Indeed, without
reshuffling the deck, the solution would be almost identical to the
example given. 

\textbf{Grading Policy:} Failure to somehow capture the idea that the deck
was reshuffled was -3 points.  Imprecise language was -1 point.

Writing something like: $\abs{S'}=\abs{S_1S_2}$ was -1 point.  This
indicated the right idea, and is a necessary condition, does not really
describe the reshuffling.  You needed to point out that not only are the
sets the same size, but also that the same cards are in $S'$ as are in
$S_1S_2$.}


\ppart[12] Indicate next to each of the following derived variables
which of these properties it has:
\begin{center}
\begin{tabular}{|ll|} \hline
constant              & C  \\  
strictly increasing   & SI \\
strictly decreasing   & SD \\
weakly increasing but not constant & WI \\
weakly decreasing but not constant & WD \\
 none of the above     & N  \\\hline
\end{tabular}
\end{center}

\begin{itemize}

\item $\abs{S} \eqdef$ the size of the deck \brule{0.4in}

\solution{Weakly Decreasing.

The first transition maintains the size of the deck, while the second
transition decreases the size of the deck.

\emph{Grading Policy}: Each part was graded all or none (2 points per
part).}

\item $\alpha \eqdef$ the number of ``out-of-order'' pairs $(i,j)$ such
that $i>j$ but card $i$ is above card $j$ in the deck. \brule{0.4in}

\solution{None of the Above.

The first transition decreases the number of ``out-of-order'' pairs (it
removes an out of order pair and otherwise leaves the deck as it was).
The second transition, however, can increase \emph{or} decrease the number
of out-of-order pairs.  If the deck originally has 10 out-of-order pairs,
after the reshuffling it can have less or more out-of-order pairs.

\emph{Common Mistakes}: Some people thought this was a decreasing 
quantity because at the end of the run, the deck is empty and has no
out-of-order pairs left.
}

\item $\abs{S} + \alpha$ \brule{0.4in}

\solution{None of the Above.

While $S$ is weakly decreasing, $\alpha$ is willy nilly all over the place
(that phrase should be used more often).  So, for example, in case 2,
after 2 cards are removed $\abs{S}$ decreases by 2, but who knows how many
out of order pairs exist after the reshuffling.}

\item $(\alpha, \abs{S})$ under lexicographic order \brule{0.4in}

\solution{None of the Above.

Under the first transition, $\alpha$ decreases while $\abs{S}$ stays the
same.  Right there we know that the quantity must be some decreasing form
or none of the above.  Under the second transition, however, we don't know
what happens to $\alpha$.  It could increase, or decrease, or stay the
same.  }

\item $(\abs{S}, \alpha)$ under lexicographic order \brule{0.4in}

\solution{
Strictly Decreasing.

In the first transition, the size of the deck stays the same, while
$\alpha$ decreases by 1.  In the second transition, $\abs{S}$ decreases by
2 as 2 cards are removed, and $\alpha$ does something.  However, since the
first term in the pair decreases, it doesn't matter what the second term
does under lexigraphical ordering.

\iffalse
Remember, lexigraphical ordering means: $x$ is less than $y$ if the first
term of $x$ is less than the first term of $y$ \emph{or} the first term of
$x$ = the first term of $y$ and the \emph{second} term of $x$ is less than
the second term of $y$. Continuing on for things that have more than 2
terms.\fi
}


\item $n^2\abs{S}+ \alpha$ \brule{0.4in}
\solution{
Strictly Decreasing.

This one was kind of tough.  In the first transition, $\alpha$ decreases
and $\abs{S}$ stays the same.  The quantity decreases.  In the second
transition, the $n^2\abs{S}$ decreases by $2n^2$, while $\alpha$ does
something.  How much can $\alpha$ increase by?  The worst case is that the
deck has no out-of-order pairs, and then the reshuffling puts the entire
deck in reverse order (maximum out-of-order pairs).  In this case, the top
card is out of order with the $2n-1$ cards below, the next card is out of
order with the $2n-2$ cards below, \etc  This yields the familiar
closed form $2n (2n-1)/2 = 2n^2-n$ which is less than $2n^2$.  So, the
quantity again decreases.}

\end{itemize}

\eparts

\end{examproblem}

\iffalse

\instatements{\newpage}
\begin{examproblem}{20}
Let $x$ and $n$ be integers with $n>1$.  A \emph{square root modulo $n$ of
$x$} is an integer, $r$, such that
\[
r^2 \equiv x \pmod{n}.
\]

\bparts

\ppart[5] List every square root modulo 7 of 4 in the set $\set{0, 1,
\ldots, 6}$.

\solution[\vspace{1.5in}]{2 and 5}

\ppart[15] Let $p$ be a prime, and let $s$ be a square root modulo $p$ of
$x$.  Show $r$ is a square root of $x$ modulo $p$ if and only if:
\[
r \equiv s \pmod{p}
\hspace{0.5in} \text{or} \hspace{0.5in} r \equiv - s \pmod{p}
\]

Hint: $p \mid (s - r) (s + r)$

\solution[\newpage]{Since $s^2 \equiv x \pmod{p}$ and $r^2 \equiv x
\pmod{p}$, we know that $s^2 \equiv r^2 \pmod{p}$.  This means that $p
\mid (s^2 - r^2)$, which is equivalent to $p \mid (s - r) (s + r)$.
Since $p$ is a prime, this holds if and only if either $p \mid s - r$
(which means $r \equiv s \pmod{p}$) or else $p \mid s + r$ (which
means $r \equiv - s \pmod{p}$).}

\eparts

\end{examproblem}
\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\instatements{\newpage}

\begin{examproblem}{20}
We have a deck with 54 cards.  (We left the two jokers in.)  In a {\em
perfect shuffle}, we cut the deck exactly in half and then interlace
the two halves.  The top card remains on the top after the shuffle,
and the bottom card remains on the bottom.  A perfect shuffle with an
8-card deck is illustrated below:

\bigskip
\centerline{\resizebox{5in}{!}{\includegraphics{figures/perfectshuffle}}}
\bigskip

Suppose there are initially $i$ cards above card $C$.  Then number of
cards above $C$ after a perfect shuffle is congruent to $2i$ modulo
53.  You may assume this without proof, though it is not difficult to
verify.

\bparts

\ppart[5] \label{ki} Suppose there are initially $i$ cards above card $C$.  The
number of cards above $C$ after $k$ perfect shuffles must be congruent
to \brule{1.0in} modulo 53.
\iffalse

\bigskip
\centerline{\fbox{\begin{minipage}{1.5in}
\instatements{\hspace{1.5in}\vspace{0.75in}}
\insolutions{\bigskip \centerline{$2^k \cdot i$} \bigskip}
\end{minipage}} \quad modulo 53.} 
\fi

\ppart[15] Prove that 52 successive perfect shuffles restore the deck to
its original configuration. \iffalse (Continue your argument on the back
side of this page if necessary.)\fi


\solution[\newpage]{The top and bottom cards never move.  Consider a
card $C$ with $i \in \set{1, 2, \ldots, 52}$ cards above.  After 52 perfect
shuffles:

\begin{align*}
\text{\# of cards above $C$}
    & \equiv 2^{52} \cdot i \pmod{53} & \text{(by part~(\ref{ki}))}\\
    & \equiv 1 \cdot i \pmod{53} & \text{(by Fermat's Theorem)}\\
    & \equiv i \pmod{53}
\end{align*}

If the number of cards above $C$ is congruent to $i \in \set{1, 2, \ldots,
52}$, then it must be equal to $i$.  Thus, every card returns to its
original position and the deck is restored after 52 perfect shuffles.}

\eparts

\end{examproblem}

\instatements{\newpage}
\begin{examproblem}{20}
Sammy the Shark is a financial service provider who offers loans on
the following terms.

\begin{itemize}

\item Sammy loans a client $m$ dollars in the morning.  This puts the
client $m$ dollars in debt to Sammy.

\item Each evening, Sammy first charges a ``service fee'', which increases
the client's debt by $f$ dollars, and then Sammy charges interest, which
multiplies the debt by a factor of $p$.  For example, if Sammy's interest
rate was 5\% per day, then $p$ would be $1.05$.

\end{itemize}

\bparts

\ppart[3] What is the client's debt at the end of the first day?

\solution[\vspace{1in}]{At the end of the first day, the client owes
  Sammy $(m + f) p = m p + f p$ dollars.
  
  \emph{Grading Policy}: There was one point taken off if 1.05 was used
  instead of $p$, or $1+p$ was used instead of $p$.}

\ppart[5] What is the client's debt at the end of the second day?

\solution[\vspace{1in}]{$((m + f) p + f) p = m p^2 + f p^2 + f p$

  \emph{Grading Policy}: Almost everybody got either full credit, or
  no credit on this.  One point was taken off if the second day was
  confused for the first day.}

\ppart[12] Write a formula for the client's debt after $d$ days.  A
correct \emph{closed form} formula gets full credit; a correct formula
\emph{not} in closed form gets half credit.

\solution{
The client's debt after three days is
\[
(((m + f) p + f) p + f) p  =  m p^3 + f p^3 + f p^2 + f p.
\]
Generalizing from this pattern, the client owes
\begin{equation}\label{mpd}
m p^d + \sum_{k=1}^d fp^k
\end{equation}
dollars after $d$ days.  Applying the formula for a geometric sum
to~\eqref{mpd} gives:
\[
m p^d + f \cdot \paren{\frac{p^{d+1} - 1}{p - 1} - 1}.
\]

\emph{Grading Policy}: Correct, closed form solutions were given 12
points.  Correct formulas not in closed form were given 6 points.  In
addition, partial credit was given if incorrect closed form solutions
were derived from correct formulas not in closed form.}

\eparts

\end{examproblem}


\instatements{\newpage}
\begin{examproblem}{20}

Prove that $2\ln(n^3)+2$ and $\sum_{i=1}^{n} 6/i$ are asymptotically equal
($\sim$).  You may assume any results from class, text, or Notes in your
proof.

\solution[\vspace{3in}]{ The left-hand side equals $2+ 6\ln n \sim 6\ln n$,
while the right-hand side is $6 H_n$; but we know that $H_n\sim\ln n$, and
hence $6\ln n\sim 6H_n$, as well.}

\end{examproblem}


\end{document}
