\documentclass[11pt,twoside]{article}	
\usepackage{latex-macros/course}
\usepackage{textcomp} % to get \textcent
\usepackage{psfig}

\renewcommand{\reading}{
\href{
http://theory.lcs.mit.edu/classes/6.042/fall02/handouts/lectures/ln2.pdf}
{Week 2 Notes}, Rosen \S 3.2, 3.3 through Example 6.}
\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

%\hidesolutionsls

%\showsolutions

\begin{document}
\problemset{2}

\instatements{
\textbf{Reading Comments (required):} By 11am on the \emph{Reading
Problems due date} (which is generally the week before the pset due date),
send email to
\begin{center}
\href{mailto:6042-probs@theory.lcs.mit.edu}{\texttt{6042-probs@theory.lcs.mit.edu}}
\end{center}
indicating in at most three sentences one or more of the following: the
passage in the reading---including its page number---you
\begin{itemize}
\item found most difficult, 
\item found most surprising, 
\item would like to have discussed in the next lecture. 
\end{itemize}
}

\begin{problem}
%f01-ps2-1

Use induction to prove that the following equation holds for all
$n \geq 2$.

\begin{equation*}
\left(1 - \frac{1}{2}\right)
\left(1 - \frac{1}{3}\right)
\cdots
\left(1 - \frac{1}{n}\right)  =  \frac{1}{n}
\end{equation*}

\solution{\begin{proof}
The proof is by induction on $n$.  Let $P(n)$ be the proposition that
the above equation holds.  In the base case, $P(2)$ is true because
$(1 - \frac{1}{2}) = \frac{1}{2}$.  In the inductive step, for $n \geq
2$ assume $P(n)$ to prove $P(n+1)$ as follows.

\begin{eqnarray*}
\left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right)
\cdots
\left(1 - \frac{1}{n}\right) \left(1 - \frac{1}{n+1}\right)
        & = &   \frac{1}{n} \left(1 - \frac{1}{n+1}\right) \\
        & = &   \frac{1}{n} \cdot \frac{n}{n+1} \\
        & = &   \frac{1}{n+1}
\end{eqnarray*}

The first step uses the induction hypothesis, and the second and third
steps are simplifications.  This shows that $P(n)$ implies $P(n+1)$,
and the claim is proved by induction.
\end{proof}
}

\end{problem}

%------------------------------------------------
\begin{problem}
%s00-ps2-1
% ordinary induction 
% source: 

Suppose you take a piece of paper and draw a bunch of straight lines, no one
exactly on top of another, that completely cross the paper.  This divides
the paper up into polygonal regions.  Prove by induction that you can
always color the various regions using only \emph{two} colors, so that any
two regions that share a boundary line are different colors.  Regions that
share only a boundary point may have the same color.

