% This is a TeX file
% It is essentially a programming language for mathematics documents
% You can ignore this first portion of the file, as it is essentially a bunch of "include" statements.
\documentclass[10pt]{article}

\usepackage{pictex, latexsym, graphicx,amsmath,amssymb,amsbsy,amsfonts,amsthm,verbatim}
\usepackage{graphics}
\usepackage{fullpage}
\usepackage{fancyhdr}
\usepackage{hyperref}

\usepackage{algorithm,algorithmic}
\usepackage{multirow}

\setlength{\voffset}{-0.25in}
\setlength{\headsep}{0.25in}
\setlength{\parskip}{1em}
\setlength{\parindent}{0em}

% The following denotes a counter for the problems.
\newcounter{problem}
\newcommand{\problem}{\textbf{\refstepcounter{problem}Problem \theproblem.} }

% These are macro shortcuts! Helpful!
\def\vu{\mathbf{u}}
\def\vx{\mathbf{x}}
\def\vy{\mathbf{y}}
\def\vz{\mathbf{z}}
\def\vb{\mathbf{b}}
\def\vv{\mathbf{v}}
\def\vw{\mathbf{w}}

\renewcommand{\implies}{\rightarrow}
%\newcommand{\lnot}{\neg}
\renewcommand{\lor}{\vee}
\renewcommand{\land}{\wedge}
\newcommand{\xor}{\oplus}
\newcommand{\symmdiff}{\triangle}
\renewcommand{\iff}{\leftrightarrow}
\newcommand{\TRUE}{\mathbf{T}}
\newcommand{\FALSE}{\mathbf{F}}
\newcommand{\universe}{\mathcal{U}}


\def\N{\mathbb{N}}
\def\Q{\mathbb{Q}}
\def\C{\mathbb{C}}
\def\Z{\mathbb{Z}}
\def\R{\mathbb{R}}
\def\cP{\mathcal{P}}


\begin{document}
\pagestyle{fancyplain}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% NOW you can start typing your text that will appear in the PDF!!!

% Note that anything after a '%' is a comment!

% Anything immediately after a '\' is a command. 
% Some denote formatting, some are for special characters.
% The '$' symbol starts and ends "math mode". Use this only for mathematical statements
% In math mode, any sequence of letters is meant to be a list of variables, so use "\sin x" for the sine of x, which will look much different from "sin x"
\chead{COM S 330 --- Homework 08 --- Solutions}

\textit{Type your answers to the following questions and submit a PDF file to Blackboard. 
One page per problem.}


% Problems about State Machines! Monotonicity Principle!
\problem\ [10pts] Let $M = (S,T, s_0)$ be the state machine where $S = \N \times \N$ and the transitions in $T$ are given as
$(m,n) \to (m-1,n+1)$ if $m \geq 1$, and $(m,n) \to (m, n-1)$ if $n \geq 1$. 
Define a function $f : \N \times \N \to \N$ where $f$ is decreasing with respect to $M$ and use the Monotonicity Principle to prove that if the initial state is $(m,n)$, then the machine will halt in at most $f(m,n)$ transitions. (Bonus 1pt for defining $f(m,n)$ to be \emph{optimal}, predicting exactly the maximum number of steps from $(m,n)$ to a halting state.) [Hint: Draw the points $(m,n)$ in the plane and draw lines between points for possible transitions.]

\begin{proof}
Let $f(m,n) = 2m+n$.
Consider a state $(m,n)$.
The transition $(m,n) \to (m,n-1)$ satisfies $f(m,n) = 2m+n > 2m+n-1 = f(m,n-1)$.
The transition $(m,n) \to (m-1,n+1)$ satisfies $f(m,n) = 2m+n > 2m+n-1 = 2(m-1)+(n+1) = f(m-1,n+1)$.
Therefore, $f(m,n)$ is a decreasing function and $f(m,n) \geq 0$ for all $m,n \in \N$.
By the Monotonicity Principle, the state machine halts in at most $f(m,n)$ steps.

