TOÁN TRÒ CHƠI: CÔNG CỤ, PHƯƠNG PHÁP, PHÂN LOẠI
(Câu lạc bộ giáo viên Hà Nội, Đông Anh, 11-3-2011)
PGS TS Tạ Duy Phượng
(Viện Toán học)
Một công cụ, một phương pháp có thể sử dụng để giải nhiều bài toán.
Một bài toán có thể được giải bằng các công cụ và phương pháp khác nhau.
Sự phân loại chỉ là tương đối.
Lời giải rất sơ lược và tóm tắt. Lời giải chi tiết có thể xem trong [1].
[1] Tạ Duy Phượng, Đoàn Hữu Dũng, Đoàn Văn Lới: Giới thiệu một số trò chơi toán học
(bản thảo, 2011, 150 trang)
§1 Phương pháp đại lượng bất biến hoặc đơn biến
Bất biến là đại lượng không đổi, đơn biến là đại lượng bảo đảm tính không tăng hoặc
không giảm (đơn điệu). Để tìm lời giải toán học cho một số trò chơi, ta thường phải phát
hiện ra tính bất biến hoặc tính đơn biến của một đại lượng nào đó.
1.1 Bất biến
Bài 1 Trên bàn cờ có 32 quân trắng và 32 quân đen, mỗi quân chiếm một ô vuông.
Tại mỗi bước đi người chơi thay tất cả các quân trắng thành quân đen và tất cả các quân
đen thành quân trắng trên một hàng hoặc một cột nào đó. Hỏi sau hữu hạn bước, có thể
còn lại chính xác một quân đen trên bàn cờ không?
88×
Bất biến: Số các quân đen trên bàn cờ luôn là chẵn. Đáp số: Không thể.
Bài 2 (Chọn đội tuyển Hồng Kông tham gia IMO, 2000, vòng 1) Có 1999 tách uống trà
đặt trên bàn. Lúc đầu tất cả đều được đặt ngửa. Mỗi một nước đi, ta làm cho 100 tách
trong số chúng lật ngược lại. Sau một số nước đi, có thể làm cho tất cả chúng đều úp
xuống được không? Tại sao? Trả lời hai câu hỏi này trong trường hợp chỉ có 1998 tách.
Bất biến: Tính chẵn lẻ của số các tách đặt úp xuống không thay đổi.
Bài 3 Bốn chữ
X
và năm chữ được viết trên một vòng tròn theo thứ tự bất kì. Nếu
hai chữ liên tiếp là như nhau thì ta đặt một chữ
O

X
vào giữa chúng. Nếu hai kí hiệu liên
tiếp là khác nhau thì ta đặt một chữ vào giữa chúng. Bỏ đi các chữ và
O O
X
cũ. Liên
tục làm như vậy, hỏi sau một số bước có thể có được 9 chữ không?
O
Bất biến: Gán 1
X
= , . Gọi là tích của chín số tại bước thứ . Khi ấy luôn
bằng 1 với mọi Mà tích của chin chữ O bằng
1O =−
i
P
i
i
P
2,3, i =
1
−
. Đáp số: Không thể.
Bài 4 Ba đống bi tương ứng có 19, 8 và 9 viên. Được phép chọn hai đống bi bất kì và
chuyển một viên bi từ mỗi đống bi đã chọn vào đống thứ ba. Sau một số lần làm như vậy,
có thể đạt được mỗi đống bi có 12 viên không?
Bất biến: Tại mỗi bước số dư trong ba đống bi theo luôn bằng 0,1,2. Không thể.
mod 3

1
Bài 5 (Thi học sinh giỏi Bungaria, 1999, lớp 8) Có ba đống đá có 51, 49 và 5 viên. Ta

