Avoiding Incest and Intergenerational Mating

Question

On the planet of Caturn, God created $m$ male cats and $f$ female cats, each with zero stripes. At any time, two cats of opposite genders can mate, giving birth to a cat with a gender of the parents' choice.

The laws of cat genetics dictate that the number of stripes a child has will be one more than the number of stripes of its stripier parent. In other words, if the mother has $s$ stripes, and the father has $t$ stripes, the child will have $1+\max(s,t)$ stripes.

However, God issued the following two commandments:

• No Incest: Two cats may not mate if they have a common ancestor.

• Similarity: Two cats may only mate if their stipe numbers differ by at most one. (A cat with $9$ stripes can only mate with an $8,9$ or $10$ stripe cat.)

Assuming the cats obey these commandments, what is the largest number of stripes a cat on Caturn could possible have (as a function of $m$ and $f$)?

---

This is a variant of How long can a population last without incest? Other than rewording, the only change I made was adding the "Similarity" rule.

Answer 1

Here is the answer:

A population can breed $s$ cats if and only if $\min(m,f)\geq F_s$ and $m+f\geq F_{s+2}$ (where $F_n$ is the $n^{th}$ Fibonacci number, starting with $F_0=0$ and $F_1=1$)

To prove that this is correct, let us consider the family tree of the stripiest cat. We may notice that any cat in this ancestry with stripes might as well be a hermaphrodite (able to breed with any other cat) since we may choose their gender freely and they may only breed once in this tree (as otherwise there would be incest).

Motivated by this, we see that gender only matters in so far as we have some number of stripeless male-female couples, along with some more zero-stripe cats (of either gender) who breed with hermaphrodites. In particular, define $f(s)$ as the number of male-female couples required to breed a cat with $s$ stripes and $g(s)$ as the number of additional cats required. We see easily that, as the cheapest way to make a cat with $s$ stripes is to breed a cat with $s-1$ stripes with one with $s-2$ stripes that:

$$f(s)=f(s-1)+f(s-2)$$ $$g(s)=g(s-1)+g(s-2)$$ and we see the initial conditions are: $$f(0)=0$$ $$f(1)=1$$ $$g(0)=1$$ $$g(1)=0$$

Easily, from this, we see that $f$ is exactly the Fibonacci sequence and $g(s)=f(s-1)$. Thus, to breed a cat with $s$ stripes, we need at least $F_s$ couples along with $F_{s-1}$ additional individuals - meaning both genders need at least $F_s$ individuals. So, in total, we need at least $F_{s+2}=F_{s-1}+2F_s$ individuals.