\problemdata                                                             
        {Coins on a table} % latex-friendly label for the prob.
        {State Machines} % The topic(s) of the problem content.  
        {S98, Quiz 1} % Source (if known)      
        {S01 Tutorial 5, 6} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
Start with 102 coins on a table, 98 showing ``heads'' and 4 showing
``tails.''  There are two ways to change the coins:
\begin{enumerate}
\item[(i)] flip over any ten coins, or

\item[(ii)] let $n$ be the number of coins on the table showing heads.  Place
$n+1$ additional coins on the table, with all the new coins initially
showing tails.
\end{enumerate}
For example, you might begin by flipping nine heads and one tail,
yielding 90 heads and 12 tails, then add 91 tails, yielding 90 heads and
103 tails.

\begin{problemparts}
\problempart
Model this situation as a state machine, carefully defining the set of
states, the start state and the possible state transitions.

\solution{
This can be modeled by a state machine $M=\{Q,Q_0,\delta\}$, where:\\

\begin{itemize}
\item $Q=\naturals\times\naturals$, the first integer is the number of
heads and the second integer is the number of tails;

\item  $Q_0=\{(98,4)\}$

\item  $\delta$ is given by the rule that the next state of $(h,t)$ can be
any state of the form:\\
\[\begin{array}{l}
(h-a+(10-a),t+a-(10-a)) \mbox{ where }0\leq a\leq 10,\ a\leq h,\ 10-a\leq t,\\
\mbox{or }(h,t+h+1).\\
\end{array}\]
\end{itemize}

\vskip0.5in
{\bf Comment:} Most students forgot to specify the range of $a$ precisely
for the first transition.
}

\problempart Explain how to reach a state with exactly one tail showing.

\solution{
\begin{enumerate}

\item Do operation 2 three times, yielding $(98, 4+3\cdot99)= (98,301)$.

\item Repeat 30 times: Do operation 1 to flip 10 tails into heads. This
will result in the state $(398,1)$, which is the desired state.
\end{enumerate}
}

\problempart
Define the following derived variables of a state $q$:
\begin{eqnarray*}
 C(q) & \eqdef & \mbox{ the number of coins on the table},\\
 H(q) & \eqdef & \mbox{ the number of heads},\\
 T(q) & \eqdef & \mbox{ the number of tails},\\
 C_2(q) & \eqdef & \mbox{remainder}(C(q)/ 2),\\
 H_2(q) & \eqdef & \mbox{remainder}(H(q)/ 2),\\
 T_2(q) & \eqdef & \mbox{remainder}(T(q)/ 2).
\end{eqnarray*}

Which of these variables is
\begin{enumerate}

\item increasing \solution{NONE}
\item\label{ndec} nondecreasing \solution{$C(q)$, $H_2(q)$}
\item decreasing \solution{NONE}
\item constant \solution{$H_2(q)$.

{\bf Comment:} A lot of students failed to notice that a constant variable
is also a nondecreasing variable, and did not put $H_2(q)$ in part~\ref{ndec}.
}
\end{enumerate}


\problempart Prove that it is not possible to reach a state in which there is
exactly one head showing.

\solution{

We claimed above that $H_2(q)$ is an invariant value, that is, it does not
change under state tramsitions.  To prove this, let $(h,t)$ be a state
with $h$ even.  For the next state, we have two cases to consider:
\begin{enumerate}
\item The first operation is executed:
$(h,t)\rightarrow(h-2a+10,t+2a-10)$.  Since $-2a+10$ is even, $H_2((h,t))=
H_2(h-2a+10, t+2a-10)$.

\item The second operation is executed: $(h,t)\rightarrow(h,t+h+1)$. The
number of heads does not change in this case, so $H_2$ does not change.
\end{enumerate}
Since the initial number of heads, 98, is even, that is, $H_2((98,4))=0$,
the Invariant Method now implies that the number of heads in a reachable
state is always even.  But since one is odd, it is not possible to reach a
state in which there is exactly one head showing.

}

\end{problemparts}
\end{problem}
                                 