\solution{ We assume that all lines are straight and completely cross the
  paper.  Also, when we say that the regions are colored, we always mean
  they are colored using at most two colors, \eg red and green.  We say
  that two regions are \emph{adjacent} if they share a boundary line.
  Note that two regions cannot share two distinct boundary lines.

  Let $P(n)$ be the predicate that the regions formed by any set of $n$
  distinct lines can be colored so that any two adjacent regions are
  colored with different colors.  We prove that $P(n)$ holds for all $n
  \in \naturals$ by induction on $n$.

\begin{description}

\item[Base case:] The base case is $P(0)$.  There is only one region,
namely the whole page, and thus there are no adjacent regions. The region may be colored either red or green.

\item[Inductive step:] We must show that for all $n \in \naturals$ it is
the case that $(P(n) \implies P(n+1))$; that is, if the regions formed by
any $n$ distinct lines can be two-colored so that adjacent regions have
different colors, then the regions formed by any $n+1$ distinct lines can
be two-colored so that adjacent regions have different colors.


%\textbf{REVISE INTO READABLE UNSTRUCTURED FORM:}


\begin{enumerate}

% \item 

\item
Assume that the regions formed by any $n$ distinct lines 
can be colored so that adjacent regions have different colors. 


%\item
%Fix a set of $n+1$ lines. 
%These lines divide the paper into a set $X$ of regions. 

\item
Given a paper containing $n+1$ distinct lines that completely 
cross the paper, choose any single line $l$ and erase it.

%The remianing $n$ other lines divide the paper into a set $Y$ of regions, 
%such that every region in $X$ is either a region in $Y$ 
%or else it is part of a region in $Y$ that is split by $l$. 

\item
By the inductive hypothesis, 
the regions formed by the $n$ remaining lines can be colored 
so that adjacent regions are different colors. 

Call this coloring of the regions the original coloring and redraw line $l$.

\item Line $l$ splits the paper into two sides.  Select one of the
  sides and flip all the colors of the regions on that side 
  (a region that was previously red should be green and vice versa). Leave the other side of line $l$ exactly the way it was in the original coloring.
 We will prove that, using the new coloring, any adjacent 
	regions have different colors.

%\begin{enumerate}

\item Choose any two adjacent regions in the new coloring.  
\begin{description}

\item[Case 1:\ ] The regions share boundary line $l$.  The two regions
  had the same color in the original coloring.  The two regions are on
  opposite sides of $l$.  Therefore, the color in exactly one of the
  two regions was flipped and they have different colors in the new
  coloring.

\item[Case 2:\ ] The regions do not share boundary line $l$.  The two
  regions had different colors in the original coloring, and they are
  on the same side of $l$.  Thus, the color of either none or both
  regions was flipped and the two regions have different colors in
  the new coloring.

\end{description}


\item 
The regions formed by any $n+1$ distinct lines 
can be colored so that adjacent regions have different colors. 


%\item QED (universal generalization over adjacent regions)

%\end{enumerate}

%\item QED (universal generalization over sets of $n+1$ lines)

%\end{enumerate}

%\item QED (implication)

\end{enumerate}

\item QED (induction)

\end{description}
}
\end{problem}

%------------------------------------------------

\begin{problem} 

%f01-ps2-4  Routine

The 6.042 course information sheet states:

\begin{quotation}\noindent
Tutorials will be devoted to solving interesting problems, with students
working in teams of three or four.
\end{quotation}

Using strong induction, prove that if a recitation contains at least 6
students, then the class can be divided into teams, each consisting of
either 3 or 4 students.

\solution{\begin{proof}
The proof is by strong induction.  Let $P(n)$ be the proposition that
a recitation with $n$ students can be divided into teams of 3 or 4.
In the base cases, $P(6)$ is true because there could be two teams of
3, $P(7)$ is true because there could be a team of 3 and a team of 4,
and $P(8)$ is true because there could be two teams of 4.  In the
inductive step, for $n \geq 8$, assume $P(6), \ldots, P(n)$ to prove
$P(n+1)$.  If a recitation has $n+1$ students, then three students can
form a team of 3, and the remaining $n-2$ students can be divided into
teams of 3 or 4 by induction.  This shows that $P(6), \ldots, P(n)$
imply $P(n+1)$, and the claim is proved by induction.
\end{proof}}

\end{problem}

\iffalse
%------------------------------------------------

%boring

\begin{problem}
%s00-ps2-3
% ordinary induction
% source: fall98

Prove by induction on $n$ that for all $n \geq 0$, the inequality $|x|
+ |y| \leq n$ has exactly $2 n^2 + 2n + 1$ solutions where $x$ and $y$
are integers.

