Nim là bài toán hai người lần lượt bốc sỏi từ nhiều đống: mỗi lượt chọn một đống và bốc bao nhiêu viên tuỳ ý (ít nhất một), ai bốc viên cuối cùng thắng. Cách giải: viết số viên mỗi đống ra số nhị phân, cộng các số đó theo kiểu không nhớ; nếu kết quả bằng 0, người sắp đi đang ở thế thua, nếu khác 0, người sắp đi thắng được.
Người nắm thế thắng chỉ cần mỗi lượt đưa tổng không nhớ về 0. Quy tắc này đúng với mọi số đống và mọi số viên, nên Nim là một trong ít cuộc đấu được giải trọn vẹn bằng một phép tính. Dưới đây là cách cộng không nhớ cho người chưa quen nhị phân, lời giải mẫu từng bước, lý do quy tắc đúng, và cách chỉnh khi luật đổi thành ai bốc viên cuối là thua.
Viết số viên ra nhị phân
Nhị phân chỉ dùng hai chữ số 0 và 1. Mỗi cột có một giá trị: cột phải nhất là 1, cột kế là 2, rồi 4, rồi 8. Một số được viết bằng cách chọn những cột cộng lại ra số đó. Với các đống từ 1 đến 7 viên, ba cột là đủ:
| Số viên | Cột 4 | Cột 2 | Cột 1 | Đọc là |
|---|---|---|---|---|
| 1 | 0 | 0 | 1 | 1 |
| 2 | 0 | 1 | 0 | 2 |
| 3 | 0 | 1 | 1 | 2 + 1 |
| 4 | 1 | 0 | 0 | 4 |
| 5 | 1 | 0 | 1 | 4 + 1 |
| 6 | 1 | 1 | 0 | 4 + 2 |
| 7 | 1 | 1 | 1 | 4 + 2 + 1 |
Đống tám viên trở lên thì thêm cột 8, cột 16 và cứ thế. Mẹo nhớ: tách số viên thành tổng các luỹ thừa của 2, mỗi luỹ thừa có mặt thì cột đó ghi 1. Ví dụ 13 = 8 + 4 + 1, nên 13 viết là 1101.
Ai không muốn dùng chữ số 0 và 1 có thể hình dung khác: mỗi đống sỏi được tách thành các nhóm nhỏ 1, 2, 4, 8 viên. Đống 5 viên là một nhóm 4 và một nhóm 1; đống 6 viên là một nhóm 4 và một nhóm 2.
Cộng không nhớ là gì
Cộng không nhớ (tổng Nim) là cộng từng cột riêng rẽ, rồi chỉ giữ lại chẵn hay lẻ: cột nào có số chữ 1 là số lẻ thì kết quả cột đó là 1, số chẵn thì là 0. Không có chuyện "nhớ 1 sang cột bên trái" như cộng thường.
Theo cách hình dung nhóm sỏi: xếp các đống cạnh nhau, đếm xem có bao nhiêu nhóm 4 viên, bao nhiêu nhóm 2 viên, bao nhiêu nhóm 1 viên. Loại nhóm nào có số lượng lẻ thì "dư" ra một. Tổng Nim bằng 0 nghĩa là mọi loại nhóm đều xuất hiện số chẵn lần — các đống "cân" nhau theo từng loại nhóm.
Ví dụ ba đống 1, 2, 3: viết ra 01, 10, 11. Cột 2 có hai chữ 1 (của 2 và 3), chẵn, ghi 0. Cột 1 có hai chữ 1 (của 1 và 3), chẵn, ghi 0. Tổng Nim là 0, nên người đi trước ở thế thua. Thử bằng tay: bốc cả đống 3 thì còn 1, 2, đối phương bốc 1 viên ở đống 2 để còn 1, 1, rồi bắt chước bạn đến hết. Bốc ở đống 2 hay đống 1 cũng có cách đáp tương tự.
Tại sao gọi là cộng mà lại bỏ phần nhớ? Vì trong Nim, điều quan trọng không phải tổng số sỏi mà là các đống có cân nhau theo từng loại nhóm hay không. Bốn mươi viên chia thành hai đống hai mươi là thế cân, còn chia thành hai đống mười chín và hai mươi mốt thì không.
Lời giải mẫu: ba đống 3, 4, 5 viên
Bạn đi trước. Ba đống có 3, 4 và 5 viên.
- Viết nhị phân: 3 = 011, 4 = 100, 5 = 101 (thứ tự cột 4, 2, 1).
- Cộng không nhớ từng cột: cột 4 có hai chữ 1 (của 4 và 5), chẵn, ghi 0. Cột 2 có một chữ 1 (của 3), lẻ, ghi 1. Cột 1 có hai chữ 1 (của 3 và 5), chẵn, ghi 0. Tổng Nim là 010, tức là 2. Khác 0 nên bạn ở thế thắng.
- Tìm đống để bốc: nhìn cột trái nhất có chữ 1 trong tổng, ở đây là cột 2. Chọn một đống có chữ 1 ở cột đó: chỉ có đống 3 (011).
- Tính số viên để lại: lật các cột của đống đó ở những chỗ tổng có chữ 1. Tổng là 010, nên lật cột 2 của 011 thành 001, tức là 1 viên. Bốc 3 − 1 = 2 viên từ đống thứ nhất.
- Kiểm lại: ba đống còn 1, 4, 5 = 001, 100, 101. Cột 4: hai chữ 1, chẵn. Cột 2: không có, chẵn. Cột 1: hai chữ 1, chẵn. Tổng 000. Đối phương đang ở thế thua.
- Đối phương đi, bạn đáp: giả sử họ bốc 4 viên ở đống 5, còn 1, 4, 1. Tổng: 001 + 100 + 001 không nhớ = 100, tức 4. Cột trái nhất có chữ 1 là cột 4, đống có chữ 1 ở cột đó là đống 4 viên. Lật thành 000: bốc hết 4 viên. Còn 1, 0, 1, tổng lại bằng 0.
- Kết thúc: còn hai đống một viên. Đối phương bốc một viên nào, bạn bốc viên còn lại — viên cuối cùng, bạn thắng.
Vì sao quy tắc này luôn đúng
Từ thế tổng 0, mọi nước đi đều làm tổng khác 0. Mỗi nước đi chỉ đổi đúng một đống. Đống đó đổi số viên thì ít nhất một cột của nó đổi chữ, làm số chữ 1 ở cột đó đổi từ chẵn sang lẻ. Tổng không thể còn bằng 0.
Từ thế tổng khác 0, luôn có nước đưa tổng về 0. Lấy cột trái nhất có chữ 1 trong tổng; có ít nhất một đống có chữ 1 ở cột đó (vì số chữ 1 ở cột ấy là lẻ). Lật các cột của đống này theo tổng. Cột trái nhất từ 1 thành 0, các cột bên trái nó giữ nguyên, nên số mới nhỏ hơn số cũ — tức là nước đi hợp lệ, bốc bớt chứ không thêm.
Thế kết thúc có tổng 0. Hết sỏi thì mọi đống đều 0, tổng bằng 0. Người đến lượt ở thế đó không đi được và thua. Nên thế tổng 0 là thế thua, khớp với hai ý trên.
Ai giữ thế thắng thì giữ mãi. Bạn luôn đưa tổng về 0, đối phương buộc đưa tổng khác 0, bạn lại đưa về 0. Số sỏi giảm dần nên cuộc đấu phải dừng, và người dừng ở tổng 0 khi hết sỏi là đối phương.
Biến thể: ai bốc viên cuối là thua
Khi luật đảo lại, ai bốc viên cuối cùng là thua, cách đi gần như giữ nguyên. Bạn vẫn đưa tổng không nhớ về 0 ở mọi lượt, trừ một lúc: khi nước đi theo quy tắc cũ sẽ để lại toàn những đống chỉ có một viên.
Lúc đó, thay vì để lại số đống một viên là số chẵn (quy tắc cũ cho ra như vậy), bạn để lại số đống một viên là số lẻ. Khi chỉ còn các đống một viên, hai bên chỉ việc lần lượt bốc từng đống; số đống lẻ đến lượt đối phương nghĩa là họ bốc viên cuối và thua.
Ví dụ: còn ba đống 1, 1, 4 và đến lượt bạn. Theo quy tắc cũ, bạn sẽ bốc hết đống 4 để còn 1, 1 (tổng 0). Nhưng với luật mới, 1, 1 là hai đống một viên: đối phương bốc một, bạn phải bốc viên cuối và thua. Đúng ra bạn bốc 3 viên ở đống 4, để lại 1, 1, 1 — ba đống một viên, số lẻ. Đối phương bốc một, bạn bốc một, đối phương phải bốc viên cuối.
Điểm mấu chốt: biến thể bốc cuối thua chỉ khác ở pha kết thúc. Trước đó cứ đi theo tổng không nhớ; đến khi chỉ còn đúng một đống lớn hơn một viên, hãy dừng lại đếm số đống một viên trước khi đi.
Ba thế để tự luyện, có đáp án
Che cột phải, tự tính tổng không nhớ rồi tìm nước đi, sau đó mới đối chiếu. Mỗi thế đều đến lượt bạn.
| Thế (số viên các đống) | Nhị phân và tổng không nhớ | Kết luận và nước đi |
|---|---|---|
| 2, 5, 6 | 010, 101, 110. Cột 4: hai chữ 1, chẵn. Cột 2: hai, chẵn. Cột 1: một, lẻ. Tổng 001 | Thế thắng. Chỉ đống 5 có chữ 1 ở cột 1: lật thành 100 = 4, tức bốc 1 viên. Còn 2, 4, 6, tổng 000 |
| 1, 4, 5 | 001, 100, 101. Cột 4: hai, chẵn. Cột 2: không. Cột 1: hai, chẵn. Tổng 000 | Thế thua. Đi gì cũng được, hãy chọn nước làm thế rối nhất và chờ đối phương sai |
| 3, 5, 7 | 011, 101, 111. Cột 4: hai, chẵn. Cột 2: hai, chẵn. Cột 1: ba, lẻ. Tổng 001 | Thế thắng, có ba nước đúng vì cả ba đống đều có chữ 1 ở cột 1: bốc 1 viên ở bất kỳ đống nào. Ví dụ còn 2, 5, 7 = 010, 101, 111, tổng 000 |
Thế thứ hai chính là thế mà lời giải mẫu phía trên để lại cho đối phương. Nếu bạn gặp nó ở lượt mình, nghĩa là đối phương đã tính đúng.
Nhầm lẫn hay gặp với Nim
Cộng thường thay cho cộng không nhớ. Ba đống 3, 4, 5 cộng thường ra 12, không nói lên gì. Phải cộng theo từng cột và chỉ giữ chẵn lẻ.
Chọn sai đống để bốc. Không phải đống nào cũng dùng được. Chỉ đống có chữ 1 ở cột trái nhất của tổng mới cho một nước hợp lệ; chọn đống khác thì số mới tính ra lớn hơn số cũ, tức là phải thêm sỏi — không được.
Nhầm Nim với bốc sỏi một đống có giới hạn. Bốc từ một đống, mỗi lần một đến ba viên, là bài khác: giải bằng chia lấy dư. Nim cho bốc bao nhiêu cũng được nhưng chỉ từ một đống mỗi lượt.
Áp quy tắc cũ cho luật bốc cuối thua đến tận cùng. Như ví dụ 1, 1, 4 ở trên, đi theo quy tắc cũ ở pha cuối là tự nộp thua. Luôn hỏi: luật là bốc cuối thắng hay bốc cuối thua?
Câu hỏi thường gặp
Tổng Nim bằng 0 có nghĩa là gì?
Nghĩa là khi viết số viên mỗi đống ra nhị phân, mỗi cột có số chữ 1 là số chẵn. Người sắp đi ở thế này sẽ thua nếu đối phương đi đúng, vì mọi nước đi đều làm tổng khác 0 và đối phương luôn đưa được tổng về 0.
Không biết nhị phân có giải Nim được không?
Được, bằng cách tách mỗi đống thành các nhóm 1, 2, 4, 8 viên rồi đếm xem mỗi loại nhóm xuất hiện chẵn hay lẻ lần. Mỗi loại đều chẵn là thế thua cho người sắp đi. Cách này cũng là cộng không nhớ, chỉ không dùng chữ số.
Hai đống bằng nhau thì ai thắng?
Hai đống bằng nhau có tổng Nim bằng 0, nên người đi sau thắng. Cách đi rất đơn giản: đối phương bốc bao nhiêu viên ở đống này, bạn bốc đúng bấy nhiêu ở đống kia, giữ hai đống luôn bằng nhau đến khi hết.
Có bao nhiêu nước đi đúng ở một thế thắng?
Có thể có một hoặc nhiều. Số nước đúng bằng số đống có chữ 1 ở cột trái nhất của tổng. Với ba đống 3, 4, 5 chỉ có một nước đúng là bốc 2 viên ở đống 3; với các thế khác có thể có hai hoặc ba lựa chọn.
Nim có ý nghĩa gì ngoài việc bốc sỏi?
Rất nhiều cuộc đấu hai người lần lượt đi, không may rủi, ai hết nước là thua, đều quy được về Nim bằng cách gán cho mỗi phần một con số tương đương. Hiểu Nim là có nền để phân tích những cuộc đấu ghép từ nhiều phần độc lập.