Câu hỏi 5
Cho số nguyên dương $n$. Harry xếp $n$ đồng xu thành một hàng trên bàn, mỗi đồng xu có thể ngửa hoặc sấp. Harry thực hiện thao tác sau: nếu có $k$ đồng xu ngửa và $k \gt 0$, lật đồng xu thứ $k$; nếu không, dừng quá trình. Ví dụ, từ $THT$ ta có quá trình $THT \to HHT \to HTT \to TTT$, gồm ba bước.
Chứng minh quá trình luôn dừng, và tính số bước trung bình trên tất cả $2^n$ cấu hình ban đầu.
Chứng minh quá trình luôn dừng, và tính số bước trung bình trên tất cả $2^n$ cấu hình ban đầu.