Queen's Pedigree

If $Q_n$ is the number of female ancestors, queens, going back $n$ generations and $M_n$ is the number of male ancestors going back $n$ generations, then

$Q_n=Q_{n-1}+M_{n-1}$

$M_n=Q_{n-1}$

Substituting from second equation into the first, we get

$Q_n=Q_{n-1}+Q_{n-2}$

So we see that the number of female ancestors forms a Fibonacci sequence.

To get the total number of ancestors, we only need to add the males

$T_n=Q_n+M_n=Q_n+Q_{n-1}=Q_{n+1}$

The total will come to the next number in Fibonacci sequence after the one for females alone.

Doing back one generation, we have $2$ ancestors, that is $F_3$ , the third Fibonacci number. $Q_n=F_{n+2}$

So going back $20$ generations, the number of ancestors will be $F_{22}=\boxed{17711}$ .

Did this as an exercise in writing recursion in R:

beeparents <- function(female, male, gen) {
  if(gen == 0) {
    return(female + male)
  } else {
    female_parents <- female + male
    male_parents <- female
    beeparents(female_parents, male_parents, gen - 1)
  }
}

> beeparents(1, 0, 20)
[1] 17711

If you know Fibonacci numbers, it is not difficult to see that we are dealing with them here. However, I give a more elementary approach that shows an efficient way to calculate the actual number.

If a generation has $q$ queens and $m$ males, then the previous generation has $\begin{cases} q_1 = q + m \\ m_1 = q \end{cases}$ Applying this equation to itself, two generations back has $\begin{cases} q_2 = q_1 + m_1 = 2q + m \\ m_2 = q_1 = q + m \end{cases}$ Applying this to itself, four generations back gives $\begin{cases} q_4 = 2q_2 + m_2 = 5q + 3m \\ m_4 = q_2 + m_2 = 3q + 2m \end{cases}$ Also, five generations back we have $\begin{cases} q_5 = q_4 + m_4 = 8q + 5m \\ m_5 = q_4 = 5q + 3m \end{cases}$ For ten generations we get $\begin{cases} q_{10} = 8q_5 + 5m_5 = 89q + 55m \\ m_{10} = 5q_5 + 3m_5 = 55q + 34m \end{cases}$ Finally, for twenty generations we get $\begin{cases} q_{20} = 89q_{10} + 55m_{10} = 10946q + 6765m \\ m_{20} = 55q_{10} + 34m_{10} = 6765q + 4181m \end{cases}$

Thus twenty generations back, starting from one queen bee ( $q = 1, m = 0$ ), we have $q_{20} + m_{20} = (10946 + 6765)\cdot 1 + (6765 + 4181)\cdot 0 = \boxed{17711}$ ancestors.

I used the transformation matrix (2x2) [0,1,1,1] taken to power 20, multiplied by most recent generation of 1 queen [0,1]. The transformation takes the number of females in any generation and makes that the number of males in the previous generation. The number of females in the previous generation is the sum of males and females in the following generation. This method gives you not only the total number in a given generation, but also numbers by sex.

A simple Python Snippet:

1
2
3
4
5
6

def F(male,female,N,ct):
  if ct==N:
    return male+2*female
  return F(female,male+female,N,ct+1)

print F(0,1,20,1)

If there is 3 ancestors in 2nd gen, and 2 in 1st gen then there will be 5 ancestors in 3rd gen. If we follow that, the number of ancestors in n-th gen is: N(n) = N(n-1)+N(n-2), where n=3..20. If we follow the sequence step by step we got N(20)=17711.

Dear Challenge Masters, if this problem is for week from 21-27Aug, how it is possible to have first response dated Aug 8th? This is interesting problem too ;)