Trong trò bốc sỏi mà mỗi lượt được lấy một, hai hoặc ba viên, ai lấy viên cuối cùng thì thắng, người biết chiến lược sẽ luôn để lại cho đối thủ một số viên chia hết cho bốn, và như vậy chắc chắn thắng. Cách tìm ra chiến lược đó, và chiến lược của nhiều trò khác, là đi ngược từ cuối ván để phân biệt thế nào là thế thắng, thế nào là thế thua.
Chào bạn, đây là Nhà Toán Học. Bài toán trò chơi là món khoái khẩu của đề thi học sinh giỏi, vì nó đo đúng khả năng suy luận mà không cần nhiều công thức. Tập này mình chơi thật một ván, rồi rút ra ba cách nghĩ dùng cho hầu hết các bài trò chơi.
Chơi thử một ván với hai mươi mốt viên sỏi
Trên bàn có hai mươi mốt viên sỏi. Hai người lần lượt bốc, mỗi lượt một, hai hoặc ba viên. Ai bốc viên cuối cùng thì thắng. Bạn được đi trước. Nên bốc mấy viên.
Câu trả lời là bốc một viên, để lại hai mươi. Từ đó, đối thủ bốc bao nhiêu, bạn bốc sao cho tổng hai người trong lượt đó là bốn. Đối thủ bốc một, bạn bốc ba. Đối thủ bốc hai, bạn bốc hai.
Số sỏi sẽ đi qua mười sáu, mười hai, tám, bốn, rồi không. Mỗi lần tới lượt đối thủ, số sỏi chia hết cho bốn, và cuối cùng chính bạn bốc viên chót.
Nếu số sỏi ban đầu đã chia hết cho bốn thì sao. Khi đó người đi trước chắc chắn thua nếu đối thủ biết chơi. Lời khuyên lịch sự: hãy nhường đối thủ đi trước.
Đi ngược từ cuối ván: thế thắng và thế thua
Làm sao nghĩ ra con số bốn. Bắt đầu từ cuối. Nếu tới lượt bạn mà còn không viên nào, bạn đã thua vì đối thủ vừa bốc viên cuối. Gọi đó là thế thua.
Còn một, hai hoặc ba viên tới lượt bạn: bạn bốc hết, thắng. Đó là thế thắng. Còn bốn viên: bốc bao nhiêu cũng để lại một, hai, ba cho đối thủ, tức thế thắng của họ. Vậy bốn là thế thua.
Năm, sáu, bảy: bạn bốc để lại bốn cho đối thủ, thế thắng. Tám: lại là thế thua. Quy luật hiện ra: các số chia hết cho bốn là thế thua, còn lại là thế thắng.
Định nghĩa gọn: một thế là thế thua nếu mọi nước đi đều dẫn tới thế thắng của đối thủ. Một thế là thế thắng nếu có ít nhất một nước đi dẫn tới thế thua của đối thủ. Đi ngược từ cuối và tô màu từng thế là cách giải hầu hết các trò chơi hữu hạn.
Chiến lược đối xứng: bắt chước đối thủ
Một trò khác: hai người lần lượt đặt những đồng xu giống nhau lên một mặt bàn tròn, không chồng lên nhau. Ai không còn chỗ đặt thì thua. Người đi trước có chiến lược thắng không.
Có, và nó rất đẹp. Người đi trước đặt đồng xu đầu tiên đúng tâm bàn. Sau đó, mỗi khi đối thủ đặt một đồng xu ở đâu, người đi trước đặt một đồng xu ở vị trí đối xứng qua tâm.
Vì bàn tròn đối xứng qua tâm, hễ đối thủ còn chỗ đặt thì chỗ đối xứng cũng còn trống. Vậy người đi trước không bao giờ hết chỗ trước đối thủ. Không cần biết bàn rộng bao nhiêu, đồng xu cỡ nào.
Chiến lược đối xứng dùng được cho nhiều trò trên bàn cờ, trên dãy số, trên hình học. Khi thấy một trò có hình dạng đối xứng, hãy thử nghĩ cách bắt chước đối thủ qua một trục hay một tâm.
Biết mình thắng mà không biết thắng cách nào
Có một trò gọi là trò cắn sô cô la. Thanh sô cô la hình chữ nhật chia ô, ô góc dưới bên trái có độc. Mỗi lượt, người chơi chọn một ô và ăn ô đó cùng mọi ô ở phía trên và bên phải nó. Ai phải ăn ô độc thì thua.
Người ta chứng minh được người đi trước luôn có chiến lược thắng, bằng một lập luận gọi là ăn cắp chiến lược. Giả sử người đi sau có chiến lược thắng. Người đi trước ăn đúng ô góc trên bên phải. Nếu người đi sau có nước đáp trả thắng, thì người đi trước lẽ ra đã có thể đi ngay nước đó từ đầu, vì nó cũng ăn luôn ô góc trên bên phải. Vô lý.
Lập luận cho biết có chiến lược thắng, nhưng không cho biết chiến lược đó là gì. Với nhiều kích thước thanh sô cô la, đến nay người ta vẫn chưa có công thức gọn cho nước đi thắng.
Đây là ví dụ đẹp của chứng minh tồn tại, như nguyên lý Dirichlet mình đã kể: biết chắc có, mà không chỉ ra được cụ thể.
Từ bốc sỏi tới trò chơi Nim
Một mở rộng nổi tiếng là trò Nim, với nhiều đống sỏi, mỗi lượt được bốc bao nhiêu tuỳ ý nhưng chỉ từ một đống. Đầu thế kỷ hai mươi, người ta đã tìm ra lời giải đầy đủ dựa trên cách viết số trong hệ nhị phân.
Lời giải của Nim là nền móng cho cả một lý thuyết về trò chơi tổ hợp, dùng để phân tích rất nhiều trò hai người có thông tin đầy đủ, không có may rủi.
Với học sinh, thứ quý nhất từ các bài trò chơi là thói quen nghĩ ngược từ đích, và thói quen tìm một đại lượng mình có thể kiểm soát sau mỗi lượt, như số sỏi chia cho bốn dư mấy.
Câu đố nhỏ: trò bốc sỏi như trên nhưng mỗi lượt được bốc từ một tới năm viên, có ba mươi hai viên, ai bốc viên cuối thắng. Người đi trước nên bốc mấy viên.
Câu hỏi thường gặp
Thế thắng và thế thua là gì?
Thế thua là trạng thái mà mọi nước đi đều đưa đối thủ tới thế thắng. Thế thắng là trạng thái có ít nhất một nước đi đưa đối thủ tới thế thua. Phân loại các thế từ cuối ván ngược lên là cách giải nhiều bài trò chơi.
Trò bốc sỏi mỗi lượt một tới ba viên có chiến lược gì?
Luôn để lại cho đối thủ một số viên chia hết cho bốn. Nếu số viên ban đầu không chia hết cho bốn, người đi trước bốc phần dư rồi giữ tổng mỗi cặp lượt bằng bốn là chắc thắng.
Chiến lược đối xứng là gì?
Là cách người chơi đáp lại mỗi nước của đối thủ bằng một nước đối xứng qua một tâm hoặc trục, giữ cho trạng thái luôn cân bằng. Nó dùng được khi luật chơi và bàn chơi có tính đối xứng.
Lập luận ăn cắp chiến lược là gì?
Là cách chứng minh người đi trước có chiến lược thắng bằng phản chứng: nếu người đi sau có chiến lược thắng, người đi trước có thể bắt chước nó với một nước đi thừa vô hại, dẫn tới vô lý. Lập luận chỉ chứng minh sự tồn tại, không chỉ ra chiến lược cụ thể.
Bài toán trò chơi thuộc mảng nào trong thi học sinh giỏi?
Bài toán trò chơi thuộc mảng tổ hợp. Nó thường kết hợp với bất biến, đồng dư và tính đối xứng, và là dạng bài kiểm tra tốt khả năng suy luận.
