Tài liệu MỘT SỐ BÀI TOÁN TRÒ CHƠI CÓ NỘI DUNG TOÁN HỌC

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN *** ĐOÀN VĂN LỚI MỘT SỐ BÀI TOÁN TRÕ CHƠI CÓ NỘI DUNG TOÁN HỌC LUẬN VĂN THẠC SỸ KHOA HỌC Hà Nội , Năm 2012 1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN *** ĐOÀN VĂN LỚI MỘT SỐ BÀI TOÁN TRÕ CHƠI CÓ NỘI DUNG TOÁN HỌC Chuyên ngành : Phương pháp toán sơ cấp Mã số : 60 46 40 LUẬN VĂN THẠC SỸ KHOA HỌC Người hướng dẫn khoa học : PGS.TS Tạ Duy Phượng Hà Nội , Năm 2012 2 MỤC LỤC Trang Mục lục……………………………………………………………... 1 Lời nói đầu…………………………………………………………. 2 Chƣơng 1 Giải một số bài toán trò chơi nhờ công cụ hệ đếm cơ số 2……......................................................................................…… 4 §1 Hệ đếm cơ số 2 …………………….......................................…... 4 §2 Máy đọc ý nghĩ.............................................................................. 6 §3 Trò chơi Nim.................................................................................. 7 §4 Giải bài toán Tháp Hà Nội nhờ hệ đếm cơ số 2 ............................ 21 Chƣơng 2 Giải một số bài toán trò chơi cơ học nhờ công cụ mã Gray cơ số 2……............................................................................... 31 §1 Mã Gray cơ số 2 ………........................................……………… 31 §2 Mã Gray, trò chơi Tháp Hà Nội và trò chơi Hamilton trên đa 41 diện đều............................................................................................... §3 Baguenaudier hay trò chơi tháo vòng Trung Hoa…..…………… 48 Chƣơng 3 Một số ví dụ toán trò chơi........................................... 66 Kết luận…………………………………………………………… 74 Tài liệu tham khảo………………………………………………… 75 3 LỜI NÓI ĐẦU Trò chơi và lí thuyết trò chơi có lịch sử phát triển lâu đời. Nó được nhiều nhà toán học nổi tiếng (L. Euler, U. Hamilton, E. Lucas,...) nghiên cứu và làm phong phú nội dung. Nó cũng được nhiều chuyên gia về trò chơi toán học (E. Lucas, H. E. Dudeney, W. W. Rouse Ball, M. Gardner,...) phổ biến rộng rãi. Nhiều lĩnh vực của toán học (Lí thuyết tập hợp, lí thuyết đồ thị, toán tổ hợp, hệ đếm, tối ưu,...) được phát triển gắn liền với lí thuyết trò chơi, đồng thời toán học cũng là những công cụ hữu hiệu để giải quyết nhiều bài toán trò chơi. Với sự phát triển của công nghệ thông tin, các bài toán trò chơi thu hút sự quan tâm đặc biệt của các chuyên gia toán-tin học, nhiều bài toán trò chơi được giải nhờ công cụ máy tính, đồng thời các bài toán trò chơi cũng là những thí dụ minh họa tốt trong xây dựng thuật toán và kĩ thuật lập trình. Vào những năm 50 của thế kỉ trước, với đóng góp của các nhà toán học lớn (Von Neuman, J. F. Nash, R. Isaacs, L. S. Pontriagin, N. Krasovskii,...), lí thuyết trò chơi đã phát triển thành một ngành toán học độc lập và có nhiều ứng dụng trong thực tế (kinh tế, quân sự, công nghệ,...). Nhiều nhà toán học đã được giải thưởng Nobel vì những đóng góp vào lí thuyết trò chơi và ứng dụng lí thuyết này trong kinh tế. Có khá nhiều sách tiếng nước ngoài (tiếng Anh, tiếng Nga, tiếng Pháp,...) viết về các trò chơi có nội dung toán học. Tuy nhiên, các sách về toán trò chơi ở Việt Nam nói chung còn rất ít, đặc biệt là những tài liệu đi sâu tìm hiểu nội dung toán học của các bài toán trò chơi. Luận văn Một số bài toán trò chơi có nội dung toán học có mục đích trình bày một số bài toán trò chơi có lời giải sử dụng các công cụ toán học, chủ yếu là sử dụng hệ đếm cơ số 2 và mã Gray cơ số 2. Luận văn gồm Phần mở đầu, ba Chương chính và Tài liệu tham khảo. Chương 1 trình bày lời giải một số bài toán trò chơi nhờ công cụ hệ đếm cơ số 2. Chương 2 trình bày lời giải một số bài toán trò chơi nhờ mã Gray cơ số 2. 4 Chương 3 tập hợp một số ví dụ trong các dạng toán trò chơi. Lý thuyết trò chơi có cơ sở toán học sâu sắc. Nó liên quan đến nhiều kiến thức của các lí thuyết toán học như lí thuyết đồ thị (đồ thị liên thông, đường đi đóng trên đồ thị,...), mô hình cây, không gian trạng thái, lí thuyết tối ưu, độ phức tạp tính toán,... Chúng tôi không có tham vọng trình bày đầy đủ các kiến thức sâu sắc ấy của lí thuyết trò chơi hay các lí thuyết toán học liên quan ngay cả trong các trò chơi xét trong khuôn khổ luận văn này, mà chúng tối chỉ cố gắng mô tả lịch sử trò chơi và trình bày lời giải chúng nhờ công cụ hệ đếm cơ số 2. Luận văn được hoàn thành dưới sự hướng dẫn tận tình của PGS.TS Tạ Duy Phượng, Viện Toán học. Em xin bày tỏ lòng biết ơn sâu sắc nhất đối với Thầy và xin được cám ơn Thầy đã cung cấp nhiều tài liệu đồng thời cho phép sử dụng bản thảo các cuốn sách của Thầy về toán Trò chơi. Tôi xin được cảm ơn khoa Toán, khoa Sau Đại học trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội đã quan tâm giúp đỡ, tạo điều kiện thuận lợi cho tôi thực hiện kế hoạch học tập. Xin được cảm ơn người thân, đồng nghiệp, bạn bè đã cổ vũ động viên tôi trong suốt quá trình học cao học và làm luận văn. Hà Nội, 31.12.2011 Đoàn Văn Lới 5 Chƣơng 1 GIẢI MỘT SỐ BÀI TOÁN TRÕ CHƠI NHỜ CÔNG CỤ HỆ ĐẾM CƠ SỐ 2 §1 Hệ đếm cơ số 2 Cho p là một số tự nhiên bất kì. Theo thuật toán chia Euclid, mọi số tự nhiên a đều có thể biểu diễn duy nhất dưới dạng a  ak p k  ak 1 p k 1  ...  a1 p  a0 p 0 với các hệ số nguyên 0  ai  p  1, i  0,..., k ; ak  0. Như vậy, nếu chọn p làm cơ số của hệ đếm, thì mọi số tự nhiên a có thể biểu diễn dưới dạng  ak ak 1a1a0  p trong hệ đếm cơ số p . Nếu p  10 thì ta có hệ đếm cơ số 10. Do thói quen, lịch sử, truyền thống và thuận tiện, hệ đếm cơ số 10 được sử dụng rộng rãi trong cuộc sống hiện đại. Hệ đếm được định nghĩa như trên là hệ đếm theo vị trí, tức là mỗi hệ số ai (được gọi là các chữ số của a ) ở vị trí khác nhau có giá trị khác nhau (hàng “đơn vị”, “hàng chục”, “hàng trăm”,...). Bằng cách chia cho 2, một số tự nhiên bất kì đều có thể biểu diễn dưới dạng tổng các lũy thừa của 2 với các hệ số bằng 1 hoặc bằng 0. Thí dụ, 2011  210  29  28  27  26  24  23  21  20 . Như vậy, nếu chọn 2 làm cơ số trong hệ đếm cơ số 2, thì mọi số tự nhiên đều có một biểu diễn duy nhất trong hệ đếm cơ số 2. Các chữ số của nó (chỉ có thể bằng 0 hoặc bằng 1) chính là các hệ số trong phân tích số đã cho dưới dạng lũy thừa của 2. Thí dụ, ta có, 201110 = 111110110112 =111110110112 . Hệ đếm cơ số 2 được sử dụng từ thời cổ đại, thí dụ, Kinh Dịch (Trung Hoa. Hơn 2000 năm trước công nguyên) được xây dựng dựa trên hai gạch (hai kí hiệu), 6 một gạch ngắn và một gạch dài, tương ứng với chữ số 0 và chữ số 1 trong hệ đếm cơ số 2. Dưới đây là quan hệ giữa Kinh Dịch và hệ đếm cơ số 2 (trong cuốn sách của E. Lucas, xem [13], trang 174) Mặc dầu vậy, chỉ với nhà toán học vĩ đại người Đức Leibnitz, hệ đếm cơ số 2 mới được xây dựng một cách hoàn chỉnh. Leibnitz nhìn thấy trong hệ đếm cơ số 2 biểu hiện của chân lí siêu hình sâu sắc. Số 0 đối với Leibnitz là biểu tượng của sự không tồn tại, trống rỗng, còn số 1 là biểu tượng của tồn tại hay vật chất. Ông coi số 0 cũng quan trọng và cần thiết như số 1 đối với Đấng tạo hóa, bởi vì vũ trụ được tạo thành từ vật chất thuần túy không thể tách rời khỏi khoảng không trống rỗng, khoảng không này không bị nhiễu loạn bởi vũ trụ và được biểu tượng bởi số 0. Theo Leibnitz, mọi thứ trong thế giới được hình thành từ hai cực đối lập: tồn tại và không tồn tại, cũng như mọi số được biểu diễn trong cơ số 2 chỉ bởi các số 0 và 1. Từ thời Leibnitz cho mãi tới gần đây, người ta vẫn thường coi hệ đếm cơ số 2 chỉ là một thứ gì đó kì lạ và hấp dẫn, nhưng không có nhiều ý nghĩa thực tiễn. Chỉ khi xuất hiện máy tính điện tử, vai trò của hệ đếm cơ số 2 mới được xác lập. Rất nhiều bộ phận của máy tính điện tử làm việc theo nguyên lí “có-không” hay 7 “0-1”: Dòng điện hoặc là chạy theo dây dẫn, hoặc không; công tắc hoặc tắt, hoặc bật; cực của nam châm hoặc là bắc, hoặc là nam; một ô nhớ chỉ có thể ở một trong hai trạng thái chứa thông tin hoặc rỗng (không chứa thông tin). Điều này cho phép xây dựng các máy tính có khả năng xử lí các dữ liệu được mã hóa trong hệ đếm cơ số 2 với tốc độ cực nhanh và độ chính xác tuyệt đối. Nhiều trò chơi có thể giải nhờ công cụ hệ đếm cơ số 2: trò chơi với “máy đọc ý nghĩ”, trò chơi Nim, trò chơi Tháp Hà Nội,... Trong các bài, mục tiếp theo, ta sẽ mô tả các trò chơi này và giải chúng bằng công cụ hệ đếm cơ số 2. §2 Máy đọc ý nghĩ Xét trò chơi được trang bị một “máy đọc ý nghĩ”, tức là ta có một (một số) bảng lập sẵn, đóng vai trò như các máy phiên dịch các số trong hệ đếm cơ số 10 sang hệ đếm cơ số 2. Nhờ đó mà ta có thể “đọc” được người đối diện đã nghĩ số nào. Thí dụ 2.1 Giả sử bạn chọn một số bất kì trong khoảng từ 1 đến 1000. Tôi sẽ hỏi bạn 10 câu hỏi, bạn có quyền trả lời “đúng” hoặc “sai”. Dựa trên 10 câu trả lời của bạn, tôi sẽ khẳng định được bạn đã chọn số nào. Tại sao? Giải Các câu hỏi lần lượt như sau. Câu thứ nhất: Lấy số đã chọn chia cho 2. Hỏi phép chia có dư hay không? Nếu bạn trả lời là “không” thì tôi viết số 0, còn nếu câu trả lời là “có” thì tôi viết chữ số 1. Câu thứ hai: Lấy thương của phép chia vừa rồi chia cho 2. Hỏi phép chia có dư hay không? Nếu câu trả lời là “không” thì tôi viết số 0, còn nếu câu trả lời là “có” thì tôi viết chữ số 1 vào phía trước (về bên trái) số đã viết (chữ số 0 hoặc chữ số 1) của câu trả lời thứ nhất. Các câu hỏi tiếp theo cũng tương tự: Lấy thương của phép chia vừa xong chia cho 2. Hỏi phép chia có dư không? 8 Nếu câu trả lời là “không” thì viết chữ số 0, còn nếu câu trả lời là “có” thì viết chữ số 1 trước số đã viết. Sau 10 lần trả lời, ta nhận được 10 chữ số chỉ gồm các chữ số 0 và 1, chữ số đầu tiên bao giờ cũng là chữ số 1. Như vậy, hệ thống 10 câu hỏi trên chính là cách chuyển biểu diễn của một số đã cho (dưới 1000) từ hệ đếm cơ số 10 sang hệ đếm cơ số 2. Hơn nữa, 10 câu hỏi là đủ, bởi vì mọi số từ 0 đến 1000 đều có thể viết được dưới dạng một số trong hệ đếm cơ số 2 với không quá 10 chữ số ( 210  1024  100000000002 ). Vì số ban đầu chưa biết nên bây giờ chỉ cần chuyển số nhận được trong hệ đếm cơ số 2 sang hệ đếm cơ số 10, ta khôi phục được số ban đầu. Thí dụ, sau 10 lần trả lời, ta nhận được số 1010011010. Đổi số này từ hệ đếm cơ số 2 sang hệ đếm cơ số 10 theo định nghĩa ta được 1010011010 2  667 . Vậy số ban đầu bạn chọn là 667. Kiểm tra lại: 667=333  2+1=(166  2+1)  2+1=((83  2)  2+1)  2+1 =(((41  2+1)  2)  2+1)  2+1=((((20  2+1)  2+1)  2)  2+1)  2+1 =(((((10  2)  2+1)  2+1)  2)  2+1)  2+1 =(((((5  2)  2+1)  2+1)  2)  2+1)  2+1 =((((((2  2+1)  2)  2+1)  2+1)  2)  2+1)  2+1 =(((((((1  2)  2+1)  2)  2+1)  2+1)  2)  2+1)  2+1 =29+27+24+23+2+1=(1010011010)2. §3 Trò chơi Nim 3.1 Giới thiệu trò chơi Nim Người Trung Quốc thời xưa có trò chơi gọi là trò chơi Nim. Nội dung của trò chơi này như sau: Có ba đống sỏi, hai người chơi lần lượt lấy một số sỏi bất kì (khác 0) từ một trong ba đống đó (và mỗi lần chơi chỉ lấy sỏi từ một đống). Ai là người nhặt viên sỏi cuối cùng thì người đó thắng. Có hay không một chiến lược chơi để người đi trước thắng? 9 Giải Các viên sỏi cũng có thể được thay thế bởi các đồ vật khác, thí dụ, trẻ em thường dùng các que diêm hoặc các mảnh bìa, vì vậy trò chơi này cũng được gọi là trò chơi ăn diêm. Người lớn thường dùng các đồng tiền xu đặt lên trên bàn các quầy bar. Dạng phổ biến nhất của trò chơi Nim là trò chơi gồm 12 đồng xu đặt thành ba hàng với 3, 4, 5 đồng xu Hình 3.1 trong mỗi hàng (Hình 3.1). Qui tắc chơi của trò chơi Nim rất đơn giản: Hai người chơi lần lượt nhặt các đồng xu (ít nhất một đồng) chỉ từ một hàng nào đó. Người nào nhặt đồng xu cuối cùng thì người đó thắng. Cũng có thể nêu qui tắc ngược lại: ai phải nhặt đồng xu cuối cùng thì người đó thua. Ta có một số nhận xét đơn giản nhưng rất cơ bản sau đây. Nhận xét 1 Nếu sau một số lượt đi, chỉ còn lại hai hàng với số đồng xu bằng nhau và đến lượt người chơi thứ hai thì người chơi thứ nhất thắng (trong trò chơi với qui tắc người nhặt đồng xu cuối cùng là người thắng). Chứng minh Vì số đồng xu trong hai hàng như nhau nên đến lượt người chơi thứ hai, anh ta phải lấy một số đồng xu từ một hàng, do đó số đồng xu trong hai hàng khác nhau. Nếu người thứ hai nhặt toàn bộ xu ở một hàng thì người thứ nhất cũng nhặt toàn bộ xu ở hàng còn lại và thắng. Nếu sau khi người thứ hai đi mà vẫn còn hai hàng thì người thứ nhất chọn chiến lược: nhặt số đồng xu bằng chính số đồng xu mà người chơi thứ hai đã nhặt, nhưng ở hàng khác. Số đồng xu ở hai hàng lại bằng nhau. Cứ tiếp tục như vậy, đến khi còn lại mỗi hàng đúng một đồng xu. Người thứ hai buộc phải nhặt một đồng xu ở một hàng, người thứ nhất nhặt đồng xu cuối cùng ở hàng còn lại và thắng. 10 Hệ quả 1 Nếu sau một số bước, số đồng xu trong ba hàng chỉ còn lại là  a, b, c  với a  b và đến lượt người thứ hai thì người thứ hai thắng (theo qui tắc kết thúc trò chơi ai là người lấy viên bi cuối cùng người đó thắng). Chứng minh Người thứ hai chỉ việc lấy tất cả c đồng xu ở hàng thứ ba, còn lại hai hàng, mỗi hàng có số đồng xu bằng nhau. Theo nhận xét 1, đến lượt người chơi thứ nhất (đóng vai trò người chơi thứ hai trong Nhận xét 1) và do đó người chơi thứ hai (đóng vai trò người chơi thứ nhất trong Nhận xét 1) là người thắng. Nhận xét 2 Sau một số lượt đi, nếu chỉ còn lại hai hàng với số đồng xu bằng nhau và số đồng xu ở mỗi hàng lớn hơn 1, đến lượt người chơi thứ hai thì người chơi thứ nhất thắng (trong qui tắc người nhặt đồng xu cuối cùng là người thua). Chứng minh Trước tiên ta thấy rằng, nếu còn hai hàng với chỉ một đồng xu ở mỗi hàng và đến lượt người chơi thứ hai thì người chơi thứ nhất thua (theo qui tắc người nào nhặt đồng xu cuối cùng là thua). Vì chỉ có hai hàng và số đồng xu trong hai hàng như nhau nên đến lượt người chơi thứ hai, anh ta phải lấy một số đồng xu từ một hàng, do đó sau khi anh ta đi xong thì số đồng xu trong hai hàng là khác nhau. Trƣờng hợp 1 Nếu người chơi thứ hai nhặt toàn bộ xu ở một hàng thì chỉ còn lại một hàng có nhiều hơn 1 đồng xu. Đến lượt mình, người chơi thứ nhất nhặt tất cả các xu, chỉ để lại một đồng. Người chơi thứ hai buộc phải nhặt đồng xu cuối cùng và thua. Trƣờng hợp 2 Nếu sau khi người chơi thứ hai đi mà vẫn còn hai hàng và số đồng xu trong một hàng bằng 1 (tức là người chơi thứ hai đã nhặt toàn bộ số đồng xu từ một hàng, chỉ để lại một đồng xu trong hàng đó) thì người chơi thứ nhất nhặt toàn bộ số đồng xu của hàng kia. Như vậy, chỉ còn lại một đồng xu cuối cùng. Người chơi thứ hai buộc phải nhặt đồng xu cuối cùng và thua. Trƣờng hợp 3 Nếu sau khi người chơi thứ hai đi mà vẫn còn hai hàng và số đồng xu trong cả hai hàng lớn hơn 1 thì người chơi thứ nhất nhặt số đồng xu 11 bằng chính số đồng xu mà người chơi thứ hai đã nhặt, nhưng ở hàng khác. Như vậy, số đồng xu ở hai hàng lại bằng nhau và lớn hơn 1. Cứ tiếp tục như vậy, đến khi chỉ còn một hàng có số đồng xu lớn hơn 2 (trở về Trường hợp 1) hoặc còn cả hai hàng nhưng một hàng còn lại đúng một đồng xu (trở về Trường hợp 2). Người chơi thứ nhất áp dụng chiến lược như trong trường hợp 1 hoặc trong trường hợp 2. Người chơi thứ hai buộc phải nhặt nốt đồng xu cuối cùng và thua. Hệ quả 2 Nếu sau một số bước, số đồng xu trong ba hàng chỉ còn lại là  a, b, c  với a  b  1 và đến lượt người chơi thứ hai thì người chơi thứ hai thắng (theo qui tắc kết thúc trò chơi ai là người lấy viên bi cuối cùng người đó thua). Chứng minh Người chơi thứ hai chỉ việc lấy tất cả c đồng xu ở hàng thứ ba, còn lại hai hàng, mỗi hàng có số đồng xu bằng nhau. Theo nhận xét 2, đến lượt người chơi thứ nhất (đóng vai trò người chơi thứ hai trong Nhận xét 1) và người chơi thứ hai (đóng vai trò người chơi thứ nhất trong Nhận xét 1) thắng. Nhận xét 3 Giả sử sau một số bước, số đồng xu trong ba hàng chỉ còn lại tương ứng là 1, 2, và 3. Nếu đến lượt người chơi thứ hai thì người chơi thứ nhất thắng (theo qui tắc kết thúc trò chơi ai là người lấy viên bi cuối cùng người đó thắng). Chứng minh Nếu người thứ hai lấy tất cả các đồng xu ở một hàng thì còn lại hai hàng với số đồng xu không bằng nhau. Đến lượt mình, người chơi thứ nhất đưa về thế thắng bằng cách nhặt số đồng xu ở hàng có số đồng xu lớn hơn sao cho hai hàng có số đồng xu bằng nhau. Áp dụng Nhận xét 1, người chơi thứ nhất thắng. Vì vậy người chơi thứ hai chỉ có thể lấy 1 đồng xu ở hàng thứ hai hoặc 1 (hoặc 2) đồng xu ở hàng thứ ba. Gọi khả năng có thể của số đồng xu tại một bước nào đó là một trạng thái  a; b; c  của trò chơi. Trạng thái tương ứng của trò chơi sau bước đi của người chơi thứ hai chỉ có thể là: (1; 1; 3), khi người chơi thứ hai lấy 1 đồng xu ở hàng thứ hai; (1; 2; 2), khi người chơi thứ hai lấy 1 đồng xu ở hàng thứ ba hoặc (1; 2; 1), khi người chơi thứ hai lấy 2 đồng xu ở hàng thứ ba, nghĩa là luôn có ba hàng với hai hàng có số đồng xu bằng nhau. 12 Người chơi thứ nhất chỉ việc lấy tất cả số đồng xu ở một hàng và để lại hai hàng có số đồng xu bằng nhau. Theo Nhận xét 1, người chơi thứ nhất thắng. Nhận xét 4 Nếu trò chơi ở trạng thái phổ biến (3, 4, 5), nghĩa là ba hàng tương ứng có 3, 4, 5 đồng xu, và đến lượt người chơi thứ nhất thì người đi trước thắng (theo qui tắc kết thúc trò chơi ai là người lấy viên bi cuối cùng người đó thắng). Chứng minh Trước tiên người chơi thứ nhất nhặt hai đồng xu ở hàng đầu tiên, đưa trò chơi về trạng thái (1, 4, 5) với số đồng xu ở các hàng không bằng nhau. Nếu người chơi thứ hai lấy tất cả số đồng xu ở một hàng thì số đồng xu còn lại ở hai hàng không bằng nhau. Theo Nhận xét 1, người chơi thứ nhất chỉ việc đưa về trạng thái thắng bằng cách làm cho số đồng xu ở hai hàng bằng nhau. Vì vậy người chơi thứ hai phải giữ lại cả ba hàng (với hi vọng không thua). Theo Nhận xét 1 và Hệ quả 1, các trạng thái sau đây là trạng thái thua của người chơi thứ hai: (1; 1; 5); (1; 4; 1); (1; 4; 4). Vì vậy, người chơi thứ hai chỉ có thể: 1) Lấy 1 hoặc 2 đồng xu ở hàng thứ hai. Đưa trò chơi về một trong hai trạng thái: (1; 3; 5) hoặc (1; 2; 5). 2) Lấy 2 hoặc 3 đồng xu ở hàng thứ ba. Đưa trò chơi về trạng thái (1; 4; 3) hoặc trạng thái (1; 4; 2). Đến lượt người chơi thứ nhất lấy số đồng xu ở các hàng tương ứng để đưa trò chơi về trạng thái (1; 2; 3) tương ứng như sau: 1.1) (1; 3; 5)  (1; 3; 2) 2.1) (1;4;3)  (1; 2; 3) 1.2) (1; 2; 5)  (1; 2; 3) 2.2) (1;4;2)  (1; 3; 2) Theo Nhận xét 3, người chơi thứ nhất thắng trong mọi trường hợp. 3.2 Giải bài toán trò chơi Nim bằng công cụ hệ đếm cơ số 2 Dưới đây trình bày lời giải của trò chơi Nim với ba đống sỏi và số sỏi bất kì trong mỗi đống nhờ công cụ hệ đếm cơ số 2. 13 Giả sử số sỏi trong các đống thứ nhất, thứ hai và thứ ba tương ứng là a , b và c viên. Trong hệ đếm cơ số 2, các số này được biểu diễn dưới dạng a  an .2n  an1.2n1  ...  a1.2  a0   anan1...a1a0 2 ; b  bn .2n  bn1.2n1  ...  b1.2  b0   bnbn1...b1b0 2 ; c  cn .2n  cn1.2n1  ...  c1.2  c0   cncn1...c1c0 2 . Các hệ số ai , bi , ci , i  0,..., n có giá trị 0 hoặc 1. Ở đây, để tiện trình bày, ta đã viết biểu diễn của a , b và c cùng có bậc cao nhất là 2n . Điều này dễ dàng làm được vì nếu cần ta có thể thêm các hệ số bằng 0, tức là ta không đòi hỏi tất cả các hệ số an , bn , cn phải khác 0, nhưng vì n là bậc cao nhất nên ít nhất một trong các hệ số an , bn , cn phải khác 0. Người chơi đầu tiên sẽ lấy một số sỏi (khác 0) từ một trong ba đống, thí dụ, từ đống thứ nhất. Khi ấy các hệ số ai , i  0,..., n sẽ bị thay đổi. Tương tự, nếu lấy sỏi từ đống thứ hai (hoặc từ đống thứ ba), thì ít nhất một trong các hệ số bi , i  0,..., n (hoặc ci , i  0,..., n ) của b ( hoặc c ) sẽ bị thay đổi. Xét các tổng an  bn  cn , an1  bn1  cn1 ,…, a1  b1  c1 , a0  b0  c0 . Vì các hệ số ai , bi , ci , i  0,..., n chỉ nhận giá trị 0 hoặc 1 nên mỗi tổng này chỉ có thể nhận một trong bốn giá trị 0,1, 2, 3 . Nếu một trong các tổng trên là số lẻ (tức là tổng nhận giá trị 1 hoặc 3) thì người chơi thứ nhất có thể thắng nhờ chiến lược sau: Tại mỗi bước đi, người chơi thứ nhất sẽ lấy đi một số sỏi từ một đống để được tất cả các tổng ai  bi  ci , i  0,..., n là chẵn. Chiến lược này có thể thực hiện được nhờ cách đi như sau. Giả sử ak  bk  ck là tổng đầu tiên (tính từ trái sang phải) là lẻ, tức là có ít nhất một trong ba số ak , bk , ck bằng 1. Giả sử, thí dụ, ak  1 . Khi ấy người chơi thứ nhất lấy một lượng sỏi d từ đống thứ nhất sao cho tất cả các tổng ai  bi  ci , 14 i  0,..., n là chẵn. Để làm việc này chỉ cần lấy d viên sỏi sao cho số sỏi còn lại từ đống thứ nhất sẽ là a  anan1...ak 1 0ak 1...a1a0 , trong đó ai  ai nếu ai  bi  ci , i 0,..., k  1 là chẵn (khi ấy ai  bi  ci  ai  bi  ci vẫn là chẵn) và ai  1  ai nếu ai  bi  ci là lẻ (khi ấy ai  bi  ci  1  ai   bi  ci  ai  bi  ci  1  2ai là chẵn). Do các hệ số an , an1,..., ak 1 của a và a bằng nhau, còn hệ số ak của a bằng 1, mà hệ số ak của a bằng 0 nên a  a ' và d  a  a  0 , tức là người chơi thứ nhất có thể làm giảm thật sự số sỏi (trong đống a ) nhờ qui tắc trên. Như vậy, sau bước đi đầu tiên của người chơi thứ nhất, tất cả các tổng ai  bi  ci , i  0,..., n là chẵn. Bây giờ giả sử người chơi thứ hai lấy một số sỏi bất kì, thí dụ, d  viên từ một đống nào đó. Vì d  khác 0 nên trong biểu diễn của d  trong hệ đếm cơ số 2 phải có ít nhất một chữ số 1, do đó bắt buộc ít nhất một trong các tổng ai  bi  ci phải thay đổi từ chẵn sang lẻ. Tiếp tục cách làm trên, sau một số hữu hạn q bước, tất cả các tổng ai  bi  ci , i  0,..., n phải bằng 0 (vì tổng số sỏi giảm thực sự sau mỗi bước), tức là không còn viên sỏi nào sau bước đi thứ q  1 của người thứ nhất, và anh ta thắng. Nếu ban đầu tất cả các tổng ai  bi  ci , i  0,..., n là chẵn, thì sau lần đi đầu tiên của người thứ nhất, cho dù anh ta lấy đi bao nhiêu sỏi từ một đống bất kì nào đó, thì có ít nhất một tổng ai  bi  ci bắt buộc phải lẻ, vì vậy, đến lượt người chơi thứ hai, anh ta sẽ sử dụng chiến lược như người chơi thứ nhất thực hiện khi số sỏi ban đầu là lẻ (như chiến lược đã trình bày ở trên) và anh ta sẽ thắng. Tùy theo số sỏi cụ thể trong từng đống, mỗi người chơi có thể chọn số lượng sỏi trong mỗi bước đi để đảm bảo thắng nhanh nhất hoặc lâu thua nhất. Thí dụ 3.1 Giả sử người chơi thứ nhất biết chiến lược để thắng. Hãy thực hiện chiến lược trong trò chơi Nim với a  15 , b  12 , c  10 . Giải Ta có 15 a  15  23  22  2  1  11112   a3a2a1a0 2 ; b  12  23  22  11002   b3b2b1b0 2 ; c  10  23  2  1010 2   c3c2c1c0 2 . Tổng các hệ số: a3  b3  c3  3 ; a2  b2  c2  2 ; a1  b1  c1  2 ; a0  b0  c0  1. Lượt đi thứ nhất: Ta có a3  b3  c3  3 là tổng lẻ đầu tiên. Vì a3  1 nên người chơi thứ nhất sẽ lấy d viên sỏi từ đống thứ nhất sao cho số sỏi còn lại là a  01102  6 (qui tắc: thay a3  1 thành a3  0 ; a2  a1  1 giữ nguyên do a2  b2  c2  2 ; a1  b1  c1  2 là các tổng chẵn; vì a0  b0  c0  1 là tổng lẻ nên thay a0  1 thành a0  0 ). Nghĩa là, người chơi thứ nhất muốn thắng thìphải lấy d1  a  a  11112  01102  10012  9 viên sỏi. Số sỏi còn lại ở các đống là: a  6   0110 2 ; b  12  11002   b3b2b1b0 2 ; c  10  10102   c3c2c1c0 2 . Bây giờ ta có a3  b3  c3  2 ; a2  b2  c2  2 ; a1  b1  c1  2 ; a0  b0  c0  0 . Số sỏi trong tất cả các đống đều chẵn. Người chơi thứ hai, dù biết hay không biết chiến lược, cũng phải chọn một số sỏi từ một đống nào đó. Để thua lâu nhất, người chơi thứ hai chỉ lấy một viên sỏi từ một đống nào đó, thí dụ lấy d1  1   00012 từ đống thứ hai. Đống thứ hai còn lại 11 viên sỏi. Số sỏi còn lại ở ba đống là: a  6   0110 2   a3a2a1a0 2 ; b  11  10112   b3b2b1b0 2 ; c  10  1010 2   c3c2c1c0 2 . Tổng các hệ số sau khi người chơi thứ hai đã đi là: a3  b3  c3  2 ; a2  b2  c2  1 ; a1  b1  c1  3 ; a0  b0  c0  1. Lượt đi thứ hai: Do a2  b2  c2  1 là tổng lẻ đầu tiên, a2  1 nên người chơi thứ nhất lấy từ đống thứ nhất d 2 viên sỏi sao cho số sỏi còn lại ở đống thứ nhất là 16 a   00012  1 viên (theo qui tắc “bù để tổng các cột đều chẵn” như trên), tức là chọn d2  a  a  6  1  5 viên. Số sỏi còn lại ở các đống là: a  6  5  1   00012 , b  11  10112   b3b2b1b0 2 , c  10  1010 2   c3c2c1c0 2 . Bây giờ ta lại có a3  b3  c3  2 ; a2  b2  c2  0 ; a1  b1  c1  2 ; a0  b0  c0  2 . Người chơi thứ hai buộc phải lấy ra số sỏi bất kì từ một đống bất kì, nhưng không thể để mình vào trạng thái thua  a; b; b  theo Hệ quả 1, vì vậy không thể chọn 1 viên ở đống thứ hai (khi ấy số sỏi ở hai đống thứ nhất và đống thứ hai cùng bằng 10), do đó anh ta phải chọn, thí dụ, 1 viên ở đống thứ ba, số sỏi còn lại ở ba đống là: a  1   00012   a3a2a1a0 2 ; b  11  10112   b3b2b1b0 2 , c  9  10012   c3c2c1c0 2 . Tổng các hệ số trong cơ số 2 ở mỗi cột sau khi người chơi thứ hai đã đi là: a3  b3  c3  2 ; a2  b2  c2  0 ; a1  b1  c1  1 ; a0  b0  c0  3 . Lượt đi thứ ba: Vì a1  b1  c1  1 , a1  0 , b1  1 , nên người chơi thứ nhất lấy (theo qui tắc “bù thành chẵn”) từ đống thứ hai d 3 viên sỏi sao cho số sỏi còn lại ở đống thứ hai là b  10002  8 viên, tức là lấy ra d3  b  b  11  8  3 viên. Số sỏi còn lại ở các đống bây giờ là: a  1   00012   a3a2a1a0 2 , b  8  10002   b3b2b1b0 2 , c  9  10012   c3c2c1c0 2 . Bây giờ ta lại có a3  b3  c3  2 ; a2  b2  c2  0 ; a1  b1  c1  0 ; a0  b0  c0  2 . Người chơi thứ hai chọn số sỏi bất kì, nhưng không thể đưa về trạng thái thua  a; b; b  theo Hệ quả 1, vì vậy phải chọn, thí dụ, 2 viên từ đống thứ ba, số sỏi còn lại ở ba đống là: a  1   00012   a3a2a1a0 2 , b  8  10002   b3b2b1b0 2 , c  7   01112   c3c2c1c0 2 . 17 Tổng các hệ số: a3  b3  c3  1; a2  b2  c2  1 ; a1  b1  c1  1 ; a0  b0  c0  2 . Lượt đi thứ tư: Do a3  b3  c3  1, a3  0 , b3  1 , nên người chơi thứ nhất chọn d 4 viên sỏi từ đống thứ hai (theo qui tắc “bù chẵn”) sao cho số sỏi còn lại ở đống thứ hai là b   0110 2  6 viên, tức là d2  c  c  8  6  2 viên. Số sỏi còn lại ở các đống là: a  1   0012   a2a1a0 2 , b  6  110 2   b2b1b0 2 , c  7  1112   c2c1c0 2 . Bây giờ ta lại có: a2  b2  c2  2 ; a1  b1  c1  2 ; a0  b0  c0  2 . Người chơi thứ hai chỉ có thể chọn, để không rơi vào trạng thái thua  a; b; b  hoặc để thua lâu hơn, thí dụ, 2 viên từ đống thứ ba, số sỏi còn lại ở ba đống là: a  1   0012   a2a1a0 2 , b  6  110 2   b2b1b0 2 , c  5  1012   c2c1c0 2 . Tổng các hệ số: a2  b2  c2  2 ; a1  b1  c1  1 ; a0  b0  c0  2 . Lượt đi thứ năm: Do a1  b1  c1  1 , a1  0 và b1  1 nên người chơi thứ nhất chọn d 5 (theo qui tắc “bù chẵn”) viên sỏi từ đống thứ hai sao cho số sỏi còn lại ở đống thứ hai là b  100 2  4 viên, tức là d2  b  b  6  4  2 viên. Số sỏi còn lại ở ba đống là: a  1   0012   a2a1a0 2 , b  4  1002   b2b1b0 2 , c  5  1012   c2c1c0 2 . Trò chơi trở về trạng thái (1; 4; 5) và đến lượt người thứ hai. Theo Chứng minh trong Nhận xét 4, người chơi thứ nhất thắng. Lời bình 1 Người chơi thứ hai có thể chọn nhiều cách đi. Tuy nhiên, như ta đã phân tích, nếu lúc đầu có ít nhất một tổng ak  bk  ck là lẻ thì với mỗi cách đi của người thứ hai, người chơi thứ nhất bao giờ cũng chọn được ít nhất một cách đi tương ứng để sau khi đi thì tất cả các tổng ai  bi  ci , i  0,..., n là chẵn, và cuối cùng anh ta sẽ thắng. Tương tự, nếu tất cả các tổng ai  bi  ci , i  0,..., n là chẵn thì người thứ hai sẽ thắng (theo qui tắc ai nhặt viên sỏi cuối cùng thì người đó thắng). Người thứ hai 18 chỉ thắng (trong trò chơi với qui tắc ai nhặt viên sỏi cuối cùng là người thắng) khi tất cả các tổng ai  bi  ci , i  0,..., n là chẵn. Khả năng thắng của người chơi thứ hai ít hơn nhiều so với người chơi thứ nhất (vì người thứ nhất chỉ cần một trong các tổng ai  bi  ci , i  0,..., n là lẻ). Thí dụ, với 10 viên sỏi chia làm ba đống a  b  c  10 thì có tất cả 8 khả năng viết số 10=(1010)2 dưới dạng tổng của ba số dương khác 0: 1) 10=1+1+8=(0001)2+(0001)2+(1000)2; 2) 10=1+2+7=(0001)2+(0010)2+(0111)2; 3) 10=1+3+6=(0001)2+(0011)2+(0110)2; 4) 10=1+4+5=(0001)2+(0100)2+(0101)2; 5) 10=2+2+6=(0010)2+(0010)2+(0110)2; 6) 10=2+3+5=(0010)2+(0011)2+(0101)2; 7) 10=2+4+4=(0010)2+(0100)2+(0100)2; 8) 10=3+3+4=(0011)2+(0011)2+(0100)2. Trong 8 cách này, chỉ có duy nhất một cách (cách 4) trong đó tất cả các tổng ai  bi  ci , i  0,2,3,4 là chẵn: 10=1+4+5=(0001)2+(0100)2+(0101)2. Tất nhiên, trò chơi chỉ thú vị khi ít nhất một trong hai người chơi không biết toán (biết suy luận như trên), nói cách khác, biết toán sẽ bảo đảm biết chắc thắng hay chắc thua. Nếu cả hai người chơi đều đã biết thuật toán như trên thì trò chơi mất thú vị, vì chỉ cần tính các tổng ai  bi  ci , i  1,2,..., n là biết ai sẽ thắng. Lời bình 2 Cũng có thể giải bài toán trò chơi Nim bằng phương pháp đồ thị (xem [6]). 3.3 Trò chơi Nim mở rộng Ở trên ta đã xét trò chơi Nim với ba đóng sỏi (ba hàng các đồng xu). Phân tích trò chơi này cho ta cảm giác không còn gì đáng hấp dẫn về trò chơi Nim nữa. Tuy nhiên, năm 1901, Charles L. Burton, Giáo sư trường đại học Harvard, đã phát hiện ra một điều đáng ngạc nhiên: Trò chơi Nim sẽ trở nên thú vị hơn, nếu 19 số đống sỏi (số hàng các đồng xu, các quân bài) có thể bất kì và đồng thời số sỏi trong mỗi đống cũng bất kì. Hơn nữa, sử dụng hệ đếm cơ số 2, có thể đưa ra một chiến lược đơn giản tương tự như trong trò chơi Nim với ba đống sỏi (như đã trình bày ở trên) để giải quyết bài toán trò chơi này. Charles L. Burton đã phân tích chứng minh sự tồn tại chiến lược tối ưu cho trò chơi Nim tổng quát. Trò chơi Nim mở rộng được phát biểu như sau. Giả sử có n hàng, lúc đầu mỗi hàng có một số đồng xu. Hai người lần lượt lấy ra từ một hàng một số (không ít hơn 1) đồng xu. Người chiến thắng là người nhặt được đồng xu cuối cùng. Gọi mỗi vectơ (bộ số sắp thứ tự)  x1,..., xn  , trong đó xi là số đồng xu (còn lại) của hàng thứ i , i  1,2,.., n tại bước thứ k nào đó, là một trạng thái của trò chơi. Trạng thái của trò chơi được hình thành sau bước đi của người chơi là an toàn, nếu nó bảo đảm cho người chơi đi đến chiến thắng. Nếu ngược lại thì trạng thái được gọi là nguy hiểm. Thí dụ, từ trạng thái (3; 4; 5) ban đầu, người chơi thứ nhất lấy ra 2 đồng xu ở hàng thứ nhất, tạo ra trạng thái (1; 4; 5) an toàn cho mình. Trong trò chơi Nim, bằng một chiến lược thích hợp, từ mỗi trạng thái nguy hiểm (cho đối phương) đều có thể đi đến trạng thái an toàn (cho mình). Ngược lại, từ một trạng thái an toàn (của đối phương) đều chỉ có thể đi đến trạng thái nguy hiểm (cho mình), không có chiến lược nào đưa một trạng thái an toàn (của đối phương) đến trạng thái an toàn (cho mình) cho mình cả. Vì vậy, các chiến lược thích hợp là đưa trạng thái nguy hiểm (cho đối phương) về trạng thái an toàn (cho mình), hoặc tìm chiến lược để kéo dài cuộc chơi được lâu nhất (nếu đối phương đã ở vào trạng thái an toàn nên tình thế không thể đảo ngược). Thí dụ 3.2 Có 16 quân bài được đặt thành bốn hàng như hình vẽ dưới đây. Hãy phân tích và tìm chiến lược chơi để chiến thắng (nhặt quân bài cuối cùng). Giải Viết số quân bài tại mỗi hàng trong hệ đếm cơ số 2 và tính tổng từng cột: 1= 0 0 1 3= 0 1 1 20