1

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.

David K
  • 98,388
arif
  • 21
  • I have not tried the problem, but the hint sounds like it solves your problem. – anak Jul 13 '15 at 16:24
  • You are asked to prove that Z <= 2B. The hint is suggesting that you prove Z <= B since Z <= B means Z <= 2B – user137481 Jul 13 '15 at 21:27
  • Thanks for the hint , even though i have trouble seeing how the one implies to the other. I mean the end situation ends with z and b lings at same number always. That is 1:1ratio and not 2:1 for zbling. Thanks anyway for the help to both of you. – arif Jul 13 '15 at 22:37
  • "At most twice" does not mean "twice". It means "twice or less." You are not being asked to prove the ratio is 2:1, rather, you are asked to prove that it is 2:1 or less. 1:1 is less than 2:1 so it is a perfectly OK result. – David K Jul 14 '15 at 16:20
  • "Use a stronger hypothesis" does not mean "use strong induction." You can use the "non-strong" type of induction perfectly well for this problem. – David K Jul 14 '15 at 16:37

1 Answers1

1

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.

user137481
  • 2,605