Trò chơi Nim và định lý Sprague-Grundy

Mức độ: Nâng cao

Bài Vị trí thắng, vị trí thua giải được trò chơi một đống sỏi. Khi có nhiều đống và mỗi lượt chọn một đống để đi, số vị trí tăng rất nhanh (10 đống, mỗi đống 100 viên là 101¹⁰ vị trí), không lập bảng được. Bài này dạy hai công cụ giải quyết chuyện đó: phép XOR cho trò chơi Nim, và số Grundy cho mọi trò chơi khác.

Các bạn cần biết phép XOR trong bài Phép toán bit.

Trò chơi Nim

Có nhiều đống sỏi. Mỗi lượt, người chơi chọn một đống và bốc bao nhiêu viên cũng được (ít nhất 1) từ đống đó. Ai bốc viên cuối cùng thì thắng.

Định lý (Bouton): người đi trước thua khi và chỉ khi XOR số sỏi của mọi đống bằng 0.

Ví dụ ba đống 3, 4, 5. Viết theo hệ nhị phân rồi XOR từng cột (cột nào có lẻ số chữ số 1 thì kết quả là 1):

Đống	Nhị phân
3	011
4	100
5	101
XOR	010 = 2

XOR bằng 2, khác 0, nên người đi trước thắng. Nước đi thắng: tìm đống a mà a XOR 2 nhỏ hơn a. Đống 3: 3 XOR 2 = 1, nhỏ hơn 3. Bốc đống 3 còn 1 viên, ba đống thành 1, 4, 5 và 1 XOR 4 XOR 5 = 0.

Vì sao đúng? Gọi X là XOR của mọi đống.

Nếu X = 0: bốc ở một đống làm số viên đống đó đổi, ít nhất một bit đổi, nên X thành khác 0.
Nếu X khác 0: xét bit cao nhất của X, có một đống a có bit đó bằng 1. Khi đó a XOR X nhỏ hơn a (bit cao nhất đó tắt, các bit cao hơn giữ nguyên). Bốc đống a còn a XOR X viên thì X thành 0.

Người gặp X = 0 chỉ có thể trả lại X khác 0, còn người gặp X khác 0 luôn đưa được về 0. Vị trí cuối cùng (mọi đống bằng 0) có X = 0, nên người gặp X = 0 là người thua.

Số Grundy

Với một trò chơi bất kỳ (bốc theo tập nước đi, chia đống, đi quân cờ…), mỗi vị trí v có một số Grundy g(v):

g(v) = mex của tập các g(w), với w là mọi vị trí đi tới được từ v.

mex của một tập số tự nhiên là số tự nhiên nhỏ nhất không có trong tập: mex(0, 1, 3) = 2, mex(1, 2) = 0, mex của tập rỗng là 0.

Ví dụ trò chơi bốc 1, 2 hoặc 3 viên:

n	0	1	2	3	4	5	6	7	8
g(n)	0	1	2	3	0	1	2	3	0

g(4) = mex(g(3), g(2), g(1)) = mex(3, 2, 1) = 0. Ta thấy g(n) = n % 4.

Hai tính chất quan trọng:

g(v) = 0 khi và chỉ khi v là vị trí thua. Quy tắc mex chính là quy tắc thắng thua ở bài trước: không có nước đi nào tới vị trí thua (g = 0) thì 0 không có trong tập, nên mex bằng 0.
Một đống Nim có n viên thì g = n (đi được tới mọi số nhỏ hơn).

Định lý Sprague-Grundy

Nhiều trò chơi độc lập chơi cùng lúc, mỗi lượt chọn một trò chơi để đi một nước, ai không đi được ở mọi trò chơi thì thua. Gọi đó là tổng các trò chơi.

Định lý: số Grundy của tổng bằng XOR các số Grundy của từng trò chơi.

Vậy mỗi trò chơi thành phần giống như một đống Nim có g viên. Người đi trước thua khi và chỉ khi XOR các số Grundy bằng 0.