\solution{
  Let $P(n)$ be the proposition that there are $2 n^2 + 2n + 1$
  solutions to the inequality $|x| + |y| \leq n$, where $x$ and $y$
  are integers.  We prove that $P(n)$ holds for all $n \geq 0$ by
  induction on~$n$.

  In the base case, $P(0)$ is true because $2 (0)^2 + 2 (0) + 1 = 1$
  and there is one solution to the equation $|x| + |y| \leq 0$, namely
  $x = y = 0$.  This is easily argued by contradiction.  Without loss
  of generality, suppose that $x$ is not zero.  Then, since $|z| \geq
  0$, for all $z$, and $|z| > 0$, for all $z \not = 0$, it follows
  that $|x| + |y| > 0$; a contradiction.  Thus, $x$ must be zero.

  In the inductive step, assume $P(n)$ to prove $P(n+1)$.  That is, we
  want to prove that there are $2 (n+1)^2 + 2 (n + 1) + 1 = 2n^2 + 6n
  + 5$ solutions to the inequality $|x| + |y| \leq n + 1$.  Every
  solution to this inequality is also either a solution to the tighter
  inequality $|x| + |y| \leq n$ or else to the equation $|x| + |y| = n
  + 1$.  Thus, the number of solutions is equal to the number of
  solutions to the tighter inequality plus the number of solutions to
  the equation.

  By the inductive hypothesis, there are $2 n^2 + 2n + 1$ solutions to
  the tighter inequality.  All that remains is to count solutions to
  the equation.  The value of $x$ must be in the range $-(n+1),
  \ldots, n+1$.  If $x$ takes on either of the two values $-(n+1)$ or
  $n+1$, then there is a single solution, with $y = 0$.  If $x$ takes
  on one of the $2n+1$ values in the range $-n, \ldots, n$, then there
  are two solutions, one with $y = n + 1 - |x|$ and one with $y = -(n
  + 1 - |x|)$.  Thus, there are $2 + 2 \cdot (2n + 1) = 4n + 4$
  solutions to the equation and $2 n^2 + 2n + 1$ solutions to the
  tighter inequality, giving $2 n^2 + 6n + 5$ solutions in all, as
  desired.  Therefore, $P(n)$ implies $P(n+1)$, which concludes the
  inductive step.
}
\end{problem}


%------------------------------------------------
% \begin{problem}
% The C.I.A. wants you to design plans to build, for an arbitrary $k
% \geq 1$, a $2^k \times 2^k \times 2^k$ cubic foot granite cube that is
% solid except for a missing single cubic foot that is one of the eight
% cubic feet nearest the center of the cube.  It will have one of its
% corners exactly at the center of the large cube.  The C.I.A. is not
% telling you what is to be placed inside the cube.

% You are to build this by cementing together {\em basic blocks} that
% are 2-foot $\times$ 2-foot $\times$ 2-foot cubes, with one one-foot
% cube missing from its corner~---~as shown in the diagram below.

% \begin{figure}[h]
% \centerline{\psfig{figure=figures/cube.ps,height=1in}}
% \end{figure}

% Describe your method for doing this.  Your plans should be described
% recursively on $k$.

%   \solution{
%     Let an $2^n \times 2^n \times 2^n$ cube with an arbitrary one-foot
%     cubic block missing be denoted as an $n$-cube.  Moreover,
%     throughout this problem, we assume that the one-foot block that is
%     missing from any $n$-cube is at a lattice point, \ie at an
%     integral number of feet from each side.

%     \begin{theorem*} 
%       For any positive integer $n$, any $n$-cube can be build out of
%       $1$-cubes.
%     \end{theorem*}
%     \begin{proof} 
%       Let $P(n)$ be the predicate that an $n$-cube can be build out of
%       $1$-cubes.  We prove that $P(n)$ holds for any positive integer
%       $n$ by induction on $n$.
      
%       \begin{description}\itemsep 0ex
%       \item[Base Case:~~] $P(1)$ is true since a $1$-cube is what we
%         need to build.  This is precisely what we are given as a basic
%         block.
 
%       \item[Inductive Step:~~] We must show that for any positive
%         integer $n$, $P(n)$ implies $P(n+1)$.  Consider an
%         $(n+1)$-cube.  This block can be built using eight $n$-cubes
%         as follows: build seven $n$-cubes such that they are all
%         missing one of their corner blocks, arrange them so that their
%         missing corner blocks meet in the center of the $(n+1)$-cube,
%         fill up the gap with a $1$-cube such that the corner
%         corresponding to the eighth $n$-cube is left empty, and,
%         finally, build the eighth $n$-cube such that the appropriate
%         one-foot cubic block is missing.  Notice, that the eight
%         $n$-cubes can be build as desired because of the inductive
%         hypothesis; that is, that any $n$-cube can be build out of
%         $1$-cubes.
%       \end{description}
%     \end{proof}

%     Now, we can state the following corollary.

%     \begin{corollary*}
%       For any positive integer $n$, an $n$-cube with any one-foot
%       cubic block missing from its center can be build out of
%       $1$-cubes.
%     \end{corollary*}
%     \begin{proof}
%       $n$-cubes of this particular form, \ie with any one-foot cubic
%       block missing from their center, is a particular case of what we
%       showed in the above Theorem.  Thus, we know that $n$-cube with
%       any one-foot cubic block missing from its center can be build
%       out of $1$-cubes.  The construction of such a block can be done
%       as outlined in the above theorem, with the exception that the
%       missing one-foot block is missing from the center of the
%       $(n+1)$-cube.
%     \end{proof}
%   }
% \end{problem}

