Pendahuluan: Kepastian Mutlak di Balik Aturan Sederhana — Permainan Kombinatorial Imparsial

Di atas meja terdapat tiga tumpukan batu yang masing-masing berisi $3$, $4$, dan $5$ batu. Dua pemain bergiliran melangkah; pada setiap giliran, seorang pemain memilih satu tumpukan bebas dan mengambil minimal satu batu (boleh juga mengambil seluruh tumpukan). Pemain yang mengambil batu terakhir dinyatakan menang. Inilah permainan Nim yang legendaris dan diabadikan dalam film klasik karya Alain Resnais, Last Year at Marienbad. Sekilas permainan ini tampak seperti adu psikologi dan tebak-tebakan taktis; namun di mata matematikawan, pemenangnya sudah terkunci $100\,\%$ bahkan sebelum langkah pertama dimulai: selama pemain pertama memahami invarian aljabar yang tersembunyi di balik representasi biner, ia pasti menang apa pun langkah balasan lawan.

Dalam matematika modern, kelas permainan ini disebut permainan kombinatorial imparsial (Impartial Combinatorial Games) dan memenuhi lima aksioma: (1) dua pemain melangkah secara bergantian; (2) informasi sempurna (Perfect Information) tanpa kartu tersembunyi; (3) deterministik tanpa dadu atau faktor kebetulan; (4) imparsialitas, artinya dari posisi mana pun himpunan langkah sah yang tersedia persis sama bagi kedua pemain (berbeda dengan permainan partisan seperti catur atau go, di mana tiap pemain hanya boleh menggerakkan buah miliknya sendiri); serta (5) terminasi berhingga, yang menjamin permainan pasti berakhir dalam jumlah langkah berhingga pada graf asiklik berarah (DAG). Di bawah aturan standar — konvensi permainan normal (Normal Play Convention) — pemain pertama yang kehabisan langkah sah dinyatakan kalah (ekuivalen dengan pemain yang melakukan langkah terakhir menang).

Melalui induksi mundur (Teorema Zermelo), seluruh posisi dalam permainan imparsial terbagi secara tunggal menjadi dua kelas saling lepas: posisi-$\mathcal{P}$ (Previous-player winning, posisi kalah bagi pemain yang sedang mendapat giliran jalan) dan posisi-$\mathcal{N}$ (Next-player winning, posisi menang bagi pemain yang sedang mendapat giliran jalan). Definisi rekursifnya sangat jernih: semua posisi terminal tanpa langkah adalah posisi-$\mathcal{P}$; suatu posisi adalah posisi-$\mathcal{N}$ jika terdapat setidaknya satu langkah sah menuju posisi-$\mathcal{P}$; dan suatu posisi adalah posisi-$\mathcal{P}$ jika semua langkah sah darinya selalu berujung pada posisi-$\mathcal{N}$.

  flowchart TD
    A["Impartial Game Position G"] --> B{"Compute Grundy Value g(G)"}
    B -->|"g(G) > 0"| C["N-Position: Next Player Wins"]
    B -->|"g(G) = 0"| D["P-Position: Previous Player Wins"]
    C -->|"Optimal Move: Choose option G' with g(G') = 0"| D
    D -->|"Every Legal Move: Flips at least one bit"| C

1. Terobosan Charles Bouton (1901): XOR Biner (Nim-sum) dan Dua Lema Invariansi

Jika terdapat banyak tumpukan dengan jutaan batu, induksi mundur langsung pada graf status akan mengalami ledakan eksponensial. Pada tahun 1901, matematikawan Universitas Harvard Charles Leonard Bouton menerbitkan makalah bersejarah yang memecahkan permainan Nim secara tuntas. Ia menemukan bahwa kuncinya adalah menuliskan ukuran setiap tumpukan dalam bilangan biner lalu menghitung jumlah XOR bit-demi-bit (Bitwise XOR, disebut jumlah Nim atau Nim-sum).

Untuk posisi $(n_1, n_2, \dots, n_k)$, jumlah Nim didefinisikan sebagai $S = n_1 \oplus n_2 \oplus \dots \oplus n_k$. Operasi $\oplus$ adalah penjumlahan biner tanpa simpanan (carry-less addition) di atas medan hingga $\mathbb{F}_2 = ext{GF}(2)$ (komutatif, asosiatif, dan memenuhi $x \oplus x = 0$). Teorema Bouton menyatakan: Suatu posisi Nim $(n_1, \dots, n_k)$ adalah posisi kalah (posisi-$\mathcal{P}$) jika dan hanya jika jumlah Nim-nya $S = 0$, dan merupakan posisi menang (posisi-$\mathcal{N}$) jika dan hanya jika $S eq 0$.