[Bonus] Starting at a state $(m,n)$, use $m$ transitions of the type $(m,n) \to (m-1,n+1)$ to arrive at the state $(0,n+m)$.
Then use $m+n$ transitions of the type $(m,n) \to (m,n-1)$ to arrive at the state $(0,0)$.
Therefore, $(m,n)$ has a set of $2m+n$ transitions until reaching the halting state $(0,0)$.
\end{proof}


% Problems about State Machines! 
 \clearpage
\problem\ [10pts] Let $\Sigma = \{ a^+, a^-, b^+, b^-\}$.
Let $M = (S,T,s_0)$ be the state machine where $S = \Sigma^*$ and the transitions available in $T$ from a string $x_1\dots x_n \in \Sigma^*$ are as follows:
\vspace{-1em}
\begin{itemize}
\item If there exists $i \in \{1,\dots,n-1\}$ such that $x_i = a^+$ and $x_{i+1} = a^-$, then $x_1\dots x_n \longrightarrow x_1\dots x_{i-1}x_{i+2}\dots x_n$.
\item If there exists $i \in \{1,\dots,n-1\}$ such that $x_i = a^-$ and $x_{i+1} = a^+$, then $x_1\dots x_n \longrightarrow x_1\dots x_{i-1}x_{i+2}\dots x_n$.
\item If there exists $i \in \{1,\dots,n-1\}$ such that $x_i = b^+$ and $x_{i+1} = b^-$, then $x_1\dots x_n \longrightarrow x_1\dots x_{i-1}x_{i+2}\dots x_n$.
\item If there exists $i \in \{1,\dots,n-1\}$ such that $x_i = b^-$ and $x_{i+1} = b^+$, then $x_1\dots x_n \longrightarrow x_1\dots x_{i-1}x_{i+2}\dots x_n$.
\end{itemize}
\textbf{a.} [5pts] Describe all of the possible state sequences when starting at the string $b^+a^+b^+b^-a^-b^+a^+b^-b^+$.

$b^+a^+b^+b^-a^-b^+a^+b^-b^+$ can transition to $b^+a^+a^-b^+a^+b^-b^+$ (collapsing $b^+b^-$ in positions 3 and 4) or $b^+a^+b^+b^-a^-b^+a^+$ (collapsing $b^-b^+$ in positions 8 and 9).

$b^+a^+a^-b^+a^+b^-b^+$ can transition to $b^+b^+a^+b^-b^+$ (collapsing $a^+a^-$ in positions 2 and 3) or $b^+a^+a^-b^+a^+$ (collapsing positions 6 and 7).

 $b^+a^+b^+b^-a^-b^+a^+$ can transition to  $b^+a^+-a^-b^+a^+$ (collapsing $b^+b^-$ in positions 3 and 4).
 
 $b^+b^+a^+b^-b^+$ can transition to $b^+b^+a^+$ (collapsing $b^-b^+$ in positions 4 and 5).

$b^+a^+a^-b^+a^+$  can transition to $b^+b^+a^+$ (collapsing $a^+a^-$ in positions 2 and 3).

$b^+b^+a^+$ is a halting state.

\textbf{b.} [5pts] For certain states in $\Sigma^*$, there may be more than one outgoing transition. Prove that for every string $\vx \in \Sigma^*$, there is a unique halting state reachable from $\vx$. [Hint: List the possible outgoing states $\vy^{(1)}, \dots, \vy^{(k)}$ and show that every pair $\vy^{(i)}$ and $\vy^{(j)}$ have a common outgoing state, so they have a common halting state.]

We claim that for every state $\vx$, there is a unique halting state reachable from $\vx$.

\begin{proof}
We will use proof by strong induction, using $n = |\vx|$, the length of $\vx$.

Case $n = 0$: If $|\vx| = 0$, then $\vx$ is the empty word. There are no transitions from $\vx$, so $\vx$ is its own unique halting state.

Case $n = 1$: If $|\vx| = 1$, then $\vx$ has exactly one letter. There are no transitions from $\vx$, so $\vx$ is its own unique halting state.

