Một số bài toán trò chơi
Ngô Minh Đức
A. Giới thiệu
Trong bài viết này chúng ta sẽ xét một số bài toán trò chơi, từ dễ đến khó. Về nguyên tắc,
các bài toán trò chơi thường được cho dưới dạng: nhập vào một trạng thái của trò chơi, tìm
nước đi “tốt nhất” có thể được, hoặc nhập vào một trạng thái của trò chơi, khẳng định
người đi trước sẽ thắng hay thua, v.v...
1. Trò chơi bốc sỏi
Đây là trò chơi đơn giản nhất, luật chơi như sau:
Có 2 người chơi, I và II và một đống sỏi có khối lượng là 21 viên.
Mỗi nước đi được phép lấy không qúa 3 viên ra khỏi đống, nhưng phải lấy ít nhất 1 viên.
Hai người lần lượt đi và người I đi trước. Ai lấy được viên sỏi cuối cùng sẽ thắng.
Hướng dẫn: sau khi phân tích, dễ dàng nhận thấy người I luôn luôn thắng, chỉ cần đưa về
các vị trí 20,16,12,8,4 viên sỏi là được
Tổng quát nếu mỗi bước đi không được phép lấy qúa k viên sỏi, ta sẽ có các vị trí thắng là
bội số của k+1. Nếu n là bội số của k+1 thì người II thắng, còn không thì người I thắng.
Nếu đổi luật thành người lấy được viên sỏi cuối cùng thì thua, ta cũng tìm được một chiến
thuật chơi tốt. Vị trí thắng là các vị trí thắng ban đầu cộng thêm 1.
2. Làm rỗng và phân chia
Có hai cái hộp, ban đầu một hộp chứa m viên sỏi, hộp kia chứa n viên sỏi. Ta kí hiệu là
(m,n) với m>0, n>0. Hai người chơi lần lượt đi. Một nước đi được phép làm rỗng (lấy hết
sỏi ra) một hộp, và chia số sỏi trong hộp còn lại vào hai hộp, với ít nhất một viên trong mỗi
hộp. Người nào không đi được nữa là thua.
Nhập vào: (m,n)
Xuất ra: WIN nếu người đi trước thắng, LOSE nếu người đi trước thua.
Hướng dẫn: Vị trí thắng là các vị trí (m,n) sao cho cả m và n đều lẻ
Chứng minh: dùng phép quy nạp
Rõ ràng (1,1) là vị trí thắng
Giả sử điều khẳng định đúng với các vị trí (x,y), x,y<=n. Ta chứng minh điều khẳng đỉnh
đúng với các vị trí (x,y), x,y<=n+1
Ta chứng minh điều khẳng định đúng với các vị trí (m,n+1) trong đó m<=n+1.

4. Trò chơi 3 đống sỏi
Có 3 đống sỏi, lần lượt gồm a,b,c viên sỏi. Hai người lần lượt đi. Mỗi nước đi được phép
chọn một đống bất kỳ và lấy số lượng viên sỏi tùy ý ra khỏi đống đó, nhưng phải lấy ít
nhất 1. Người nào lấy được viên sỏi cuối cùng là thắng.
Nhập vào: a,b,c
Xuất ra: LOSE nếu khẳng định người đi trước thua, còn không xuất ra a’,b’,c’ là nước đi
“tối ưu” của người đi trước. Nếu có nhiều nước đi tối ưu, chỉ cần xuất ra 1.
Hướng dẫn: vị trí thắng là các vị trí thỏa điều kiện: a xor b xor c = 0
Chứng minh: dựa vào tính chất của phép xor:
a xor a = 0 với mọi a
a xor b = b xor a
(a xor b) xor c = a xor (b xor c)
Vậy cách đi là như sau: từ vị trí (a,b,c)
Đặt a’=b xor c, b’ = a xor c, c’=b xor a.
Nếu a’
Nếu b’
Nếu c’<>
B. Một số trò chơi khác
1. Đồng xu lăn
Có một hàng các ô vuông được đánh số 0,1,2,3,... Có một số lượng hữu hạn các đồng
xu được đặt trên các ô vuông, có thể có nhiều đồng xu trên cùng một ô. Hai người
chơi lần lượt đi. Mỗi nước đi được phép lấy một trong các đồng xu và di chuyển về
một ô bất kỳ ở bên trái. Trò chơi kết thúc khi tất cả đồng xu đều nằm ở ô 0. Người đi
cuối cùng thắng.
Dữ liệu vào: DONGXU.IN
Dòng 1: n – số lượng ô vuông ban đầu
n dòng sau, dòng i chứa một số nguyên là số đồng xu trên ô i tại thời điểm ban đầu
Kết qủa: DONGXU.OUT
Gồm 1 dòng duy nhất, là “WIN” nếu khẳng định người đi trước thắng, “LOSE” nếu
khẳng định người đi trước thua

quân cờ khác. Người nào không đi được nữa là thua.
Nếu trò chơi chỉ có 1 quân cờ mỗi loại, cách chơi đơn giản là đi quân cờ đến sát cạnh
quân đối phương. Với 2 quân cờ mỗi loại, trò chơi trở nên phức tạp hơn:
Hơn nữa có thể xảy ra trạng thái hòa:
Yêu cầu: nếu người đi trước có thể thắng, hãy xác định nước đi tối ưu, còn không thì
xác định kết cục là người đi trước thua hay hòa.
Dữ liệu vào: BOARD.IN
Một dòng duy nhất gồm một chuỗi 60 ký tự, mỗi ký tự mô tả một hố trên bàn cờ: ‘0’
là hố rỗng, ‘1’ là quân cờ thuộc về người I, ‘2’ là quân cờ thuộc về người II. Hai
người chơi có cùng số lượng quân cờ, và có ít nhất 2 hố rỗng trên bàn cờ.
Kết qủa: BOARD.OUT