im stuck on this assignment. Can someone give me a hint?
Here is the assignment: There are two types of creature on planet Char, Z-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 generationconsists entirely of their offspring.
The creatures of Char pair with a mate in order to reproduce. First, as many Z-B pairs as possible are formed. The remaining creatures form Z-Z pairs or B-B pairs, depending on whether there is an excess of Z-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:
If both parents are Z-lings, then they have three Z-ling offspring.
If both parents are B-lings, then they have two B-ling offspring and one Z-ling offspring.
If there is one parent of each type, then they have one offspring of each type.
There are 200 Z-lings and 800 B-lings in the first generation. Use induction to prove that the number of Z-lings will always be at most twice the number of B-lings.
Hint: You may want to use a stronger hypothesis for the induction
My problem is that i always end upp with the same number of Z-lings as B-lings. The assignement however, requires me to prove the theorem that Z- lings can never be more than twice the B-lings. What am i missing? Im basically doing a simple reproduce chart to figure out the pattern but i end wih the same end result, as mentioned..
My chart
$$\begin{array}{ccccccccc} \text{Generation} & \text{Z-ling} & \text{B-ling} & \text{Z-B} & \text{Z-Z} & \text{B-B} & \text{Offs.B} & \text{Offs. Z} \\ 1 & 200 & 800 & 200 & 0 & 300 & 800 & 500 \\ 2 & 500 & 800 & 500 & 0 & 150 & 800 & 650 \\ 3 & 650 & 800 & 650 & 0 & 75 & 800 & 725 \\ 4 & 725 & 800 & 725 & 0 & 37 & 799 & 762 & -1B \\ \ldots \\ 9 & 795 & 797 & 795 & 0 & 1 & 797 & 796 \\ 10 & 796 & 797 & 796 & 0 & 0 & 796 & 796 & -1B \\ 11 & 796 & 796 & 796 & 0 & 0 & 796 & 796 \end{array}$$
First column is the generation number, followed by the number of z-lings and b-lings alive for that specific generation. and then the pairing and the offspring. Thanks in advance.
Let $z_n$ and $b_n$ be the number of Z-lings and B-lings respectively in generation n.
You are asked to prove that $z_n$ can never be more than $2b_n$
or equivalently that $z_n \leq 2b_n$ for all n.
The hint says to use a stronger hypothesis which would be to prove that $z_n \leq b_n$
Let $S(n)$ be the statement: $z_n \leq b_n$
Base Case: n = 1
$z_n = 200, b_n = 800 \Rightarrow z_n \leq b_n$
$S(1)$ is true
Inductive Hypothesis:
Assume that for some n, $S(j)$ is true for all $1 \leq j \leq n$
Inductive Step: n + 1
By assumption, $z_n \leq b_n$
if $z_n = b_n, \,\, z_{n+1} = z_n$ and $b_{n+1} = b_n$
if $z_n \lt b_n$
$\,\, z_{n+1} = z_n + \lfloor \frac{b_n-z_n}{2} \rfloor$
$\,\, b_{n+1} = z_n + 2 \lfloor \frac{b_n-z_n}{2} \rfloor$
So, $z_{n+1} \leq b_{n+1}$
$S(n+1)$ is true
Hence S(n) is true for all n.
Since $z_n \leq b_n$ for all n, $z_n \leq 2b_n$ for all n.