thực hiện một trong hai nước đi như sau. Một nước đi là dồn hai đống tùy ý thành một
đống. Nước đi thứ hai là chọn đống có số chẵn viên đá để chia làm hai đống bằng nhau.
Hỏi có thể thực hiện một dãy các nước đi như thế để chia ba đống đá thành 105 đống mà
mỗi đống chỉ có 1 viên đá hay không?
Bất biến: Dồn hai đống 5 và 49 viên, sau đó luôn được các đống có số bi là bội của 3;
Dồn hai đống 51 và 49 viên, sau đó luôn được các đống có số bi là bội của 5; Dồn hai
đống 5 và 51 viên, sau đó luôn được các đống có số bi là bội của 7. Đáp số: không thể.
1.2 Đơn biến-Phương pháp tụt vô hạn hoặc tăng hữu hạn
Bài 6 (Olympiad Kiev, 1974) Các số 1, 2, , 1974 được viết trên bảng. Người chơi được
phép thay hai số bất kì bởi một số khác bằng tổng hoặc bằng hiệu của các số đó. Hãy chỉ
ra rằng, sau 1973 lần thực hiện phép toán đó, số còn lại trên bảng không thể bằng 0.
Đơn biến: Số các số lẻ giữ nguyên hoặc giảm đi 2 sau mỗi bước.
Bài 7 (Vô địch toàn liên bang Nga lần thứ nhất, 1961) Các số thực được viết vào các ô
trong một bảng chữ nhật . Mỗi lần ta có thể đổi dấu tất cả các phần tử trong một
hàng hoặc một cột. Hãy chứng minh rằng sau một số lần như vậy, ta có thể làm cho tổng
của các số trong mỗi hàng và mỗi cột là không âm.
mn×
Đơn biến (tăng hữu hạn): Sau mỗi lần đổi dấu một hàng (cột) có tổng các số hạng âm,
tổng các số hạng trong hàng (cột) tăng lên. Số khả năng đổi dấu là hữu hạn nên cuối
cùng được bảng có tổng các số trong mỗi hang (mỗi cột) là không âm.
§2 Trò chơi hai người với thông tin đầy đủ
Trò chơi hai người thường có tính chất đối kháng: Mỗi người đều cố gắng tìm chiến lược
thắng (theo tiêu chuẩn kết thúc trò chơi) nhưng chỉ có một người thắng, một người thua.
Nếu không thắng được thì tìm chiến lược làm cho đối phương thiệt hại nhất (thua sau thời
gian lâu nhất, tốn ít năng lượng nhất,…). Thông tin là đầy đủ: Tại mỗi bước đi, mỗi người
đều biết trạng thái trò chơi, tiêu chuẩn kết thúc trò chơi, khả năng chọn chiến lược và
những hạn chế của đối phương.
Bài 8 (Vô địch Liên Xô lần thứ 9, 1975, lớp 8, 9) Cho tam giác ABC có diện tích bằng 1.
Người chơi thứ nhất chọn điểm X trên cạnh AB, người chơi thứ hai chọn điểm Y trên
cạnh BC. Sau đó người chơi thứ nhất chọn điểm Z trên cạnh AC. Mục đích của người

chơi thứ nhất là làm cực đại diện tích tam giác XYZ và mục đích của người chơi thứ hai
là làm cực tiểu diện tích tam giác XYZ. Hỏi người chơi thứ nhất có thể đảm bảo cho
mình diện tích lớn nhất của tam giác XYZ là bao nhiêu?
Chiến lược: Người thứ hai luôn chọn được
1
4
XYZ
S
≤
. Người thứ nhất chon X và Z là các
điểm giữa của AB và AC. Khi ấy
1
4
XYZ
S
=
.
Bài 9 (Kvant, 1976, No4, M337, trang 32) Cho tam giác đều ABC có cạnh bằng 1. Người
chơi thứ nhất chọn điểm X trên cạnh AB, người chơi thứ hai chọn điểm Y trên cạnh BC.
Sau đó người chơi thứ nhất chọn điểm Z trên cạnh AC. Mục đích của người chơi thứ nhất

