Question

В начальный момент в строке записана цифра 0 (ноль). На каждом из последующих 9 шагов выполняется следующая операция: в очередную строку записывается удвоенная предыдущая строка, а в конце строки приписывается очередная цифра (на i-м шаге приписывается цифра i). Для удобства в скобках пишется номер строки (начиная с 0). Ниже показаны первые строки, сформированные по описанному правилу: (0) 0 (1) 001 (2) 0010012 (3) 001001200100123 Сколько раз в последней строке встречается цифра 5?

Answer 1

Так как в записи учавствуют только цифры - цифра 1 встречается только в виде комбинации второй строки (001).
В учетом того что начиная с первой строки при каждом шаге число включений второй строки в остальные увеличивается в два раза, то число единиц будет равно 2^(n-1) ( 1 - первая строка, 2 - вторая строка, 4 - 3-я строка, 8 - 4-а строка и т. д. )
То есть в 9-ой строке единица будет встречаться 2^(9-1)=2^8=1024/4=256 раз.