Una vaca 4 años después de su nacimiento, da a luz a un nuevo ternero en el cuarto año y cada año que sigue. Todos los demás recién nacidos dan a luz también en el cuarto año después de su nacimiento y cada año que sigue, y así sucesivamente. ¿Cuántas vacas habrá después de N años?

Answer 1

Denota por año-0 el año de nacimiento de la primera vaca. Aquí solo son relevantes los años pares.

Modelamos este proceso de la siguiente manera: cuando una vaca nace en el año 2X (X, un entero no negativo), decimos que es inmadura . Luego, en el año 2 (X + 1), madura . Una vaca madura tiene una vaca nueva cada año subsiguiente.

Use un vector A_X = (a, b) para indicar el número de vacas inmaduras y maduras en el año 2X. Si A_ {X + 1} = (a ‘, b’), lo sabemos
a ‘= b (cada vaca inmadura nace de una vaca madura en el año anterior)
b ‘= b + a (la vaca inmadura madura y la madura permanece madura)
Dada la condición inicial A_0 = (1, 0), A_X es solo un par de números de Fibonacci: A_X = (F_ {X-1}, F_X).

(Note que aquí usamos la secuencia estándar de Fibonacci F_0 = 0 y F_1 = 1, y la extendemos con F _ {- 1} = F_1 – F_0 = 1.)

Cuando contamos las vacas maduras e inmaduras, tenemos F_ {X + 1} vacas en el año 2X. Por lo tanto, “después de N años”, tenemos F_ {N / 2 + 1} vacas, al redondear hacia abajo N / 2.