5
$\begingroup$

This question is distinct from Exponential growth of cow populations in Minecraft in that an important constraint present in Minecraft is missing from that post. Here are the following constraints:

  • We start with $2$ adult cows, and $0$ baby cows.
  • Any given pair of adult cows can only be bred to form $1$ baby cow every $5$ minutes. (not included in the other post)
  • A baby cow becomes an adult after $20$ minutes.

My first (failed) attempt at solving this was to intialise the following functions $A(0)=2, B(0)=0$, where $A$ and $B$ are funtions of $t$ (time, in minutes) representing the number of Adult and Baby cows respectively.

Naively, I represented this via a system of two linear differential equations given the above initial conditions:

$$\frac{dA}{dt}=\frac{B}{20}$$

$$\frac{dB}{dt}=\frac{A}{5}$$

Where my thought process was that every 20 minutes there would be an addition of $B$ adults, and every 5 minutes there would be an addition of $\frac{A}{2}$ baby cows. By use of linear algebra, it can be shown that the equations of $A$ and $B$ are as follows: $$A(t)=e^{-\frac{t}{10\sqrt{2}}}+e^{\frac{t}{10\sqrt{2}}}$$ $$B(t)=\frac{1}{\sqrt{2}}e^{\frac{-t}{10\sqrt{2}}}\left(e^{\frac{t}{5\sqrt{2}}}-1\right)$$ Where the total number of cows, call this $C(t)$ is some rounded form of $A(t)+B(t)$.

The problem with this: Given that at any given time, the 'age' of the babies within the pool will be different (non-uniform), the formation of adults will be staggered. This is the point I'm struggling to continue. I've tried to think of $B$ as forming subsequences every $5$ minutes, but I am really unsure how to implement this in any meaningful way.

So how can this formula be generated?

Edit: On second thoughts, this might be reducible to the post linked at the start. Not too sure though.

Edit 2: As pointed out in the comments by Daniel Mathias, this question is distinct from the linked post.

$\endgroup$
2
  • 1
    $\begingroup$ The linked post and OEIS entry assume that all offspring become adults between breedings. That means at least 20 minutes between breedings, so this question is indeed different. $\endgroup$ Feb 5, 2022 at 13:51
  • $\begingroup$ @DanielMathias Ah indeed you're right. Thanks, I'll edit the post. $\endgroup$
    – Simplex1
    Feb 5, 2022 at 14:18

2 Answers 2

4
$\begingroup$

You are ignoring the granularity of five minute intervals. A way to incorporate that is to define $A(n),B(n),C(n),D(n),E(n)$ as the number of cows of age $0,5,10,15,\ge 20$ minutes at time $5n$ minutes. The starting condition is all $0$s except $E(0)=2$ unless the first cow is born at minute $0$. In that case $A(0)=1$. You have a set of recurrences $$A(n+1)=\frac 12E(n)\\ B(n+1)=A(n),C(n+1)=B(n),D(n+1)=C(n)\\ E(n+1)=E(n)+D(n)$$ You can write the current population as a vector and the recurrences as a matrix, find its eigenvalues, and find the growth rate from the greatest eigenvalue.

$\endgroup$
12
  • $\begingroup$ Pedantically speaking, $A(n + 1)$ should really be $\left\lfloor \frac{1}{2}E(n)\right\rfloor$ (a distinction that was addressed in the similar linked question). This shouldn't greatly affect the growth of the sequence, though. $\endgroup$ Feb 6, 2022 at 3:09
  • $\begingroup$ So I've constructed a vector $\mathbb{T}(n)$ with 5 rows, that include $A(n), B(n), ..., E(n)$. I wrote everything in terms of $A_n$ then constructed something of the form: $\mathbb{T}(n+1)=A \mathbb{T}(n)$ where $A$ is some 5x5 matrix (not to be confused with $A(n)$) with numerical entries. I'm not too sure how to progress from here (I can find the eigenvalues). I'm pretty new to these types of recurrence problems. $\endgroup$
    – Simplex1
    Feb 6, 2022 at 3:20
  • $\begingroup$ That is the correct approach. Your general solution (assuming you have no repeated eigenvalues) will be a sum of $c_i\lambda_i^n$ for $\lambda_i$ the eigenvalues and $c_i$ vectors determined from the initial conditions. After some time, the term with the largest positive eigenvalue will dominate, so that is the eventual growth rate (unless the matching $c$ is 0). $\endgroup$ Feb 6, 2022 at 3:32
  • $\begingroup$ @TheoBendit: yes, and we could worry about statistical variations in the fraction of males and females. I think that is too much detail for this problem. $\endgroup$ Feb 6, 2022 at 3:36
  • 1
    $\begingroup$ @RossMillikan Ah, indeed the growth is better and better approximated (and indeed asymptotically equivalent) with that eigenvector. I suppose if I want the actual number of cows, I can take an arbitrarily large $n$, call this $n^*$ then compare this $\lambda^{n^*}$ with the actual value which can be found by $A^{n^*} t_0$, then use this ratio between them to scale every value after $n=n^*$, once we've multiplied by 1.25372. $\endgroup$
    – Simplex1
    Feb 6, 2022 at 5:40
