Bài toán trò chơi thú vị

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