2
là làm cực đại chu vi tam giác XYZ và mục đích của người chơi thứ hai là làm cực tiểu
chu vi tam giác XYZ. Hỏi người chơi thứ nhất có thể đảm bảo cho mình chu vi lớn nhất
của tam giác XYZ là bao nhiêu?
Lời giải Khó hơn nhiều so với bài trên.
Bài 10 (Vô địch Moscow lần thứ 34, 1971, lớp 10, vòng 1) Một đống gồm 1 tỉ que diêm.
Hai người chơi trò chơi sau đây. Mỗi bước người chơi có thể lấy từ đống diêm
n
p

que,
trong đó là số nguyên tố, (thí dụ, người thứ nhất lấy 25 que, người thứ hai
lấy 8 que, người thứ nhất lấy 1 que, người thứ hai lấy 5 que, người thứ nhất lấy 49 que,
Người nào lấy que diêm cuối cùng thì người đó thắng. Hỏi ai là người chiến thắng?
p 0,1, 2, n =
Chiến lược: Người đi đàu tiên luôn lấy ra số diêm bằng số dư theo và thắng.
mod 6
Bài 11 (Annual Maritine Mathematics Competition-Thi toán hàng năm miền duyên hải
Canada, 2001) A và B tiến hành chơi với 2001 hạt đậu. A đi trước và luân phiên nhau.
Một nước đi là một lần lấy khỏi đống hạt đậu đi 1, 2 hay 3 hạt. Người nào đi nước cuối
(hết đậu trong đống), người ấy thắng. Vậy người nào có chiến thuật để luôn thắng và
chiến thuật đó ra sao.
Chiến lược: Người đi trước lấy 1 hạt đậu. Sau đó anh ta lấy
4
x
−
, trong đó
x
là số hạt
đậu người thứ hai lấy. Số hạt bao giờ cũng còn lại là 0 theo
mo
(bất biến!). Cuối cùng
còn 4 hạt và đến lượt người thứ hai. Anh ta thua.
d 4
Bài 12 Hai đứa trẻ chơi trò chơi sau đây với hai đống kẹo. Đống thứ nhất có 12 chiếc và
đống thứ hai có 13 chiếc. Mỗi đứa trẻ lấy ra hoặc hai viên kẹo từ một đống (để ăn) hoặc
chuyển một viên kẹo từ đống thứ nhất sang đống thứ hai. Đứa trẻ nào không chuyển được
nữa thì sẽ thua. Hãy chỉ ra rằng đứa trẻ thứ hai không thể thua. Hỏi cậu ta có thắng
không?
Bất biến: Hiệu số kẹo giữa hai đống là luôn tăng lên 2 hoặc giảm đi 2, tức là luôn

có số dư là 1, 3, 1, 3,…
(
. Đứa trẻ thứ hai thắng.
S S
)
0
0
mod 4
Bài 13 (Vô địch Liên Xô lần thứ 3, 1969, lớp 9-10) Trên bảng có phương trình
. Hai người chơi trò chơi sau đây. Đầu tiên người thứ nhất thay một
dấu * bất kì bằng một số nguyên khác 0 (dương hoặc âm), sau đó người thứ hai thay một
số nguyên vào một trong hai dấu * còn lại. Người thứ nhất đặt nốt một số nguyên vào vị
trí tự do cuối cùng. Chứng minh rằng người thứ nhất bao giờ cũng làm cho phương trình
có ba nghiệm thực, không phụ thuộc vào cách chọn số của người chơi thứ hai.
32
***xxx+++=
Chiến lược: Người thứ nhất đi
32
**xxx
+
−+=
. Người thứ hai điền , người thứ nhất
điền . Khi ấy
k
k−
(
)
(
)
(

)
32
11xkxxk xkx x−−+=− − +
.
Bài 14 (Vô địch Moscow lần thứ 31, 2001, lớp 7, vòng 2) Trên mặt phẳng cho 1968 điểm
là các đỉnh của một đa giác đều. Hai người chơi lần lượt nối hai đỉnh của đa giác đều bởi
các đoạn thẳng theo qui tắc sau: không được nối hai điểm mà một trong các điểm ấy đã
được nối với điểm khác, và không được cắt các đoạn đã kẻ. Người thua là người không
thể làm bước tiếp theo. Hỏi làm thế nào để thắng? Ai là người thắng trong trò chơi này?

3
Chiến lược: Người thứ nhất kẻ đường chéo qua tâm chia đa giác thành hai phần. Sau đó
tại mỗi bước đi kẻ mỗi bước đi kẻ các đường chéo đối xứng với đường chéo mà người
thứ hai đã kẻ. Người thứ nhất thắng.
Bài 15 (Vô địch Liên Xô lần thứ 18, 1984, lớp 9) Có một hình lập phương và hai màu:
màu đỏ và màu xanh. Hai người chơi trò chơi sau đây. Người thứ nhất chọn ba cạnh của
lập phương và sơn chúng thành màu đỏ. Người thứ hai chọn ba cạnh chưa sơn và sơn
chúng thành màu xanh. Sau đó người thứ nhất lại chọn ba cạnh và sơn màu đỏ. Và cuối
cùng người thứ hai sơn nốt ba cạnh còn lại bằng màu xanh. Cấm sơn lại một cạnh đã sơn
(bằng màu khác cũng như bằng màu đã sơn). Người nào đầu tiên sơn được một mặt có
bốn cạnh cùng màu thì người đó thắng. Hỏi người thứ nhất có luôn thắng không?
Chiến lược: Người thứ hai sơn ba cạnh đôi một vuông góc.
Bài 16 (Vô địch Liên Xô lần thứ 16, 1982, lớp 8) Mỗi đỉnh của hình vuông được gán cho
một số thực không âm, ngoài ra tổng của tám số này bằng 1. Hai người chơi trò chơi sau
đây: Người thứ nhất chọn một mặt bất kì, sau đó người thứ hai chọn mặt tiếp theo, và sau
đó người thứ hai chọn mặt thứ ba. Ngoài ra, không được chọn mặt song song với một
trong các mặt đã được chọn. Chứng minh rằng người thứ nhất có thể chọn chiến lược
chơi sao cho số nằm trên đỉnh chung của cả ba mặt đã được chọn không vượt quá
1
6

.
Chiến lược: Bao giờ cũng chọn được ba số không vượt quá
1
6
. Hai trong ba số này phải
là hai đầu của một đường chéo của một mặt. Người thứ nhất chọn mặt này và thắng.
Bài 17 (Vô địch Moscow lần thứ 32, 1969, lớp 7, vòng 2) Hai người chơi trò chơi sau
đây. Mỗi người chơi tùy theo cách chọn của mình lần lượt gạch 9 số từ dãy số 1, 2, 3, …,
100, 101. Sau 11 lượt (người thứ nhất 6 lượt, người thứ hai 5 lượt), chỉ còn lại 2 số. Sau
đó người thứ hai phải trả cho người thứ nhất số điểm bằng đúng hiệu giữa hai số còn lại.
Chứng minh rằng người thứ nhất luôn luôn nhận được tối thiểu 55 điểm, không phụ thuộc
vào người chơi thứ hai.
Chiến lược: Bước đầu tiên người thứ nhất gạch 9 số từ 47 đến 55. Các số còn lại chia
làm hai lớp: từ 1 đến 46 và từ 56 đến 101. Với mỗi số bị gạch bởi người thứ hai, người
thứ nhất chọn
k
55 k−
.
Bài 18 (Vô địch Moscow lần thứ 31, 1968, lớp 10) Hai người chơi một trò chơi sau đây
với hai đống kẹo. Luật chơi như sau: Mỗi người chơi ăn một chiếc kẹo từ một trong các
đống, sau đó chia một đống khác thành hai phần (không nhất thiết bằng nhau). Nếu ai đó
không thể chia được nữa, tức là chỉ còn một chiếc kẹo, thì người đó ăn nốt và thắng cuộc.
Lúc đầu đống thứ nhất có 33 chiếc và đống thứ hai có 35 chiếc. Hỏi là người thắng cuộc,
và chiến lược chơi như thế nào để thắng?
Chiến lược: Người thứ nhất ăn một chiếc kẹo ở đống 33 chiếc và chia đống 35 chiếc
thành đống 17 và 18 chiếc kẹo. Bước tiếp theo người đó luôn giữ số kẹo trong mỗi đống
là hoặc
5
. Cuối cùng chỉ còn đống có 2 hoặc 3 kẹo. Người thứ hai thua.
5k + 2 3k +

Bài 19 (Vô địch Moscow lần thứ 32, 1969, lớp 10, vòng 2) Hai nhà thông thái chơi trò
chơi sau đây. Người thứ nhất gạch 512 số trong các số 1, 2, 3, , 1024. Người thứ hai
gạch 256 số còn lại. Người thứ nhất lại gạch 128 số, Đến bước thứ 10 người thứ hai

4
gạch một số, còn lại hai số. Sau đó người thứ hai trả cho người thứ nhất số điểm bằng
hiệu giữa các số đó. Hỏi ai sẽ là người có lợi hơn? Hỏi người thứ hai phải trả cho người
thứ nhất bao nhiêu, nếu chiến lược của cả hai đều đúng.
Đáp số: 32 điểm.
Bài 20 (Vô địch Moscow lần thứ 32, 1969, lớp 9, vòng 2) Hai người chơi trò chơi sau
đây. Mỗi người chơi lần lượt gạch một trong các số 1, 2, 3, , 27 cho đến khi chỉ còn hai
số. Nếu tổng hai số này chia hết cho 5 thì người thứ nhất thắng, nếu không chia hết cho 5,
thì người thứ hai thắng. Hỏi ai sẽ là người thắng cuộc?
Bài 21 (Vô địch Moscow lần thứ 40, 1977, lớp 7, vòng 2) Có 1977 chiếc đinh được đóng
trên một cái bảng. Hai người chơi trò chơi sau đây: Mỗi người nối hai chiếc đinh bằng
một sợi dây. Nếu cuối cùng ai đóng kín được các đường đã nối thì người đó thắng. Hỏi ai
thắng cuộc? (không cho phép nối lại hai chiếc đinh đã được nối).
Đáp số: Người thứ hai thắng.
Bài 22 (Vô địch Liên Xô lần thứ 21, 1987, lớp 8 và lớp 10) Mỗi người chơi lần lượt viết
lên bảng một số không vượt quá số cho trước. Qui tắc của trò chơi cấm viết lên bảng
các số là ước số của các số đã viết. Người nào không viết được nữa người đó sẽ thua.
p
b) Với , hỏi ai là người có chiến lược thắng. Hãy chỉ ra chiến lược ấy.
10p =
b) Hỏi ai là người chiến thắng nếu
1000p
=
?
Đáp số: Người thứ nhất luôn thắng.
Bài 23 (Vô địch Liên Xô lần thứ 11, 1977, lớp 10)

