Биология → Областная → 2018 → 11 класс | BeyondOlympiads

Как правильно отметил @Anton

нам достаточно решить задачу “какова вероятность того, что в последовательности из 99 нуклеотидов не будет подряд идущих двух G.

Давайте решим более общую задачу – какова вероятность того, что в последовательности из n нуклеотидов не будет подряд идущих двух G. Для этого найдем количество последовательностей из n нуклеотидов, таких, что в них нет GG, потом поделим на 4^n – на количество всех возможных последовательностей из n нуклеотидов. Так и получим вероятность.

Чтобы это найти, введем две вспомогательные функции: пусть f(n) – количество последовательностей длины n в которых нет GG и в которой последний нуклеотид G; g(n) – количество последовательностей длины n в которых нет GG и последний нуклеотид не G. Тогда ответом к нашей задаче будет число

\frac{f(99) + g(99)}{4^{99}}.

Попробуем найти рекуррентную зависимость этих двух функций.

С одной стороны, мы можем получить последовательность длины n которая не заканчивается на G, если к последовательности длины n-1 заканчивающееся на G припишем нуклеотид A,C,T (3 способа) или к последовательности длины n-1 не заканчивающееся на G припишем нуклеотид A,C,T (3 способа). Следовательно

g(n) = 3\cdot g(n -1) + 3\cdot f(n - 1).

С другой стороны, мы можем получить последовательность длины n которая заканчивается на G, если к последовательности длины n-1 не заканчивающееся на G припишем нуклеотид G (1 способ). Тогда имеем

f(n) = g(n - 1).

Соединим два равенства и распишем базовые случаи для n=1,n=2. Получаем

g(n) = 3g(n-1) + 3g(n-2), g(1) = 3, g(2) = 12.

Выпишем явную форму данного рекуррентного уравнения (можно сделать через характеристические уравнения, а можно через вольфрам). Получается вот такое несложное выражение :laughing:

g(n) = \frac{2\sqrt{21} \left(\frac{3}{2}\ - \frac{\sqrt{21}}{2}\right)^n + (21 + 5\sqrt{21}) \left(\frac{3}{2} + \frac{\sqrt{21}}{2}\right)^n}{7(3 + \sqrt{21})}.

Далее выражаем f(n) = g(n-1) .

f(n) = \frac{2\sqrt{21} \left(\frac{3}{2}\ - \frac{\sqrt{21}}{2}\right)^{n-1} + (21 + 5\sqrt{21}) \left(\frac{3}{2} + \frac{\sqrt{21}}{2}\right)^{n-1}}{7(3 + \sqrt{21})}.

Выходит, что ответ равен

\frac{f(99)+g(99)}{4^{99}} = \frac{2\sqrt{21} \left(\frac{3}{2}\ - \frac{\sqrt{21}}{2}\right)^{99} + 2\sqrt{21} \left(\frac{3}{2}\ - \frac{\sqrt{21}}{2}\right)^{98} + (21 + 5\sqrt{21}) \left(\frac{3}{2} + \frac{\sqrt{21}}{2}\right)^{99} + (21 + 5\sqrt{21}) \left(\frac{3}{2} + \frac{\sqrt{21}}{2}\right)^{98}}{7(3 + \sqrt{21})4^{99}}.
10 лайков