In genealogy, a pedigree chart, which shows one's direct ancestors (parents, grandparents, etc. but not siblings, cousins, etc.) is often replaced by the equivalent but space-saving Ahnentafel table.

An Ahnentafel table is simply a numbered list of each ancestor, usually on separate lines. The "root" person goes on line 1. Then, for any person on line n, his father goes on line 2n and his mother goes on line 2n+1. Every ancestor gets a unique line, and every line gets a unique ancestor* (mathematically, at least -- in real life Ahnentafels, because a person may not know all of his ancestors some lines may be blank, and in the case where cousins married, their common ancestors may show up in several places in their children's Ahnentafels).

Question 1: Your great-great-grandfather(2nd-great-grandfather) was the first of his name (surname) (which you inherited) to come to America. What is his Ahnentafel number? What is the Ahnentafel number of your nth-great-grandfather of the same name?(Assume the the Western tradition where a child inherits his father's surname)

Question 2: Your Mitochondrial DNA is passed on only from your mother, who got it from her mother,etc. What is the Ahnentafel number of the great-grandmother from whom it "originally" came? Of the nth-great-grandmother?

[Hint: for the general case (nth-great-grandfather in question 1, nth-great-grandmother in question 2) it might be easier to work with m=n+2; m is the number of generations between the ancestor and your children. For n=1 (your great-grandfather), m=3 -- three generations in between: your grandfather, your father, and you.]

*This statement (that there is a one-to-one correspondence between Ahnentafel numbers and the set of all natural numbers) is fairly easy to prove. And, in fact, the proof is part of a later puzzle in this series. For this puzzle, it can simply be assumed.

(In reply to re: Solution by Federico Kereki)

On re-reading my response with a fresh (and calmer) eye, I see that I may have been a little sharp. If so I apologize.

Originally this puzzle had asked for the proof that you (and Penny, after a fashion) give, and a fourth question directly related to that proof. I was convinced by the journeymen and scholars who saw it in the queue that it was too long and should be split into two puzzles.* I felt that the all-male and all-female line questions would be more "interesting" than the "proof" question as an introduction to the idea of Ahnentafel numbers, and I was concerned about someone "mooting" the other question, which really needs to be presented while the "proof" is still "unsolved."

I thought about leaving out the statement about the one-to-one correspondence in the hopes that flooblers would solve the question recursively, but while that works for the all male line, for the all-female line you need to know that there are no "skipped" lines to understand that the recursive 2(2(2(2...+1)+1)+1)+1 of the function
M:{M(0)=1, M(n+1)=2[M(n)]+1}
does indeed equal [2^(n+2)]-1

*Notes:
1. I wrote, above, that I split the puzzle into two. Actually I split it into three. There is another question which is unaffected by the "accidental" mooting of the "proof" and the proof-dependant question which will come into the queue in a month or two. Plus I have some ideas for more Ahnentafels. so there are more to look forward to.

2. The mooted question was asking about the relationship of three Ahnentafel numbers: those of Ancestors A and B on your Ahnentafel and Ancestor B on Ancestor A's Anentafel. The answer, of course, was that Ancestor B's number on your Anentafel can be constructed by appending the binary notation of his number on A's Ahnentafel -- minus the leading 1 -- to the end of the binary notation of A's number on your Anentafel.

Examples:
Your maternal grandfather's (6=110b) paternal grandmother (5=101b) is 25=11001b on your chart

Your all-female line great-grandmother's (1111b=15) all-male line 2nd great-grandfather (10000b=16) is 111110000b=240

For this question, Penny's approach using the "digits" D and M instead of 0 and 1 works even better since it eliminates the need for the pesky initial 1.
Edited on April 11, 2004, 9:11 pm

Posted by TomM on 2004-04-11 21:02:20