Вирус vs Бактерии (решение рекуррентного соотношения)

[caxap]

Из Кванта:

М101. В колонию, состоящую из $n$ бактерий, попадает один вирус. В первую минуту он уничтожает одну бактерию, затем делится на два новых вируса, и одновременно каждая из оставшихся бактерий тоже делится на две новые. В следующую минуту возникшие два вируса уничтожают две бактерии, и затем оба вируса и все оставшиеся бактерии снова делятся, и так далее. Будет ли эта колония жить бесконечно долго, или в конце концов погибнет?

Я составил реккурентность для бактерий ($B$) и вирусов ($V$):
$V_0 = 1;\quad V_k=2V_{k-1} = 2^k$
$B_0 = n; B_{k}=2(B_{k-1}-V_{k-1})=2B_{k-1}-2^k$

Первая-то легко решается, а вторая не получается. Я пытался (как и с первой) развернуть её, но закономерности не получается что-то
$B_k=2B_{k-1}-2^k=2^2B_{k-2}-2^{k+1}=2^3B_{k-3}-2^k-2^{k-1}=2^4B_{k-4}-2^{k+1}-2^{k-1}=...$

Как её можно решить? (Я посчитал в вольфраме, он говорит $B_k=2^k(n-k)$, но хочется самому это найти).

-- Вс июн 27, 2010 12:26:02 --

Если верить ответу Вольфрама, то получается на $n$-ой минуте все бактерии умрут? Т. е. поулчается вообще не зависит, сколько там бактерий было? Какой то странный результат. Было миллаард бактерий, пустили одного вируса и все через миллиард минут умрут

-- Вс июн 27, 2010 12:30:46 --

Я конечно понимаю, что вирусы в отличии от бактерий не дохнут. Т.е. их чсило только растёт. Но ведь же и бактерии тоже множаться. И тоже делением. Почему то интуитивно кажется, что бактерий всегда будет больше, хотя некоторую часть будут губить вирусы.

[gris]

По индукции.

А для понимания почему так происходит - рассмотрите долю вирусов в общей численности фигурантов.

Чем то слабо напоминает муху на резинке, правда там доля растёт гораздо медленнее, но тем не менее рано или поздно достигает 1.

Интересно рассмотреть непрерывный аналог задачи. Скорость размножения вирусов пропорциональна их количеству, для бактерий то же. Но бактерии ещё мрут со скоростью, пропорциональной количеству вирусов.
Систему ДУ. При разных коэффициентах пропорциональности ответ - ???

[мат-ламер]

Цитата:

Если верить ответу Вольфрама, то получается на $n$-ой минуте все бактерии умрут? Т. е. поулчается вообще не зависит, сколько там бактерий было? Какой то странный результат.

А почему не зависит? Зависит прямо пропорционально.

[caxap]

gris
Меня интересует не доказательство $B_k=2^k(n-k)$, а вывод.

мат-ламер в сообщении #335560 писал(а):

А почему не зависит? Зависит прямо пропорционально.

Я имел ввиду, что независимо от числа бактерий, один вирус в конце концов угробит всю колонию.

-- Вс июн 27, 2010 12:39:05 --

Кстати, а можно решить задачу без применения реккурентностей? Т.е. чисто из рассуждений дать ответ на вопрос (там же не спрашивается на каккой минуте все бактерии умрут, надо лишь узнать умрут они вообще или нет)

[ewert]

caxap в сообщении #335561 писал(а):

Кстати, а можно решить задачу без применения реккурентностей? Т.е. чисто из рассуждений дать ответ на вопрос (там же не спрашивается на каккой минуте все бактерии умрут, надо лишь узнать умрут они вообще или нет)

совсем без рекуррентностей -- вряд ли. Но можно придумать более простые рекуррентности:

$\begin{cases}V_{k+1}=2V_k \\ B_{k+1}=2(B_k-V_k)\end{cases} \qquad \Longrightarrow \qquad \dfrac{B_{k+1}}{V_{k+1}}=\dfrac{B_{k}}{V_{k}}-1.$

Т.е. отношение числа бактерий к числу вирусов убывает в арифметической прогрессии и, стало быть, рано или поздно исчезнет напрочь (и даже ясно, когда).

[Padawan]

caxap в сообщении #335561 писал(а):

Т.е. чисто из рассуждений дать ответ на вопрос (там же не спрашивается на каккой минуте все бактерии умрут, надо лишь узнать умрут они вообще или нет)

Все там будем

По поводу решения рекуррентного соотношения:
Сначала решите однородное реккурентное $B(k)=2B(k-1)$, получится $B(k)=C2^k$. Далее метод вариации произвольной постоянной $C=C(k)$, всё как в дифф.уравнениях.

[caxap]

ewert в сообщении #335567 писал(а):

Т.е. отношение числа бактерий к числу вирусов убывает в арифметической прогрессии

Спасибо, так действительно проще получается.

Padawan в сообщении #335568 писал(а):

вариации произвольной постоянной $C=C(k)$, всё как в дифф.уравнениях.

Я диф. уравнения не знаю ещё :(

А вообще есть ли какой-нибудь общий метод для решения подобных простых реккурентностях. Я читал (немножко) Конкретную математику, там вот только 2 метода объясняется: 1) угадывание и доказывание 2) репертуарный метод. Но второй я не очень понял...

Padawan в сообщении #335568 писал(а):

Сначала решите однородное реккурентное $B(k)=2B(k-1)$, получится $B(k)=C2^k$

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

[Padawan]

