Tổng quát

NIM là một trò chơi toán học về chiến lược, trong đó hai đấu thủ thay phiên lấy đi các quân trên các hàng riêng rẽ. Mỗi lượt phải lấy đi ít nhất một quân hay có thể nhiều quân với điều kiện chúng phải ở trên cùng một hàng. Tên hiện nay của trò chơi là do Charles L. Bouton thuộc Đại Học Harvard đặt ra. Có hai qui ước chơi:

Misère mode: ai bị buộc phải lấy quân sau cùng sẽ thua;

Normal mode: ai lấy quân sau cùng sẽ thắng

Ví dụ bên dưới là cuộc so tài giữa hai đấu thủ giả tưởng Nam và Bắc trên sân đấu có ba hàng với ba quân số 3, 4, và 5.

  

Lý thuyết toán học

1.      Chiến lược từng bước là luôn luôn để lại những cặp 1, 2, và 4, nếu có. 1, 2, và 4 ở đây chính là những lũy thừa của 2 (distinct powers of 2). Bất kỳ con số nào cũng là tổng số của những lũy thừa nầy. Ví dụ: 5 là tổng số của 2² 0   2⁰ = 4 0   1 = 5.

  

  

2.      Chìa khóa lý thuyết của trò chơi là tổng số nhị phân (binary digital sum) của kích thước quân số các hàng quân, nghĩa là, phép cộng nhị phân nhưng không giữ (carries), nghĩa là cột nào biết cột đó, như 5 5 = 10 thì kết quả là 0, thế thôi, không giữ 1 cho cột bên trái. Nếu hai hạng số giống nhau thì tổng bằng 0, ngược lại thì bằng 1. Phép tính còn có tên là XOR với dấu vi tính là ^ hay ⊕. Tổng số của phép tính đó thường được gọi là NIM SUM (như x ⊕ y – để phân biệt với x y).

  

  

Về Nim-Sum nầy, có một phép tính tương ứng thường dễ tính nhẩm hơn; đó là diễn tả quân số các hàng như là tổng số những lũy thừa của 2 (distinct powers of 2) như đề cập bên trên, sau đó bỏ hết những cặp lũy thừa bằng nhau và cộng gộp những gì còn lại. Ví dụ:

  

  

Theo Normal mode, muốn thắng, mỗi lượt đi phải để lại một Nim-Sum = 0. Chiến lược nầy luôn luôn có thể thực hiện nếu Nim-Sum hiện có khác 0. Ngược lại, nếu Nim-Sum hiện có bằng 0 thì đấu thủ sắp đi sẽ thua nếu đối phương không mắc phải sai lầm. Phép đi đúng là kết quả của những tính toán sau đây;

-          Cho X bằng Nim-Sum của các quân số hiện có

-          XOR X với quân số mỗi hàng và tìm xem quân số nào bị giảm bớt và ghi nhận kết quả bị giảm

-          Lấy quân ở hàng đó sao cho quân số bằng với kết quả vừa ghi nhận. Ví dụ:

  

A ⊕ X = 3 ⊕ 2 = 1 [vì (011) ⊕ (010) = 001 ]

B ⊕ X = 4 ⊕ 2 = 6

C ⊕ X = 5 ⊕ 2 = 7

Hàng duy nhất bị giảm quân là A, nên phải giảm quân của A xuống còn 1 (bằng cách lấy đi 2 quân).

Trong trường hợp đặc biệt, nếu chỉ còn hai hàng thì chiến lược là giảm quân số trong hàng lớn hơn xuống bằng hàng kia. Sau đó, bất luận đối thủ của bạn có đi nước nào thi bạn vẫn có thể áp dụng chiến thuật trên ở hàng kia.

Theo Misère mode: chiến lược nầy chỉ khác normal mode bắt đầu khi đấu thủ giảm quân ở mọi hàng xuống tối đa bằng 1 (Bước màu đỏ trong bảng bên dưới). Trong trường hợp đó, muốn thắng phải chừa lại một số lẻ những hàng có một quân (ngược với normal mode chừa lại một số chẵn nhưng hàng như thế.) Ví dụ:

  

  