Cho đa thức
10 9 8 2
* * * * 1
x
xx xx++++++
. Hai người chơi trò chơi sau đây. Đầu tiên
người thứ nhất thay một dấu * bất kì bằng một số nào đó, sau đó người thứ hai thay một
số tự chọn vào một dấu * còn lại. Cứ như vậy tiếp tục (có tất cả 9 bước đi). Nếu đa thức
không có nghiệm (thực) thì người thứ nhất thắng, còn nếu có ít nhất một nghiệm thực thì
người thứ hai thắng. Hỏi người thứ hai có thể thắng với mọi cách đi của người thứ nhất
không?
Đáp số: người thứ hai thắng.
Bài 24 (Bachet’s games) Đầu tiên, có quân cờ đam trên bàn cờ ( ). Tại mỗi bước
đi, người chơi lấy ra tối thiểu một quân và tối đa quân cờ từ bàn cờ (
1
cho
trước cố định). Người chơi nào đến lượt có thể lấy mọi quân cờ sẽ là người chiến thắng.
Hỏi
n
phải bằng bao nhiêu để người chơi thứ nhất có thể dành chiến thắng? Tương tự,
phải bằng bao nhiêu để người chơi thứ hai có thể thắng?
n 0n >
k kn<<
n
Đáp số: Nếu không là bội của
n 1k
+
thì người thứ nhất thắng. Ngược lại người thứ hai
thắng.
Bài 25 (Vô địch Liên Xô lần thứ 12, 1978, lớp 8) Một quân cờ đam đứng ở góc bàn cờ

