Školjka

Banka Batha izdaje kovanice kojima se na jednoj strani nalazi $H$, a na drugoj $T$. Borna ima $n$ takvih kovanica poredanih u niz slijeva nadesno te započinje proces sljedećih poteza: ako točno $k > 0$ kovanica pokazuje $H$, $k$-tu kovanicu slijeva okreće na drugu stranu; u suprotnom sve kovanice pokazuju $T$ i proces staje. Na primjer, ako je $n = 3$, proces koji započinje konfiguracijom $THT$ je $THT \rightarrow HHT \rightarrow HTT \rightarrow TTT$ te on staje nakon $3$ poteza. (a) Dokaži da, za svaku početnu konfiguraciju, proces staje nakon konačno mnogo poteza. (b) Za svaku početnu konfiguraciju $C$, neka je $L(C)$ broj poteza potrebnih da proces stane. Na primjer, za $n = 3$ je $L(THT) = 3$ i $L(TTT) = 0$. Odredi aritmetičku sredinu brojeva $L(C)$ po svih $2^n$ mogućnosti početne konfiguracije $C$.