Решение задачи 348

Условие:

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

Решение:

Распишем сколько будет вирусов и бактерий после следующих минут:

После нулевой: 1 вирус, 1000 бактерий.
После первой: 2 вирус, (1000−1)*2=999*2 бактерий.
После второй: 4 вируса, (999*2−2)*2=998*4 бактерий.

Здесь возникает гипотеза: после k-ой (k<1000) минуты будет 2ᵏ вирусов и (1000−k)*2ᵏ бактерий. Докажем это по индукции. База (даже три базы) уже проверена. Покажем переход, пусть для k верно, то есть после k-ой минуты будет 2ᵏ вирусов и (1000−k)*2ᵏ бактерий. Тогда нетрудно видеть, что еще через одну минуту будет 2ᵏ⁺¹ вирусов и ((1000−k)*2ᵏ−2ᵏ)*2=(1000−(k+1))*2ᵏ*2=(1000−(k+1))*2ᵏ⁺¹ бактерий. Гипотеза доказана. Значит, после 1000-ой минуты бактерий не останется.

Ответ: Верно.