How long can a population last without incest?

Question

A group of $n$ women and $m$ men have gotten themselves stuck on a desert island. Or, they're the last people left alive after the apocalypse. Whichever scenario you prefer. If they start reproducing, and assuming these people are all completely unrelated, how long will their colony last for if they want to avoid any and all incest, no matter how far removed?

More precisely, the rules are:

1. A person's generation is the maximum of their parents', plus one. The initial population all have generation zero.

2. You can reproduce with (and only with) anyone of the opposite gender with whom you share no common ancestor in the initial population (and a person is considered to be their own ancestor).

3. Ignore the fact that people have a finite lifespan and that pregnancy takes nine months. You can have as many children as you want.

4. You're trying to find the theoretical highest possible number of generations, so it's fine if your strategy requires that the kids come out with specific genders.

Try the case with, say, 1 man and 2 women (or vice versa) to whet your appetite, but the point of the puzzle is to work out the general case. Remember that you don't just need some upper bound, you need a tight upper bound - so you'll probably want to show an explicit strategy attaining that bound, along with a proof that that's the best you can do.

I have already solved this, so I can guarantee there is an elegant solution.

Answer 1

Considering numbers per gender creates a kind of distraction. Let $g(N)$ be the maximum number of 'incest-free generations' that can result from $N$ unrelated individuals, not all of whom are of the same gender. An additional individual unrelated to the $N$ others can mate with any of them who happens to be of the opposite sex. Selecting this mating partner from the most recent generation allows the formation of exactly one additional incest-free generation. So we have: $$g(N+1)=g(N)+1$$ Avoiding incest, a single man and a single woman ($N=2$) can produce no more than one generation of offspring: $$g(2)=1$$ Combining the above two results, it follows that $$g(N)= N-1$$ In this equation one can replace $N$ with $m+n$ to obtain the answer requested.

Answer 2

$m + n - 1$ generations if $if$ $n > 0$ & $m > 0$

If there is only one gender in generation 0 then they won't be able to reproduce.

If each 'couple' has male and female progeny then there could be $2*m*n$ children in the first generation. These could reproduce with $m + n -2$ from the first generation.

The second generation could reproduce with a maximum of $n + m - 3$

The third generation could reproduce with a maximum of $n + m - 4$

The maximum number of people that a person from generation $g$ could reproduce with after generation 0 is $m + n - (g + 1)$

The maximum of generations is obtained by solving:

$m + n - max(g) - 1 = 0$

$max(g) = m + n -1$

The $(m + n -1)^{th}$ generation has no non relation to reproduce with.

Answer 3

This condition:

avoid any and all incest, no matter how far removed

means that the answer is 0, because all of the initial population share common ancestors (all living humans share a set of common ancestors).

In the field of human genetics, the name Mitochondrial Eve refers to the matrilineal most recent common ancestor (MRCA), in a direct, unbroken, maternal line, of all currently living anatomically modern humans, who is estimated to have lived approximately 100,000–200,000 years ago. This is the most recent woman from whom all living humans today descend, in an unbroken line, on their mother’s side, and through the mothers of those mothers, and so on, back until all lines converge on one person. Because all mitochondrial DNA (mtDNA) generally (but see paternal mtDNA transmission) is passed from mother to offspring without recombination, all mtDNA in every living person is directly descended from hers by definition, differing only by the mutations that over generations have occurred in the germ cell mtDNA since the conception of the original "Mitochondrial Eve".

WP: Mitochondrial Eve

the MRCA [Most Recent Common Ancestor] of all present-day humans lived just a few thousand years ago in these models. Moreover, among all individuals living more than just a few thousand years earlier than the MRCA [Most Recent Common Ancestor], each presentday human has exactly the same set of genealogical ancestors.

...

Further work is needed to determine the effect of this common ancestry on patterns of genetic variation in structured populations. But to the extent that ancestry is considered in genealogical rather than genetic terms, our findings suggest a remarkable proposition: no matter the languages we speak or the colour of our skin, we share ancestors who planted rice on the banks of the Yangtze, who first domesticated horses on the steppes of the Ukraine, who hunted giant sloths in the forests of North and South America, and who laboured to build the Great Pyramid of Khufu.

Douglas L. T. Rohde, Steve Olson & Joseph T. Chang, "Modelling the recent common ancestry of all living humans", Nature vol. 431, 30 Sept 2004. doi:10.1038/nature02842

NB: The puzzle's initial condition "assuming these people are all completely unrelated" is not physically possible, and so I've discounted it - as discussed above, all individuals of our species are related to one another.

It would be possible to restate this puzzle by setting a minimum level of 'relatedness' that's allowed, and saying how closely related each member of the initial population is to each other member (because that makes a difference to the relatedness of the future generations). See Coefficient of relationship, Genetic distance # Measures of genetic distance.

Answer 4

I'll go ahead and share my preferred solution. It's not as quick Johannes's, but I think it's kind of pretty.

First, you can reach at most $N-1$ generations, where $N$ is the initial population size. Indeed, suppose Alice is of generation $n$. Call the ancestry of a person the set of their ancestors among the initial population. Alice has some set of size less than or equal to $N$ as her ancestry. One of her parents has generation $n-1$, one of their parents is of generation $n-2$, and so on: we can find a sequence of people of length exactly $n+1$ starting with Alice and ending with someone in the initial population. A person's ancstry is the disjoint union of their parents', thus the size of the ancestries strictly decreases all the way along this sequence, beginning with with some value less than or equal to $N$ and ending with $1$. Such a sequence can be of length at most $N$, and our sequence is of length $n+1$, thus $n+1\leq N$.

Now, to prove it's possible to attain the bound. First of all, if you have $1$ man and $n$ women, you can obtain a person of generation $n$ by having the man have a son with the first woman, then that son has a son with the second woman, and so on. Now if you have $m$ men and $n$ women, pick one distinguished man to perform this process with the $n$ women, producing a daughter of generation $n$. This daughter then performs the same process with the $m-1$ men she isn't related to obtain a child who, it's easy to see, will be of generation $n+(m-1)$.

Answer 5

As germcd said in his answer, the answer is $m+n-1$. But he also says that it's $1$ if $n=1$ or $m=1$. But the only exception is when $n=0$ or $m=0$, then the answer would be $0$(obviously).
I'll show a few examples(I'll replace $n$ with $f$ for females to make it easier):

Example 1: 1m+1f

They can make a baby, but then it stops(g1), so $1+1-1 = 1$

Example 2: 2m+1f

Each of those 2 men can make a girl with that female(g1). Then they can make another baby with the girl of the other guy(g2). But now they are all related*, so we can't go any further. $2+1-1=2$

Example 3: 1m+2f (lucky man)

He makes 1 boy with each of those females(1g). Then each of those boys make another kid with another starting female(2g). At that moment they are all related, so it stops there. $1+2-1=2$

Example 4: 2m+2f

1 pair makes a girl(1g). Then she makes a boy with the other starting male(2g). Then this boy makes another child with starting female(3g). They can repeat that process using other pairs, but then they will all be related. $2+2-1=3$.

---

*And with all related I mean that the kid has all starting people as his/her ancestors.