
\problemdata     
{induction-6}           
{induction}              
{}              
{S01-PS2} 		
{S01 Karger}        	




\begin{problem}
There are two types of creature on planet Xoros 19, A-lings
and B-lings. Furthermore, every creature belongs to a particular
generation.  The creatures in each generation reproduce according to
certain rules and then die off.  The subsequent generation consists
entirely of their offspring.

The creatures of Xoros 19 pair with a mate in order to reproduce.
First, as many A-B pairs as possible are formed.  The remaining
creatures form A-A pairs or B-B pairs, depending on whether there is
an excess of A-lings or of B-lings.  If there are an odd number of
creatures, then one in the majority species dies without reproducing.
The number and type of offspring is determined by the types of the
parents

\begin{itemize}
\item If both parents are A-lings, then they have three A-ling
offspring.

\item If both parents are B-lings, then they have two B-ling offspring
and one A-ling offspring.

\item If there is one parent of each type, then they have one
offspring of each type.
\end{itemize}

There are 200 A-lings and 800 B-lings in the first generation.  Use
induction to prove that the number of A-lings will always be at most
twice the number of B-lings.



\solution{


An induction proof with the hypothesis that the number of A-lings is
always at most twice the number of B-lings will not go through.  A
stronger induction hypothesis is required.



\begin{proof}
We will prove that there are always at least as many B-lings as
A-lings; the claim that the number of A-lings is always at most twice
the number of B-lings is weaker and thus follows.

The proof is by induction on the generation number.  Let $P(n)$ be the
proposition that there are at least as many B-lings as A-lings in
generation $n$.  In the base case, $P(1)$ is true because there are
800 B-lings and only 200 A-lings in the first generation.

In the inductive step, for $n \geq 1$ assume that there are at least
as many B-lings as A-lings in generation $n$ to prove that there are
at least as many B-lings as A-lings in generation $n+1$.  Let $a$ be
the number of A-lings in generation $n$, and let $b$ be the number of
B-lings.  Note that $b \geq a$ by the induction assumption.  Then
there are no A-A pairs formed, there are $a$ A-B pairs formed, and
there are $\lfloor \frac{b - a}{2} \rfloor$ $B-B$ pairs formed.  As a
result, the number of A-lings in generation $n+1$ is $a + \lfloor
\frac{b - a}{2} \rfloor$, and the number of B-lings is $a + 2 \lfloor
\frac{b - a}{2} \rfloor$.  Therefore, there are at least as many
B-lings as A-lings in generation $n+1$.  Thus, for all $n \geq 1$,
$P(n)$ implies $P(n+1)$, and the claim is proved by induction.
\end{proof}
}


\end{problem}