Кролики и почти числа Фибоначчи

[e7e5]

Встретился такой вопрос: Есть два вида кроликов $A$ и $B$, которые производят потомство по достижению двух лет. $A$ в первый раз дают две пары, а потом по одной паре. Кролики вида $B$ в первый раз производят одну пару, во второй раз - $3$ пары, дальше по одной паре. Вначале было по одной паре кроликов вида $A$ и $B$. Каких кроликов будет больше через 5 и 10 лет?

Начал с поиска закономерностей этих чисел. Сделал табличку по года, отмечая цепочки размножения на каждый год. Например, в первый год для $A$ - одна пара, во второй год будет одна пара взрослых и две пары молодых, которые к концу 3-го года станут взрослыми и дадут $4$ пары молодых. Т.е. получается ряд: $1, 3, 8, 21, 55, ...$ Попробовал поискать в oeis.org. Находится несколько похожих, но вот у меня на шестой год получается $145$, а такого члена в последовательности OEIS не увидел.
http://oeis.org/A001906
http://oeis.org/A088305
Как иначе ответить на вопрос, более простым способом?

[arseniiv]

Как обычно в такой ситуации, пишем систему рекуррентную. Для A-кроликов нам нужно различать четыре состояния пары (0, 1, 2, 3+ лет), для B-кроликов — пять (0…3, 4+ лет). Пишем связи между количествами пар разного возраста — получается по системке. Дальше с ними можно работать по-всякому, не всегда с пользой, самый скучный метод состоит в преобразовании системы в матричное уравнение и нахождении собственных чисел матрицы — тогда можно получить асимптотику или нерекуррентную формулу. У вас фигурируют 5 и 10 лет, так что проще поумножать матрицы и получить ответы прямо так, наверно.

[grizzly]

e7e5 в сообщении #1304036 писал(а):

но вот у меня на шестой год получается $145$,

Плохо получается. Должно быть $(21+13)\cdot 3+21\cdot 2=144$. Перепроверьте, пожалуйста, кто из нас ошибся.

-- 14.04.2018, 00:39 --

После перепроверки все вопросы по задаче отпадут, я думаю.

[Andrey A]

Ну никак $145$ не получается, если это конечно не цены на мороженое за прошлые годы. Иногда полезно отвлечься от кроликов и взглянуть на последовательность непредвзято. Или сравнить с рядом Фибоначчи.

[e7e5]

Andrey A в сообщении #1304101 писал(а):

Иногда полезно отвлечься от кроликов и взглянуть на последовательность непредвзято. Или сравнить с рядом Фибоначчи.

Получается члены ряда Фибоначчи через один, т.е. вместо $0,1,1,2,3,5,8,13,21,34,55,89,144,233,377$ будет $10,1,3,8,21,55,144$. Но что со второй последовательностью для типа $B$?

[Andrey A]

Найдите рекуррентное правило для последовательности типа $B$. Это не очень сложно когда два некоторых члена в сумме или разности делятся на третий. Заодно и для четных Фибоначчи.

[arseniiv]

Пусть

$$\begin{bmatrix} b'_0 \\ \vdots \\ b'_3 \\ b'_{\geqslant4} \end{bmatrix} = A \begin{bmatrix} b_0 \\ \vdots \\ b_3 \\ b_{\geqslant4} \end{bmatrix} \equiv A\mathbf b$$

— система, про которую я говорил, и пусть $f\mathbf b = b_0 + \ldots + b_{\geqslant4}$. Тогда $B_n = fA^n\mathbf b_0$, где $\mathbf b_0 = \begin{bmatrix} 1 & 0 & \cdots & 0 \end{bmatrix}^t$. Иначе, $B_{n-k} = fA^{5-k}(A^{n-5}\mathbf b_0)$. Так как $A^5 = \alpha_0A^0 + \ldots + \alpha_4A^4$, получаем искомое рекуррентное уравнение $B_n = \alpha_4B_{n-1} + \alpha_3B_{n-2} + \ldots + \alpha_0B_{n-5}$. Весь вопрос здесь в нахождении коэффициентов $\alpha_i$; это почти коэффициенты характеристического многочлена $A$, которые можно более-менее эффективно найти алгоритмом Фаддеева—Леверье, ну а можно более прямым и длинным способом по определению характеристического многочлена.

Этот метод, очевидно, работает для любой последовательности общего количества каких-то штук конечного числа типов, которые за каждый временной шаг как-то линейно влияют на количества друг друга. Никакой угадайки.

-- Сб апр 14, 2018 20:31:28 --

arseniiv в сообщении #1304207 писал(а):

общего количества каких-то штук

…и других линейных функций от этих индивидуальных количеств, конечно. Чрезвычайно общий результат. И тривиальный.