\problemdata
{S00 ps4.5}
{robot}
{computational processes}

\begin{problem}
%[[[Shishir:  This is derived from problem set 4, Handout 21, Spring
%98.  Please fill in the solution.]]]
A robot wanders on a 2-dimensional grid, starting at the origin,
$(0,0)$.
In one step, he is able to move unit distance along any diagonal line,
that is, at an angle of $\pm 45$ degrees or $\pm 135$ degrees.
\begin{problemparts}
\problempart
Describe how to model the robot's behavior as a state machine.

\solution{

The possible states are:
$Q = \{(x, y)\} \subset (\reals \times \reals) $

The initial state is: $Q_0 = (0, 0)$

The transitions are:
$\delta \subseteq Q \times Q = $ $\{(q1, q2)$ such that $q2$ is $\pm 45$ 
degrees or 
$\pm 135$ degrees from $q1\} $


}

\problempart
Give an execution of the state machine that reaches the point
$(\frac{5 \sqrt{2}}{2}, \frac{-3 \sqrt{2}}{2})$.

\solution{

Starting at $Q_0$ make the following transitions: 
\begin{enumerate}
\item $-45$ degrees: New state is $(\frac{\sqrt{2}}{2}, \frac{- \sqrt{2}}{2} )$
\item $-45$ degrees: New state is $(\frac{2 \sqrt{2}}{2}, \frac{- 2 \sqrt{2}}{2} )$
\item $-45$ degrees: New state is $(\frac{3 \sqrt{2}}{2}, \frac{- 3 \sqrt{2}}{2} )$
\item $45$ degrees: New state is $(\frac{4 \sqrt{2}}{2}, \frac{- 2 \sqrt{2}}{2} )$
\item $-45$ degrees: New state is $(\frac{5 \sqrt{2}}{2}, \frac{- 3 \sqrt{2}}{2} )$
\end{enumerate}
}

\problempart
Prove (using induction on the length of the execution) that the robot
cannot reach the point $(5,5)$. 

\solution{

We will prove a stronger theorem first and then apply it to our special
case.

\begin{theorem*} 
After any n step execution (starting at $Q_0$), the $x$ and $y$ coordinates of
the final state are both multiples of $\frac{\sqrt{2}}{2}$.
\end{theorem*}

\begin{proof} Let $P(n)$ be the predicate that after $n$ steps, the  $x$ and
the $y$ coordinates of the current state are both multiples of 
$\frac{\sqrt{2}}{2}$.

\begin{description}\itemsep 0ex
\item[Base Case:~~] $P(0)$ is true since 
$Q_0 = (0,0)$ and $0$ is a multiple of $\frac{\sqrt{2}}{2}$.
\item[Inductive Step:~~] We must show that for any positive integer $n$,
$P(n) \implies P(n+1)$. We can do this by picking an arbitrary $n$ step
execution and enumerating all the possibilities for the $(n+1)$th step. 
By the inductive hypothesis, after our $n$ step execution, the current $x$ and
$y$ coordinates are both multiples of 
$\frac{\sqrt{2}}{2}$.
Therefore, we can pick integers $k$ and $j$ and call our current state:
$(\frac{k \sqrt{2}}{2} , \frac{j \sqrt{2}}{2} )$

Now there
are 4 possible transitions to the new state, $Q_{n+1}$:
\[
\begin{array}{rccccccccc}
45~degrees: & Q_{n+1} & = & (
\frac{k \sqrt{2}}{2} + \frac{\sqrt{2}}{2},
\frac{j \sqrt{2}}{2} + \frac{\sqrt{2}}{2}) 
& = & (
\frac{(k+1)\sqrt{2}}{2}, 
\frac{(j+1)\sqrt{2}}{2}
) \\
%
-45~degrees: & Q_{n+1} & = & ( 
\frac{k \sqrt{2}}{2} + \frac{\sqrt{2}}{2},
\frac{j \sqrt{2}}{2} - \frac{\sqrt{2}}{2}) 
& = & (
\frac{(k+1)\sqrt{2}}{2}, 
\frac{(j-1)\sqrt{2}}{2}
) \\
%
135~degrees: & Q_{n+1} & = & ( 
\frac{k \sqrt{2}}{2} - \frac{\sqrt{2}}{2},
\frac{j \sqrt{2}}{2} + \frac{\sqrt{2}}{2}) 
& = & (
\frac{(k-1)\sqrt{2}}{2}, 
\frac{(j+1)\sqrt{2}}{2}
) \\
%
-135~degrees: & Q_{n+1} & = & ( 
\frac{k \sqrt{2}}{2} - \frac{\sqrt{2}}{2},
\frac{j \sqrt{2}}{2} - \frac{\sqrt{2}}{2}) 
& = & (
\frac{(k-1)\sqrt{2}}{2}, 
\frac{(j-1)\sqrt{2}}{2}
) \\
\end{array}
\]
In all four situations, our resulting state still satisfies the
predicate. Therefore, we have $P(n) \implies P(n+1)$.

\end{description}

Finally, since the $x$ and $y$ coordinates of any reachable state are always
multiples of
$\frac{\sqrt{2}}{2}$, $(5,5)$ is not reachable.
      
\end{proof}

}
\end{problemparts}
\end{problem}