%------------------------------------------------

\fi

\begin{problem}
%s00-ps2-7
% strong induction
% source: Velleman section 6.4, problem 9

Let the function, $g$, be defined on the natural numbers recursively as
follows: $g(0) = 0$, $g(1) = 1$, and $g(n) = 5 g(n-1) - 6 g(n-2)$, for
$n \geq 2$.

Prove that for all $n \in \naturals$, $g(n) = 3^n - 2^n$.

\solution{
  Let $P(n)$ be the predicate that $g(n) = 3^n - 2^n$.  We prove
  $P(n)$, for all $n \in \naturals$, by strong induction on $n$.

  \begin{description}\itemsep 0\baselineskip
  \item[Base Case:] In order to simplify the strong
    induction, we use two base cases, in particular $n = 0$ and $n =
    1$.  By the definition of the sequence it is the case that $g(0) =
    0$.  For $n = 0$, it is the case that $3^n - 2^n = 3^0 - 2^0 = 1 -
    1 = 0$; that is, it follows that $P(0)$ holds.  Similarly, by the
    definition of the sequence it is the case that $g(1) = 1$.  For $n
    = 1$, it is the case that $3^n - 2^n = 3^1 - 2^1 = 3 - 2 = 1$;
    that is, it follows that $P(1)$ holds.

  \item[Inductive Step:]
    We must show that for all $n \in \naturals, n \geq 1$, it is the case
    that $P(n+1)$ holds, assuming $P(k)$ holds for $0 \le k < n+1$.
    
    \begin{enumerate}\itemsep 0\baselineskip
  %  \item Fix $n \in \naturals, n \geq 2$.
      
    \item Assume that for some $n \in \naturals, n \geq 1$, the elements
      of the sequence $g(x)$, for $0 \leq x \leq n$, can be expressed as
      $g(x) = 3^x - 2^x$.
      
%    \item The element of the sequence $g(n+1)$ can be expressed as
%      $g(n+1) = 3^{n+1} - 2^{n+1}$.
      
%      \begin{enumerate}\itemsep 0\baselineskip

      \item By the definition of the sequence we have $g(n+1) = 5 g(n)
        - 6 g(n-1)$.  
        
      \item By our induction hypothesis, it is the case that $g(n) =
        3^n - 2^n$ and $g({n-1}) = 3^{n-1} - 2^{n-1}$
        
      \item Thus,	
	 $g({n+1}) $ 
\newline = $ 5 (3^n - 2^n) - 6 (3^{n-1} - 2^{n-1})$ 
\newline  =   $  5*3^n - 5*2^n - 2*(3)3^{n-1} + 3*(2)2^{n-1} $ 
\newline  =   $ 5*3^n - 5*2^n - 2*3^n + 3*2^n $ 
\newline  =  	$ 3*3^n - 2*2^n $ 
\newline  = 	$ 3^{n+1} - 2^{n+1} $
	
        Working through the algebra, we conclude that $g(n+1) =
        3^{n+1} - 2^{n+1}$, as needed for the inductive step.
        
 %     \item QED 
        
%      \end{enumerate}
      
    \item QED (implication and UG)
      
    \end{enumerate}
    
  \item QED (induction)
    
  \end{description}

}
\end{problem}


\iffalse
% Doesn't seem specially interesting to me; do you agree?

%------------------------------------------------
% \begin{problem}
% %f01-ps2-2
% Velleman 6.2, problem 6.

