CP223 – Trò chơi NIM – Bài 1
NIM là một trò chơi giữa 2 người bằng cách thay phiên lấy que từ một số nhóm que. Quy luật lấy que rất đơn giản. Người chơi lấy que từ một nhóm bất kỳ nào đó, bao nhiêu que hay cả nhóm que cũng được. Người thắng cuộc là người lấy que sau cùng. (Que có thể được thay thế bằng viên sỏi, đồng tiền, ….)
Thí dụ 1: An và Cư cùng chơi NIM với 3 nhóm A, B và C gồm 3, 4 và 5 que.
Đến đây, Cư phải lấy 1 que của nhóm B hay C và An sẽ lấy que ở nhóm còn lại và thắng cuộc.
Làm sao để thắng NIM
Quy tắc để thắng NIM có thể tìm được bằng toán học qua hệ thống nhị phân. Trong trò chơi NIM, người đi đầu thường thắng nếu lấy que đúng như tính toán.
Hệ thống nhị phân là hệ thống có cơ số 2, mọi số thập phân có thể phân tích thành tổng số các luỹ thừa của 2 và được diễn tả bằng một dãy những con số 0 và 1 trong hệ thống nhị phân.
Thí dụ 2:
(3)10 = 1 x 21 + 1 x 20 = (11)2
(4)10 = 1 x 22 + 0 x 21 + 0 x 20 = (100)2
(5)10 = 1 x 22 + 0 x 21 + 1 x 20 = (101)2
Định nghĩa Nim-sum
Nim-sum (hay Tổng-Nim) của 2 số X và Y, ký hiệu X ⊕ Y, là 1 số định nghĩa như sau:
a) Viết X và Y dưới dạng nhị phân
b) Dưới dạng nhị phân, nếu các số 1 trên cùng cột của X và Y có tổng số chẵn hay bằng 0 thì cột đó trong Nim-sum (dươí dạng nhị phân) bằng 0, còn ngược lại thì cột đó trong Nim-sum bằng 1.
c) Đổi Nim-sum từ dạng nhị phân sang dạng thập phân
Theo định nghĩa trên, Nim-sum cũng giống như phép cộng mà không cần số giữ trong hệ thống nhị phân (thí dụ: 1 + 1 = 0, không phải 1 + 1 = 0 và +1 đem qua cột kế bên)
Thí dụ 3:
3 ⊕ 4 => 3 = (011)2, 4 = (100)2 => 3 ⊕ 4 = (111)2 => 3 ⊕ 4 = 7
3 ⊕ 5 => 3 = (011)2, 5 = (101)2 => 3 ⊕ 5 = (110)2 => 3 ⊕ 5 = 6
4 ⊕ 5 => 4 = (100)2, 5 = (101)2 => 4 ⊕ 5 = (001)2 => 4 ⊕ 5 = 1
3 ⊕ 4 ⊕ 5 => 3 = (011)2, 4 = (100)2, 5 = (101)2 => 3 ⊕ 4 ⊕ 5 = (010)2 => 3 ⊕ 4 ⊕ 5 = 2
Quy tắc để thắng NIM là phải lấy que sao cho các nhóm que còn lại có Nim-sum bằng 0.
Thí dụ 4:
Với 3 nhóm que A, B và C gồm các que 3, 4 và 5, Nim-sum lúc đầu của 3 nhóm A, B, C bằng:
A ⊕ B ⊕ C = 3 ⊕ 4 ⊕ 5 = 2 (theo thí dụ trước).
Phải lấy que thế nào để có A ⊕ B ⊕ C = 0 ?
Vì 2 = (010)2 nên 2 là do số 1 ở cột thứ hai từ phải (hay cột 21 ) của số 3. Chỉ cần bỏ số 1
nầy trong số (010)2 = 3, tức lấy bớt 2 que của nhóm A, là ta sẽ có Nim-sum của 3 nhóm
bằng 0. Lấy 2 que nhóm A => Còn lai 1 que trong nhóm A
=> A ⊕ B ⊕ C = 1 ⊕ 4 ⊕ 5 = (001)2 ⊕ (100)2 ⊕ (101)2 = (000)2 = 0
Trong thí dụ 1, với 3 nhóm A, B, C gồm 3, 4 và 5 que, An đi đầu đúng như quy tắc lấy que để thắng như sau:
Đến đây, Cư phải lấy 1 que ở nhóm B hay nhóm C và An sẽ lấy que ở nhóm còn lại và thắng cuộc.
ĐỌC VUI VÀ SUY NGHĨ 