\documentclass[12pt,twoside]{article}   
\usepackage{latex-macros/course}% !! Use the macros

\renewcommand{\reading}{Notes for
\href{http://theory.csail.mit.edu/classes/6.042/spring06/ln3-tue.pdf}{Week3}}

\begin{document}
\problemset{3}                 % !! Start the problem set with its number


%fall 04 ps2

\begin{problem}
Suppose that we have an $n \times n$ grid, where certain squares are
\textit{infected}.  Here is an example where $n = 6$ and infected squares
are marked $\times$.

\[
\begin{array}{|c|c|c|c|c|c|}
\hline
\times& & & &\times& \\ \hline
 &\times& & & & \\ \hline
& &\times&\times& & \\ \hline
& & & & & \\ \hline
& &\times& & & \\ \hline
& & &\times& &\times \\ \hline
\end{array}
\]

\noindent Now the infection begins to spread in discrete
time steps.  Two squares are considered \textit{adjacent} if they
share an edge; thus, each square is adjacent to 2, 3 or 4 others.  A
square is infected in the next time step if either
\begin{enumerate}
\item the square was previously infected, or\label{was}

\item the square is adjacent to \textit{at least two} already-infected
squares.\label{adj}
\end{enumerate}

In the example, the infection spreads as shown below.
%
\[
\begin{array}{|c|c|c|c|c|c|}
\hline
\times& & & &\times& \\ \hline
 &\times& & & & \\ \hline
& &\times&\times& & \\ \hline
& & & & & \\ \hline
& &\times& & & \\ \hline
& & &\times& &\times \\ \hline
\end{array}
\Rightarrow
\begin{array}{|c|c|c|c|c|c|}
\hline
\times&\times& & &\times& \\ \hline
\times&\times&\times& & & \\ \hline
&\times&\times&\times& & \\ \hline
& &\times& & & \\ \hline
& &\times&\times& & \\ \hline
& &\times&\times&\times&\times \\ \hline
\end{array}
\Rightarrow
\begin{array}{|c|c|c|c|c|c|}
\hline
\times&\times&\times& &\times& \\ \hline
\times&\times&\times&\times& & \\ \hline
\times&\times&\times&\times& & \\ \hline
&\times&\times&\times& & \\ \hline
& &\times&\times&\times& \\ \hline
& &\times&\times&\times&\times \\ \hline
\end{array}
\]
%
Over the next few time-steps, the entire grid becomes infected.

This scenario can be modelled as a state machine whose states are $n
\times n$ grids with marked infected squares and the transitions
determined by the rules~\ref{was},~\ref{adj} above.

\bparts

\ppart Describe an initial state with exactly $n$ infected squares such
that the completely infected grid is reachable.

\ppart See how many infected squares you can place in a grid such that the
completely infected grid will not be reachable.  (Extra credit for getting
the maximum number.  Extra, extra credit for a proof that this is the
maximum.)

\solution{
TBA.  I don't know how hard it is to determine and verify the max --ARM.
}

\ppart

\begin{theorem*}
An $n \times n$ grid can become completely infected only if at least
$n$ squares are initially infected.
\end{theorem*}

Prove this theorem by defining a suitable derived variable and proving
that it is weakly increasing.  (This problem is easy given a one-word
hint.  If you are stuck, ask your recitation instructor for the hint!)

\solution{
\begin{proof}
Define the \term{perimeter} of an infected region to be the number of
edges with infection on exactly one side. The derived variable, $\pi$,
will be the number of edges in the perimeter.

To show that $\pi$ is weakly increasing, we must show that if $G\to H$ is
a transition between infected grids, then $\pi(G) \le \pi(H)$.

REVISE TO STATE MACHINE LANGUAGE:

\textit{Base case:} $P(0)$ is true by definition; the
perimeter of the infected region is at most $I$ after 0 time steps,
because $I$ is defined to be the perimeter of the initially-infected
region.

\textit{Inductive step:} Now we must show that $P(k)$ implies
$P(k+1)$ for all $k \geq 0$.  So assume that $P(k)$ is true, where $k \geq
0$; that is, the perimeter of the infected region is at most $I$ after $k$
steps.  The perimeter can only change at step $k + 1$ because some squares
are newly infected.  By the rules above, each newly-infected square is
adjacent to at least two previously-infected squares.  Thus, for each
newly-infected square, at least two edges are removed from the perimenter
of the infected region, and at most two edges are added to the perimeter.
Therefore, the perimeter of the infected region can not increase and is at
most $I$ after $k + 1$ steps as well.  This proves that $P(k)$ implies
$P(k+1)$ for all $k \geq 0$.

By the principle of induction, $P(k)$ is true for all $nk \geq 0$.

If an $n \times n$ grid is completely infected, then the perimeter of
the infected region is $4n$.  Thus, the whole grid can become infected
only if the perimeter is initially at least $4n$.  Since each square
has perimeter 4, at least $n$ squares must be infected initially.
\end{proof}}

\eparts
\end{problem}

%spring 04 ps3

% swiped from Discrete Applied Mathematics

% not two balls?

\begin{problem}
An urn contains 75 white balls and 150 black balls.  While there are
at least 2 balls remaining in the urn, you repeat the following
operation.  You remove 2 balls selected arbitrarily and then:
%
\begin{itemize}
\item If at least one of the two balls is black, then you discard one
black ball and put the other ball back in the urn.
\item If both of the balls are white, then you discard them both and put a
new black ball into the urn.
\end{itemize}
%
Prove that the urn never reaches the state where it is empty except
for one black ball.
\end{problem}

\solution{We use induction.  Let $P(n)$ be the proposition that the
urn always contains an odd number of white balls.

\noindent \textit{Base case.}  Initially, the urn contains 75 white
balls, which is an odd number, so $P(0)$ is true.

\noindent \textit{Inductive step.}  Suppose that the urn contains an
odd number of white balls after $n$ steps.  If there are fewer than 2
balls remaining, then the process ends.  Otherwise, there are then two
cases:
%
\begin{enumerate}
\item You draw at least one black ball.  Then the number of black
balls decreases by one and the number of white balls is unchanged.
Therefore, the number of white balls remains odd.
\item You draw two white balls.  Then the number of black balls
increases by one, and the number of white balls decreases by two.
Again, the number of white balls remains odd.
\end{enumerate}
%
Thus, the urn still contains an odd number of white balls after $n+1$
steps.  By induction, the urn always contains an odd number of white
balls.  Therefore, the urn can never hold just one black ball and zero
white balls, since zero is even.}

%spring 05 ps3

\begin{problem}
A puzzle toy contains the numbers $1, \ldots, 35$ written on small
circular disks.  The disks are arranged on an oval track with
\textit{no gaps} so that the whole sequence of disks can slide
clockwise or counterclockwise around the track.
%
\begin{center}
\rotatebox{-90}{\includegraphics{figures/track-puzzle}}
\end{center}
%
In addition, the track runs through a circular dial that is four disks
wide.  This dial can be rotated 180 degrees, reversing the order of
the four disks on that portion of the track.  For example, if the dial
were turned in the configuration above, then the the order of 34, 35,
1, 2 would become 2, 1, 35, 34.

Suppose that the puzzle is initially in the state shown above with
numbers increasing counterclockwise around the track.  Prove that no
sequence of operations has the effect of swapping disks only 1 and 2
while leaving all the other disks in the same order.
\end{problem}

\solution{Associate each configuration of the puzzle with a
permutation of the numbers $1, \ldots, 35$ by taking the numbers in
counterclockwise order starting in the middle of the dial.  Thus, the
example configuration corresponds to the permutation:
%
\[
1\ 2\ 3\ \ldots\ 35
\]

Now we use induction on the number of operations.  Let $P(n)$ be the
proposition that after $n$ operations, there are an even number of
inversions.

\noindent \textit{Base case.}  Initially, there are zero inversions.
Since zero is even, $P(0)$ is true.

\noindent \textit{Inductive step.}  Suppose that after $n$ steps there
are an even number of inversions.  There are now three cases to
consider:
%
\begin{itemize}
\item Suppose the dial is turned 180 degrees.  This transforms the
permutation
%
\[
s_1 s_2 s_3 s_4 \ldots s_{32} s_{33} s_{34} s_{35}
\]
%
into the permutation:
%
\[
s_{35} s_{34} s_3 s_4 \ldots s_{32} s_{33} s_2 s_1
\]
%
This amounts to swapping $s_1$ with $s_{35}$ and $s_2$ with $s_{34}$.
Each swap changes the parity of the number of inversions, so after two
swaps there are still an even number of inversions.

\item Suppose that the numbers are rotated one position clockwise
around the track.  This transforms the permutation
%
\[
s_1 s_2 s_3 s_4 \ldots s_{32} s_{33} s_{34} s_{35}
\]
%
into the permutation:
%
\[
s_2 s_3 s_4 \ldots s_{32} s_{33} s_{34} s_{35} s_1 
\]
%
This reverses the order of exactly 34 pairs of disks, $s_1$ and every
other disk.  This changes the parity of the number of inversions 34
times, which leaves an even number of inversions.

\item Similarly, rotating one position counterclockwise reverses the
order of 34 pairs, again leaving an even number of inversions.

\end{itemize}
%
By induction, the number of inversions is always even.  Therefore, the
configuration in which 1 and 2 are swapped (which has 1 inversion) is
unreachable.}

%fall00 ps5


\begin{problem}
In the late 1960s, the military junta that ousted the government of the
small republic of Miranda outlawed multiplication and division by any
number other than $3$.  When democracy was reinstated 30 years later,
people were interested in rediscovering the lost art of multiplication.
A young inventor came up with the following algorithm to multiply any
two natural numbers $x$ and $y$ using only multiplication and division by
3:

\begin{tabbing}
XXX\=XXX\=XXX\=XXX\kill
{\bf procedure} {\it multiply}$(x, y$: natural numbers$)$ \\
$r:=x$; \\
$s:=y$; \\
$a:=0$;\\
{\bf do until} $s = 0$ \\
   \>{\bf if} $3 \divides s$ {\bf then} \\
   \>\>   $r := 3r$; \\
   \>\>   $s := s / 3$;\\
   \>{\bf else if} $3 \divides (s-1)$ {\bf then} \\
   \>\>   $a := a + r$; \\
   \>\>   $r := 3r$; \\
   \>\>   $s := (s - 1) / 3$; \\
   \>{\bf else} \\
   \>\>   $a := a + 2r$; \\
   \>\>   $r := 3r$; \\
   \>\>   $s := (s - 2) / 3$; \\
{\bf return} $a$; \\
\end{tabbing}

We can model the algorithm as a state machine whose states are triples of
nonnegative integers with transitions given by the rule that for $s>0$:
\[
(r,s,a)\rightarrow\begin{cases}
        (3r,s/3,a) &\text{ if } 3 \divides s\\
        (3r,(s-1)/3,a+r) &\text{ if } 3 \divides (s-1)\\
        (3r,(s-2)/3,a+2r) &\text{otherwise}.
       \end{cases}
\]

\iffalse
\solution{
\medskip
\textbf{Solution:}
\begin{description}
\item $Q=\{(r,s,a,x,y) | r,s,a,x,y\in \mathbb{N}\}$
\item $Q_0=\{(x,y,0,x,y)\}$
\item $\delta: (r,s,a,x,y)\rightarrow (3r,s',a',x,y)$, where \\
If $s \equiv 0 \pmod{3}$: $s'=s/3$, and $a'=a$ \\
If $s \equiv 1 \pmod{3}$: $s'=(s-1)/3$, and $a'=a+r$\\
If $s \equiv 2 \pmod{3}$: $s'=(s-2)/3$, and $a'=a+2r$
\end{description}
}
\fi

\ppart
List the sequence of steps that appears in the execution of the
algorithm for inputs $x = 5$ and $y = 10$.

\solution{
\medskip
\textbf{Solution:}
$(5, 10, 0) \rightarrow
(15, 3, 5) \rightarrow
(45 ,1, 5) \rightarrow
(135, 0, 50)$
}

\ppart Use the invariant method to prove that the algorithm is partially
correct ---that is, if $s = 0$, then $a = xy$.

\solution{
We prove the following invariant.

$P(r,s,a,x,y) = ``xy = rs+a$''.

{\bf Base case: }
For any initial state we have $P(x,y,0,x,y)$ which is true.

{\bf Inductive step:} Consider a transition from $(r,s,a,x,y)$ to
$(r',s',a',x',y')$.  We need to prove that $P(r,s,a,x,y) \rightarrow
P(r',s',a',x',y')$.  We consider three cases:

If $s \equiv 0 \pmod{3}$, then 
$r's' + a' = (3r)\frac{s}{3} + a = rs + a = xy = x'y'.$

If $s \equiv 1 \pmod{3}$, then 
$r's' + a' = (3r)\frac{s-1}{3} + (a+r) = rs + a = xy = x'y'.$

If $s \equiv 2 \pmod{3}$, then 
$r's' + a' = (3r)\frac{s-2}{3} + (a+2r) = rs + a = xy = x'y'.$

In all three cases, the last equality was derived by applying the
inductive hypothesis, and in all cases $P(r',s',a',x',y')$ holds.
When $s=0$, the we get that $a=xy.$  We also know that the algorithm terminates
when $s=0$.  It follows, therefore, that if the algorithm terminates,
then the correct answer is produced.
}

\ppart
Prove that the algorithm terminates.

\solution{
We first notice that $s\geq 0$ for any reachable
execution state.  We prove that this is an invariant by showing
it is true for the base case, $y\geq 0$, and furthermore, no
transition exists from a state with $s\geq 0$ to $s<0$ in all
cases.

Now consider the value of $s$ during any valid execution.  Since
$s\geq 0$, as shown above, no transition increases $s$.  Furthermore,
for $s>0$, all transitions decrease $s$ by at least 1.  Thus for any
values of $x,y\in \mathbb{N}$, $s$ decreases to 0 in a finite number
of steps, and thus the program terminates in a finite number of steps.
}

\end{problem}

\end{document}