gồm ô vuông. Hai người chơi lần lượt đẩy quân cờ sang ô bên cạnh (có cạnh liền kề
với ô mà quân cờ đang đứng). Không được phép trở lại ô mà quân cờ đã đi qua. Người
nào không còn nước đi thì người ấy thua.
nn×
1) Chứng minh rằng nếu chẵn thì người chơi thứ nhất thắng, còn nếu lẻ thì người
chơi thứ hai thắng.
n n

5
2) Ai là người chiến thắng, nếu lúc đầu quân cờ không ở vị trí góc bàn cờ, mà ở ô bên
cạnh góc bàn cờ?
Đáp số: 1) Nếu chẵn thì người thứ nhất thắng. Nếu lẻ thì người thứ hai thắng.
n n
2) Người thứ nhất luôn thắng.
Bài 26 (Vô địch Israel, 1995) Hai người chơi cờ carô trên một bảng ô carô vô hạn. Người
chơi thứ nhất chọn một ô vuông và đánh dấu là O, người chơi thứ hai chọn một ô vuông
khác và đánh dấu là X. Hai người chơi cho đến khi một trong hai người có được một
dòng hoặc một cột năm ô vuông đánh dấu liên tiếp. Khi ấy người đó thắng. Hãy chỉ ra
rằng người chơi thứ hai luôn ngăn được người thứ nhất dành chiến thắng.
§3 Trò chơi đuổi bắt
Trong thực tế, trò chơi hai người hoặc nhiều người tham gia thường chuyển động với vận
tốc khác nhau. Trò chơi này thường là trò chơi đuổi bắt, tiêu chuẩn kết thúc trò chơi là
người đuổi bắt được (hoặc không bắt được) người chạy sau thời gian hữu hạn (sau thời
gian vô hạn).
Bài 27 (Vô địch Moscow lần thứ 33, 1970, lớp 7, vòng 2) Trong một công viên có sáu
đường đi cùng độ dài men theo hàng cây hẹp. Bốn đường đi theo bốn cạnh của hình
vuông, hai đường còn lại dọc theo hai đường trung bình của hình vuông. Cậu bé Kôlia
chạy khỏi bố mẹ theo các con đường đó. Hỏi bố và mẹ có thể bắt được Kôlia không nếu
cậu ta chạy nhanh gấp ba lần bố mẹ (cả ba người đều nhìn thấy nhau).
Đáp số: có thể.

