IMO

El Banco de Bath emite monedas con una $H$ en una cara y una $T$ en la otra. Harry tiene $n$ monedas de este tipo alineadas de izquierda a derecha. Él realiza repetidamente la siguiente operación: si hay exactamente $k \gt 0$ monedas con la $H$ hacia arriba, Harry voltea la $k$-ésima moneda contando desde la izquierda; en caso contrario, todas las monedas tienen la $T$ hacia arriba y él se detiene. Por ejemplo, si $n = 3$ y la configuración inicial es $THT$, el proceso sería $THT \to HHT \to HTT \to TTT$, que se detiene después de tres operaciones. (a) Demostrar que para cualquier configuración inicial que tenga Harry, el proceso se detiene después de un número finito de operaciones. (b) Para cada configuración inicial $C$, sea $L(C)$ el número de operaciones que se realizan hasta que Harry se detiene. Por ejemplo, $L(THT) = 3$ y $L(TTT) = 0$. Determinar el valor promedio de $L(C)$ sobre todas las $2^n$ posibles configuraciones iniciales de $C$.