% \solution{
% The proof is by induction.

% Let P(n) be the proposition that any equilateral triangle, that is cut into 
% $4^n$ congruent equilateral triangles with one corner removed, can be tiled 
% using tiles composed of three of the smaller congruent triangles.

% \textbf{Base case} $n=1$:  With one corner removed, a single tile can be
% used to cover the remaining area.
% %\mbox{\epsfbox{figures/ps2P5BaseCase.ps}}

% \textbf{Inductive step}: Consider a triangle, $T$, cut into $4^{n+1}$
% congruent equilateral triangles.  We can think of this triangle as being
% cut into four smaller equilateral triangles, which are each then cut into
% $4^n$ equilateral triangles.  Remove the top corner of $T$.  We know that
% we can tile the triangle that contains the removed corner by the inductive
% hypothesis.  Note that the remaining area contains three triangles, who
% have corners that meet in the same place; namely, the bottom of T,
% directly below the removed corner.  If we consider each of these triangles
% with the touching corners removed, then the inductive hypothesis says that
% we can tile each one separately.  To complete the tiling, simply use a
% single tile to cover the three adjacent removed corners, illustrated in
% Figure~\ref{triangle}.

% \begin{figure}[ht]
% \centering
% \includegraphics[width=4in]{figures/ps2P5inductive}
% \caption{The original triangle $T$.  Dark lines indicate borders of the four
% smaller triangles; light lines indicate borders of the $4^n$ triangles
% that the smaller triangles are cut into.  The black triangle is the removed
% corner; the gray triangles indicate the corners that are removed from the
% smaller triangles in order to apply the inductive hypothesis, which are
% then covered by a single tile.}\label{triangle}
% \end{figure}
% }
% \end{problem}

%------------------------------------------------
\fi


%F01 Q1  Double induction, uniqueness.  Could be extended to cover
% recursively defined set of pairs and prove existence of function.
% BETTER TO RE-EDIT AS A PSET PROBLEM.

\begin{problem}

Ackermann's function, $f: \naturals \cross \naturals \to \naturals$, satisfies
the following equations:
\begin{align}
f(m,n) &=  2n, &&\text{if $m=0$ or $n \le 1$},\label{Am0}\\ 
f(m,n) &=  f(m-1,f(m,n-1)), &&\text{if $m > 0$ and $n > 1$}.\label{AA}
\end{align}

These equations actually determine Ackermann's function uniquely.  That
is,
\begin{lemma*}
If $g: \naturals \cross \naturals \to \naturals$ also satisfies
the same equations as $f$, namely,
\begin{align}
g(m,n) &=  2n, &&\text{if $m=0$ or $n \le 1$},\label{Bm0}\\ 
g(m,n) &=  g(m-1,g(m,n-1)), &&\text{if $m > 0$ and $n > 1$},\label{BB}
\end{align}
then $f = g$.
\end{lemma*}

\bparts

\ppart Prove this Lemma \emph{by induction}.  \hint Try the induction
hypothesis
\[
P(m) \eqdef \forall n\; f(m,n)=g(m,n).
\]

\solution{

% THE VERSION BELOW WAS A QUIZ PROBLEM.  SHOULD BE REVISED INTO SOLN.

% In this question, we ask you to fill in or justify various parts of a
% proof of this Lemma.   The possible justifications are listed below.
% You must choose your answers from this list.

% \begin{itemize}
% \item one or more of the equations (\emph{indicate exactly which ones}) numbered
% (\ref{Am0}), (\ref{AA}), \dots (\ref{AB})
% \item $P(0)$
% \item $P(m)$
% \item $P(m+1)$
% \item $Q_m(0)$
% \item $Q_m(n)$
% \item $Q_0(n)$
% \item $Q_m(n+1)$
% \end{itemize}

\begin{proof}
We must prove that
\begin{eqnarray}
\forall m\, \forall n\ f(m,n) & = & g(m,n). \label{a=b}
\end{eqnarray}

The proof is by induction on $m$.  More precisely, the main induction
hypothesis, $P(m)$, is
\[
P(m) \eqdef\ \forall n\ f(m,n) = g(m,n).
\]

\textbf{Base case}: $m=0$.  It follows directly from equation(s)
(\ref{Am0}), ~(\ref{Bm0})
that $f(m,n) = g(m,n)$ for all $n$, confirming that $P(0)$
is true.

\textbf{Induction step}: Suppose $P(m)$ holds for some fixed $m \geq
0$.  We must prove that $P(m+1)$ also holds.

Namely, assuming $\forall n\ f(m,n)=g(m,n)$, we must prove

\begin{equation}
\forall n f(m+1,n)=g(m+1,n) \label{m+1}
\end{equation}


We prove~(\ref{m+1}) by another induction, this time on $n$,
using the induction hypothesis,
\[
Q_m(n) \eqdef\ f(m+1, n) = g(m+1,n).
\]

%%\begin{quotation}
\addtolength{\leftskip}{0.5in}%

\textbf{Base case}: $n=0$.  $Q_m(0)$ follows immediately from equation(s)
 (\ref{Am0}), ~(\ref{Bm0}).

\textbf{Induction step}: Suppose $Q_m(n)$ holds for some $n \geq 0$.  We
must prove that $Q_m(n+1)$ also holds.

Let $k \eqdef f(m+1, n)$, so
\begin{equation}
f(m+1, n+1) = f(m,k)\label{Ak}
\end{equation}
by (\ref{AA}).

Then also
\begin{equation}
k = g(m+1, n),\label{kB}
\end{equation}
because $Q_m(n)$
holds, and so
\begin{equation}
g(m+1, n+1) = g(m,k)\label{Bk}
\end{equation}
by (\ref{BB}).

But
\begin{equation}
f(m,k) = g(m,k),\label{AB}
\end{equation}
since $P(m)$
holds.  Now combining equations (\ref{Ak}), (\ref{Bk}), and~(\ref{AB}),
we obtain
\[
f(m+1, n+1) = g(m+1,n+1).
\]
That is, $Q_m(n+1)$ holds.

This completes the proof by induction on $n$ that~(\ref{m+1}) holds.
%%\end{quotation}
\addtolength{\leftskip}{-0.5in}%

So we have also completed the proof by induction on $m$ that $\forall m\ P(m)$.

That is, we have proved~(\ref{a=b}), as required.

\end{proof}

}

