
\begin{problem}
(Harder.)  There are $n$ chickens in a farmyard.  There is a strict
pecking order.  For each pair of distinct chickens, either the first
pecks the second or the second pecks the first, but not both.  We say
that chicken $u$ {\em virtually pecks} chicken $v$ if either:

\begin{itemize}

\item Chicken $u$ pecks chicken $v$.

\item Chicken $u$ pecks some other chicken $w$ who in turn pecks
chicken $v$.

\end{itemize}

\noindent A chicken that virtually pecks every other chicken is called
a {\em king chicken}.  Prove the following theorem:

\begin{theorem}[King Chicken Theorem]
Every farmyard with at least one chicken has a king.
\end{theorem}

\solution{
The proof is by induction on $n$, the number of chickens in the
tournament.  Let $P(n)$ be the proposition that in every $n$-chicken
tournament, there is at least one king.

First, we prove $P(1)$.  In this case, we can safely say that the lone
chicken virtually pecks every other chicken, since there are no
others.  Therefore, the only chicken in the tournament is a king, and
so $P(1)$ is true.

Next, we must show that $P(n)$ implies $P(n+1)$ whenever $n \geq 1$.
Suppose there is a chicken tournament with chickens $v_1, \ldots,
v_{n+1}$.  If we ignore the last chicken for the moment, then we are
left with a tournament among the first $n$ chickens.  By our induction
hypothesis, $P(n)$, this tournament has a king chicken, $v_k$.

Let $D_1$ be the set of chickens pecked by the king, $v_k$.  Let $D_2$
be the set of chickens virtually pecked by the king, but not pecked
directly.  Thus, each chicken in $D_2$ was pecked by some chicken in
$D_1$.

Now we reintroduce the last chicken, $v_{n+1}$, and show that the full
tournament on $n+1$ chickens has a king.  There are two cases:

\begin{enumerate}

\item Suppose that $v_k$ pecks $v_{n+1}$.  Then $v_k$ is a king of the
full tournament.

\item Otherwise, $v_{n+1}$ pecks $v_k$.  There are then two subcases:

\begin{enumerate}

\item If some chicken in $D_1$ pecks $v_{n+1}$, then $v_k$ virtually
pecks $v_{n+1}$ and so $v_k$ is again a king of the full tournament.

\item Otherwise, $v_{n+1}$ pecks every chicken in $D_1$.  In this
case, $v_{n+1}$ is a king of the full tournament; he directly pecks
$v_k$ and all the chickens in $D_1$, and he virtually pecks all the
chickens in $D_2$.
\end{enumerate}
\end{enumerate}

\noindent In every case, a chicken tournament with $n+1$ chickens has
a king, and so $P(n+1)$ holds.  Thus, by the principle of induction,
the claim is proved.
}

\end{problem}