Ví dụ ba đống 5, 6, 7, mỗi lượt chọn một đống và bốc 1, 2 hoặc 3 viên từ đống đó. Số Grundy từng đống là 5 % 4 = 1, 6 % 4 = 2, 7 % 4 = 3, XOR là 1 XOR 2 XOR 3 = 0: người đi trước thua.

Python
C++

def mex(tap):
    m = 0
    while m in tap:
        m += 1
    return m

def bang_grundy(n, nuoc_di):
    g = [0] * (n + 1)
    for i in range(1, n + 1):
        g[i] = mex({g[i - k] for k in nuoc_di if k <= i})
    return g

g = bang_grundy(100, [1, 2, 3])
x = 0
for dong in [5, 6, 7]:
    x ^= g[dong]
print("TRƯỚC" if x != 0 else "SAU")      # SAU

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n = 100;
    vector<int> nuocDi = {1, 2, 3};
    vector<int> g(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        vector<bool> co(nuocDi.size() + 2, false);   // mex không vượt quá số nước đi
        for (int k : nuocDi)
            if (k <= i && g[i - k] < (int)co.size()) co[g[i - k]] = true;
        while (co[g[i]]) g[i]++;
    }
    int x = 0;
    for (int dong : {5, 6, 7}) x ^= g[dong];
    cout << (x != 0 ? "TRƯỚC" : "SAU") << endl;  // SAU
    return 0;
}

Lưu ý: mex của k số không vượt quá k, nên khi tính mex chỉ cần đánh dấu các số nhỏ hơn hoặc bằng k.

Khi một nước đi tách trò chơi làm hai

Nhiều trò chơi có nước đi tách một phần thành hai phần độc lập, ví dụ chia một đống thành hai đống, hoặc đánh đổ một ki ở giữa hàng ki. Vị trí sau nước đi đó là tổng của hai phần, nên số Grundy của nó là g(phần 1) XOR g(phần 2). Khi tính mex, đưa các giá trị XOR này vào tập.

Ví dụ trò chơi chia đống: mỗi lượt chọn một đống và chia thành hai đống có số viên khác nhau. g(1) = g(2) = 0 (không chia được), g(3) = mex(g(1) XOR g(2)) = mex(0) = 1, g(4) = mex(g(1) XOR g(3)) = mex(1) = 0 (4 chỉ chia được thành 1 và 3, vì 2 và 2 bằng nhau).

Luyện tập

Gồm 20 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Trò chơi Nim

Bài 1. Trò chơi Nim

Dòng đầu là n (1 ≤ n ≤ 10⁵), dòng sau là số sỏi a₁, …, a_n của n đống (0 ≤ a_i ≤ 10¹⁸). Mỗi lượt, người chơi chọn một đống và bốc bao nhiêu viên cũng được (ít nhất 1). Ai bốc viên cuối cùng thì thắng. In ra TRƯỚC nếu người đi trước thắng, SAU nếu ngược lại.

Ví dụ:

Nhập	In ra
`3` `3 4 5`	`TRƯỚC`

Kiểm tra: nhập

5
1 2 3 4 5

Xem đáp số

TRƯỚC

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Đếm nước đi thắng

Cùng dữ liệu như bài 1. Có bao nhiêu nước đi giúp người đi trước chắc chắn thắng? (Hai nước đi khác nhau nếu khác đống hoặc khác số viên bốc.)

Ví dụ:

Nhập	In ra
`3` `3 4 5`	`1`

Kiểm tra: nhập

6
7 11 13 2 9 5

Xem đáp số

3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Nước đi đầu tiên

Cùng dữ liệu như bài 1. Nếu người đi trước thắng, in ra chỉ số đống (đánh số từ 1) và số viên cần bốc ở lượt đầu; nếu có nhiều cách, chọn đống có chỉ số nhỏ nhất. Nếu người đi trước thua, in ra 0.

Ví dụ:

Nhập	In ra
`3` `3 4 5`	`1 2`