\ppart Now prove this Lemma \emph{using the Least Number Principle}.
\hint Consider the least $m$ such that $\exists n\; f(m,n) \neq g(m,n)$.

\solution{

%ALBERT's VERSION:

Suppose that $f \neq g$.  Then there must be values $m_0,n_0 \in
\naturals$ such that $f(m_0,n_0) \neq g(m_0,n_0)$.  So the set
\[
M \eqdef \set{m \suchthat \exists n\, f(m,n) \neq g(m,n)}
\]
is nonempty, because it contains $m_0$.  Therefore, it has a least
element, $m_1$.  But since $m_1 \in M$, it follows that the $N=\set{n
\suchthat f(m_1,n) \neq g(m_1,n)}$ is also nonempty, and so must contain a
least number, $n_1$.

Now, $m_1 > 0$ and $n_1 > 1$ because $f(m,n)=g(m,n)=2n$ for $m=0$ or $n
\le 1$ by equation~(\ref{Am0}).

%ALBERT STOPPED HERE; rest by nikos

Therefore $m_1-1 \notin M$ and $n_1-1 \notin N$ and we can assume the
following:
\begin{equation}
f(m_1-1,k) = g(m_1-1,k)\label{m-1,k}
\end{equation}
and
\begin{equation}
f(m_1,l) = g(m_1,l) \label{m,l}
\end{equation}
$\forall k,l \in \naturals$, and $l < n_1$.

 So letting $l=n_1 - 1$ in~(\ref{m,l}), we conclude that 
   \[
   f(m_1, n_1-1) = g(m_1, n_1-1).
   \]
   So we can replace the first $k$ in~(\ref{m-1,k}) by $f(m_1, n_1-1)$, and the
   second $k$ by $g(m_1, n_1-1)$, and conclude that
   \begin{equation}\label{end}
   f(m_1-1,f(m_1, n_1-1)) = g(m_1-1,g(m_1, n_1-1)).
   \end{equation}
   But by~(\ref{AA}) and (\ref{BB}), $f(m_1,n_1)$ is equal to the lefthand side
   of~(\ref{end}), and similarly, $g(m_1,n_1)$ is equal to the righthand side
   of~(\ref{end}).  Hence, we have proved that
   \[
   f(m_1,n_1) = g(m_1,n_1),
   \]
   contradicting our choice of $m_1,n_1$ as arguments where $f$ and $g$ differ.


%Let $l=n_1-1$, and $k=f(m_1,n_1-1)=g(m_1,n_1-1)$ (because of \ref{m,l}).
%That implies $f(m_1-1,f(m_1,n_1-1))=g(m_1-1,g(m_1,n_1-1))$ by \ref{m-1,k}.
%But by the definition of the Ackerman function that implies
%that $f(m_1,n_1)=g(m_1,n_1)$. This is a contradiction since
%$m_1 \in M$ and $n_1 \in N$.
%Therefore, $\forall m \forall n f(m,n) \neq g(m,n)$.
}

