tailieunhanh - Bất biến và nửa bất biến trong các bài toán trò chơi - Nguyễn Thành Khang

Bài viết "Bất biến và nửa bất biến trong các bài toán trò chơi" giới thiệu đến các bạn những bài toán một người chơi, những bài toán hai người chơi bất bình đẳng, các loại bài toán hai người chơi bình đẳng,. | BẤT BIẾN VÀ NỬA BẤT BIẾN TRONG CÁC BÀI TOÁN TRÒ CHOI Nguyễn Thành Khang1 Khi chúng ta xem xét một quá trình có cách thức biến đổi lặp đi lặp lại chúng ta hãy cố gắng tìm ra một đại lượng không bao giờ thay đổi gọi là bất biến . Các bất biến quen thuộc trong các bài toán thi Olympic là tính chẵn lẻ phép lấy modulo lấy tổng tính đối xứng của các đại lượng . Trong một số bài toán khác chúng ta chỉ có thể tìm ra các đại lượng luôn thay đổi theo một hướng xác định gọi là nửa bất biến . Các đại lượng này cũng khá hữu ích trong các bài toán tổ hợp nói chung và đặc biệt là trong các bài toán trò chơi nói riêng. Bởi lẽ các bài toán trò chơi thường có một vị frí kết thúc và cần một đại lượng nửa bất biến để chúng ta có thể khẳng định ữò chơi sẽ đạt đến vị trí kết thúc sau hữu hạn bước. 1 Các bài toán một người chơi Các bài toán có một người chơi xuất hiện không nhiều ưong các kỳ thi Olympic. Các bài toán dạng này thường được giải quyết bằng cách tìm ra một đại lượng bất biến hoặc đại lượng nửa bất biển và so sánh đại lượng đó ở vị trí ban đầu và vị trí kết thúc. Bài toán 1. Có 2012 quả cầu màu vàng chứa trong một hộp. Ta giả thiết thêm là có đủ số các quả vàng đỏ xanh ở bên ngoài hộp để thực hiện được các động tác sau đây nhiều lần Thay hai quả cầu vàng bằng một quả cầu xanh. Thay hai quả cầu đỏ bằng một quả cầu xanh. Thay hai quả cầu xanh bằng một quả cầu vàng và một quả cầu đỏ. Thay một quả cầu vàng và một quả cầu xanh bằng một quả cầu đỏ. Thay một quả cầu xanh vả một quả cầu đỏ bằng một quả cầu vàng. a Mỗi nước đi là một lần thực hiện một cách tùy ý một trong năm động tác kể trên. Giả sử rằng sau một số hữu hạn các nước đi trong hộp đã cho còn lại ba quả cầu. Chứng minh rằng có ít nhất một quả cầu xanh. b Có chiến lược nào để sau hữu hạn các nước đi chỉ còn lại một quả cầu trong hộp Lời giải. Tại thời điểm nào đó ta giả sử ttong hộp có X quả cầu vàng y quả cầu xanh z quả cầu đỏ. Ta đặt T X 2y 3z. Rõ ràng là sau mỗi nước đi T giảm đi một bội của 4 hoặc không đổi. Ở thời .