Kiểm tra: nhập

6
7 11 13 2 9 5

Xem đáp số

2 7

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 4. Nim, ai lấy viên cuối thì thua

Như bài 1 nhưng ai bốc viên cuối cùng thì thua. Dòng đầu là n (1 ≤ n ≤ 10⁵), dòng sau là a₁, …, a_n (1 ≤ a_i ≤ 10¹⁸). In ra TRƯỚC hoặc SAU.

Ví dụ:

Nhập	In ra
`3` `1 1 1`	`SAU`

Kiểm tra: nhập

4
3 5 6 1

Xem đáp số

TRƯỚC

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Nim giới hạn số viên

Có n đống, mỗi lượt chọn một đống và bốc từ 1 đến k viên. Ai bốc viên cuối cùng thì thắng. Dòng đầu là n, k (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 10¹⁸), dòng sau là a₁, …, a_n (0 ≤ a_i ≤ 10¹⁸). In ra TRƯỚC hoặc SAU.

Ví dụ:

Nhập	In ra
`3 3` `5 6 7`	`SAU`

Kiểm tra: nhập

5 4
10 11 12 13 14

Xem đáp số

TRƯỚC

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Số Grundy

Bài 6. Số Grundy của một đống

Dòng đầu là n, m (0 ≤ n ≤ 10⁶, 1 ≤ m ≤ 10). Dòng sau là tập nước đi s₁, …, s_m (các số nguyên dương khác nhau, không quá 100): mỗi lượt bốc đúng s_i viên. In ra số Grundy của đống n viên.

Ví dụ:

Nhập	In ra
`7 3` `1 3 4`	`0`

Kiểm tra: nhập

1000000 4
2 5 7 11

Xem đáp số

1

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Nhiều đống với tập nước đi

Dòng đầu là n, m (1 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10). Dòng thứ hai là tập nước đi như bài 6. Dòng thứ ba là số sỏi a₁, …, a_n của n đống (0 ≤ a_i ≤ 10⁵). Mỗi lượt chọn một đống và bốc theo tập nước đi. Ai không đi được thì thua. In ra TRƯỚC hoặc SAU.

Ví dụ:

Nhập	In ra
`3 3` `1 3 4` `2 5 7`	`TRƯỚC`

Kiểm tra: nhập

6 3
2 3 5
100000 99999 12345 777 2026 1

Xem đáp số

TRƯỚC

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Chia đống thành hai phần khác nhau

Có n đống sỏi. Mỗi lượt, người chơi chọn một đống và chia nó thành hai đống khác rỗng có số viên khác nhau. Ai không chia được thì thua. Dòng đầu là n (1 ≤ n ≤ 10⁵), dòng sau là a₁, …, a_n (1 ≤ a_i ≤ 2000). In ra TRƯỚC hoặc SAU.

Ví dụ:

Nhập	In ra
`1` `4`	`SAU`

Kiểm tra: nhập

5
2026 1000 777 13 5

Xem đáp số

TRƯỚC

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 9. Bốc hoặc chia đống

Có n đống sỏi. Mỗi lượt, người chơi chọn một đống và hoặc bốc từ đó bao nhiêu viên cũng được (ít nhất 1), hoặc chia nó thành hai đống khác rỗng (số viên bất kỳ). Ai bốc viên cuối cùng thì thắng. Dòng đầu là n (1 ≤ n ≤ 10⁵), dòng sau là a₁, …, a_n (0 ≤ a_i ≤ 10¹⁸). In ra TRƯỚC hoặc SAU.

Ví dụ:

Nhập	In ra
`2` `3 4`	`TRƯỚC`

Kiểm tra: nhập

5
1000000000000000000 999999999999999999 7 8 2026

Xem đáp số

TRƯỚC

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Đánh đổ ki

