2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Вирус vs Бактерии (решение рекуррентного соотношения)
Сообщение27.06.2010, 12:20 
Заслуженный участник
Аватара пользователя


07/01/10
2015
Из Кванта:

М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 --

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

 Профиль  
                  
 
 Re: Вирус vs Бактерии
Сообщение27.06.2010, 12:32 
Заслуженный участник
Аватара пользователя


13/08/08
13479
По индукции.

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

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

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

 Профиль  
                  
 
 Re: Вирус vs Бактерии
Сообщение27.06.2010, 12:36 
Заслуженный участник


30/01/09
4694
Цитата:
Если верить ответу Вольфрама, то получается на $n$-ой минуте все бактерии умрут? Т. е. поулчается вообще не зависит, сколько там бактерий было? Какой то странный результат.
А почему не зависит? Зависит прямо пропорционально.

 Профиль  
                  
 
 Re: Вирус vs Бактерии
Сообщение27.06.2010, 12:37 
Заслуженный участник
Аватара пользователя


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

мат-ламер в сообщении #335560 писал(а):
А почему не зависит? Зависит прямо пропорционально.

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

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

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

 Профиль  
                  
 
 Re: Вирус vs Бактерии
Сообщение27.06.2010, 13:00 
Заслуженный участник


11/05/08
31587
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.$

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

 Профиль  
                  
 
 Re: Вирус vs Бактерии
Сообщение27.06.2010, 13:01 


13/12/05
3517
caxap в сообщении #335561 писал(а):
Т.е. чисто из рассуждений дать ответ на вопрос (там же не спрашивается на каккой минуте все бактерии умрут, надо лишь узнать умрут они вообще или нет)

Все там будем :-)

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

 Профиль  
                  
 
 Re: Вирус vs Бактерии
Сообщение27.06.2010, 13:09 
Заслуженный участник
Аватара пользователя


07/01/10
2015
ewert в сообщении #335567 писал(а):
Т.е. отношение числа бактерий к числу вирусов убывает в арифметической прогрессии

Спасибо, так действительно проще получается.
Padawan в сообщении #335568 писал(а):
вариации произвольной постоянной $C=C(k)$, всё как в дифф.уравнениях.

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

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

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

 Профиль  
                  
 
 Re: Вирус vs Бактерии
Сообщение27.06.2010, 13:13 


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

 Профиль  
                  
 
 Re: Вирус vs Бактерии
Сообщение27.06.2010, 13:30 
Заслуженный участник


11/05/08
31587
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$, представляющими собой произвольные комбинации разных степеней и геометрических прогрессий.

 Профиль  
                  
 
 Re: Вирус vs Бактерии
Сообщение28.06.2010, 14:11 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Вирус vs Бактерии
Сообщение28.06.2010, 14:28 
Заслуженный участник
Аватара пользователя


03/06/09
1497
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$.

 Профиль  
                  
 
 Re: Вирус vs Бактерии
Сообщение28.06.2010, 19:44 


02/06/10
25
Пусть 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, но только вирусы атакуют бактерии, а не наоборот, то таков результат.
Чтобы результат был другим, скорость роста колонии должна быть выше скорости ее поглощения. А здесь скорость ее поглощения постоянно увеличивается, а рост остается постоянным.

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

 Профиль  
                  
 
 Re: Вирус vs Бактерии (решение рекуррентного соотношения)
Сообщение16.08.2018, 00:31 


15/08/18
1
Просто нужно внимательно развёртывать:
$
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)
$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group