Bài 28 (Vô địch Moscow lần thứ 33, 1970, lớp 8, vòng 2) Một con khỉ của vườn bách thú
bị sổng chuồng và hai người bảo vệ đuổi bắt nó. Cả người bảo vệ cùng con khỉ đều chạy
theo các con đường nhỏ. Có tất cả 6 con đường thẳng; 3 đường dài tạo thành ba cạnh của
tam giác đều, ba cạnh ngắn nối các điểm giữa các cạnh. Tại mỗi thời điểm người và khỉ
đều nhìn thấy nhau. Hỏi hai người bảo vệ có bắt được con khỉ không? Biết rằng khỉ chạy
nhanh gấp ba lần những người bảo vệ (đâud tiên những người bảo vệ đứng ở đỉnh tam
giác, còn khỉ đứng ở một đỉnh khác)?
Bài 29a (Vô địch Moscow lần thứ 33, 1970, lớp 9, vòng 2) Ba con nhện và một con ruồi
bò theo các cạnh của một lập phương trong suốt. Vận tốc lớn nhất của ruồi lớn hơn vận
tốc lớn nhất của nhện gấp ba lần. Đầu tiên các con nhện nằm trên một đinh của lập
phương, còn con ruồi nằm ở đỉnh đối diện. Hỏi các con nhện có thể có bắt được ruồi
không (nhện và ruồi luôn luôn nhìn thấy nhau)?
Bài 29b (Vô địch Moscow lần thứ 33, 1970, lớp 10, vòng 2) Xét bài toán trên với hai con
nhện, nhưng vận tốc tối đa của ruồi và nhện là như nhau.
Bài 30 (Vô địch Liên Xô lần thứ 8, 1974, lớp 8) Hai người chơi trò “mèo-chuột” trên một
bàn cờ . Người thứ nhất (đóng vai chuột) có một quân cờ đam màu đen, người thứ
hai (đóng vai mèo) có vài quân đam trắng (vài con mèo). Tất cả các quân chuyển động
như nhau: mỗi lần đi một ô sang trái, sang phải, lên trên, xuống dưới. Nếu chuột chạy ra
đến mép bàn cờ, thì đến bước sau nó nhảy ra khỏi bàn cờ. Nếu một con mèo nhảy được
vào ô chuột đang đứng, thì mèo ăn thịt chuột.
88×

