Rabbit Inbreeding: Model Population Growth Under Constrained Inbreeding Rules

Question

## Problem

A rabbit colony starts with one breeding pair. Each month, every mature pair produces one new pair. However, to prevent inbreeding, a pair may not breed with any pair that shares a common ancestor within K generations. Compute the population (number of pairs) after M months.

```python
def rabbit_population(months: int, k: int) -> int:
    # months: total simulation months
    # k: inbreeding constraint (pairs sharing ancestor within k gens cannot breed)
    # returns: total number of pairs alive at end of month M
    pass
```

**Example:**
```
rabbit_population(6, 0) -> 8   # standard Fibonacci (no constraint)
rabbit_population(6, 1) -> ?   # pairs can't breed with their own offspring
```

## Follow-ups

1. Without the inbreeding constraint (k=0), what is the recurrence relation and why does it match Fibonacci?
2. How does the inbreeding constraint change the recurrence?
3. How would you represent the ancestry graph to efficiently check whether two pairs share a common ancestor within K generations?
4. At what value of K does the constraint have no further effect on population growth?

Rabbit Inbreeding: Model Population Growth Under Constrained Inbreeding Rules

Question Details

Full Details

Topics

More from Waymo