Câu hỏi 75
Cho $n$ là số nguyên dương. Harry có $n$ đồng xu xếp thành hàng trên bàn, mỗi đồng xu hiện mặt $H$ hoặc mặt $T$. Bạn ấy lặp lại thao tác sau: nếu có $k$ đồng xu đang ở mặt $H$ và $k\gt 0$, thì lật đồng xu thứ $k$; ngược lại thì dừng quá trình. (Ví dụ, quá trình bắt đầu từ $T H T$ sẽ là $T H T \rightarrow H H T \rightarrow H T T \rightarrow T T T$, gồm ba bước.)
Gọi $C$ là cấu hình ban đầu (một dãy gồm $n$ chữ $H$ và $T$), ký hiệu $\ell(C)$ là số bước cần thiết cho đến khi mọi đồng xu đều ở mặt $T$. Chứng minh rằng số $\ell(C)$ này hữu hạn, và xác định giá trị trung bình của nó trên tất cả $2^{n}$ cấu hình ban đầu $C$ có thể có.
Gọi $C$ là cấu hình ban đầu (một dãy gồm $n$ chữ $H$ và $T$), ký hiệu $\ell(C)$ là số bước cần thiết cho đến khi mọi đồng xu đều ở mặt $T$. Chứng minh rằng số $\ell(C)$ này hữu hạn, và xác định giá trị trung bình của nó trên tất cả $2^{n}$ cấu hình ban đầu $C$ có thể có.