Решение: Подсчёт цифр в строке
Цепочки символов (строки) создаются по следующему правилу. Первая строка состоит из одного символа — цифры «1». Каждая из последующих цепочек создаётся так: в очередную строку дважды записывается предыдущая цепочка цифр (одна за другой, подряд), а в конец приписывается ещё одно число — номер строки по порядку (на $i$-м шаге дописывается число «$i$»). Вот первые 4 строки: (1) 1; (2) 112; (3) 1121123; (4) 112112311211234. Сколько раз в общей сложности встречаются в девятой строке чётные цифры (2, 4, 6, 8)?
Решение по шагам
4 шагаОбозначим через $c_i$ количество чётных цифр в $i$-й строке. В первой строке чётных цифр нет: $c_1=0$.
При построении каждой следующей строки предыдущая строка записывается дважды, поэтому её вклад удваивается. Дополнительно учитываем чётные цифры в номере строки.
$$c_i=2c_{i-1}+e_i$$Для номеров строк от 2 до 9 чётными являются цифры в номерах $2$, $4$, $6$ и $8$, поэтому $e_i=1$ для этих номеров, а для $3$, $5$, $7$ и $9$ значение равно нулю.
Последовательно вычисляем: $c_2=1$, $c_3=2$, $c_4=5$, $c_5=10$, $c_6=21$, $c_7=42$, $c_8=85$, $c_9=170$.
Где здесь ошибаются
Не учитывать удвоение всей предыдущей строки.
Не добавлять чётную цифру номера строки при переходах к строкам 2, 4, 6 и 8.
Считать количество символов в строке вместо количества чётных цифр.