IMO олимпиада по математике 2019 года | Казахстанские олимпиады

Банк города Бат выпускает монеты с буквой HH на одной стороне и буквой TT на другой стороне. Гарри разложил nn таких монет в ряд слева направо. Он последовательно производит следующую операцию: если в ряду ровно k>0k > 0 монет лежат букой HH кверху, то он переворачивает kk-ю слева монету; иначе все монеты лежат буквой TT кверху, и он останавливается. Например, если n=3n=3 и процесс начинается с конфигурации THT,THT, то последовательность операций выглядит так THTHHTTTT,THT \to HHT \to TTT, то есть процесс остановится после трех операций.
   a) Докажите, что при любой начальной конфигурации процесс остановится после конечного числа операций.
   b) Для каждой начальной конфигурации CC через L(C)L(C) обозначим количество операций, после которых процесс остановится. Например, L(THT)=3L(THT) =3 и L(TTT)=0. L(TTT)=0. Найдите среднее арифметическое значений L(C),L(C), когда CC пробегает все 2n2^n возможных начальных конфигураций.