Một số bài toán trò chơi có nội dung toán học

Đoàn Văn Lới

Trường Đại học Khoa học Tự nhiên
Luận văn Thạc sĩ ngành: Phương pháp toán sơ cấp; Mã số: 60 46 40
Người hướng dẫn: PGS.TS Tạ Duy Phượng
Năm bảo vệ: 2011

Abstract: 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.

Keywords: Phương pháp toán sơ cấp; Toán ứng dụng; Bài toán trò chơi

Content
1.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
10
1 1 0

kk
kk

Nếu
10p 
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ố
i
a
(đượ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ụ,
10 9 8 7 6 4 3 1 0
2011 2 2 2 2 2 2 2 2 2        
.

2
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ó,
 
10 2
2
2011 = 11111011011 =11111011011
.
2.2 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.

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

3
=(((41

2+1)

2)

2+1)

2+1=((((20

2+1)

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)


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:

4
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.
Hệ quả 1 Nếu sau một số bước, số đồng xu trong ba hàng chỉ còn lại là
 
,,abc
với
ab

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.

b b b b b b b bb


     
;
 
1
1 1 0 1 1 0
2
.2 .2 .2
nn
n n n n
c c c c c c c cc


     
.
Các hệ số
i
a
,
i
b
,
i
c
,
0, ,in
có giá trị 0 hoặc 1. Ở đây, để tiện trình bày, ta đã viết biểu
diễn của

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ố
i
a
,
0, ,in
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ố
i
b
,
0, ,in
(hoặc
i
c
,
0, ,in
) của
b
(
hoặc
c
) sẽ bị thay đổi.

5
3.4 Baguenaudier hay trò chơi tháo vòng Trung Hoa
Trò chơi vòng Trung Hoa gồm một số các vòng được treo trên một thanh đôi (có khe trống
giữa hai thanh) sao cho vòng đầu tiên tại một đầu (đầu A, xem Hình 3.1) có thể được lấy ra
qua đầu A hoặc luồn qua khe giữa hai thanh đôi một cách dễ dàng, nhưng mọi vòng khác chỉ

[1] Mao Thị Hiền, Trò chơi Tháp Hà Nội và các bài toán liên quan, Luận văn Cao học, Đại
học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội, 2012.
[2] Nguyễn Thị Hồng Phượng, Thuật toán Frame-Stewart giải bài toán Tháp Hà Nội tổng
quát, Luận văn Cao học, Đại học Sư phạm Thái Nguyên, 2010.
[3] Tạ Duy Phượng, Hệ đếm và ứng dụng (Trong bộ sách Chuyên đề bồi dưỡng học sinh giỏi
Giải toán trên máy tính điện tử), Nhà xuất bản Giáo dục, 2007.
[4] Tạ Duy Phượng, Trò chơi Tháp Hà Nội: Lịch sử và những vấn đề Toán-Tin học liên quan
(Bản thảo), 150 trang, 2010.
[5] Tạ Duy Phượng, Trò chơi toán học (Bản thảo, 120 trang), 2011.
[6] Vũ Thị Mai Thanh, Lý thuyết trò chơi trên đồ thị, Luận văn Cao học, Đại học Khoa học
Tự nhiên, Đại học Quốc gia Hà Nội, 2007.
Tiếng Anh
[7] W. W. Rouse Ball, Mathematical Recreations and Essays, Macmillan and Co., London,
Sixth Edition, (1914).
[8] Henry Ernest Dudeney, The Canterbury Puzzles (and other curious problems), Thomas
Nelson and Sons, Ltd., London, 1907; New York, E. P. Dutton and Company, 1908.
[9] Martin Gardner, Mathematical Puzzles and Diversions, The University of Chicago Press,
1959, 1987.

7
[10] Martin Gardner, Knotted doughnuts and other mathematical entertainments, W. H.
Freeman and Company, 1986, USA.
[11] Martin Gardner, Hexaflexagons, Probability Paradoxes, and the Tower of Hanoi,
Cambridge University Press, 2008.
[12] William Rowan Hamilton, Memorandum respecting a new System of Roots of Unity By
Sir William Rowan Hamilton, Professor of Astronomy in the University of Dublin, and Royal
Astronomer of Ireland. The London, Edinburgh and Dublin Philosophical Magazine and
Journal of Science, 4th series, vol. xii, 1856, p. 446).
[13] Édouard Lucas, Récréations Mathématiques, Gauthier-Villars, Paris, 1892.
[14] Édouard Lucas, L’Arithméique Amusante: Introduction aux Récréations