nhoc_ngoc1909
New Member
Luận văn: Một số bài toán trò chơi có nội dung toán học : Luận văn ThS. Toán học: 60 46 40
Nhà xuất bản: ĐHKHTN
Ngày: 2012
Chủ đề: Phương pháp toán sơ cấp
Toán ứng dụng
Bài toán trò chơi
Miêu tả: 76 tr. + CD-ROM + Tóm tắt
Luận văn ThS. Phương pháp toán sơ cấp -- Trường Đại học Khoa học Tự nhiên. Đại học Quốc gia Hà Nội, 2012
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: hệ đếm số 2; máy đọc ý nghĩ; trò chơi Nim; giải bài toán Tháp Hà Nội nhờ đếm cơ số 2. Nghiên cứu lời giải một số bài toán trò chơi cơ học nhờ công cụ mã Gray cơ số 2: mã Gray cơ số 2; mã Gray, trò chơi Tháp Hà Nội và trò chơi Hamilton trên đa diện đều; Baguenaudier hay trò chơi tháo vòng Trung Hoa. Tập hợp một số ví dụ trong các dạng toán trò chơi
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
diện đều...............................................................................................
41
§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………………………………………………… 754
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.
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi5
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 tui 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 Thank 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.
tui xin được Thank 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 tui thực hiện kế hoạch học tập.
Xin được Thank người thân, đồng nghiệp, bạn bè đã cổ vũ động viên tui 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ới6
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
1 0
1 1 0 ...
k k
a a p a p a p a p k k
với các hệ số nguyên 0 1, a p i i k 0,..., ; 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 a a a a k k1 1 0p 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 hay bằng 0. Thí dụ,
2011 2 2 2 2 2 2 2 2 2 10 9 8 7 6 4 3 1 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 hay 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ó,
2011 = 11111011011 =11111011011 10 2 2 .
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),
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi7
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” hay8
“0-1”: Dòng điện hay là chạy theo dây dẫn, hay không; công tắc hay tắt, hoặc
bật; cực của nam châm hay là bắc, hay là nam; một ô nhớ chỉ có thể ở một
trong hai trạng thái chứa thông tin hay 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. tui sẽ hỏi
bạn 10 câu hỏi, bạn có quyền trả lời “đúng” hay “sai”. Dựa trên 10 câu trả lời
của bạn, tui 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ì tui viết số 0, còn nếu câu trả lời là “có” thì tui 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ì tui viết số 0, còn nếu câu trả lời là “có” thì tui viết
chữ số 1 vào phía trước (về bên trái) số đã viết (chữ số 0 hay 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?
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi9
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ố
( 2 1024 10000000000 10 2). 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 667 2 .
Vậy số ban đầu bạn chọn là 667. Kiểm tra lại:
667=3332+1=(1662+1) 2+1=((832) 2+1) 2+1
=(((412+1)2) 2+1) 2+1=((((202+1)2+1)2) 2+1) 2+1
=(((((102)2+1)2+1)2) 2+1) 2+1
=(((((52)2+1)2+1)2) 2+1) 2+1
=((((((22+1)2)2+1)2+1)2) 2+1) 2+1
=(((((((12)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?10
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 hay 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.
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi11
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 xu12
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) hay 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 hay 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 hay 1
(hay 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 hay (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.
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi13
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 hay 2 đồng xu ở hàng thứ hai. Đưa trò chơi về một trong hai trạng
thái: (1; 3; 5) hay (1; 2; 5).
2) Lấy 2 hay 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.14
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 a a a a a a a a n n n n .2 .2 ... .2 ... n n 1 1 0 1 1 0 1 2 ;
b b b b b b b bb n n n n .2 .2 ... .2 ... n n 1 1 0 1 1 0 1 2 ;
c c c c c c c c c n n n n .2 .2 ... .2 ... n n 1 1 0 1 1 0 1 2 .
Các hệ số ai , bi , ci , i n 0,..., có giá trị 0 hay 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 n 0,..., sẽ bị thay đổi. Tương tự, nếu lấy
sỏi từ đống thứ hai (hay từ đống thứ ba), thì ít nhất một trong các hệ số bi ,
i n 0,..., (hay ci , i n 0,..., ) của b ( hay c ) sẽ bị thay đổi.
Xét các tổng
a b c n n n , a b c n n n 1 1 1 ,…, a b c 1 1 1 , a b c 0 0 0 .
Vì các hệ số ai , bi , ci , i n 0,..., chỉ nhận giá trị 0 hay 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 hay 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 a b c i i i ,
i n 0,..., là chẵn. Chiến lược này có thể thực hiện được nhờ cách đi như sau.
Giả sử
a b c k k k 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ố a b c k k k , , 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 a b c i i i ,
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi15
i n 0,..., 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 a a a a a a n n k k 1 1 1 1 0 ... 0 ... , trong đó a a i i nếu a b c i i i ,
i k 0,..., 1 là chẵn (khi ấy a b c a b c i i i i i i vẫn là chẵn) và a a i i 1
nếu
a b c i i i là lẻ (khi ấy a b c a b c a b c a i i i i i i i i i i 1 1 2 là
chẵn). Do các hệ số a a a n n k , ,..., 1 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
a b c i i i , i n 0,..., 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
a b c i i i 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 a b c i i i ,
i n 0,..., 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 a b c i i i , i n 0,..., 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 a b c i i i 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 hay 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ó16
a a a a a 15 2 2 2 1 1111 3 2 2 3 2 1 0 2 ;
b b b bb 12 2 2 1100 3 2 2 3 2 1 0 2 ;
c c c c c 10 2 2 1010 3 2 3 2 1 02.
Tổng các hệ số:
a b c 3 3 3 3; a b c 2 2 2 2; a b c 1 1 1 2; a b c 0 0 0 1.
Lượt đi thứ nhất: Ta có a b c 3 3 3 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 0110 6 2 (qui tắc: thay a3 1 thành a3 0; a a 2 1 1 giữ nguyên do
a b c 2 2 2 2; a b c 1 1 1 2 là các tổng chẵn; vì a b c 0 0 0 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 d a a 1 2 2 2 1111 0110 1001 9 viên sỏi. Số sỏi còn lại ở các đống là:
a 6 0110 2; b b b bb 12 11002 3 2 1 0 2 ; c c c c c 10 1010 2 3 2 1 02 .
Bây giờ ta có
a b c 3 3 3 2; a b c 2 2 2 2; a b c 1 1 1 2; a b c 0 0 0 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 a a a a 6 0110 ; 2 3 2 1 02 b b b bb 11 1011 ; 2 3 2 1 0 2
c c c c c 10 1010 2 3 2 1 0 2.
Tổng các hệ số sau khi người chơi thứ hai đã đi là:
a b c 3 3 3 2 ; a b c 2 2 2 1; a b c 1 1 1 3; a b c 0 0 0 1.
Lượt đi thứ hai: Do a b c 2 2 2 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 d2 viên sỏi sao cho số sỏi còn lại ở đống thứ nhất là
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi17
a 0001 1 2 viên (theo qui tắc “bù để tổng các cột đều chẵn” như trên), tức
là chọn d a a 2 6 1 5 viên. Số sỏi còn lại ở các đống là:
a 6 5 1 0001 2 , b b b bb 11 10112 3 2 1 0 2 , c c c c c 10 1010 2 3 2 1 0 2 .
Bây giờ ta lại có
a b c 3 3 3 2; a b c 2 2 2 0; a b c 1 1 1 2; a b c 0 0 0 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 a a a a 1 0001 2 3 2 1 02 ; b b b bb 11 10112 3 2 1 0 2 ,
c c c c c 9 1001 2 3 2 1 0 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à:
a b c 3 3 3 2; a b c 2 2 2 0; a b c 1 1 1 1; a b c 0 0 0 3.
Lượt đi thứ ba: Vì a b c 1 1 1 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 d3 viên sỏi sao cho số sỏi còn lại
ở đống thứ hai là b 1000 8 2 viên, tức là lấy ra d b b 3 11 8 3 viên.
Số sỏi còn lại ở các đống bây giờ là: a a a a a 1 0001 2 3 2 1 02 ,
b b b bb 8 10002 3 2 1 0 2 , c c c c c 9 1001 2 3 2 1 0 2.
Bây giờ ta lại có
a b c 3 3 3 2; a b c 2 2 2 0; a b c 1 1 1 0; a b c 0 0 0 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 a a a a 1 0001 2 3 2 1 02 , b b b bb 8 10002 3 2 1 0 2 ,
c c c c c 7 0111 2 3 2 1 0 2 .18
Tổng các hệ số: a b c 3 3 3 1; a b c 2 2 2 1; a b c 1 1 1 1; a b c 0 0 0 2.
Lượt đi thứ tư: Do a b c 3 3 3 1, a3 0, b3 1, nên người chơi thứ nhất chọn
d4 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 6 2 viên, tức là d c c 2 8 6 2 viên.
Số sỏi còn lại ở các đống là:
a a a a 1 001 2 2 1 02 , b b bb 6 110 2 2 1 0 2 , c c c c 7 111 2 2 1 0 2 .
Bây giờ ta lại có: a b c 2 2 2 2; a b c 1 1 1 2; a b c 0 0 0 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 ; ;
hay để 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 a a a 1 001 2 2 1 02 , b b bb 6 110 2 2 1 0 2 , c c c c 5 101 2 2 1 02 .
Tổng các hệ số: a b c 2 2 2 2; a b c 1 1 1 1; a b c 0 0 0 2.
Lượt đi thứ năm: Do a b c 1 1 1 1, a1 0 và b1 1 nên người chơi thứ nhất
chọn d5 (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 4 2 viên, tức là d b b 2 6 4 2 viên. Số sỏi
còn lại ở ba đống là:
a a a a 1 001 2 2 1 02 , b b bb 4 1002 2 1 0 2, c c c c 5 101 2 2 1 0 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 a b c k k k 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 a b c i i i , i n 0,..., 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 a b c i i i , i n 0,..., 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
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi19
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 a b c i i i , i n 0,..., 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 a b c i i i , i n 0,..., 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:
Dưới đây là trò chơi Hamilton (The Hamilton’s Icosian Game - trò chơi 12 mặt
hay 20 mặt đều) cùng với tờ hướng dẫn trò chơi được lưu giữ trong Bảo tàng
trò chơi (The puzzle museum).
Lời giải bài toán tìm đường đi kép kín trên khối đa diện đều 12 mặt được
Hamilton trình bày lần đầu tiên năm 1856 (xem [12]).
Để tìm đường đi Hamilton, trước tiên ta phân tích một vài bước đi ban đầu.
Giả sử bước đi đầu tiên ta xuất phát từ một đỉnh và đi theo một cạnh nào đó của
khối đa diện đều 12 mặt sang đỉnh thứ hai. Vì trong khối đa diện đều 12 mặt, tại
mỗi đỉnh có và chỉ có đúng ba cạnh xuất phát, nên tại bước thứ hai ta chỉ còn
đúng hai con đường, được gọi là trái (left - kí hiệu là l) và phải (right –kí hiệu là
r). Như vậy, tại bước thứ ba, ta sẽ có bốn khả năng. Hình 2.5 chỉ ra ba bước đi
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
Nhà xuất bản: ĐHKHTN
Ngày: 2012
Chủ đề: Phương pháp toán sơ cấp
Toán ứng dụng
Bài toán trò chơi
Miêu tả: 76 tr. + CD-ROM + Tóm tắt
Luận văn ThS. Phương pháp toán sơ cấp -- Trường Đại học Khoa học Tự nhiên. Đại học Quốc gia Hà Nội, 2012
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: hệ đếm số 2; máy đọc ý nghĩ; trò chơi Nim; giải bài toán Tháp Hà Nội nhờ đếm cơ số 2. Nghiên cứu lời giải một số bài toán trò chơi cơ học nhờ công cụ mã Gray cơ số 2: mã Gray cơ số 2; mã Gray, trò chơi Tháp Hà Nội và trò chơi Hamilton trên đa diện đều; Baguenaudier hay trò chơi tháo vòng Trung Hoa. Tập hợp một số ví dụ trong các dạng toán trò chơi
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
diện đều...............................................................................................
41
§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………………………………………………… 754
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.
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi5
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 tui 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 Thank 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.
tui xin được Thank 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 tui thực hiện kế hoạch học tập.
Xin được Thank người thân, đồng nghiệp, bạn bè đã cổ vũ động viên tui 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ới6
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
1 0
1 1 0 ...
k k
a a p a p a p a p k k
với các hệ số nguyên 0 1, a p i i k 0,..., ; 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 a a a a k k1 1 0p 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 hay bằng 0. Thí dụ,
2011 2 2 2 2 2 2 2 2 2 10 9 8 7 6 4 3 1 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 hay 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ó,
2011 = 11111011011 =11111011011 10 2 2 .
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),
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi7
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” hay8
“0-1”: Dòng điện hay là chạy theo dây dẫn, hay không; công tắc hay tắt, hoặc
bật; cực của nam châm hay là bắc, hay là nam; một ô nhớ chỉ có thể ở một
trong hai trạng thái chứa thông tin hay 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. tui sẽ hỏi
bạn 10 câu hỏi, bạn có quyền trả lời “đúng” hay “sai”. Dựa trên 10 câu trả lời
của bạn, tui 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ì tui viết số 0, còn nếu câu trả lời là “có” thì tui 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ì tui viết số 0, còn nếu câu trả lời là “có” thì tui viết
chữ số 1 vào phía trước (về bên trái) số đã viết (chữ số 0 hay 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?
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi9
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ố
( 2 1024 10000000000 10 2). 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 667 2 .
Vậy số ban đầu bạn chọn là 667. Kiểm tra lại:
667=3332+1=(1662+1) 2+1=((832) 2+1) 2+1
=(((412+1)2) 2+1) 2+1=((((202+1)2+1)2) 2+1) 2+1
=(((((102)2+1)2+1)2) 2+1) 2+1
=(((((52)2+1)2+1)2) 2+1) 2+1
=((((((22+1)2)2+1)2+1)2) 2+1) 2+1
=(((((((12)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?10
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 hay 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.
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi11
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 xu12
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) hay 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 hay 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 hay 1
(hay 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 hay (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.
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi13
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 hay 2 đồng xu ở hàng thứ hai. Đưa trò chơi về một trong hai trạng
thái: (1; 3; 5) hay (1; 2; 5).
2) Lấy 2 hay 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.14
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 a a a a a a a a n n n n .2 .2 ... .2 ... n n 1 1 0 1 1 0 1 2 ;
b b b b b b b bb n n n n .2 .2 ... .2 ... n n 1 1 0 1 1 0 1 2 ;
c c c c c c c c c n n n n .2 .2 ... .2 ... n n 1 1 0 1 1 0 1 2 .
Các hệ số ai , bi , ci , i n 0,..., có giá trị 0 hay 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 n 0,..., sẽ bị thay đổi. Tương tự, nếu lấy
sỏi từ đống thứ hai (hay từ đống thứ ba), thì ít nhất một trong các hệ số bi ,
i n 0,..., (hay ci , i n 0,..., ) của b ( hay c ) sẽ bị thay đổi.
Xét các tổng
a b c n n n , a b c n n n 1 1 1 ,…, a b c 1 1 1 , a b c 0 0 0 .
Vì các hệ số ai , bi , ci , i n 0,..., chỉ nhận giá trị 0 hay 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 hay 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 a b c i i i ,
i n 0,..., là chẵn. Chiến lược này có thể thực hiện được nhờ cách đi như sau.
Giả sử
a b c k k k 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ố a b c k k k , , 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 a b c i i i ,
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi15
i n 0,..., 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 a a a a a a n n k k 1 1 1 1 0 ... 0 ... , trong đó a a i i nếu a b c i i i ,
i k 0,..., 1 là chẵn (khi ấy a b c a b c i i i i i i vẫn là chẵn) và a a i i 1
nếu
a b c i i i là lẻ (khi ấy a b c a b c a b c a i i i i i i i i i i 1 1 2 là
chẵn). Do các hệ số a a a n n k , ,..., 1 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
a b c i i i , i n 0,..., 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
a b c i i i 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 a b c i i i ,
i n 0,..., 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 a b c i i i , i n 0,..., 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 a b c i i i 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 hay 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ó16
a a a a a 15 2 2 2 1 1111 3 2 2 3 2 1 0 2 ;
b b b bb 12 2 2 1100 3 2 2 3 2 1 0 2 ;
c c c c c 10 2 2 1010 3 2 3 2 1 02.
Tổng các hệ số:
a b c 3 3 3 3; a b c 2 2 2 2; a b c 1 1 1 2; a b c 0 0 0 1.
Lượt đi thứ nhất: Ta có a b c 3 3 3 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 0110 6 2 (qui tắc: thay a3 1 thành a3 0; a a 2 1 1 giữ nguyên do
a b c 2 2 2 2; a b c 1 1 1 2 là các tổng chẵn; vì a b c 0 0 0 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 d a a 1 2 2 2 1111 0110 1001 9 viên sỏi. Số sỏi còn lại ở các đống là:
a 6 0110 2; b b b bb 12 11002 3 2 1 0 2 ; c c c c c 10 1010 2 3 2 1 02 .
Bây giờ ta có
a b c 3 3 3 2; a b c 2 2 2 2; a b c 1 1 1 2; a b c 0 0 0 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 a a a a 6 0110 ; 2 3 2 1 02 b b b bb 11 1011 ; 2 3 2 1 0 2
c c c c c 10 1010 2 3 2 1 0 2.
Tổng các hệ số sau khi người chơi thứ hai đã đi là:
a b c 3 3 3 2 ; a b c 2 2 2 1; a b c 1 1 1 3; a b c 0 0 0 1.
Lượt đi thứ hai: Do a b c 2 2 2 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 d2 viên sỏi sao cho số sỏi còn lại ở đống thứ nhất là
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi17
a 0001 1 2 viên (theo qui tắc “bù để tổng các cột đều chẵn” như trên), tức
là chọn d a a 2 6 1 5 viên. Số sỏi còn lại ở các đống là:
a 6 5 1 0001 2 , b b b bb 11 10112 3 2 1 0 2 , c c c c c 10 1010 2 3 2 1 0 2 .
Bây giờ ta lại có
a b c 3 3 3 2; a b c 2 2 2 0; a b c 1 1 1 2; a b c 0 0 0 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 a a a a 1 0001 2 3 2 1 02 ; b b b bb 11 10112 3 2 1 0 2 ,
c c c c c 9 1001 2 3 2 1 0 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à:
a b c 3 3 3 2; a b c 2 2 2 0; a b c 1 1 1 1; a b c 0 0 0 3.
Lượt đi thứ ba: Vì a b c 1 1 1 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 d3 viên sỏi sao cho số sỏi còn lại
ở đống thứ hai là b 1000 8 2 viên, tức là lấy ra d b b 3 11 8 3 viên.
Số sỏi còn lại ở các đống bây giờ là: a a a a a 1 0001 2 3 2 1 02 ,
b b b bb 8 10002 3 2 1 0 2 , c c c c c 9 1001 2 3 2 1 0 2.
Bây giờ ta lại có
a b c 3 3 3 2; a b c 2 2 2 0; a b c 1 1 1 0; a b c 0 0 0 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 a a a a 1 0001 2 3 2 1 02 , b b b bb 8 10002 3 2 1 0 2 ,
c c c c c 7 0111 2 3 2 1 0 2 .18
Tổng các hệ số: a b c 3 3 3 1; a b c 2 2 2 1; a b c 1 1 1 1; a b c 0 0 0 2.
Lượt đi thứ tư: Do a b c 3 3 3 1, a3 0, b3 1, nên người chơi thứ nhất chọn
d4 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 6 2 viên, tức là d c c 2 8 6 2 viên.
Số sỏi còn lại ở các đống là:
a a a a 1 001 2 2 1 02 , b b bb 6 110 2 2 1 0 2 , c c c c 7 111 2 2 1 0 2 .
Bây giờ ta lại có: a b c 2 2 2 2; a b c 1 1 1 2; a b c 0 0 0 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 ; ;
hay để 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 a a a 1 001 2 2 1 02 , b b bb 6 110 2 2 1 0 2 , c c c c 5 101 2 2 1 02 .
Tổng các hệ số: a b c 2 2 2 2; a b c 1 1 1 1; a b c 0 0 0 2.
Lượt đi thứ năm: Do a b c 1 1 1 1, a1 0 và b1 1 nên người chơi thứ nhất
chọn d5 (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 4 2 viên, tức là d b b 2 6 4 2 viên. Số sỏi
còn lại ở ba đống là:
a a a a 1 001 2 2 1 02 , b b bb 4 1002 2 1 0 2, c c c c 5 101 2 2 1 0 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 a b c k k k 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 a b c i i i , i n 0,..., 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 a b c i i i , i n 0,..., 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
Ket-noi.com kho tai lieu mien phi Ket-noi.com kho tai lieu mien phi19
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 a b c i i i , i n 0,..., 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 a b c i i i , i n 0,..., 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:
Dưới đây là trò chơi Hamilton (The Hamilton’s Icosian Game - trò chơi 12 mặt
hay 20 mặt đều) cùng với tờ hướng dẫn trò chơi được lưu giữ trong Bảo tàng
trò chơi (The puzzle museum).
Lời giải bài toán tìm đường đi kép kín trên khối đa diện đều 12 mặt được
Hamilton trình bày lần đầu tiên năm 1856 (xem [12]).
Để tìm đường đi Hamilton, trước tiên ta phân tích một vài bước đi ban đầu.
Giả sử bước đi đầu tiên ta xuất phát từ một đỉnh và đi theo một cạnh nào đó của
khối đa diện đều 12 mặt sang đỉnh thứ hai. Vì trong khối đa diện đều 12 mặt, tại
mỗi đỉnh có và chỉ có đúng ba cạnh xuất phát, nên tại bước thứ hai ta chỉ còn
đúng hai con đường, được gọi là trái (left - kí hiệu là l) và phải (right –kí hiệu là
r). Như vậy, tại bước thứ ba, ta sẽ có bốn khả năng. Hình 2.5 chỉ ra ba bước đi
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links
Last edited by a moderator: