Trong mỗi ô của bảng 2x200 có đặt một đồng xu. Hai bạn An, Bình chơi trò chơi, luân phiên thực hiện các nước đi. Số xu tối đa mà Bình có thể nhận được
Bài toán Trò chơi trên bảng 2x200
Trong mỗi ô của bảng $2 \times 200$ có đặt một đồng xu. Hai bạn An và Bình chơi một trò chơi, luân phiên thực hiện các nước đi, An bắt đầu trước.
Trong một lượt, người chơi chọn bất kỳ một đồng xu nào và di chuyển nó:
- An: Di chuyển đồng xu sang một ô chung đỉnh theo đường chéo.
- Bình: Di chuyển sang một ô chung cạnh.
Nếu hai đồng xu nằm trong cùng một ô, một trong số chúng sẽ ngay lập tức được đưa ra khỏi bảng và thuộc về Bình.
Bình có thể dừng trò chơi bất cứ lúc nào và lấy tất cả các đồng xu thu được.
Hỏi: Số xu tối đa mà Bình có thể nhận được là bao nhiêu, bất kể An chơi như thế nào?
Đáp số
$\boxed{300}$Lời giải
1. Chiến thuật của Bình để đạt được ít nhất 300 đồng xu
Đầu tiên, ta đưa ra chiến thuật cho Bình để luôn đạt được 300 đồng xu.
Nếu Bình chưa nhận được quá 299 đồng xu, thì trước lượt đi của Bình trên bảng vẫn còn ít nhất 101 đồng xu.
Chia bảng thành 100 hình vuông $2 \times 2$. Theo nguyên lý Dirichlet, sẽ có ít nhất hai đồng xu nằm trong cùng một hình vuông $2 \times 2$ đó.
- Nếu hai đồng xu này nằm kề cạnh nhau, Bình di chuyển đồng xu này đè lên đồng xu kia và nhận thêm một đồng xu.
- Nếu hai đồng xu nằm chéo nhau, Bình di chuyển một trong hai đồng xu vào cùng cột với đồng xu kia (ở đây cột có chiều dài 2, hàng có chiều dài 200).
Bây giờ, bất kể An thực hiện nước đi nào, hai đồng xu này vẫn sẽ nằm kề cạnh nhau (hoặc một chiếc bị loại bỏ và thuộc về thu nhập của Bình), nghĩa là trong lượt tiếp theo, Bình sẽ có thể nhận được thêm một đồng xu.
Bằng cách này, Bình luôn có thể tăng số tiền thắng của mình khi nó còn ít hơn 300.
2. Chiến thuật của An để giới hạn Bình ở mức 300 đồng xu
Tiếp theo, ta chỉ ra cách chơi của An để Bình không thể nhận được quá 300 đồng xu.
Đánh số các cột từ 1 đến 200 theo thứ tự, chọn một đồng xu trong mỗi cột lẻ và quy ước tô chúng màu đỏ.
An chỉ cần đảm bảo rằng các đồng xu đỏ luôn ở trên bảng. Để làm được điều này, chỉ cần chắc chắn rằng không bao giờ có hai đồng xu đỏ rơi vào cùng một ô.
Gọi một cấu hình là "ổn định" nếu có một đồng xu đỏ nằm ở mỗi cột $1, 3, 5, ..., 197$, và một đồng xu đỏ nữa nằm ở một trong hai cột cuối cùng $199, 200$.
Dễ thấy rằng sau bất kỳ nước đi nào từ cấu hình ổn định, hai đồng xu đỏ sẽ không cùng nằm trong một ô.
An sẽ chơi sao cho sau mỗi lượt của mình, cấu hình thu được là ổn định.
Nếu sau lượt của Bình, cấu hình vẫn ổn định, An sẽ di chuyển đồng xu đỏ thứ 100 giữa hai cột cuối cùng; An cũng làm như vậy trong lượt đi đầu tiên của mình.
Nếu sau lượt của Bình, cấu hình không còn ổn định, nghĩa là Bình đã di chuyển một đồng xu đỏ từ cột x sang cột lân cận, khi đó An trong lượt của mình sẽ đưa nó trở lại cột x.
Như vậy, bằng cách chơi theo chiến thuật này, An giữ được tất cả 100 đồng xu đỏ trên bảng.