(Strong Induction Hypothesis) Let $N > 0$ and suppose that for all $0 \leq n < N$, the statement holds for all words of length $n$.

Case $N$: Let $\vx$ have length $N$.
If $\vx$ has no transitions, then $\vx$ is its own unique halting state and $k = 0$.
Now suppose that $\vx$ has transitions $\vx \to \vy^{(i)}$ for $i \in \{1,\dots,k\}$ for some $k \geq 1$.
If $k = 1$, then $\vx$ has a unique outgoing transition, and $\vy^{(1)}$ has a unique halting state, so $\vx$ has a unique halting state.
Thus, we can suppose that $k \geq 2$.
(Note that $|\vy^{(i)}| = N - 2$, so the induction hypothesis holds for each $\vy^{(i)}$.
Since $\vx$ transitions to each $\vy^{(i)}$, there is a value $c_i \in \{1,\dots,N-1\}$ where the positions $x_{c_i}x_{c_i+1}$ are deleted from $\vx$ to form $\vy^{(i)}$.
We can order the transitions such that when $i < j$, $c_i < c_j$ ($c_i \neq c_j$ since equality would create the same word).
Thus, $\vy^{(i)} = x_1\dots x_{c_i-1}x_{c_i+2}\dots x_n$.

Note: If $c_j = c_i+1$, then observe that $x_{c_i} = x_{c_i+2}$ and hence $\vy^{(i)} = \vy^{(j)}$. This is a very subtle point and students will not lose points if they do not mention this point.
Therefore, since $\vy^{(i)}\neq \vy^{(j)}$, we have $c_i + 2 \leq c_j$ when $i < j$.

For $1 \leq i < j \leq k$, we will prove that the halting state for $\vy^{(i)}$ is the same as the halting state for $\vy^{(j)}$.
If suffices to show that $\vy^{(i)}$ and $\vy^{(j)}$ have a common outgoing transition $\vw$, and by the induction hypothesis, $\vw$ has a unique halting state $\vz$, which is the unique halting state for both $\vy^{(i)}$ and $\vy^{(j)}$.
In $\vy^{(j)}$, the letters in the $c_i$ and $c_i+1$ positions are the same as those in the word $\vx$ (as $c_i < c_j$ so there were two letters removed \emph{after} the $c_i$ position), so there is a transition out of $\vy^{(j)}$ to the word $\vw = x_1\dots x_{c_i-1}x_{c_i+2}\dots x_{c_j-1}x_{c_j+2}\dots x_n$.
In $\vy^{(j)}$, the letters in the $c_j-2$ and $c_j-1$ positions are the same as the $c_j$ and $c_j+1$ positions in the word $\vx$ (as $c_i < c_j$ so there were two letters removed \emph{before} the $c_j$ position), so there is a transition out of $\vy^{(j)}$ to the word $\vw = x_1\dots x_{c_i-1}x_{c_i+2}\dots x_{c_j-1}x_{c_j+2}\dots x_n$.
By Strong Induction, $\vw$ has a unique halting state $\vz$, which is equal to the unique halting state of $\vy^{(i)}$ and $\vy^{(j)}$.
Thus, for all $i \in \{1,\dots,k\}$, the halting state from $\vy^{(i)}$ is the halting state $\vz$.
Finally, this halting state $\vz$ is the unique halting state reachable from $\vx$.
\end{proof}


% Reversibility Principle!
 \clearpage
\problem\ [10pts] Let $M = (\Q, T, s_0)$ be a state machine on the rational numbers with transitions $\frac{p}{q} \to \frac{p}{q} + \frac{1}{pq} = \frac{p^2+1}{pq}$, when $p > 0$ and $q > 0$. 

\textbf{a.} [5pts] Let $P_d(\frac{p}{q})$ be the property ``$d \leq \frac{p}{q} < d+1$.''
Prove that when $d$ is an integer with $d \geq 3$, $P_d$ is a reversible invariant for the state machine $M$.
[Hint: Show that $P_d$ is a preserved invariant for all $d \geq 2$. If $P_d(\frac{p}{q})$ is true, then $p = dq + r$ where $r$ is an integer and $0 \leq r < q$. To show $P_d$ is a reversible invariant for $d \geq 3$, use the fact that it is a preserved invariant for $d \geq 2$.]

\begin{proof}
Let $d \geq 2$.
Suppose $P_d(\frac{p}{q})$ is true and $\frac{p}{q} \to \frac{p^2+1}{pq}$ is a transition.
Since $d \leq \frac{p}{q} < d+1$, we have $dq \leq p < dq+q$ and hence $p = dq+r$ for an integer $r$ with $0 \leq r < q$.
Then, since $p \geq dq \geq 2$ we have $r + \frac{1}{p} \leq r + \frac{1}{2} < q$ and $rp+1 = p(r+1/p) < pq$ and hence
\[
p^2+1 = p(dq+r)+1 = dpq+rp+1 < dpq+pq = (d+1)pq.
\] 
Therefore,
\[
d \leq \frac{p}{q} < \frac{p^2+1}{pq} < d+1,
\]
and $P_d$ is a preserved invariant for $d \geq 2$.

Now let $d \geq 3$.
For the sake of contradiction, suppose that $P_d$ is not a reversible invariant, so there exists a fraction $\frac{p}{q}$ where $P_d(\frac{p}{q})$ is false but $P_d(\frac{p^2+1}{pq})$ is true.
This means $d \leq \frac{p}{q} + \frac{1}{pq} < d+1$.
Since $\frac{p}{q} < \frac{p}{q} + \frac{1}{pq}$, we know that $\frac{p}{q} < d+1$, so since $P_d(\frac{p}{q})$ is false it must be because $\frac{p}{q} < d$.
If $\frac{p}{q} \geq 2$, then $P_e(\frac{p}{q})$ is true for some $e \geq 2$, but since $P_e$ is a preserved invariant, it must be that $e = d$.
Therefore, $\frac{p}{q} < 2$, implying that $1 < \frac{p^2+1}{pq} - \frac{p}{q} = \frac{1}{pq} \leq 1$, a contradiction.
\end{proof}

\textbf{b.} [5pts] Use part (a) and the Reversibility Principle to say that if $\frac{p}{q}$ is the initial state with $\frac{p}{q} \geq 3$ and $\frac{i}{j}$ is a reachable state, then $\lfloor \frac{p}{q}\rfloor = \lfloor \frac{i}{j}\rfloor$.
[You can get full points for this part if you assume (a), even if you have not proven (a) correctly.]

\begin{proof}
Let $d$ be the integer where $P_d(\frac{p}{q})$ is true.
Since $\frac{p}{q} \geq 3$, $d \geq 3$ and $P_d$ is a reversible invariant.
By the reversibility principle, $P_d(\frac{p}{q})$ is true if and only if $P_d(\frac{i}{j})$ is true.
Thus, $d = \lfloor \frac{p}{q}\rfloor = \lfloor \frac{i}{j}\rfloor$.
\end{proof}


\textbf{c.} [Bonus 1pt] Find a fraction $\frac{p}{q}$ such that $P_1(\frac{p}{q})$ is true but $P_1(\frac{p^2+1}{pq})$ is false.

\textbf{d.} [Bonus 1pt] Find a fraction $\frac{p}{q}$ such that $P_2(\frac{p}{q})$ is false but $P_2(\frac{p^2+1}{pq})$ is true.

Let $p = q = 1$.
Then $1 \leq \frac{1}{1} < 2$ but $\frac{1^1+1}{1\cdot 1} = \frac{2}{1} = 2$.
Thus, this transition shows that $P_1$ is not a preserved invariant and $P_2$ is not a reversible invariant (although $P_2$ \emph{is} a preserved invariant).



% Problems about Structural Induction!
 \clearpage
\problem\ [10pts] Define a set $S \subseteq \R$ recursively using the Recursive Step ``If $x \in S$, then $(x-1)(x+1) \in S$.'' Consider the following bases.

\textbf{a.} [3pts] Prove that if the basis step is ``$0 \in S$'' then $S = \{ 0, -1 \}$.

\begin{proof}
By the basis step, $0 \in S$.
Using $0$ in the recursive step, $(0-1)(0+1) = -1$ and hence $-1 \in S$.
Thus, $\{ 0,-1\} \subseteq S$.

Using $-1$ in the recursive step, $(-1-1)(-1+1) = 0$ and hence $0 \in S$.
Therefore, no other elements are in the set.
\end{proof}

\textbf{b.} [3pts] Prove that if the basis step is ``$1 \in S$'' then $S = \{ 1, 0, -1 \}$.

\begin{proof}
By the basis step, $1 \in S$.
Using $1$ in the recursive step, $(1-1)(1+1) = 0$ and hence $0 \in S$.
Using $0$ in the recursive step, $(0-1)(0+1) = -1$ and hence $-1 \in S$.
Thus, $\{1, 0,-1\} \subseteq S$.

Using $-1$ in the recursive step, $(-1-1)(-1+1) = 0$ and hence $0 \in S$.
Therefore, no other elements are in the set.
\end{proof}

\textbf{c.} [4pts] Prove that if the basis step is ``$2 \in S$'' then $S$ is an infinite set.

\begin{proof}
We use proof by contradiction.
Suppose that $S$ is finite.
Then there exists a maximum element $x = \max S$.
Since $2 \in S$ by the basis step, $x \geq 2$.

Since $x \in S$, the element $(x-1)(x+1) = x^2 - 1$ is in $S$ by  the recursive step.
Since $x \geq 2$, $x^2 > x+1$, and hence $x^2 - 1 > x$, contradicting that $x$ is the maximum element in $S$.
\end{proof}





% Problems about Structural Induction!
 \clearpage
\problem\ [10pts] Define a set $S \subseteq \R$ recursively by (Basis Step) $\frac{1}{1} \in S$, and (Recursive Step) If $x \in S$, then $2x \in S$ and $\frac{x}{3} \in S$. Prove that $S = \{ \frac{2^i}{3^j} : i, j \in \N \}$.

\begin{proof}
$(S \subseteq \{ \frac{2^i}{3^j} : i,j \in \N\}$) We use structural induction.

(Basis) $\frac{1}{1} = \frac{2^0}{3^0}$.

(Recursive Step) Let $\frac{2^i}{3^i}$ be an element of $S$.
The transition $\frac{2^i}{3^j} \to 2\frac{2^i}{3^j}$ implies the element $\frac{2^{i+1}}{3^j}$ is in $S$.
The transition $\frac{2^i}{3^j} \to \frac{\frac{2^i}{3^j}}{3}$ implies the element $\frac{2^{i}}{3^{j+1}}$ is in $S$.

Therefore, by structural induction every element of $S$ is of the form $\frac{2^i}{3^j}$.


$(\{ \frac{2^i}{3^j} : i,j \in \N\}\subseteq S$)
We use induction on $i + j$ to show that $\frac{2^i}{3^j}$ is in $S$.

Case $i + j = 0$: $\frac{2^0}{3^0} = \frac{1}{1}$ which is in $S$ by the basis step.

(Induction Hypothesis) Let $n \geq 0$ and suppose that for all $i,j \in \N$ with $i + j = n$ we have $\frac{2^i}{3^j} \in S$.

Case $i + j = n+1$: If $i > 0$, then since $i-1 \in\N$ and $(i-1)+j = n$ we have $\frac{2^{i-1}}{3^j} \in S$.
By the construction step, $2\cdot\frac{2^{i-1}}{3^j} = \frac{2^i}{3^j}$ is in $S$.
If $i = 0$, then since $j = n+1 > 0$ we have $j-1 \in \N$ and $\frac{1}{3^{j-1}}$ is in $S$.
By the construction step, $\frac{\frac{1}{3^{j-1}}}{3} = \frac{1}{3^j}$ is in $S$.

By induction, every element $\frac{2^i}{3^j}$ with $i, j \in \N$ is in $S$.
\end{proof}










\end{document} 