Pembuktiannya bertumpu pada dua lema aljabar yang sangat elegan: Pertama: Dari posisi mana pun dengan $S = 0$, setiap langkah sah pasti menghasilkan $S' eq 0$. Jika pemain mengurangi tumpukan ke-$i$ dari $n_i$ menjadi $n_i' < n_i$, representasi biner $n_i$ dan $n_i'$ pasti berbeda setidaknya pada satu bit, sehingga $n_i \oplus n_i' eq 0$. Jumlah Nim yang baru adalah $S' = S \oplus n_i \oplus n_i' = 0 \oplus (n_i \oplus n_i') eq 0$. Artinya, pemain yang menerima kondisi $S=0$ terpaksa menyerahkan posisi menang $S' eq 0$ kepada lawannya. Kedua: Dari posisi mana pun dengan $S eq 0$, selalu ada setidaknya satu langkah sah yang menghasilkan $S' = 0$. Perhatikan bit paling signifikan (Most Significant Bit, MSB) yang bernilai $1$ pada representasi biner $S eq 0$, misalkan pada kolom ke-$d$. Karena bit ke-$d$ dari $S$ bernilai $1$, pasti terdapat sejumlah ganjil (minimal satu) tumpukan $n_i$ yang bit ke-$d$-nya juga bernilai $1$. Pilih tumpukan $n_i$ tersebut dan tetapkan ukuran barunya menjadi $n_i' = n_i \oplus S$. Karena baik $n_i$ maupun $S$ memiliki bit $1$ di kolom $d$, hasil XOR mengubah bit ke-$d$ pada $n_i'$ menjadi $0$, sedangkan semua bit yang lebih tinggi tidak berubah. Maka berlaku tegas $n_i' < n_i$! Mengambil $n_i - (n_i \oplus S)$ batu adalah langkah sah, dan jumlah Nim baru menjadi $S' = S \oplus n_i \oplus n_i' = S \oplus n_i \oplus (n_i \oplus S) = 0$. Pada contoh awal $(3, 4, 5)$, kita punya $S = 3 \oplus 4 \oplus 5 = 2 = (010)_2 eq 0$. Bit tertinggi bernilai $2$, yang dimiliki oleh $n_1 = 3 = (011)_2$. Pemain pertama mengubah tumpukan pertama menjadi $n_1' = 3 \oplus 2 = 1$, menyisakan $(1, 4, 5)$ dengan $1 \oplus 4 \oplus 5 = 0$ dan mengunci kemenangan!

2. Teorema Sprague-Grundy (1935/1939): Setiap Permainan Imparsial Isomorfik dengan Nim

Lebih dari tiga dekade setelah Bouton, Roland Sprague (1935) dan Patrick Michael Grundy (1939) secara independen menemukan teorema universal yang mengguncang matematika diskrit: bukan hanya Nim, melainkan setiap permainan kombinatorial imparsial berhingga di bawah konvensi normal secara matematis isomorfik dengan satu tumpukan Nim berukuran tertentu!

Untuk membangun isomorfisme ini, kita memperkenalkan nilai minimum yang dikecualikan (Minimum Excluded Value, $ ext{mex}$) dan bilangan Grundy (Grundy Value atau Nimber). Untuk himpunan bagian berhingga bilangan bulat tak-negatif $A \subset \mathbb{N}_0$, $ ext{mex}(A)$ adalah bilangan bulat tak-negatif terkecil yang tidak ada di $A$ (misalnya $ ext{mex}(\emptyset) = 0$, $ ext{mex}(\{0, 1, 3\}) = 2$). Untuk setiap posisi $u$ pada graf permainan, bilangan Grundy $\mathcal{G}(u)$ didefinisikan secara rekursif sebagai $ ext{mex}$ dari himpunan bilangan Grundy seluruh posisi penerus $v$ yang dapat dicapai dalam satu langkah. Dua sifat fundamental langsung terlihat: (1) $\mathcal{G}(u) = 0$ jika dan hanya jika tidak ada penerus bernilai $0$, yakni $u$ adalah posisi-$\mathcal{P}$; (2) jika $\mathcal{G}(u) = g > 0$, maka untuk setiap bilangan bulat $m$ dengan $0 \le m < g$ terdapat setidaknya satu penerus $v$ dengan $\mathcal{G}(v) = m$. Ini persis perilaku satu tumpukan Nim berisi $g$ batu!

Lebih jauh lagi, ketika kita menggabungkan beberapa permainan imparsial independen $G_1, G_2, \dots, G_k$ menjadi jumlah disjungtif (Disjunctive Sum) $G = G_1 + G_2 + \dots + G_k$ (setiap giliran pemain memilih salah satu sub-permainan dan melangkah di sana hingga semuanya berakhir), Teorema Sprague-Grundy membuktikan bahwa bilangan Grundy permainan gabungan sama persis dengan XOR bit-demi-bit dari bilangan Grundy masing-masing sub-permainan: $\mathcal{G}(G_1 + \dots + G_k) = \mathcal{G}(G_1) \oplus \dots \oplus \mathcal{G}(G_k)$. Bahkan jika suatu sub-permainan mengizinkan langkah menuju bilangan Grundy yang lebih besar (setara dengan menambah batu ke tumpukan), lawan selalu dapat langsung menetralkannya kembali ke nilai semula. Dengan demikian, permainan graf atau pembagian serumit apa pun dapat direduksi menjadi perhitungan $ ext{mex}$ dan XOR!

  flowchart TD
    G1["Subgame G1: Grundy Value g(G1)"] --> XOR["Bitwise XOR Sum: S = g(G1) XOR g(G2) XOR g(G3)"]
    G2["Subgame G2: Grundy Value g(G2)"] --> XOR
    G3["Subgame G3: Grundy Value g(G3)"] --> XOR
    XOR -->|"Sprague-Grundy Isomorphism"| NIM["Equivalent to 3-Heap Nim (g(G1), g(G2), g(G3))"]

3. Aplikasi Klasik dan Jebakan Konvensi Misère

Teorema Sprague-Grundy memberi kita pisau bedah untuk membedah berbagai permainan:

• Permainan Pengurangan (Subtraction Games, permainan Bachet): setiap giliran hanya boleh mengambil $1$ sampai $m$ batu. Diperoleh secara periodik $\mathcal{G}(n) = n mod (m+1)$, sehingga posisi kalah terjadi tepat ketika $n$ kelipatan $m+1$.
• Permainan Pembelahan: Kayles dan Catur Dawson: dalam permainan boling Kayles, terdapat $n$ pin berjajar dan setiap lemparan merobohkan $1$ pin atau $2$ pin bersebelahan. Hal menarik terjadi saat pin di tengah barisan dirobohkan: barisan awal terbelah menjadi dua sub-barisan independen berukuran $a$ dan $b$! Berdasarkan Teorema Sprague-Grundy, posisi baru ekuivalen dengan jumlah disjungtif kedua sub-barisan sehingga nilai Grundy-nya langsung $\mathcal{G}(a) \oplus \mathcal{G}(b)$. Dengan pemrograman dinamis $O(n^2)$, seluruh barisan nilai Grundy dapat dihitung (dan bersifat periodik murni dengan periode $12$ mulai $n \ge 72$).
• Konvensi Misère (Misère Play — pengambil batu terakhir kalah): bagaimana jika aturan dibalik sehingga pemain yang mengambil batu terakhir kalah? Banyak pemula keliru mengira cukup membalik posisi $\mathcal{P}$ dan $\mathcal{N}$. Bouton membuktikan aturan eksak Misère Nim: selama masih ada minimal dua tumpukan berukuran lebih dari $1$, bermainlah persis seperti Nim normal (pertahankan $S = 0$). Hanya pada langkah tepat yang untuk pertama kalinya akan menyisakan semua tumpukan berukuran $1$, ubahlah langkah agar menyisakan jumlah ganjil tumpukan berukuran $1$ (yakni $S = 1$)! Namun, untuk permainan imparsial umum di bawah aturan Misère, Teorema Sprague-Grundy runtuh sepenuhnya; baru pada awal abad ke-21 Thane Plambeck dan Aaron Siegel mengembangkan teori kuosien Misère (Misère Quotients) berbasis monoid komutatif untuk memetakan struktur aljabarnya.