Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
As a graph, I think we could state this as "the maximum number of nodes in a directed acyclic graph with $n$ sources where each non-source has in-degree $2$ and there is at most one path between any two vertices". Not sure what to do with that though! –  usul Dec 14 '12 at 7:33
    
Can you confirm using your program whether the sequence matches oeis.org/A151150 ? –  Qiaochu Yuan Dec 14 '12 at 7:36
1  
You could also ask an inverse question: Suppose we are left with $m$ immortals who never have children. What's the largest number of immortals there could be? Taking these as sources, we want to find the largest directed acyclic graph where each non-sink has out-degree 2 and restricting to any one vertex's transitive closure yields a binary tree with that vertex at the root. Also the number of sinks in this graph tells us how many immortals there were to start with. –  usul Dec 14 '12 at 7:37
    
@Qiaochu: It doesn’t, according to the computations posted at the Reddit link. –  Brian M. Scott Dec 14 '12 at 7:59
    
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. –  Qiaochu Yuan Dec 14 '12 at 8:23

1 Answer 1

up vote 10 down vote accepted

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)!!\;. $$

share|improve this answer
    
Sorry, I hadn't looked at the reddit thread before; I just realized that this is already given there. Let me know if you'd like me to delete it so the question is treated as unanswered. I doubt you'll find something simpler, though. –  joriki Dec 14 '12 at 9:47
2  
should add this to oeis.org ! –  Greg Martin Dec 14 '12 at 10:47
1  
@Greg: Done; it should be OEIS sequence A220452 once it's approved. –  joriki Dec 15 '12 at 8:58
2  
@Greg: The sequence has now been published. –  joriki Dec 17 '12 at 5:47

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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