7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Parent + Child = Incest (in my opinion) $\endgroup$ – warspyking Jul 27 '15 at 3:01
  • $\begingroup$ What is the death rate of these cats? At what age does a cat typically become fertile? At what age does a cat typically become infertile? What is the gestation period for these cats? Does a cat count as its own ancestor, or are descendants allowed to mate with their ancestors? $\endgroup$ – Ian MacDonald Jul 27 '15 at 12:22
  • 4
    $\begingroup$ @ian A cat is its own ancestor. Death and infertility (menopaws?) are not limitations in this puzzle $\endgroup$ – Mike Earnest Jul 27 '15 at 12:41
4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ According to your solution, if $m=14$ and $f=7$, it would be possible to produce a $6$ stripe cat (since $F_{6+2}=21=\min(42,21,21)$). This is not possible. Your solution does work for $m<14,f<7$. $\endgroup$ – Mike Earnest Jul 27 '15 at 15:34
  • $\begingroup$ @MikeEarnest Oops. I fixed it (hopefully) $\endgroup$ – Milo Brandt Jul 27 '15 at 23:05
  • $\begingroup$ Your condition on $s$ is sufficient (so what you wrote is true), but not necessary. For example, when $(m,f)=(4,4)$, you can produce a 4-stripe cat, even though $max(m,f)\not \ge F_{4+1}$. I'll accept if you find a necessary and sufficient condition, since this gives a way to compute $s$ as a function of $m$ and $f$ (i.e. the answer is the largest $s$ for which the condition holds). $\endgroup$ – Mike Earnest Jul 28 '15 at 0:20
  • $\begingroup$ @MIkeEarnest Well, I'm pretty sure I got it now - I just changed the last paragraph to properly use the foundations I set up in my proof (unlike last time, where I guess I'd forgotten about semantics by the time I concluded) and edited the result to suit. $\endgroup$ – Milo Brandt Jul 28 '15 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.