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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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.2011 Đoàn Văn Lới 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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,.
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. 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 = 111110110112 =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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com “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.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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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. 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).