6
Chuột đi bước đầu tiên. Mục đích của chuột là nhảy ra khỏi bàn cờ. Bước tiếp theo là
bước đi của mèo: tất cả các con mèo đều chuyển động, có thể theo các hướng khác nhau).
Mục đích của mèo là bắt được chuột.
1) Giả sử có hai con mèo. Chuột đã đứng ở một ô nào đó bên trong bàn cờ (không ở ô
ngoài biên). Hỏi có thể đặt hai con mèo tại vị trí nào đó trên biên bàn cờ, để chúng có thể
bắt được chuột không?
2) Giả sử có ba con mèo, nhưng mỗi bước chuột có thể nhảy hai ô liền. Hãy chứng minh

rằng chuột có thể chạy thoát từ mọi vị trí ban đầu.
Công cụ: Hệ đếm
Bài 31 Giả sử bạn chọn một số bất kì nào đó trong khoảng từ 1 đến 1000. Tôi sẽ hỏi bạn
10 câu hỏi, bạn chỉ 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?
Bài 32 (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ì (tối thiểu một viên cho đến cả đống sỏi) 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 để thắng?
Bài 33 (Đề dự tuyển Vô địch Quốc tế, 1999)
Một nhà sinh vật học quan sát một con thạch sùng đang bắt ruồi và nó nghỉ ngơi sau mỗi
lần bắt được một con ruồi. Nhà sinh vật học này nhận thấy rằng:
(i) Con ruồi đầu tiên bị bắt sau thời gian nghỉ một phút;
(ii) Thời gian nghỉ trước khi bắt con ruồi thứ bằng thời gian nghỉ trước khi bắt con
ruồi thứ
m
và kém một phút so với thời gian nghỉ trước khi bắt con ruồi thứ ;
2m
21m +
(iii) Khi thạch sùng hết nghỉ, nó bắt ruồi ngay lập tức.
Hỏi:
a) Có bao nhiêu con ruồi bị bắt trước thời gian nghỉ lần đầu tiên là 9 phút?
b) Sau bao nhiêu phút thì thạch sùng bắt được con ruồi thứ 98?
c) Có bao nhiêu con ruồi bị thạch sùng bắt sau 1999 phút trôi qua?
Bài 34 (Kì thi mùa đông Bungaria, 2001)
Ivan và Peter thay nhau viết các chữ số 0 hoặc 1 (mỗi lần một chữ số) cho đến khi mỗi
người viết được 2001 chữ số. Như vậy, ta sẽ nhận được một dãy gồm 4002 chữ số 0 hoặc
1. Coi đây là biểu diễn nhị phân của một số. Peter là người thắng cuộc nếu số nhận được
không viết được dưới dạng tổng của hai số chính phương. Chứng minh rằng Peter (đi sau)

