\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}]{
\begin{proof}
\textbf{Base Case} ($r = \lambda$):
If $t' \in \SMU$, then $rt'=\lambda t'= t' \in \SMU$.  That is $P(r)$ holds. 
\end{proof}}

\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{
Def. of $P(r)$.
}

Then
\begin{align*}
t t' & \in \SMU & \text{(by \brule{0.4in})}.
\end{align*}
\solution{Structural induction hypothesis for $t$.}
Let $t'' \eqdef t t'$.  Now
\begin{align*}
rt' & = (\mathtt{0}s\mathtt{1}t) t' & \text{(by \brule{0.4in})}\\
    & =  \mathtt{0}s\mathtt{1} (t t') & \text{(by \brule{0.4in})}\\
    & = \mathtt{0}s\mathtt{1} t''  & \text{(by \brule{0.4in})}
\end{align*}

\solution{def. of $r$

associativity of string concatenation

def. of $t''$
}
Therefore, $rt' \in \SMU$ by \brule{0.4in}
\solution{
Case (\SMU-ind) of the definition of \SMU.
}
\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$.}

\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$.}


\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}

\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}

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

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

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

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

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

\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$}

\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}.
\]
}

\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}
