Bath은행은 한 면은 H, 반대면은 T인 동전을 발행한다. Harry는 $n$개의 동전을 왼쪽에서 오른쪽으로 일렬로 늘어놓았다. 그는 다음과 같은 시행을 반복적으로 한다: 만일 이 동전 중 H가 정확히 $k$($k>0$)개가 있으면 왼쪽부터 $k$번째 동전을 뒤집는다. 만일 모든 동전이 모두 T이면 시행을 멈춘다. 예를 들어, $n=3$이고 초기 놓임이 THT인 경우, 다음과 같이 3번의 시행을 한 후 멈춘다. THT$\to$HHT$\to$HTT$\to$TTT.

(a) 초기 놓임이 어떠하든, Harry는 유한 번의 뒤집는 시행을 한 후에 시행을 멈추게 됨을 보여라.

(b) 각 초기 놓임 $C$에 대하여, $L(C)$를 Harry가 시행을 멈추기 전까지 한 시행의 횟수라 하자. 예를 들어 $L(THT)=3$이고 $L(TTT)=0$이다. $2^n$개의 모든 가능한 초기 놓임 $C$에 대하여, $L(C)$의 평균값을 구하여라.