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

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