Chiến thuật XOR (Nim-sum) trong trò Bốc Sỏi Nim

Khái niệm

Trò Nim: có vài đống sỏi, mỗi lượt người chơi bốc bất kỳ số sỏi nào (từ 1 trở lên) từ một đống. Ai bốc viên cuối cùng là người thắng.

Chiến thuật thắng: tính Nim-sum = XOR tất cả số sỏi của các đống. Nếu Nim-sum ≠ 0, bạn đang ở thế thắng và phải đưa Nim-sum về 0 sau nước đi; nếu Nim-sum = 0, mọi nước đi đều đưa về thế ≠ 0 và bạn sẽ thua trước đối thủ chơi đúng.

Ví dụ

Ba đống 3, 4, 5: Nim-sum = 3 ⊕ 4 ⊕ 5 = 2 (≠ 0). Tìm một đống k sao cho k ⊕ 2 < k: 3 ⊕ 2 = 1 < 3. Bốc đống 3 xuống còn 1 → 1 ⊕ 4 ⊕ 5 = 0, đối thủ rơi vào thế thua.

Với hai đống bằng nhau, Nim-sum = 0: người đi trước ở thế thua nếu đối thủ luôn "bắt chước" nước đi ở đống còn lại.

Minh hoạ động