\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{\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.  Calculators are not allowed.
  \item 
  There are 4 problems totaling 80 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}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%   Structural Induction
%

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

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

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

\item The empty string, $\lambda$, (consisting of no parentheses) is an \SMU.
 \qquad (SMU-base)

\item If $s$ and $t$ are \SMU's, then $\mathbf{(} \cdot s \cdot \mathbf{)}
\cdot t$ is an \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[3] Prove the base case of the structural induction.

\solution[\newpage]{
\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[12] Below is a proof of the inductive case of the structural
induction, that is, a proof that if $r = \mathbf{(} s \mathbf{)} t$ for
$s,t \in \SMU$, then $P(r)$ holds.  Some possible justifications for lines
of the proof are also listed below.  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.  By \brule{0.3in}, we need only prove
that $rt' \in \SMU$.

\solution{
Def. of $P(r)$.
}

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

\solution{def. of $r$

associativity of string concatenation

def. of $t''$
}
Therefore, $rt' \in \SMU$ by \brule{0.3in}
\solution{
Case (SMU-ind) of the definition of \SMU.
}
\end{proof}

Justifications:
\begin{enumerate}



\item[(i)] structural induction hypothesis for $t$.

\item[(ii)] structural induction hypothesis for $s$.

\item[(iii)] structural induction hypothesis for $r$.

\item[(iv)] definition of $r$.

\item[(v)] definition of $t'$.

\item[(vi)] definition of $t''$.

\item[(vii)] definition of $P(r)$.

\item[(viii)] associativity of string concatenation.

\item[(ix)] $\lambda \in \SMU$.

\item[(x)] $\SMU =$ strings that ``count right''.

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

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

\end{enumerate}

\eparts

\end{examproblem}

\instatements{\newpage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%    State Machine
%

\begin{examproblem}{20}

A deck of cards numbered $1,\dots, 2n$ where $n\geq 1$ 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.

\begin{itemize}

\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 placed in one of two separate piles of
  cards as follows:
\begin{itemize}

  \item if the two cards are both even or are both odd, the smaller card is
        placed on the first pile and the larger card on the second pile.

  \item if one of the cards is even and the other is odd, of the piles is
    chosen and both cards are placed on it.

  \item If there are still cards in the deck, \emph{the deck is reshuffled}
  step (*) is repeated.  Otherwise, the process is over.

\end{itemize}

\end{itemize}

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 a triple $(S,P,Q)$ where $S$ is the sequence from top to bottom of
(the numbers of) the cards on the table, $P$ is the set of cards in one of
the piles, and $Q$ is the set in the other pile.

\bparts

\ppart[1] What are the possible start states of the machine?
\solution{$(S,\emptyset,\emptyset)$, where $S$ is any sequence of the
integers $1,\dots, 2n$.}

\solution[\newpage]{All triples $(S, \set{}, \set{})$, where $S$ is an
sequence containing every number from $1$ to $2n$ exactly once.}

\ppart[4] Transitions $(S,P,Q) \longrightarrow (S',P',Q')$ corresponding to
a card switch 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$, $P' = P$, $Q' = Q$.
\end{quote}
Describe the conditions that $S'$, $P'$ and $Q'$ must satisfy in order
for $(S,P,Q) \longrightarrow (S',P',Q')$ to be a transition corresponding
to removing two cards from the deck.

\solution[\vspace{3.25in}]{
There are $k < l$ such that $S = S_1 k l S_2$, and
\begin{itemize}

\item $S'$ is a sequence of the same numbers as are in the sequence
  $S_1S_2$.

\item if $k \equiv l \pmod 2$, then $P' = P \union \set{k}$, $Q' = Q \union
  \set{l}$.

\item if $k \not\equiv l \pmod 2$, then $P' = P \union \set{k,l}$, $Q' = Q$
  or $P' = P$, $Q' = Q \union \set{k,l}$.

\end{itemize}
}

\ppart[7] 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.3in}

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

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

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

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

\item $e_P \eqdef$ the number of even cards in the first pile \brule{0.3in}

\item $\abs{P} \eqdef$ the number of cards in the first pile \brule{0.3in}

\item $\abs{P} + \abs{Q} + \abs{S}$ \brule{0.3in}

\end{itemize}

\instatements{\newpage}

\ppart[8] Note that the number of odd cards in the first pile is $o_P
\eqdef \abs{P}-e_P$; likewise for $o_Q$.  Prove that
\[
o_P - e_P = o_Q - e_Q
\]
is an invariant of the state machine.

\solution[\vspace{4in}]{TBA}

\eparts

\end{examproblem}

\instatements{\newpage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%    Harmonic Sum and Asymptotics
%

\begin{examproblem}{10}

Prove that
\[
2\ln(n^3)+2 \sim \sum_{i=1}^{n} 6/i.
\]
You may assume any results from class 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}

\instatements{\newpage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%    Summing Series
%

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

\begin{enumerate}

\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$.  Thus, if
Sammy's interest rate is a reasonable 25\% per day, then $p = 1.25$.

\end{enumerate}

\bparts

\ppart[5] 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 after $d$ days?  Your answer need
not be a closed-form expression.

\solution[\vspace{2in}]{The client owes

\begin{eqnarray*}
((m + f) p + f) p & = & m p^2 + f p^2 + f p
\end{eqnarray*}

after two days, and owes

\begin{eqnarray*}
(((m + f) p + f) p + f) p & = & m p^3 + f p^3 + f p^2 + f p
\end{eqnarray*}

after three days.  Generalizing from this pattern, the client owes

\[
m p^d + f \cdot \sum_{k=1}^d p^k
\]

dollars after $d$ days.}

\ppart[5] Give a closed-form expression for the client's debt after
$d$ days.

\solution[\vspace{2in}]{Applying the formula for the sum of a
geometric series to the preceding expression gives:

\begin{eqnarray*}
m p^d + f \cdot \left(\frac{p^{d+1} - 1}{p - 1} - 1 \right)
\end{eqnarray*}
}

\eparts

\end{examproblem}

\instatements{\newpage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%    Basic Number Theory
%

\begin{examproblem}{15}
Let $p$ be a prime greater than 2, and let $x$ be an integer.  A {\em
square root of $x$ modulo $p$} is an integer $r$ such that:

\begin{eqnarray*}
r^2 \equiv x \pmod{p}
\end{eqnarray*}

\bparts

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

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

\ppart[10] Let $s$ be one square root of $x$ modulo $p$.  Complete the
 proof below that if $r$ is a square root of $x$ modulo $p$ then:

\[
r \equiv s \pmod{p}
\hspace{0.5in} \text{or else} \hspace{0.5in} r \equiv - s \pmod{p}
\]

{\em Proof.} By the definition of square root, we know that $s^2
\equiv x \pmod{p}$ and $r^2 \equiv x \pmod{p}$...

\solution[\newpage]{Therefore, $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}

\instatements{\newpage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%    Fermat's Theorem
%

\begin{examproblem}{10}
We have a deck with 54 cards.  (We left the 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{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[4] Suppose there are initially $i$ cards above card $C$.  The
number of cards above $C$ after $k$ perfect shuffles must be congruent
to

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

\ppart[6] Prove that 52 successive perfect shuffles restore the deck
to its original configuration.  (Use the back of this page if you need
more space.)

\solution{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{eqnarray*}
\text{\# of cards above $C$}
    & \equiv & 2^{52} \cdot i \pmod{53} \\
    & \equiv & 1 \cdot i \pmod{53} \\
    & \equiv & i \pmod{53}
\end{eqnarray*}

The second congruence uses Fermat's Theorem, which implies that
$2^{52} \equiv 1 \pmod{53}$.  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}

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

\end{document}
