Q10 Matemática  (IMO Shortlist 2019)

O Bank of Bath emite moedas com $H$ de um lado e $T$ do outro. Harry tem $n$ dessas moedas dispostas em uma linha da esquerda para a direita. Ele executa repetidamente a seguinte operação: se houver exatamente $k>0$ moedas mostrando $H$, então ele vira a $k$ésima moeda da esquerda; caso contrário, todas as moedas mostram $T$ e ele para. Por exemplo, se $n=3$ o processo iniciando com a configuração $THT$ seria $THT\to HHT\to HTT\to TTT$, que para após três operações. (a) Mostre que, para cada configuração inicial, Harry para após um número finito de operações. (b) Para cada configuração inicial $C$, seja $L(C)$ o número de operações antes de Harry parar. Por exemplo, $L(THT)=3$ e $L(TTT)=0$. Determine o valor médio de $L(C)$ sobre todas as $2^n$ possíveis configurações iniciais $C$. Proposto por David Altizio, EUA