\documentclass[12pt,twoside]{article}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\graphicspath{{../problemRepository/figs/}}
%\usepackage{amsmath}
\usepackage{psfig}  
\input{../handouts/macros-course}
\newcommand{\cross}{\times}
\newcommand{\eqdef}{\mathbin{::=}}



%\def\cent{{\not\!\mathrm{c}}}
\renewcommand{\implies}{\longrightarrow}
\renewcommand{\labelenumi}{\arabic{enumi})}  
\setlength{\itemsep}{0cm}

%\newcommand{\solution}[1]{}
%\newcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}
\askaboutsolutions

\begin{document}

\handout{tut5}{Mini-Quiz 5}{March 9, 2001}
\begin{enumerate}
\item Your name:
\item How many 6.042 lectures have there been this term?
\end{enumerate}


\newpage

\thispagestyle{empty}

\mbox{}

\setcounter{page}{0}

\newpage



\handout{tut5}{Tutorial 5 Problems}{March 9, 2001}


\begin{problems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem  Four people are interested in participating in
the VI-A program where each person ranks his top choices of companies
and the companies rank the students as well.  The people Albert, Ben,
Chris, and Doug are interested in companies AT\&T, Bellcore, Compaq,
and Draper Labs.  Below are the students' rankings of the companies
and the companies' rankings of the students.

\begin{center}
\begin{tabular}{c|c} 
Student & Companies \\ \hline
Albert:  & Compaq, Bellcore, AT\&T, Draper \\
Ben:     & AT\&T, Bellcore, Draper, Compaq \\
Chris:   & Compaq, Draper, AT\&T, Bellcore \\
Doug:    & Draper, AT\&T, Bellcore, Compaq 
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{c|c}
Company & Students \\ \hline
AT\&T:    & Doug, Albert, Chris, Ben \\
Bellcore: & Chris, Ben, Albert, Doug \\
Compaq:   & Doug, Chris, Albert, Ben \\
Draper:   & Ben, Doug, Chris, Albert
\end{tabular}
\end{center}

\begin{problemparts}
\problempart What is a student-optimal stable marriage set for
this problem?

\solution{
You were guaranteed to get a student-optimal stable marriage set if
you ran the stable marriage algorithm given in lecture, where Students
are Men and Companies are Women.  The result is the following assignment:

\begin{center}
\begin{tabular}{c|c|c} 
Student & Companies & Rank in the original list \\ \hline
Albert:  & Bellcore & 2\\
Ben:     & AT\&T & 1\\
Chris:   & Compaq & 1\\
Doug:    & Draper &1
\end{tabular}
\end{center}
}

\problempart What is a company-optimal stable marriage set for
this problem?

\solution{
Similarly, you were guaranteed to get a company-optimal stable
marriage set if you ran the stable marriage algorithm given in
lecture, where Students are Women and Companies are Men.  The result
is the following assignment:

\begin{center}
\begin{tabular}{c|c|c}
Company & Students & Rank in the original list\\ \hline
AT\&T:    & Albert & 2\\
Bellcore: & Ben & 2\\
Compaq:   & Chris & 2\\
Draper:   & Doug & 2
\end{tabular}
\end{center}
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem \textbf{The 15 puzzle.}  This puzzle consists of sliding square
tiles numbered $1,\dots,15$ held in a $4\times4$ frame with one blank
square.  Any tile adjacent to the blank square can slide into it.

The state machine model of the puzzle has states consisting of a 4 by 4
matrix with 16 entries consisting of the integers $1,\dots,15$ and a
blank.  For example, the standard initial position is
\[\begin{array}{|c|c|c|c|}
\hline 1 & 2 & 3 & 4\\
\hline 5 & 6 & 7 & 8\\
\hline 9 & 10 & 11 & 12\\
\hline 13 & 14  & 15 & \\
\hline
\end{array}\]
We would like to reach the target position (known in my youth as ``the
impossible'' --- ARM):
\[\begin{array}{|c|c|c|c|}
\hline 15 & 14 & 13 & 12\\
\hline 11 & 10 & 9 & 8\\
\hline7 & 6 & 5 & 4\\
\hline3 & 2 & 1 & \\
\hline
\end{array}\]

The state transitions correspond to exchanging the blank square and an
adjacent numbered tile.  For example, a blank at position $(2,2)$ can
exchange position with tile above it, namely, at position $(1,2)$:
\[\begin{array}{|c|c|c|c|}
\hline n_1 & n_2 & n_3 & n_4\\
\hline n_5 &  & n_6 & n_7\\
\hline n_8  & n_9 & n_{10} & n_{11}\\
\hline n_{12} & n_{13} & n_{14}  & n_{15}\\
\hline
\end{array} \longrightarrow
\begin{array}{|c|c|c|c|}
\hline n_1 &  & n_3 & n_4\\
\hline n_5 & n_2 & n_6 & n_7\\
\hline n_8  & n_9 & n_{10} & n_{11}\\
\hline n_{12} & n_{13} & n_{14}  & n_{15}\\
\hline
\end{array} 
\]

In this problem you will use the invariant method prove that starting from
the initial state, there is no way to reach the target state.

We begin by noting that a state can also be represented as a pair
consisting of two
things:
\begin{enumerate}

\item a list of the numbers $1,\dots,15$ in the order in which they
appear---reading rows left-to-right from the top row down, ignoring the
blank square, and

\item the coordinates of the blank square---where the upper left
square has coordinates $(1,1)$, the lower right $(4,4)$.

\end{enumerate}
Let $L$ be such an ordered list of the numbers $1,\dots,15$.  A pair of
integers is an \emph{out-of-order pair} in $L$ when the first element of
the pair both comes earlier in the list, and is larger, than the second element
of the pair. For example, the list 12453 has two out-of-order
pairs: 43 and 53.  The increasing list $12\dots n$ has no out-of-order
pairs.

\bparts

Representing a state, $S$, as the pair $(L, (i,j))$ described above,
define the \emph{parity} of $S$ to be the mod 2 sum of the number of
out-of-order pairs in $L$ and the row-number, $i$, of the blank square.

\ppart Verify that the parity of the initial state and the parity of the
target state are different.

\solution{The parity of the initial state is $0+4 \bmod 2 = 0$.  Parity of
target is $((15 \cdot 14/ 2) + 4) \bmod 2 = 1$.}

\ppart  Show that the parity of a state is invariant under transitions.
Conclude that ``the impossible'' is impossible to reach.

\solution{

To show that the parity is constant, note that horizontal moves change
nothing, and vertical moves both change $i$ by 1, and move a tile three
places forward or back in the list, $L$.  This reverses the order of three
pairs in $L$, changing the number of inversions by 3 or 1, but always by
an odd amount.  So the sum of $i$ and the number of out-of-order pairs
changes by an even amount, which implies that its parity remains the same.
Since the initial state has parity 0 (even), all states reachable from the
initial state must have parity 0, so the target state with parity 1 can't
be reachable.

}

\eparts

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

\newpage
\problem
Suppose that the following procedure is used to multiply two
non-negative integers $a$ and $b$.

\centerline{
\begin{minipage}{0 in}
\medskip
\begin{tabbing}
xxx \= xxx \= xxx \= xxx \= xxx \= xxx \= \kill
Let $x = a$, $y = b$, $p = 0$. \\
Repeat the following steps. \\
\> If $x = 0$, then output $p$ and terminate. \\
\> Otherwise, if $x$ is even, then let $x = x/2$ and $y = 2y$. \\
\> Otherwise, if $x$ is odd, then let $x = x - 1$ and $p = p + y$.
\end{tabbing}
\medskip
\end{minipage}}

\begin{problemparts}

\problempart Model the procedure with a state machine.

\solution{The set of states $Q$ consists of quintuples $(a, b, x, y,
p)$ where all variables are non-negative integers.  The set of start
states $Q_0$ consists of the single state $(a, b, a, b, 0)$.  The set
of transitions $\delta$ consists of transitions of the form $(a, b, x,
y, p) \rightarrow (a, b, x', y', p')$ where one of the following two
sets of conditions holds:

\begin{enumerate}
\item $x$ is even and positive, $x' = x/2$, $y' = 2y$, and $p' = p$.
\item $x$ is odd, $x' = x - 1$, $y' = y$, and $p' = p + y$.
\end{enumerate}
}

\problempart Formulate an invariant relating $a$, $b$, $x$, $y$, and
$p$ that holds at the top of the loop.  Your invariant should imply
that when $x = 0$, $p = ab$.

\solution{
\[
xy + p = ab
\]
}

\problempart Prove that the invariant holds.

\solution{ The invariant holds initially, because $x = a$, $y = b$,
and $p = 0$.  Suppose that the invariant holds in state $(a, b, x, y,
p)$.  The invariant holds under a transition of the first type because:

\begin{eqnarray*}
x' y' + p'      & = &   (x / 2) \cdot 2y + p \\
                & = &   x y + p \\
                & = &   a b
\end{eqnarray*}

The first equation follows from the definition of the first type of
transition.  The second line is obtained by simplification, and the
third line uses the hypothesis that the invariant holds prior to the
transition.  By similar reasoning, the invariant holds under a
transition of the second type:

\begin{eqnarray*}
x' y' + p'      & = &   (x - 1) \cdot y + (p + y)\\
                & = &   x y + p \\
                & = &   a b
\end{eqnarray*}
}

\problempart Prove that the procedure terminates.

\solution{The variable $x$ is a non-negative integer that decreases
under every transition.  Therefore, the procedure must terminate after
at most $x$ transitions.}

\end{problemparts}

%%%%%%%%%% PROBLEM %%%%%%%%%

\problem
Over the weekend, your 6.042 TAs came across the following puzzle: a
$3 \times 3$ grid of squares, where each square contains one of the
digits in the set $\set{1, 2, 3, 4, 5, 6, 7, 8, 9}$, each digit
appearing exactly once in the puzzle.  Each row can be rotated right
or left and each column can be rotated up or down.  The effects of
such rotations are demonstrated in the following figure.

\begin{figure}[htbp]
  \begin{center}
    \leavevmode

\[
\begin{array}{|c|c|c|}
\hline
2 & 3 & 6 \\ \hline
7 & 8 & 9 \\ \hline
5 & 4 & 1 \\ \hline
\end{array}
\rightarrow
\begin{array}{|c|c|c|}
\hline
5 & 3 & 6 \\ \hline
2 & 8 & 9 \\ \hline
7 & 4 & 1 \\ \hline
\end{array}
\rightarrow
\begin{array}{|c|c|c|}
\hline
5 & 3 & 6 \\ \hline
8 & 9 & 2 \\ \hline
7 & 4 & 1 \\ \hline
\end{array}
\]

  \end{center}
  \caption{Examples of puzzle row and column rotations.}
  \label{fig:roteg}
\end{figure}

The first picture shows the initial configuration of the puzzle.  The
leftmost column is then rotated downward to give the middle picture.
The $2$ and $7$ move down and the $5$ rotates back up to the top.
Then, the middle row is rotated leftward to produce the final picture.
The $8$ and $9$ move left and the $2$ rotates back around to the
right.

Since discovering the puzzle, your 6.042 TAs have spent hours trying
to obtain the following configuration, starting of course from the
initial configuration of Figure~\ref{fig:roteg} and using legal row
and column rotations.

\[
\begin{array}{|c|c|c|}
\hline
1 & 2 & 3 \\ \hline
4 & 5 & 6 \\ \hline
7 & 8 & 9 \\ \hline
\end{array}
\]

Sad to say, your 6.042 TAs have failed miserably.

Based on prior experience with puzzles, the 6.042 students believe
that the puzzle might be designed in a way that makes this
configuration impossible, no matter what sequence of row and column
rotations one attempts.

\begin{problemparts}

  \problempart Model the puzzle as a state machine.

\solution{
The puzzle can be modeled by the state machine $M$ defined as follows:

\begin{itemize}

\item The set of states $Q$ consists of all arrangements of the digits
  in the set $\set{1, 2, 3, 4, 5, 6, 7, 8, 9}$ on a $3 \times 3$ grid
  where each digit appears exactly once.

\item The set of start states $Q_0$ consists of the single arrangement
  236 789 541.

\item The set $\delta \subseteq Q \times Q$ consists of all pairs of
  states $(q_1, q_2)$ such that $q_2$ can be obtained from $q_1$ by a
  row or column rotation.

\end{itemize}
}

\problempart Given the initial configuration of the puzzle indicated
above, namely 236 789 541, prove that your 6.042 TAs can never obtain
the configuration 123 456 789.

\solution{%

  The idea is to keep track of the number of digit pairs that are out
  of order relative to the desired configuration 123 456 789.  For
  example, in the initial configuration, $2$ appears before $1$; this
  pair of digits is out of order, because $1$ appears before $2$ in
  the desired configuration 123 456 789.  We will refer to an
  out-of-order digit pair as an {\em inversion}.  In the initial
  configuration, there are 17 inversions:

\[
\begin{array}{ccccc}
21 & 31 & 61 & 64 & 61 \\
75 & 74 & 71 & 85 & 84 \\
81 & 95 & 94 & 91 & 54 \\
51 & 41
\end{array}
\]

The key observation is that a rotation always changes the number of
inversions by an even amount.  Since the puzzle initially has an odd
number of inversions, no sequence of rotations can reduce the number
of inversions to 0, an even number.  Consequently, there will always
be at least one pair of digits out of order.

The main challenge is to prove that a rotation always changes the
number of inversions by an even amount.  We will prove this claim in a
sequence of lemmas, and then we will prove the main result as a
theorem.

\begin{lemma}
Swapping an adjacent pair of digits changes the number of inversions
by an odd amount.
\end{lemma}

\begin{proof}
  If the digits were initially in the same order as in 123 456 789,
  then the number of inversions is increased by 1, an odd number.
  Otherwise, the digits were initially in the wrong order, and the
  number of inversions is decreased by 1, also an odd number.
\end{proof}

\begin{lemma}
Swapping any pair of digits changes the number of inversions by an
odd amount.
\end{lemma}

\begin{proof}
  We will show how to swap any pair of digits using an odd number of
  swaps of adjacent digits.  The preceding lemma says that swapping
  adjacent digits changes the number of inversions by an odd amount.
  Therefore, swapping any pair of digits changes the number of
  inversions by an odd amount, because the sum of an odd number of odd
  numbers is odd.

  All that remains is to show how to swap any pair of digits using an
  odd number of swaps of adjacent digits.  Suppose that we are
  swapping digits $x$ and $y$, where $x$ is on the left, $y$ is on the
  right, and there are $k$ stray digits between the two.  First, we
  swap $x$ with its right neighbor $k$ times.  This leaves $x$
  directly left of $y$ and leaves all the stray digits shifted one
  place to the left.  Then we swap $x$ and $y$, putting $x$ into $y$'s
  original positions.  Finally, we swap $y$ with its left neighbor $k$
  times.  This puts $y$ into $x$'s original position and shifts the
  stray digits back to their original position.  The total number of
  swaps of adjacent digits is $k + 1 + k = 2k + 1$, which is odd for
  all $k \geq 0$.
\end{proof}

\begin{lemma}\label{lem:rotate}
  Rotating any row or column changes the number of inversions by an
  even amount.
\end{lemma}

\begin{proof}
  We show below that any row or column rotation can be obtained by two
  swaps.  The preceding lemma says that every swap changes the number
  of inversions by an even amount.  Since the sum of two odd numbers
  is even, any row or column rotation changes the number of inversions
  by an even amount.

  Here is how to obtain a rotation from two swaps.  Suppose that the
  digit sequence $xyz$ appears in some row or column.  Swapping $x$
  with $y$ and then swapping $x$ with $z$ creates the sequence $yzx$,
  which corresponds to a leftward or upward rotation.  Swapping $z$
  with $y$ and then $z$ with $x$ creates the sequence $zxy$.  This
  corresponds to a rightward or downward rotation.
\end{proof}

\begin{theorem}
  Your 6.042 TAs can not obtain the configuration 123 456 789.
\end{theorem}

\begin{proof}
  Let $P$ be a predicate on the states of $M$, denoting whether the
  number of inversions in the digit sequence of the puzzle relative to
  the 123 456 789 sequence is odd.  Moreover, let $P'(n)$, for $n \geq
  0$, be the predicate that asserts $P$ for all states that can be
  reached by $n$-step executions of $M$.  We show that $P$ is an
  invariant property of $M$, by showing that $P'(n)$ holds for all
  $n\geq0$.  The proof is by induction on the length $n$ of the
  execution of the state machine $M$.

  For the base case, we need to show that the property holds in the
  start state, \ie an execution of length $n = 0$.  This is true
  because in the initial configuration, the number of inversions is
  odd, in particular equal to 17.  For the inductive step, we must
  show that if $P$ holds for any configuration reachable after $n$
  steps of $M$, the $P$ holds for any configuration reachable after
  $n+1$ steps of $M$.  Fix $n \geq 0$ and let $q_0, q_1,\ldots, q_n,
  q_{n+1}$ denote any $n+1$-step execution of $M$.  $q_n$ is thus the
  final state of an $n$-step execution of $M$.  Thus, by our inductive
  hypothesis, in the state $q_n$, the puzzle has an odd number of
  inversions.  Now, consider the final step $(q_n,q_{n+1})$ of the
  $n+1$-step execution of $M$.  By Lemma~\ref{lem:rotate}, this step
  changes the number of rotations by an even amount.  It follows that
  the number of rotations of the state $q_{n+1}$ is odd.  Thus, by
  induction, we have shown that $P$ is an invariant property of $M$.

  Finally, since the number of inversions relative to 123 456 789 is
  always odd, the desired configuration with 0 inversions can not be
  obtained.
\end{proof}

In the above proof, we have proven that the the property that the
puzzle has an odd number of inversions is an invariant property of the
state machine $M$.
}

\end{problemparts}

\end{problems}
\end{document}



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

\problem In this problem we'll generalize the choose-a-pair game to
``choose-a-tuple''.  Here are the rules:

Player 1 chooses any integer $n\geq 1$.  Then player 2 chooses any
$n$-tuple of natural numbers.  After that, the players alternate moves,
choosing at each move any $n$-tuple of natural numbers which is NOT
coordinatewise $\geq$ any previously chosen $n$-tuple.  The game ends when
some player cannot move.

For example, player 1 might begin by choosing $n=3$.  Then player 2 might
choose the 3-tuple (8, 9, 10).  Possible subsequent choices might then be
\[
(7,8,9), (0,1,67), (83, 0,0), (1,0,0), (0,0,1) (0,1,0)
\]
This finally leaves player 1 with only the move (0,0,0), and the game ends
since no more moves are possible.

It turns out that every one of these games must end at some point; no game
can go on forever!  You proved this for the $n=2$ case on Problem Set 6 by
applying an ingenious, \emph{ad hoc}, well-ordering to the states of the
game.  Rather than try to generalize that bit of ingenuity (which can get
messy), we'll help you to prove this remarkable fact by developing
properties of a special class of well-founded posets.

\begin{defin}
A poset $(P,\prec)$ is \emph{well-quasi-ordered} iff, for every nonempty
subset $S \subseteq P$ has at least one, but at most a finite number of,
minimal elements.
\end{defin}

\bparts

\ppart Prove:
\begin{lemma}\label{coord-wqo}
Suppose  $(P, \leq_P)$ and $(Q, \leq_Q)$ are well-quasi-ordered posets.
Then so is $P \cross Q$ under the coordinatewise partial order.
\end{lemma}

\solution{

Suppose $\emptyset \neq S \subseteq P \cross Q$.  We first prove $S$ has
at least one minimal element.  This was proved in S99, Handout 18 as
follows:

\begin{proof}
Then $\set{p \in P \mid (p,q) \in S \mbox{ for some } q \in Q}$ is a
nonempty subset of $P$, and so has a $\leq_P$-minimal element $m_P$.  Now
$\set{q \in Q \mid (m_P,q) \in S}$ is a nonempty subset of $Q$ and so has
a $\leq_Q$-minimal element $m_Q$.  It follows that $(m_P,m_Q)$ is a
coordinatewise minimal element of $S$.
\end{proof}

Now suppose $S$ had an infinite set $F \subseteq S$ of minimal elements.  
Then $\set{p \in P \mid (p,q) \in F \mbox{ for some } q \in Q}$ is
a nonempty subset of $P$, and so has only finitely many minimal elements
of $P$.  TO BE COMPLETED
}

\ppart Now prove that any choose-a-tuple game must end.

\solution{
\begin{proof}
Just show by induction on $n\geq 1$ that $\naturals^n$ under
coordinatewise order is well-quasi-ordered.  The base case $n=1$ is
immediate, and Lemma~\ref{coord-wqo} handles the induction case.
\end{proof}
}

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem  %S98 Q1

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.

\bparts
\ppart
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.
}

\ppart 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}
}

\ppart
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}


\ppart 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.

}

\eparts