có chiến lược đảm bảo anh ta thắng cuộc.
Một số bài toán khác
Bài 35 (Vô địch Moscow lần thứ 33, 1970, lớp 7, vòng bổ sung) Trong trò chơi đôminô
thông thường, các quân đôminô được đặt sao cho hiệu giữa các số trên các quân cạnh
nhau bằng 0. Hỏi có thể đặt tất cả 28 quân đôminô vào một vòng khép kín để cho tất cả
các hiệu bằng ?
1±
Bài 36 (Vô địch Liên Xô lần thứ 12, 1978, lớp 8) Một quân cờ đam đứng ở góc bàn cờ
gồm ô vuông. Hai người chơi lần lượt đẩy quân cờ sang ô bên cạnh (có cạnh liền kề
nn×

7
với ô mà quân cờ đang đứng). Không được phép trở lại ô mà quân cờ đã đi qua. Người
nào không còn nước đi thì người ấy thua.
1) Chứng minh rằng nếu chẵn thì người chơi thứ nhất thắng, còn nếu lẻ thì người
chơi thứ hai thắng.
n n
2) Ai là người chiến thắng, nếu lúc đầu quân cờ không ở vị trí góc bàn cờ, mà ở ô bên
cạnh góc bàn cờ?
Bài 37 Mỗi thành viên trong câu lạc bộ có tối thiểu ba kẻ thù (hai người có thể có chung
kẻ thù). Hãy chỉ ra rằng có thể chia số thành viên câu lạc bộ thành hai nhóm sao cho mỗi
thành viên câu lạc bộ có nhiều nhất một kẻ thù trong nhóm.
Bài 38 Cho điểm trên mặt phẳng không có ba điểm nào thẳng hàng. Hãy chỉ ra rằng
chúng có thể chia thành
n
cặp sao cho đoạn nối chúng đôi một không cắt nhau.
2n
n
Bài 39 Hai mươi cô gái ngồi quanh bàn và chơi một trò chơi với n quân bài. Đầu tiên,
một cô gái giữ tất cả các quân bài. Sau mỗi lần rút bài, nếu tối thiểu một cô gái giữ tối

thiểu hai quân bài, một trong số các cô gái đó phải chuyển quân bài cho hai người ngồi
cạnh. Trò chơi kết thức nếu mỗi cô gái chỉ giữ tối đa một quân bài.
1) Chứng minh rằng nếu thì trò chơi không thể kết thúc.
20n ≥
2) Chứng minh rằng nếu thì cuối cùng trò chơi phải kết thúc.
20n <
Bài 40 (Vô địch Moscow lần thứ 34, 1971, lớp 10, vòng 2) Kế toán và người chơi chơi
trò chơi sau đây. Kế toán gọi một số có 1000 chữ số . Biết số đó, người chơi gọi một
số
1
A
1
B
nào đó. Sau đó kế toán xem xét và quyết định trừ số lớn cho số nhỏ hoặc cộng
chúng. Được số và báo cho người chơi. Người chơi lại báo cho kế toán số
2
A
2
B
nào đó.
Trò chơi tiếp tục cho tới khi nếu kế toán nhận được một trong các số 1, 10, 100, 1000,…
Chứng minh rằng người chơi luôn có thể kết thúc trò chơi sau khi thông báo cho kế toán
không quá 20 số.
Bài 41 (Winconsin Mathematics Science and Engineering Talent Search- Thi chọn tài
năng của đại học Winconsin, 2000-2001) Một chiếc máy kì diệu làm việc như sau: nếu
anh bỏ vào máy 1 đồng xu (penny), nó cho nhảy ra một đồng hào (dime); nếu bạn bỏ vào
1 đồng hào, sẽ nhảy ra một đồng xu và 1 đồng 25 xu (a quater), còn nếu bạn bỏ vào 1
đồng 25 xu, nó sẽ nhảy ra 2 đồng hào.
Bắt đầu bằng một đồng hào, tôi chơi với máy một lúc. Khi đếm tiền, tôi thấy mình có
đúng 100 đồng xu cùng với một số đồng tiền khác. Hỏi số tiền bé nhất mà tôi có thể có

vào lúc này là bao nhiêu? (1 dollar = 10 dime = 100 penny).




8