Câu hỏi 75
Alice và Barbara nghĩ ra trò chơi sau. Họ có một bảng ô vuông $1 \times 2018$, các ô được đánh số từ $1$ đến $2018$ từ trái sang phải, và $2018$ quân bài cũng được đánh số từ $1$ đến $2018$. Trò chơi bắt đầu với bảng trống, và hai người chơi lần lượt thực hiện nước đi; người đến lượt có thể chọn một trong hai cách:
- chọn một quân bài chưa được đặt lên bảng và đặt nó vào một ô trống, với điều kiện các số trên những quân bài đã đặt, đọc từ trái sang phải, theo thứ tự tăng dần;
- chọn một quân bài đã được đặt trên bảng và di chuyển nó sang một ô kề bên sao cho quân bài tiến lại gần ô mang cùng số với quân bài đó, với điều kiện ô đến đang trống (ví dụ: nếu quân bài số $7$ đang ở ô số $12$ thì có thể di chuyển nó sang trái, nhưng không được sang phải; còn nếu một quân bài đã nằm ở ô có cùng số với nó thì không thể di chuyển nó nữa).
(a) Chứng minh rằng ở mỗi lượt, nếu chưa phải tất cả quân bài đều ở trên bảng thì luôn tồn tại một nước đi hợp lệ.
(b) Nếu Alice đi trước và người đặt quân bài cuối cùng là người thắng, ai có chiến lược thắng?
- chọn một quân bài chưa được đặt lên bảng và đặt nó vào một ô trống, với điều kiện các số trên những quân bài đã đặt, đọc từ trái sang phải, theo thứ tự tăng dần;
- chọn một quân bài đã được đặt trên bảng và di chuyển nó sang một ô kề bên sao cho quân bài tiến lại gần ô mang cùng số với quân bài đó, với điều kiện ô đến đang trống (ví dụ: nếu quân bài số $7$ đang ở ô số $12$ thì có thể di chuyển nó sang trái, nhưng không được sang phải; còn nếu một quân bài đã nằm ở ô có cùng số với nó thì không thể di chuyển nó nữa).
(a) Chứng minh rằng ở mỗi lượt, nếu chưa phải tất cả quân bài đều ở trên bảng thì luôn tồn tại một nước đi hợp lệ.
(b) Nếu Alice đi trước và người đặt quân bài cuối cùng là người thắng, ai có chiến lược thắng?