2
$\begingroup$

We can limit our counting to only count the number of adult cows. If there are $C_n$ adult cows in generation $n$, then the $\lfloor C_n/2\rfloor$ baby cows born to that generation will become adult cows $20$ minutes later, just in time to be part of the adult population in generation $n + 4.$

Looking at it the other way around -- asking where the cows in generation $n$ came from -- the recurrence relation is $$ C_n = C_{n-1} + \left\lfloor \frac12 C_{n-4}\right\rfloor.$$

If we ignore the floor function (which has a significant impact on early generations, not so much on later generations), the recurrence relation simplifies to $ C_n - C_{n-1} - \frac12 C_{n-4} = 0$ and its characteristic polynomial is $r^4 - r^3 - \frac12 = 0.$

The characteristic polynomial has four distinct roots, but only the root $r\approx 1.25372495821695$ has absolute value (or complex modulus) greater than $1,$ and the powers of that root will determine the approximate growth rate of the population after some number of generations; whereas "approximate growth rate" is all this method can hope to give us, since it ignores the floor function in the actual recursion.

Setting $r_1 = 1.25372495821695,$ a naïve formula for the adult population growth starting with $2$ adult cows in generation $0$ would be $$ C_n \approx 2 \cdot r_1^n, \tag1 $$ rounding to the nearest integer, which is easily shown to be relatively inaccurate: after $30$ generations this says we would have $1766$ cows whereas the actual number is $955$, so this estimate is about $85\%$ too high, and it continues at about $85\%$ above the correct value for up to at least $n=200$ (which is as far as I looked).

An obvious reason for the discrepancy is the floor function, which causes fewer adult cows to be added to the population than the simplified recursion says. Noting that the percentage error seems to settle down after a few dozen generations, we could try computing $k$ generations exactly and then using the formula $$ C_n \approx C_{k} \cdot r_1^{n-k} \tag2 $$ to estimate the remaining generations.

Trying this with $k = 24,$ I found that the estimate was about $4.95\%$ greater than the exact value at generation $54$ and about the same at generation $200$. (I did not look beyond generation $200$.) With $k = 44,$ I found that the estimate was about $2.09\times10^{-3}\%$ greater than the exact value at generation $70$ and about the same at generation $200$. With $k = 70,$ I found that the estimate was about $4.78\times10^{-6}\%$ greater than the exact value at generation $105$ and about the same at generation $200$.

This suggests that you could fit the growth of the adult population pretty well, though not exactly, by using the exact data for the first few generations and a formula in the form $$ C_n \approx M \cdot r_1^n $$ for higher generations. The constant $M$ might be estimated by finding the approximate limit of the percentage error for one of the formulas derived from Equation $(2)$ or even for Equation $(1)$. Following this idea I get the formula $$ C_n = 1.08068409116794 \cdot 1.25372495821695^n, $$ which is actually within $\pm 1$ of the exact result for all generations up through generation $140$ (and exact for all but $8$ generations up through generation $131$) if you round up instead of rounding to nearest. After that I found that the relative error starts to grow slowly, but at that point the numbers involved are so large that Excel seems to be unable to do completely correct integer arithmetic on them, so it is possible that some of the "error" I see is actually due to miscalculation of the exact sequence.


If you want to know the total number of cows including baby cows, I would compute generation $n$ and the previous three generations; the number of baby cows can then be computed from the previous generations. Add that number to the number of adult cows in generation $n.$

$\endgroup$

You must log in to answer this question.