Câu hỏi 10
Đặt $n$ là số nguyên dương. Harry có $n$ đồng xu được xếp trên bàn, mỗi đồng xu có một trong hai mặt: mặt ngửa hoặc mặt sấp. Anh ta liên tục thực hiện thao tác sau: nếu có $k$ đồng xu hiển thị mặt ngửa và $k\gt 0$, thì anh ta lật đồng xu thứ $k$; nếu không thì anh ta sẽ dừng quá trình này. (Ví dụ: quy trình bắt đầu bằng THT sẽ là THT $\rightarrow H H T \rightarrow H T T \rightarrow T T T$, thực hiện ba bước.)
Để $C$ biểu thị cấu hình ban đầu (dãy gồm $n H$ và $T$, nghĩa là n kí hiệu H hoặc T), hãy viết $\ell(C)$ cho số bước cần thiết trước khi tất cả các đồng xu hiển thị $T$. Chứng minh rằng số $\ell(C)$ này là hữu hạn và xác định giá trị trung bình của nó trên tất cả các cấu hình ban đầu có thể có của $2^{n}$ $C$.
Để $C$ biểu thị cấu hình ban đầu (dãy gồm $n H$ và $T$, nghĩa là n kí hiệu H hoặc T), hãy viết $\ell(C)$ cho số bước cần thiết trước khi tất cả các đồng xu hiển thị $T$. Chứng minh rằng số $\ell(C)$ này là hữu hạn và xác định giá trị trung bình của nó trên tất cả các cấu hình ban đầu có thể có của $2^{n}$ $C$.