\eparts

\end{problem}

\begin{problem}

%(* difficult)

%From F97 PS2-10, much revised by ARM; also F01 PS2-8

An \emph{$n$-player tournament} consists of some set of $n\geq 2$
\emph{players}, and, for every two distinct players, a specification that
one of the players beats the other.  That is, player $p$ beats player $q$
iff $q$ does not beat $p$, for all players $p \neq q$.

A sequence of distinct players $p_1,p_2, \ldots, p_k$, such that player
$p_i$ beats player $p_{i+1}$ for $1 \leq i < k$ is called a {\em ranking}
of these players.  If also player $p_k$ beats player $p_1$, the ranking is
called a $k$-\emph{cycle}.

\begin{problemparts}

\problempart Prove by induction that in every tournament, either there is a
``champion'' player that beats every other player, or there is a 3-cycle.

\solution{The induction hypothesis $P(n)$, is
``In an $n$-player tournament, either there is a player that
beats every other player, or there is a 3-cycle.''

\textbf{Base case} $n=2$: By definition of a 2-player tournament, one of the
players beats the only other player and therefore is the champion.

\textbf{Inductive step}:
Assume that $P(n)$ is true in order to show that $P(n+1)$ is true.

Consider an $n+1$-player tournament.  If there is a champion, we are done.
So we may assume that every player is beaten by some other player.  Now
remove any player, say player $p$, and treat the remaining $n$ players as an
$n$-player tournament.  There are two cases:

1) Every player in the $n$-player tournament is beaten by some other
player in the tournament.

2) There is some champion in the $n$-player tournament who beats every
other player in the $n$-player tournament.

In case (1), we have by induction hypothesis a 3-cycle of players in the
$n$-player tournament.  Since a 3-cycle in the $n$-player tournament will
also be a 3-cycle in the full $n+1$-player tournament, we are OK in this
case.

In case (2), there is some ``champion'', $q$, in the $n$-player
tournament.  Since everybody in the ($n+1$)-player tournament is beaten by
somebody, $q$ must be beaten by a player not in the $n$-player tournament,
that is, $p$ beats $q$.  For the same reason, there is some
player $r$ that beats $p$.  Since $r$ is in the $n$-player tournament, $r$
is beaten by the champion $q$.  So we have found a 3-cycle $p,q,r$.
}

\problempart
A {\em consistent ranking} is a sequence $p_1,p_2, \ldots, p_n$ of all
$n$ players in the tournament such that $p_i$ beats $p_j$ iff $i < j$, for
$1 \leq i,j \leq n$.  Conclude that a tournament has no consistent ranking
iff some subset of three of its players has no consistent ranking.

\solution{By definition of tournament, the restriction of the
tournament to any subset of two or more of its players is also a
(sub)tournament.  Also any consistent ranking of a tournament remains
consistent when restricted to a subset of players.  So if some subset of
three players has no consistent ranking, then the whole tournament
can't have a consistent ranking either.

So we have only to prove the converse implication: if every three players
have a consistent ranking, then the tournament as a whole has one.
The proof is by induction on $n$.

{\bf Base case $n=2$:} Every two player tournament obviously has a
consistent ranking.

{\bf Inductive step:} Suppose $n\ge2$ and there is a consistent ranking of
any tournament of $n$ players whose three-player subsets have consistent
rankings.  Now consider any $n+1$ player tournament whose three-player
subsets have consistent rankings.

This tournament cannot have a 3-cycle, because there is no consistent
ranking for the players in the 3-cycle.  Hence, by the previous part, the
tournament has a champion.  The $n$-player tournament obtained by ignoring
the champion also has no 3-cycles, so by induction it has a consistent
ranking.  Then this ranking of $n$-nonchampions followed by the champion
at then end is a consistent ranking of the whole tournament of $n+1$
players.
}
\end{problemparts}

\end{problem}



\end{document}                            
