Câu hỏi 9
C4 (EST) Có $n+1$ vị trí cố định trên một hàng, được ghi nhãn từ $0$ đến $n$ theo thứ tự tăng dần từ phải sang trái. Các thẻ đánh số từ $0$ đến $n$ được xáo trộn và chia, mỗi vị trí một thẻ. Mục tiêu của trò chơi là đặt thẻ $i$ vào vị trí thứ $i$ với $0\le i\le n$. Nếu chưa đạt điều đó, thực hiện nước đi sau. Xác định $k$ nhỏ nhất sao cho vị trí thứ $k$ chứa thẻ $l\gt k$. Lấy thẻ này ra, trượt tất cả các thẻ từ vị trí thứ $(k+1)$ đến vị trí thứ $l$ sang phải một vị trí, rồi đặt thẻ $l$ vào vị trí thứ $l$.
(a) Chứng minh trò chơi kéo dài nhiều nhất $2^n-1$ nước.
(b) Chứng minh tồn tại duy nhất một cấu hình ban đầu mà trò chơi kéo dài đúng $2^n-1$ nước.
(a) Chứng minh trò chơi kéo dài nhiều nhất $2^n-1$ nước.
(b) Chứng minh tồn tại duy nhất một cấu hình ban đầu mà trò chơi kéo dài đúng $2^n-1$ nước.