Định lý: Trong một trò chơi NIM, đấu thủ nào đi trước đều có cơ hội thắng, chỉ với điều kiện là tổng quân số các hàng theo định nghĩa Nim-Sum khác 0. Bằng không đối phương sẽ thắng.

(In a normal Nim game, the player making the first move has a winning strategy if and only if the nim-sum of the sizes of the heaps is nonzero. Otherwise, the second player has a winning strategy.)

Chứng minh: Xin nhớ rằng Nim-sum (⊕) tuân theo luật chuyển cụm (associativity) và chuyển trị (commutativity), đồng thời thỏa mãn đặc tính x ⊕ x = 0.

[Associativity: a (bc) = (ab)c.

Commutativity: a b = b a]

Cho x₁, ..., x_n  là những quân số của các hàng trước khi lấy quân, và y₁, ..., y_n là những quân số tương ứng sau khi lấy quân. Cho s = x₁ ⊕ ... ⊕ x_n và t = y₁ ⊕ ... ⊕ y_n. Giả sử quân được lấy từ hàng k thì chúng ta có x_i = y_i với tất cả i ≠ k, and x_k > y_k.       Theo những đặc tính của  ⊕ nói trên, chúng ta có

                            t = 0 ⊕ t

                                        = s ⊕ s ⊕ t       [ 0 = s ⊕s]

                                          = s ⊕ (x₁ ⊕ ... ⊕ x_n) ⊕ (y₁ ⊕ ... ⊕ y_n)  [ s =       ⊕ of x;  t= ⊕ of y]

                                          = s ⊕ (x₁ ⊕ y₁) ⊕ ... ⊕ (x_n ⊕ y_n)  [Associativity]        

                                          = s ⊕ 0 ⊕ ... ⊕ 0 ⊕ (x_k ⊕ y_k) ⊕ 0 ⊕ ... ⊕ 0 [x ⊕ x = x ⊕ y=0; và (x_k ⊕ y_k) ≠ 0]

                                          = s ⊕ x_k ⊕ y_k

Nghĩa là

(*) t = s ⊕ x_k ⊕ y_k.

Kết quả này sẽ được hai bổ đề dưới đây chứng minh là chiến lược đúng theo quy nạp.

 

Bổ đề 1: Nếu s = 0 thì t ≠ 0     bất luận nước là gì. (If s = 0, then t ≠ 0 no matter what move is made.)

Chứng minh: Khi s = 0 và nếu không còn nước đi, thì theo qui ước normal, đối phương đương nhiên thua. Ngược lại, bất kỳ động thái nào trong hàng k cũng sẽ cho t = x_k ⊕ y_k theo kết quả từ (*), nghĩa là t ≠ 0 vì       x_k ≠ y_k.

 

Bổ đề 2: Nếu s ≠ 0, thì có thể đi sao cho t = 0. (If s ≠ 0, it is possible to make a move so that t = 0.)

Chứng minh: Giả sử d là vị trí của bit cực trái khác 0 (lớn nhất) theo biểu thị nhị phân của Nim-sum s, và thử chọn hàng quân k sao cho bit ở vị thứ d của s trong hàng k (x_k ) cũng khác 0.  (Một hàng k như thế phải có vì nếu không trị nhị phân lớn nhất của s sẽ bằng 0.) Nếu đặt quân số còn lại trong hàng k tức y_k  bằng XOR của s (s ⊕ x_k) với quân số của hàng k của s nghĩa là y_k = s ⊕ x_k, chúng ta nói rằng y_k < x_k: tất cả những bits bên trái của bit d đều giống nhau trong x_k và y_k nhưng bit d mất đi một trị bằng 2^d và xuống còn 0); (và bất kỳ thay đổi nào trong những bits còn lại của Nim-sum cũng tối đa bằng 2^d−1.) Như thế ai đi trước có thể lấy một số quân bằng x_k − y_k trong hàng k, và:

t = s ⊕ x_k ⊕ y_k           (theo (*))

              = s ⊕ x_k ⊕ (s ⊕ x_k)  [Associativity và s ⊕ s = 0]

              = 0.

              = 0.

Reference: http://en.wikipedia.org/wiki/Nim#Mathematical_theory

 

Ví dụ: