\documentclass[12pt,twoside]{article}
\input{macros-course}

\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{graphics}
\usepackage{amsfonts}
\usepackage{amssymb}

\addtolength{\textheight}{.05in}

\begin{document}

\pset{7}{April 8, 2003}{Start of class on Tuesday, April 15}

%\newcommand{\solution}[1]{}                          % hide solutions
\newcommand{\solution}[1]{\textbf{Solution.} #1}    % show solution

\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}
\newcommand{\ex}[1]{\text{Ex} \left[ #1 \right] }
\newcommand{\pr}[1]{\text{Pr} \left\{ #1 \right\} }

\begin{problems}


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

\problem Provide recursive definitions of the following sets and functions:

\begin{problemparts}

\problempart The set $S = \{ 2^a 3^b 5^c \mid a, b, c \in \mathbb{N}
\}$.

\solution{ We can define the set $S$ recursively as follows:

\begin{enumerate}
\item $1 \in S$
\item If $n \in S$, then $2n$, $3n$, and $5n$ are in $S$.
\end{enumerate}
}

\problempart The set $L = \{ (a, b) \in \mathbb{Z} \times \mathbb{Z}
\mid \text{$a + 2b = 3k$ for some $k \in \mathbb{Z}$} \}$.

\solution{
\begin{enumerate}
\item $(0, 0) \in L$
\item If $(a, b) \in L$, then $(a + 3, b)$, $(a - 3, b)$, $(a + 2, b -
1)$, and $(a - 2, b + 1)$ are in $L$.
\end{enumerate}
}

\problempart The set $\Sigma^*$, which consists of all finite strings
of symbols drawn from the set $\{ p, n, d, q \}$.  (We'll use this set
$\Sigma^*$ in the next three problem parts as well.)

\solution{
\begin{enumerate}
\item The empty string $\lambda$ is in $\Sigma^*$.
\item If $\alpha \in \Sigma^*$, then $p\alpha$, $n\alpha$, $d\alpha$,
$q\alpha$ are in $\Sigma^*$.
\end{enumerate}
}

\problempart Recursively define a function $l : \Sigma^* \to
\mathbb{N}$ that maps each string in $\Sigma^*$ to its length.

\solution{
\begin{enumerate}
\item $l(\lambda) = 0$.
\item If $\alpha \in \Sigma^*$, and $\beta \in \{p, n, d, q\}$, then
$l(\beta \alpha) = 1 + l(\alpha)$.
\end{enumerate}
}

\problempart Suppose that $p$ stands for penny, $n$ stands for nickel,
$d$ stands for dime, and $q$ stands for quarter.  Recursively define a
function $m : \Sigma^* \to \mathbb{N}$ that maps each string in
$\Sigma^*$ to the monetary value of the corresponding pile of change.

\solution{
\begin{enumerate}
\item $m(\lambda) = 0$.
\item If $\alpha \in \Sigma^*$, then $m(p \alpha) = 1 + m(\alpha)$.
\item If $\alpha \in \Sigma^*$, then $m(n \alpha) = 5 + m(\alpha)$.
\item If $\alpha \in \Sigma^*$, then $m(d \alpha) = 10 + m(\alpha)$.
\item If $\alpha \in \Sigma^*$, then $m(q \alpha) = 25 + m(\alpha)$.
\end{enumerate}
}

\problempart Recursively define a function $r : \Sigma^* \to \Sigma^*$
that maps each string $\sigma_1 \sigma_2 \ldots \sigma_{n}$ in
$\Sigma^*$ to its reverse:

\[
\sigma_n \sigma_{n-1} \ldots \sigma_1
\]

\solution{
\begin{enumerate}
\item $r(\lambda) = \lambda$.
\item If $\alpha \in \Sigma^*$ and $\beta \in \{p, n, d, q\}$, then
$r(\beta \alpha) = r(\alpha) \beta$.
\end{enumerate}
}

\end{problemparts}

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

\problem This problem was cancelled due to an error.

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

\problem Let $B$ be the set of balanced parentheses strings.  We want
to include all strings of parentheses that might appear in a valid
arithmetic expression, such as $(()())$, $((()))()$, and
$()((()())())$.  We want to exclude strings such as $)($, $((()$, and
$(()()))$.

\begin{problemparts}

\problempart Give a recursive definition of $B$, the set of balanced
parentheses strings.

\solution{
We define $S$ recursively as follows:

\begin{enumerate}
\item $\lambda \in B$
\item If $\alpha \in B$, then $(\alpha) \in B$.
\item If $\alpha, \beta \in B$, then $\alpha \beta \in B$.
\end{enumerate}
}

\problempart Show how $()((()())())$ is generated by the rules in your
definition.

\solution{
We reason as follows:

\begin{tabular}{rll}
a. & $\lambda \in B$ & rule 1 \\
b. & $() \in B$ & a and rule 2 \\
c. & $()() \in B$ & b and rule 3 \\
d. & $(()()) \in B$ & c and rule 2 \\
e. & $(()())() \in B$ & d, b, and rule 3 \\
f. & $((()())()) \in B$ & e and rule 2 \\
g. & $()((()())()) \in B$ & b, e and rule 3
\end{tabular}
}

\problempart Give a recursive definition of $P$, the set of all finite
parentheses strings, including those that are not balanced.

\solution{
We can define $P$ recursively as follows:

\begin{enumerate}
\item $\lambda \in B$
\item If $\alpha \in B$, then $( \alpha \in B$ and $) \alpha \in B$.
\end{enumerate}
}

\problempart Recursively define the functions $L : P \to \mathbb{N}$
and $R : P \to \mathbb{N}$ so that $L[\alpha]$ is the number of left
parentheses in the string $\alpha$ and $R[\alpha]$ is the number of
right parentheses.  (We are using square brackets here, because the
argument of $L$ is a string of parentheses!)

\solution{The functions $L$ and $R$ can be defined recursively as
follows.  For the function $L$, we have:

\begin{enumerate}
\item $L[\lambda] = 0$, $L[(] = 1$, and $L[)] = 0$.
\item For $\alpha, \beta \in P$, $L[\alpha \beta] = L[\alpha] + L[\beta]$.
\end{enumerate}

And for the function $R$, we have:

\begin{enumerate}
\item $R[\lambda] = 0$, $R[(] = 0$, and $R[)] = 1$.
\item For $\alpha, \beta \in P$, $R[\alpha \beta] = R[\alpha] + R[\beta]$.
\end{enumerate}
}

\problempart Use structural induction to prove that $L[\alpha] =
R[\alpha]$ for all $\alpha \in B$.

\solution{The proof is by structural induction on the definition of
balanced parentheses strings.  Let $P(\gamma)$ be the proposition that
$L[\gamma] = R[\gamma]$.  For the base element $\lambda$, we have
$L[\lambda] = R[\lambda] = 0$.  Next, we show that that $P(\gamma)$
holds for every recursively-generated balanced parentheses string
$\gamma$, given that it holds for the generating elements.  There are
two cases to consider.

\begin{enumerate}
\item Suppose that $\gamma = ( \alpha )$ for some $\alpha \in B$.  Then
we have:

\beqn
L[\gamma]
	& = &	L[( \alpha )] \\
	& = &	L[(] + L[ \alpha] + L[)] \\
	& = &	L[\alpha] + 1 \\
	& = &	R[\alpha] + 1 \\
	& = &	R[(] + R[\alpha] + R[)]\\
	& = &	R[( \alpha )] \\
	& = &	R[\gamma]
\eeqn

\item Suppose that $\gamma = \alpha \beta$ for some $\alpha, \beta \in
B$.  Then we can reason as follows:

\beqn
L[\gamma]
	& = &	L[\alpha \beta] \\
	& = &	L[\alpha] + L[\beta] \\
	& = &	R[\alpha] + R[\beta] \\
	& = &	R[\alpha \beta] \\
	& = &	R[\gamma]
\eeqn

\end{enumerate}

Thus, $L[\gamma] = R[\gamma]$ for every balanced parentheses string
$\gamma$ by structural induction.
}

\problempart Use structural induction to prove that for every prefix
$\alpha$ of a balanced parentheses string, we have $L[\alpha] \geq
R[\alpha]$.

\solution{The proof uses structural induction on the definition of
balanced parentheses strings.  Let $P(\gamma)$ be the proposition that
for every prefix $\gamma'$ of the balanced parentheses string
$\gamma$, we have $L[\gamma'] \geq R[\gamma']$.

First, we show that the proposition holds for the basis element.  When
$\gamma$ is the empty string $\lambda$, we must have $L[\gamma'] =
R[\gamma'] = 0$.  Next, we show that the proposition holds for each
recursively-generated balanced parentheses string $\gamma$, provided
it holds for the generating strings.  There are two cases.

\begin{enumerate}

\item Suppose that $\gamma = ( \alpha )$ for some $\alpha \in B$.  If
the prefix $\gamma'$ is empty, then $L[\gamma'] = R[\gamma'] = 0$.  If
$\gamma'$ is all of $\gamma$, then $L[\gamma'] = R[\gamma']$, because
$\gamma' = \gamma$ is a balanced parentheses string.  Otherwise,
$\gamma'$ consists of $($ together with a prefix $\alpha'$ of
$\alpha$.  Thus, we have:

\beqn
L[\gamma']
	& = &	L[( \alpha' ] \\
	& = &	L[(] + L[\alpha'] \\
	& = &	1 + L[\alpha'] \\
	& \geq & 1 + R[\alpha'] \\
	& > &	R[\alpha'] \\
	& = &	R[(] + R[\alpha'] \\
	& = &	R[( \alpha'] \\
	& = &	R[\gamma']
\eeqn

\item Otherwise, suppose that $\gamma = \alpha \beta$ for some
$\alpha, \beta \in B$.  As before, $L[\gamma'] = R[\gamma']$ if
$\gamma'$ is the empty string or all of $\gamma$.  If $\gamma'$ is a
prefix of $\alpha$, then the claim holds by induction.  If $\gamma'$
contains all of $\alpha$ and a prefix $\beta'$ of $\beta$, then we
have:

\beqn
L[\gamma']
	& = &	L[\alpha \beta'] \\
	& = &	L[\alpha] + L[\beta'] \\
	&\geq&	R[\alpha] + R[\beta'] \\
	& = &	R[\gamma']
\eeqn

Thus, by structural induction, $L[\gamma'] \geq R[\gamma']$ for every
prefix of every balanced parentheses string $\gamma$

\end{enumerate}
}

\end{problemparts}

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

\problem Suppose that you have a regular deck of cards arranged as
follows, from top to bottom:

\[
A \heartsuit\ 2 \heartsuit \dots K \heartsuit\ 
A \spadesuit\ 2 \spadesuit \dots K \spadesuit\ 
A \clubsuit\ 2 \clubsuit \dots K \clubsuit\ 
A \diamondsuit\ 2 \diamondsuit \dots K \diamondsuit
\]

Only two operations on the deck are allowed: {\em inshuffling} and
{\em outshuffling}.  In both, you begin by cutting the deck exactly in
half, taking the top half into your right hand and the bottom into
your left.  Then you shuffle the two halves together so that the cards
are perfectly interlaced; that is, the shuffled deck consists of one
card from the left, one from the right, one from the left, one from
the right, etc.  The top card in the shuffled deck comes from the
right hand in an outshuffle and from the left hand in an inshuffle.

\begin{problemparts}

\problempart Model this problem as a state machine.

\solution{Let the set of states $Q$ be all the possible orderings of
the deck of cards.  Let the set of start states $Q_0$ consist of the
single ordering listed above.  For each state $(c_1, \ldots c_{52}) \in
Q$, there are two transitions in $\delta$:

\beqn
(c_1, \ldots c_{52})
	& \rightarrow &
		(c_1, c_{27}, c_2, c_{28}, \ldots, c_{26}, c_{52}) \\
(c_1, \ldots c_{52})
	& \rightarrow &
		(c_{27}, c_1, c_{28}, c_2, \ldots, c_{52}, c_{26})
\eeqn
}

\problempart Use the Invariant Theorem to prove that you can not make
the entire first half of the deck black through a sequence of
inshuffles and outshuffles.

\solution{The proof uses the Invariant Theorem.  Define two cards to
be {\em opposites} if the sum of their positions is 53.  For example,
the top card is opposite the bottom card, the second card from the top
is opposite the second from the bottom, etc.

Let $P$ be the property that $A \heartsuit$ is opposite $K
\diamondsuit$, $2 \heartsuit$ is opposite $Q \diamondsuit$, etc., as
in the initial configuration.  We claim that $P$ is an invariant.
Suppose that $P$ holds for a given state and consider the two types of
transition out of that state.  Note that, for both types of
transition, cards in opposite positions are mapped to opposite
positions.  Therefore, the property $P$ still holds.  Thus, $P$ is an
invariant.

Note that the invariant holds for the start state by definition.
However, the invariant can not hold when all black cards are in the
top half of the deck; in that case, every black card is opposite a red
card.  Therefore, by the Invariant Theorem, that state is not
reachable.}

\end{problemparts}

Note: Discovering a suitable invariant can be difficult!  The standard
approach is to identify a bunch of reachable states and then look for
a pattern, some feature that they all share.\footnote{If this does not
work, consider twitching and drooling until someone takes the problem
away.}

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

\problem A robot named ``Spike'' wanders around a two-dimensional
grid.  He starts out at $(0,0)$ and is allowed to take four different
types of step:

\begin{enumerate}
\item $(+2,-1)$
\item $(+1,-2)$
\item $(+1,+1)$ 
\item $(-3,0)$ 
\end{enumerate}

Thus, for example, Spike might walk as follows.  The types of his
steps are listed above the arrows.

\[
(0,0) \stackrel{1}{\rightarrow}
(2,-1) \stackrel{3}{\rightarrow}
(3,0) \stackrel{2}{\rightarrow}
(4,-2) \stackrel{4}{\rightarrow}
(1,-2) \rightarrow \ldots
\]

Spike's true love, a perky toaster named ``Daisy'', awaits at $(0,2)$.

\begin{problemparts}

\problempart Describe a state machine model of this problem.

\solution{Let the set of states $Q$ be $\mathbb{Z} \times \mathbb{Z}$.
Let the set of start states $Q_0$ consist of the single state $(0,
0)$.  For each $(x, y) \in Q$, there are four transitions in $\delta$:

\beqn
(x, y) & \rightarrow & (x + 2, y - 1) \\
(x, y) & \rightarrow & (x + 1, y - 2) \\
(x, y) & \rightarrow & (x + 1, y + 1) \\
(x, y) & \rightarrow & (x - 3, y) \\
\eeqn
}

\problempart State the most restrictive invariant you can find that
holds for all the states that Spike can reach.

\solution{Let $P$ be the property that $x + 2y$ is a multiple of 3 for
every reachable position $(x, y)$.  We show that the property is
preserved under each transition in $\delta$.  Suppose that $x + 2y =
3k$ for some $k \in \mathbb{Z}$.  Then we can show that the property
still holds after one transition as follows:

\beqn
(x + 2) + 2 (y - 1)
	& = &	x + 2 y \\
	& = &	3k \\
(x + 1) + 2 (y - 2)
	& = &	x + 2 y - 3\\
	& = &	3 (k - 1) \\
(x + 1) + 2 (y + 1)
	& = &	x + 2 y + 3\\
	& = &	3 (k + 1) \\
(x - 3) + 2 y
	& = &	x + 2 y - 3 \\
	& = &	3 (k - 1)
\eeqn

Therefore, $P$ is an invariant.
}

\problempart Will Spike ever find his true love?  Either find a path
from Spike to Daisy or use the Invariant Theorem to prove that no such
path exists.

\solution{The invariant $P$ holds in the start state, since $0 + 2
\cdot 0 = 0$, which is a multiple of 3.  However, the invariant does
not hold for Daisy's position, $(0, 2)$, since $0 + 2 \cdot 2 = 4$ is
not a multiple of 3.  Therefore, by the Invariant Theorem, this is not
a reachable state.

Later, though, as it turns out, Spike takes one ``illegal'' step,
sweeps up Daisy, and carries her off to the third quadrant of
$\mathbb{C}^2$, where they live happily every after.}

\end{problemparts}

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

\problem The set of {\em mixup strings} is recursively defined as
follows:

\begin{enumerate}

\item $yxz$ and $zyx$ are mixup strings.

\item If $\alpha$ is a mixup string, then so is the reverse of $\alpha$.

\item Below are a set of transformation rules.  If the segment on the
left side of a rule appears as a substring in a mixup string, then
replacing that substring with the segment on the right side of the
rule gives a new mixup string.  Here, $\lambda$ denotes the empty
string, the string consisting of no symbols.

\[
\begin{array}{lcrcl}
{\bf (a)} & \quad & xy & \rightarrow & \lambda \\
{\bf (b)} & & xzz & \rightarrow & y \\
{\bf (c)} & & y & \rightarrow & zzz \\
{\bf (d)} & & xz & \rightarrow & zx \\
{\bf (e)} & & zy & \rightarrow & xyz \\
{\bf (f)} & & xyx & \rightarrow & x \\
{\bf (g)} & & z & \rightarrow & y
\end{array}
\]

\end{enumerate}

Is $\lambda$ a mixup string?  If your answer is yes, prove your answer
correct by showing a sequence of valid transformations from one of the
base strings to $\lambda$.  If your answer is no, state an invariant
satisfied by all mixup strings, but not satisfied by $\lambda$.  A
full proof is not required.

\solution{The solution is as follows:

\[
\begin{array}{rcll}
xyz	& \rightarrow &	xyy       & (g) \\
	& \rightarrow &	xzzzy	  & (c) \\
	& \rightarrow & xzyzy     & (g) \\
	& \rightarrow & xzyyy     & (g) \\
	& \rightarrow & xxyzyy    & (e) \\
	& \rightarrow & xzyy      & (a) \\
	& \rightarrow & xxyzy     & (e) \\
	& \rightarrow & xxyxyz    & (e) \\
	& \rightarrow & xxyz      & (f) \\
	& \rightarrow & xxyy      & (g) \\
	& \rightarrow & xy        & (a) \\
	& \rightarrow & \lambda   & (a)
\end{array}
\]

This problem was much harder than we intended.  You will {\em not} be
expected to wade through such complexities on an exam!}

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

\problem Can you build a $6 \times 6 \times 6$ cube from $1 \times 2
\times 4$ bricks?  Justify your answer.

\solution{No.  Regard the $6 \times 6 \times 6$ cube as a $3 \times 3
\times 3$ cube of $2 \times 2 \times 2$ subcubes.  Color the subcubes
black and white in checkerboard style so that the corners are all
white.  (That is, two subcubes that share a face should be colored
oppositely.)  Then there are 14 white subcubes and 13 black subcubes.

Now we formulate the construction process as a state machine.  The set
of states consists of all partial constructions of a $6 \times 6
\times 6$ cube.  The start state is is the construction containing no
bricks.  There is a transition from one state to another if the second
can be obtained from the first by adding one brick.

Consider the property that the number of black and white positions
covered by bricks are equal.  Each brick, no matter how it is
oriented, covers an equal number of black and white positions.
Therefore, if this property holds for one partial construction, then
it holds for every partial construction that can be formed by adding
one more brick.  Therefore, this property is an invariant.

This invariant holds for the start state, when zero black positions
are covered and zero white positions are covered.  However, it does
not hold for the entire $6 \times 6 \times 6$ block, which has $14
\times 2^3$ white positions and $13 \times 2^3$ black positions.
Therefore, by the Invariant Theorem, a $6 \times 6 \times 6$ cube can
not be built.
}

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

\end{problems}
\end{document}