caxap
Нет, угадывать не надо! Подставьте в исходное уравнение вместо $B(k)$ $C(k)2^k$ получится уравнение для $C(k)$ оно решается простым суммированием, т.е. ответ будет в виде \large $C(k)=\sum\limits_{\nu=1}^k f(\nu)+C_0$.

[ewert]

caxap в сообщении #335574 писал(а):

А вообще есть ли какой-нибудь общий метод для решения подобных простых реккурентностях.

Поскольку речь о линейных рекуррентностях -- способ есть, и очень простой. У Вас линейное неоднородное разностное уравнение: ${B_{k+1}=2B_k-2\cdot2^k}$. Соответствующее однородное уравнение: ${B_{k+1}=2B_k}$ имеет общее решение ${B_k^{(0)}=C\cdot2^k}$, где $C$ -- произвольная постоянная. Согласно общей теории, общее решение неоднородного уравнения есть ${B_k=B_k^{(0)}+\widetilde B_k}$, где ${\widetilde B_k}$ -- это хоть какое-то частное решение неоднородного уравнения. Его следует искать примерно в том же виде, что и "неоднородность" $f_k$ в уравнении (в данном случае ${f_k=-2\cdot2^k}$), но более общем: ${\widetilde B_k=A\cdot2^k}$, где $A$ -- неопределённый коэффициент. Подставляя это в уравнение, находим $A$. Точнее, так надо было бы делать, если бы основания геометрической прогрессии в $B_k^{(0)}$ и в $f_k$ были бы разными. А у нас оба они равны двойке ("резонанс"), поэтому (опять же согласно теории) выражение для частного решения надо дополнительно умножить на $k$, т.е. искать решение в виде ${\widetilde B_k=A\cdot2^k\cdot k}$. Вот теперь всё получится. После подстановки окажется ${A=-1}$, т.е. ${B_k=C\cdot2^k-k\cdot2^k}$. Наконец, произвольную постоянную $C$ находим из начального условия: ${B_0=n}$, откуда ${C=n}$.

Всё это естественным образом обобщается на уравнения высших порядков (с несколькими слагаемыми $B_{k},B_{k+1},B_{k+2},\ldots$) и с неоднородностями $f_k$, представляющими собой произвольные комбинации разных степеней и геометрических прогрессий.

[caxap]

ewert в сообщении #335578 писал(а):

...Точнее, так надо было бы делать, если бы основания геометрической прогрессии в $B_k^{(0)}$ и в $f_k$ были бы разными. А у нас оба они равны двойке ("резонанс"), поэтому (опять же согласно теории) выражение для частного решения надо дополнительно умножить на $k$, т.е. искать решение в виде ${\widetilde B_k=A\cdot2^k\cdot k}$...

Спасибо. Но всё равно не до конца понял. Ну ладно, когда буду проходить дифуравнения, думаю и с этим разберусь.

[meduza]

caxap в сообщении #335574 писал(а):

Я читал (немножко) Конкретную математику, там вот только 2 метода объясняется: 1) угадывание и доказывание 2) репертуарный метод.

Там был ещё один. Суть его в том, что исходная реккурентность множится или делится на что-нибудь, в результате получается более простая реккурентность.

Для данной задачи: делим $B_k=2B_{k-1}-2^k$ на $2^k$ (до этого легко догадаться), получаем $\dfrac{B_k}{2^k}=\dfrac{B_{k-1}}{2^{k-1}}-1$. Т. е. получается простая реккурентность относительно $T_k=\dfrac {B_k}{2^k}$: $T_k=T_{k-1}-1=T_0-k=n-k$, а значит $B_k=2^k(n-k)$.

-- Пн июн 28, 2010 15:33:48 --

(Оффтоп)

Кстати, догадываться до $2^k$ не нужно. Я посмотрел КМ, этот метод называется "метод суммирующего множителя", причём множитель находится из реккурентности. В данном случае ($a_k=1$, $b_k=2$, $c_k=-2^k$ в обозначениях книги) она такая: $s_k\cdot 2=s_{k-1}\cdot 1$, $s_0=1$, т. е. $s_k=1/2^k$.

[Darkstar]

Пусть n(число бактерий)=4, v(число вирусов)=1
1-я минута: n=2(4-1)=6, v=2
2-я: n=2(6-2)=8, v=4
3-я n=2(8-4)=8, v=8
4-я n=2(8-8)=0, v=16

Поскольку колонии растут с одинаковой скоростью, начиная с начального состояния n и v, но только вирусы атакуют бактерии, а не наоборот, то таков результат.
Чтобы результат был другим, скорость роста колонии должна быть выше скорости ее поглощения. А здесь скорость ее поглощения постоянно увеличивается, а рост остается постоянным.

Обратите внимание, что в задаче ничего не спрашивается про цифры, только да или нет.

[tmpAnswer]

Просто нужно внимательно развёртывать:
$ B_{k}=2\cdot B_{k-1}-2^{k}=2\cdot(2\cdot B_{k-2}-2^{k-1})+2^{k}=2^{2}\cdot B_{k-2}-2\cdot2^{k-1}-2^{k}=2^{2}\cdot B_{k-2}-2^{k}-2^{k}=2^{2}\cdot B_{k-2}-2\cdot2^{k}= 2^{2}\cdot(2\cdot B_{k-3}-2^{k-2})-2\cdot2^{k}=2^3\cdot B_{k-3}-2^{k}-2\cdot2^{k}= 2^{3}\cdot B_{k-3}-3\cdot2^{k}=...=2^{m}\cdot B_{k-m}-m\cdot2^{k}=2^{k}\cdot B_{0}-k\cdot2^{k}=2^{k}\cdot n-k\cdot2^{k}=2^{k}\cdot (n-k) $