Một hàng ki được mô tả bằng xâu gồm ký tự I (ki đang đứng) và . (chỗ trống), dài không quá 1000. Mỗi lượt, người chơi đánh đổ 1 ki, hoặc 2 ki đứng cạnh nhau (liền kề, không có chỗ trống ở giữa). Ai đánh đổ ki cuối cùng thì thắng. In ra TRƯỚC hoặc SAU.

Ví dụ: nhập III.II thì in ra TRƯỚC.

Kiểm tra: nhập IIIIIII.IIII.III..IIIIIIIIIIIII.I.

Xem đáp số

SAU

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Quân cờ và đồng xu

Bài 11. Nhiều quân xe

Trên bàn cờ rất lớn có k quân xe (các quân có thể đứng chung ô). Mỗi lượt, người chơi chọn một quân và di chuyển nó sang trái hoặc xuống dưới bao nhiêu ô cũng được (ít nhất 1, không ra ngoài bàn, ô góc là (0, 0)). Ai không đi được thì thua. Dòng đầu là k (1 ≤ k ≤ 10⁵), k dòng sau là tọa độ x, y của từng quân (0 ≤ x, y ≤ 10¹⁸). In ra TRƯỚC hoặc SAU.

Ví dụ:

Nhập	In ra
`1` `3 3`	`SAU`

Kiểm tra: nhập

Xem đáp số

TRƯỚC

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 12. Nhiều quân vua

Như bài 11 nhưng là k quân vua: mỗi lượt chọn một quân và đi sang trái 1 ô, xuống 1 ô, hoặc chéo xuống trái 1 ô. Dòng đầu là k (1 ≤ k ≤ 10⁵), k dòng sau là tọa độ x, y (0 ≤ x, y ≤ 1000). In ra TRƯỚC hoặc SAU.

Ví dụ:

Nhập	In ra
`2` `1 1` `2 0`	`TRƯỚC`

Kiểm tra: nhập

Xem đáp số

TRƯỚC

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 13. Nhiều quân mã

Bàn cờ N × N, ô (x, y) với 1 ≤ x, y ≤ N. Có k quân mã, mỗi lượt chọn một quân và đi một trong bốn nước (x - 2, y + 1), (x - 2, y - 1), (x + 1, y - 2), (x - 1, y - 2), phải ở trong bàn (các quân có thể đứng chung ô). Ai không đi được thì thua. Dòng đầu là N, k (1 ≤ N ≤ 500, 1 ≤ k ≤ 10⁵), k dòng sau là tọa độ các quân. In ra TRƯỚC hoặc SAU.

Ví dụ:

Nhập	In ra
`15 2` `5 4` `3 3`	`TRƯỚC`

Kiểm tra: nhập

Xem đáp số

TRƯỚC

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 14. Lật đồng xu

Hàng đồng xu được mô tả bằng xâu gồm N (ngửa) và S (sấp), dài không quá 10⁵, đồng xu thứ nhất ở bên trái. Mỗi lượt, người chơi chọn một đồng ngửa, lật nó thành sấp, và có thể (không bắt buộc) lật thêm một đồng bất kỳ nằm bên trái nó (ngửa thành sấp hoặc sấp thành ngửa). Ai không đi được (mọi đồng đều sấp) thì thua. In ra TRƯỚC hoặc SAU.

Ví dụ: nhập NSNS thì in ra TRƯỚC.

Kiểm tra: nhập SNNSNSSNSNNNSSNS.

Xem đáp số

TRƯỚC

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 15. Nim bậc thang

Cầu thang có n bậc, đánh số 1 đến n từ dưới lên, bậc i có a_i viên sỏi. Mỗi lượt, người chơi chọn một bậc i có sỏi và chuyển ít nhất 1 viên từ bậc i xuống bậc i - 1 (sỏi ở bậc 1 chuyển xuống thì rơi ra ngoài, mất luôn). Ai không đi được thì thua. Dòng đầu là n (1 ≤ n ≤ 10⁵), dòng sau là a₁, …, a_n (0 ≤ a_i ≤ 10¹⁸). In ra TRƯỚC hoặc SAU.

Ví dụ:

Nhập	In ra
`3` `1 2 1`	`SAU`

Kiểm tra: nhập

6
3 1 4 1 5 9

Xem đáp số

TRƯỚC

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Vận dụng

Bài 16. Nim trên đoạn

Dãy a₁, …, a_n (n ≤ 2 × 10⁵, 0 ≤ a_i ≤ 10¹⁸). Có q câu hỏi (q ≤ 2 × 10⁵), mỗi câu cho l, r: chơi Nim với các đống a_l, …, a_r, ai thắng? Dòng đầu là n, q, dòng thứ hai là dãy a, q dòng sau là các cặp l r. In mỗi câu trả lời (TRƯỚC hoặc SAU) trên một dòng.

Ví dụ:

Nhập	In ra
`5 3` `3 4 5 1 1` `1 3` `1 5` `4 5`	`TRƯỚC` `TRƯỚC` `SAU`

Kiểm tra: nhập

8 4
7 11 13 2 9 5 6 3
1 8
2 4
6 8
5 5

Xem đáp số

TRƯỚC
TRƯỚC
SAU
TRƯỚC

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 17. Đếm đoạn người đi trước thua

Dãy a₁, …, a_n (1 ≤ n ≤ 2 × 10⁵, 0 ≤ a_i ≤ 10¹⁸). Có bao nhiêu đoạn con [l, r] (1 ≤ l ≤ r ≤ n) mà khi chơi Nim với các đống a_l, …, a_r thì người đi trước thua? Dòng đầu là n, dòng sau là dãy a.

Ví dụ:

Nhập	In ra
`5` `3 4 5 1 1`	`2`

Kiểm tra: nhập

10
1 2 3 1 2 3 0 4 4 7

Xem đáp số

12

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 18. Đếm nước đi thắng với tập nước đi

Như bài 7 (n đống, tập nước đi s₁, …, s_m, a_i ≤ 10⁵). Có bao nhiêu nước đi giúp người đi trước chắc chắn thắng? (Nước đi là cặp: đống nào, bốc bao nhiêu.)

Ví dụ:

Nhập	In ra
`3 3` `1 3 4` `2 5 7`	`1`

Kiểm tra: nhập

5 3
2 3 5
100 37 64 999 2026

Xem đáp số

6

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 19. Ba trò chơi cùng lúc

Ba trò chơi được chơi cùng lúc, mỗi lượt chọn một trò chơi để đi một nước, ai không đi được ở cả ba thì thua. Dòng 1: một đống Nim có a viên. Dòng 2: một đống b viên, mỗi lượt bốc 1, 2 hoặc 3 viên. Dòng 3: một quân xe ở (x, y), mỗi lượt đi sang trái hoặc xuống bao nhiêu ô cũng được (như bài 11). Mọi số không quá 10¹⁸. In ra TRƯỚC hoặc SAU.

Ví dụ:

Nhập	In ra
`5` `6` `3 1`	`TRƯỚC`

Kiểm tra: nhập

123456789
987654321
1000 2026

Xem đáp số

TRƯỚC

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 20. Số Grundy có chu kỳ

Như bài 7 nhưng số sỏi mỗi đống tới 10¹⁸: dòng đầu là n, m (1 ≤ n ≤ 10⁵, 1 ≤ m ≤ 10), dòng thứ hai là tập nước đi (các số không quá 10), dòng thứ ba là a₁, …, a_n (0 ≤ a_i ≤ 10¹⁸). In ra TRƯỚC hoặc SAU.

Ví dụ:

Nhập	In ra
`3 3` `1 3 4` `1000000000000000000 5 7`	`TRƯỚC`

Kiểm tra: nhập

4 3
2 5 7
123456789123456789 987654321987654321 2026 1

Xem đáp số

TRƯỚC

Hướng dẫn giải chi tiết: liên hệ tác giả.

Th.S Trần Huy Phúc

Kỹ sư phần mềm @Adnovum & Bumbii Academy

Học Tiếng Anh với Bumbii English