23
$\begingroup$

I saw this riddle posted on reddit a long time ago, called the "Seven Immortals."

In the beginning, the world is inhabited by seven immortals, ageless and sexless, who begin to multiply and populate the land. Any immortal can mate with any other to produce exactly one child, and the same is true of their descendants, with the caveat that no immortal could mate with his own ancestors or relatives. No couple can mate more than once, and they continue to intermingle until no more matings are possible. How many immortals are left in the end?

The solution is

$19873$, which I lazily confirmed by writing a Mathematica program.

Having a mathematical mind, I of course immediately wondered about the "$n$ Immortals" problem. Surely a combinatorial solution with binomial coefficients should be attainable by extending the "genes" approach discussed in the comments. But is this the only way? It feels like a graph theory problem to me.

My second question is, is there any significance to this problem? Does the solution arise in any other mathematical contexts?

  • 0
    Got it. Graph theory does not seem like the right language; I would talk about trees. You can identify an immortal with its tree of ancestors, and the question is to count certain such trees, which have leaves labeled by the original population of immortals, and the condition on mating is a condition on upward-closed subtrees.2012-12-14

1 Answers 1

12

Given $n$ initial immortals, for any group of $k$ of them there is exactly one descendant with exactly these ancestors for every unordered full binary tree with $k$ labeled leaves, of which there are $(2k-3)!!$ (where $(-1)!!=1$). Thus the total number of immortals is

$ \sum_{k=1}^n\binom nk(2k-3)!!\;. $

  • 0
    There are no immortals with exactly *one* ($k=1$) ancestor. And there are $n$ immortals with *zero* ($k=0$) ancestors. But I guess you consider each of the initial immortals as their own (and only) ancestor $-$ so it works.2017-10-06