Trên bàn có một đống sỏi N viên, hai đấu thủ A và B lần lượt đi, A đi nước
đầu tiên. Mỗi nước đi đấu thủ buộc phải bốc từ 1 đến M viên sỏi khỏi bàn. Đấu
thủ nào đến lượt mình không đi nổi thì thua. Cả hai đấu thủ đều chơi rất giỏi.
Với hai số N và M cho trước hãy cho biết A thắng (ghi 1) hay thua (ghi 0).
Ta thử chơi với M = 3
và vài dữ liệu ban đầu N = 1, 2 ,… Để
tính nước đi cho đấu thủ A bạn hãy kẻ một bảng gồm 2 dòng. Dòng thứ nhất là các
giá trị của N. Dòng thứ hai được ghi 0 ứng với tình huống A thua và 1 cho tình cho trường hợp A thắng, nếu A là đấu thủ đi nước đầu tiên.
|
M = 3
|
N =
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
…
|
|
A thắng (1) hay thua (0)?
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
1
|
1
|
0
|
1
|
…
|
|
|
Cách đi: số viên cần bốc để chắc thắng
|
#
|
1
|
2
|
3
|
#
|
1
|
2
|
3
|
#
|
1
|
2
|
3
|
#
|
1
|
…
|
|
|
Một vài tình huống cho bài Bốc sỏi A, M
= 3; # - đầu hàng/bốc tạm 1 viên
|
||||||||||||||||
Thí
dụ, với M = 3 cho trước và cố định, A là đấu thủ đi trước, ta có
N
= 0 là một thế thua, vì A không có cách đi.
N
= 1 là một thế thắng, vì A sẽ bốc 1 viên, B hết cách đi.
N = 2 là một thế thắng, vì A sẽ bốc 2 viên, B hết cách đi.
N
= 3 là một thế thắng vì A sẽ bốc 3 viên, B hết cách đi.
N
= 4 là một thế thua, vì dù A bốc 1, 2, hoặc 3 viên đều dẫn đến các thế thắng là
3, 2, 1…
Làm
thế nào để xác định được bất biến của trò chơi? Phương pháp đơn giản là tư duy
Nhân - Quả hay là lập luận lùi. Cụ thể là, nếu biết kết quả là Q ta hãy gắng
tìm nguyên nhân N sinh ra Q. Ta để ý rằng,
|
Qui tắc xác định
thế thắng / thua
|
|
Từ một thế X đang xét,
·
nếu tìm được một nước đi dẫn đến thế thua T thì X sẽ là thế
thắng V, và
·
nếu mọi nước đi từ X đều dẫn đến thế thắng thì X sẽ là thế thua T.
|
Trước
hết ta sẽ tìm một thế thua nhỏ nhất
của cuộc chơi hay còn gọi là thế thua kết hoặc thế thua cuối cùng, vì đấu thủ nào gặp thế này đều phải đầu hàng và
ván chơi kết thúc.
Dễ
thấy thế thua kết sẽ là N = 0: Hết sỏi, không thể thực hiện được nước đi nào.
Vậy
trước đó, những nước đi nào có thể dẫn đến thế thua T(N = 0)?
Do
mỗi đấu thủ chỉ được phép bốc 1, 2 hoặc 3 viên nên các thế thắng V trước đó chỉ
có thể là N = 1, 2, hoặc 3. Ta viết
T(N =
0) ß
V(N = 1 | 2 | 3) ß
T(N = ?)
trong
đó T là kí hiệu cho thế thua, V là kí hiệu cho thế thắng.
Ta thử xác định thế thua T(N = ?). Dễ thấy
với N = 4 thì mọi cách bốc 1, 2 hoặc 3 viên sỏi đều dẫn đến thế thắng V(N = 3 | 2 | 1). Ta có,
T(N = 0) ß V(N = 1 | 2 | 3) ß T(N = 4)…
Đến đây ta có thể dự
đoán bất biến thua sẽ là N = 4k, cho trường hợp M = 3, hoặc tổng quát hơn, N =
k(M+1), k ³ 0.
Vậy bất biến thua
là:
T: Số viên sỏi
trong đống là bội của M+1: N = k(M+1), k ³ 0.
Ta sẽ chứng minh rằng
nếu N = k(M+1), k = 0, 1, 2,…thì người đi trước (là A) luôn luôn thua.
Trước hết để ý rằng
nếu đấu thủ A gặp số sỏi là bội của M+1 thì với mọi cách đi của A số sỏi còn
lại sẽ không phải là bội của M+1. Thật vậy, muốn bảo toàn tính chất là bội của
M+1 thì A buộc phải bốc một bội nào đó của M+1, đây là điều không được phép vì
vi phạm luật chơi.
Giả sử N = k(M+1), k ³ 1. Gọi số sỏi A bốc là s. Ta có, do 1 £ s £ M nên B sẽ bốc u = (M+1)-s viên sỏi và do đó số sỏi còn lại sẽ lại
là N = k(M+1) – s – ((M+1) – s) k(M+1)–(M+1) = (k–1)(M+1). Đây là một bội của
(M+1).
Nếu số sỏi là bội của
M+1 thì với mọi cách đi hợp lệ, số sỏi còn lại sẽ không còn là bội của M+1. Nếu
số sỏi không phải là bội của M+1 thì luôn luôn tồn tại một cách đi để chỉnh số
sỏi trở thành bội của M+1.
|
Kết luận Bài Bốc sỏi A
|
|
Nếu số sỏi N = k(M+1),
k ³ 0
thì đấu thủ nào đi trước sẽ thua.
|
Với
giả thiết A là đấu thủ đi trước, ta viết hàm Ket(N,M) cho ra giá trị 1 nếu A thắng, ngược lại
hàm cho giá trị 0 nếu A thua. Hàm có hai
tham biến: N là số viên sỏi trong đống, M là giới hạn số viên sỏi được phép
bốc. Hàm đơn thuần chỉ kiểm tra xem trị N có là bội của M+1 hay không.
(* Pascal *)
function Ket(N,M: integer): integer;
begin
if (N mod (M+1) = 0)
then ket := 0 else Ket := 1;
end;
Hàm
CachDi(N,M)
dưới đây đảm nhận chức năng hướng dẫn người chơi chọn một cách đi. Trước hết
cần kiểm tra xem thế đang xét là thắng hay thua. Nếu đó là thế thua và còn sỏi
thì bốc 1 viên nhằm kéo dài thời gian thua. Nếu đó là thế thắng thì bốc số sỏi
dư để số sỏi còn lại sẽ là bội của (M+1).
(* Pascal *)
function CachDi(N,M: integer): integer;
var r: integer;
begin
r := N mod (M+1);
if r = 0 then { thua }
begin
if N = 0 then CachDi := 0 else CachDi := 1;
exit;
end;
CachDi := r;
end;
Nguồn:
SÁNG TẠO
TRONG THUẬT TOÁN
VÀ
LẬP TRÌNH
Không có nhận xét nào:
Đăng nhận xét