Câu hỏi 82
Alice và Bob chơi trò Token Tag trên bàn cờ $8\times8$. Lúc bắt đầu, Bob đặt một quân cho mỗi người lên bàn. Sau đó, trong mỗi lượt, Alice di chuyển quân của mình trước rồi Bob di chuyển quân của mình. Nếu vào bất kỳ thời điểm nào trong một lượt, hai quân nằm trên cùng một ô, Alice thắng ngay. Nếu Alice chưa thắng sau 2012 lượt thì Bob thắng.
a. Giả sử mỗi quân được phép đi đến một ô kề theo chiều ngang hoặc dọc. Chứng minh Bob có chiến lược thắng.
b. Thay vào đó, giả sử mỗi quân được phép đi đến một ô kề theo chiều ngang, dọc hoặc chéo. Chứng minh Alice có chiến lược thắng.
a. Giả sử mỗi quân được phép đi đến một ô kề theo chiều ngang hoặc dọc. Chứng minh Bob có chiến lược thắng.
b. Thay vào đó, giả sử mỗi quân được phép đi đến một ô kề theo chiều ngang, dọc hoặc chéo. Chứng minh Alice có chiến lược thắng.