Tổ hợp và Toán rời rạc

Bất biến và đơn biến

Các đại lượng giữ nguyên hoặc biến đổi đơn điệu qua các bước của một quá trình tổ hợp, dùng để chứng minh điều không thể xảy ra.

Trực giácVì sao có những trò chơi không bao giờ giải được

Bỏ đi hai ô ở hai góc đối diện của bàn cờ vua $8\times 8$ , còn lại $62$ ô. Liệu có thể lát kín phần còn lại bằng $31$ quân domino kích thước $2\times 1$ không? Thử đặt bằng tay luôn thất bại, nhưng có tới hàng triệu cách đặt. Thay vì thử từng trường hợp, hãy nhìn vào màu sắc: mỗi quân domino luôn phủ đúng $1$ ô đen và $1$ ô trắng, nên $31$ quân domino phải phủ $31$ ô đen và $31$ ô trắng. Nhưng hai góc đối diện của bàn cờ có cùng màu, nên phần còn lại có $32$ ô màu này và $30$ ô màu kia! Hiệu $W - B$ là một bất biến của phép đặt domino, chứng minh sự bất khả thi chỉ trong một dòng.

Tô màu hai phía như một bất biến: mỗi cạnh (quân domino) nối một đỉnh ở mỗi phía, nên mọi cặp ghép hoàn hảo đòi hỏi số đỉnh hai bên bằng nhau.

Đại họcĐịnh nghĩa: bất biến và đơn biến

Định nghĩa: Bất biến và đơn biến của hệ trạng thái

Xét một quá trình tổ hợp với không gian trạng thái $\mathcal{S}$ và các bước chuyển hợp lệ $s \to s'$ . Một hàm $I: \mathcal{S} \to X$ gọi là bất biến nếu $I(s') = I(s)$ với mọi bước đi hợp lệ $s \to s'$ . Một hàm giá trị thực $M: \mathcal{S} \to \mathbb{R}$ gọi là đơn biến (hay hàm thế) nếu $M(s') < M(s)$ (giảm ngặt) hoặc $M(s') > M(s)$ (tăng ngặt) qua mỗi bước đi hợp lệ.

I(s_0) = I(s_1) = \cdots = I(s_k) \implies \text{if } I(s_{\mathrm{target}}) \neq I(s_0),\ s_{\mathrm{target}} \text{ is unreachable}

M(s_0) > M(s_1) > M(s_2) > \cdots \ge 0,\quad M(s) \in \mathbb{N} \implies \text{process terminates in } \le M(s_0) \text{ steps}

Các mẫu bất biến và đơn biến thường gặp trong toán thi và nghiên cứu
Công cụ	Dạng thường gặp	Điều chứng minh được
Bất biến chẵn lẻ	$S \bmod 2$ hoặc $(-1)^{\text{inversions}}$	Trạng thái đích không thể đạt tới
Bất biến đồng dư / đại số	$\sum a_i \bmod m$ hoặc giá trị đa thức	Cấu hình cuối được xác định duy nhất
Đơn biến nguyên	$M(s) \in \mathbb{N}$ với $M(s') \le M(s) - 1$	Quá trình buộc phải dừng sau $\le M(s_0)$ bước

Đại họcĐịnh lý then chốt: tính chẵn lẻ trò chơi 15 ô và định lý dừng đơn biến

Định lý: Bất biến chẵn lẻ Loyd–Johnson cho trò chơi 15 ô

Trong trò chơi trượt $15$ ô trên bảng $4\times 4$ , gọi $N(s)$ là số nghịch thế của các ô số (các cặp $(i,j)$ với $i > j$ sao cho ô $i$ đứng trước ô $j$ theo thứ tự đọc từng hàng từ trái sang phải) và $r(s) \in \{1,2,3,4\}$ là chỉ số hàng của ô trống, hay tương đương $d(s)$ là khoảng cách Manhattan của ô trống tới góc dưới phải. Khi đó tính chẵn lẻ $(N(s) + r(s)) \bmod 2$ là bất biến qua mọi bước trượt hợp lệ. Đặc biệt, cấu hình chỉ đổi chỗ hai ô $14$ và $15$ là vô nghiệm.

Vì sao đúng?

Một bước trượt ngang giữ nguyên hoàn toàn thứ tự đọc theo hàng của $15$ ô số, trong khi một bước trượt dọc đưa một ô nhảy qua đúng $3$ ô số khác trong thứ tự hàng (làm số nghịch thế thay đổi $\pm 1$ hoặc $\pm 3$ , luôn là số lẻ) và đồng thời làm hàng của ô trống $r(s)$ thay đổi $\pm 1$ .

Chứng minh

Bước 1 (trượt ngang). Khi ô trống trượt sang trái hoặc phải trong cùng một hàng, không có ô số nào đổi vị trí trong dãy đọc theo hàng của $15$ ô số, và ô trống vẫn ở hàng $r(s)$ . Do đó $\Delta N = 0$ và $\Delta r = 0$ , nên $N(s) + r(s)$ không đổi.

Bước 2 (trượt dọc). Khi ô trống trượt lên hoặc xuống, ô số $t$ chuyển vào vị trí cũ của ô trống sẽ dịch chuyển đúng $3$ vị trí trong dãy đọc theo hàng của $15$ ô số. Đi qua mỗi ô trong $3$ ô đó sẽ đảo trạng thái nghịch thế của cặp $(t, u)$ , làm $N(s)$ thay đổi $+1$ hoặc $-1$ cho mỗi ô. Tổng thay đổi là $\Delta N \in \{-3, -1, +1, +3\}$ , luôn là số lẻ. Đồng thời $\Delta r \in \{-1, +1\}$ cũng lẻ, nên $\Delta(N + r)$ là số chẵn.

Bước 3 (đổi chỗ 14 và 15). Đổi chỗ hai ô $14$ và $15$ khi ô trống giữ nguyên ở hàng $r = 4$ làm $N(s)$ tăng thêm $+1$ (từ $0$ lên $1$ ) trong khi $\Delta r = 0$ . Vì vậy $(N + r) \bmod 2$ khác nhau giữa trạng thái đầu ( $1 + 4 \equiv 1 \pmod 2$ ) và trạng thái đích ( $0 + 4 \equiv 0 \pmod 2$ ), chứng minh không có dãy bước trượt hợp lệ nào đạt tới trạng thái đích.

Định lý: Định lý dừng nhờ đơn biến trên tập sắp thứ tự tốt

Giả sử mỗi bước đi hợp lệ $s \to s'$ của một quá trình đều làm giảm một hàm nhận giá trị nguyên $M: \mathcal{S} \to \mathbb{Z}$ ít nhất $1$ đơn vị, tức $M(s') \le M(s) - 1$ , và $M(s) \ge 0$ với mọi trạng thái $s \in \mathcal{S}$ . Khi đó xuất phát từ trạng thái $s_0$ bất kỳ, quá trình buộc phải dừng sau nhiều nhất $M(s_0)$ bước.

Vì sao đúng?

Bạn không thể bước xuống một cầu thang cao $M(s_0)$ bậc quá $M(s_0)$ lần nếu mỗi bước đều xuống ít nhất một bậc và không bao giờ xuống thấp hơn tầng trệt $0$ .

Chứng minh

**Bước 1 (chặn quy nạp sau $k$ bước).** Cho $s_0 \to s_1 \to s_2 \to \cdots \to s_k$ là một dãy $k$ bước đi hợp lệ bất kỳ. Áp dụng giả thiết $M(s_{i}) \le M(s_{i-1}) - 1$ với $i = 1, 2, \dots, k$ rồi cộng dồn rút gọn cho ta $M(s_k) \le M(s_0) - k$ .

**Bước 2 (chặn trên cho $k$ ).** Vì $M(s_k) \ge 0$ với mọi trạng thái đạt được $s_k \in \mathcal{S}$ , kết hợp hai bất đẳng thức ta có $0 \le M(s_k) \le M(s_0) - k$ , suy ra ngay $k \le M(s_0)$ . Vậy không có quỹ đạo hợp lệ nào dài $k > M(s_0)$ , và quá trình phải dừng sau nhiều nhất $M(s_0)$ bước.

Nâng caoỨng dụng thực tiễn và Ví dụ minh họa

Trong kiểm chứng hình thức và kỹ nghệ phần mềm, bất biến vòng lặp và hàm xếp hạng (đơn biến) là cách chuẩn mực để các trợ lý chứng minh (Lean, Coq, Dafny) chứng nhận thuật toán trọng yếu trả về kết quả đúng và không bao giờ treo trong vòng lặp vô hạn. Trong đồng thuận phân tán và mạng bắn chip, bất biến đại số xác định những trạng thái cân bằng tải nào có thể đạt tới.

Ví dụ: Xóa hai số và viết hiệu của chúng

Trên bảng viết các số $1, 2, 3, \dots, 2026$ . Mỗi bước, ta xóa hai số $a, b$ bất kỳ và viết $|a - b|$ thay vào đó, cho đến khi chỉ còn một số. Số cuối cùng có thể bằng $0$ không?

Lời giải

Nhận xét rằng $|a - b| \equiv a + b \pmod 2$ , vì $(a + b) - |a - b| = 2\min(a,b)$ luôn là số chẵn. Do đó tính chẵn lẻ của tổng tất cả các số trên bảng, $S \bmod 2$ , là một bất biến!

Ban đầu tổng là $S_0 = \frac{2026 \times 2027}{2} = 1013 \times 2027$ . Vì cả $1013$ và $2027$ đều lẻ nên $S_0$ là số lẻ ( $S_0 \equiv 1 \pmod 2$ ). Sau $2025$ bước, số duy nhất còn lại vẫn phải đồng dư với $S_0 \equiv 1 \pmod 2$ , nên nó là số lẻ và không bao giờ bằng $0$ .

Ví dụ: Gỡ các đoạn thẳng cắt nhau trên mặt phẳng

Cho $n$ điểm đỏ và $n$ điểm xanh ở vị trí tổng quát trên mặt phẳng, được nối thành $n$ đoạn thẳng đôi một rời nhau về đầu mút. Mỗi khi hai đoạn $A_1B_1$ và $A_2B_2$ cắt nhau, ta thay chúng bằng $A_1B_2$ và $A_2B_1$ . Chứng minh quá trình này buộc phải dừng sau hữu hạn bước, khi không còn hai đoạn nào cắt nhau.

Lời giải

Đặt hàm thế $L(s) = \sum_{i=1}^n |A_iB_i|$ là tổng độ dài Euclid của $n$ đoạn thẳng. Khi $A_1B_1$ và $A_2B_2$ cắt nhau tại $P$ , bất đẳng thức tam giác trong $\triangle A_1 P B_2$ và $\triangle A_2 P B_1$ cho $|A_1B_2| + |A_2B_1| < (|A_1P| + |PB_2|) + (|A_2P| + |PB_1|) = |A_1B_1| + |A_2B_2|$ .

Vậy $L(s)$ là một đơn biến giảm ngặt qua mỗi bước! Vì chỉ có hữu hạn $n!$ cách ghép cặp giữa $n$ điểm đỏ và $n$ điểm xanh, $L(s)$ chỉ nhận tối đa $n!$ giá trị khác nhau nên không thể giảm quá $n! - 1$ lần. Do đó quá trình dừng sau nhiều nhất $n! - 1$ bước.

Vì sao không thể lát bàn cờ $8\times 8$ bị khuyết hai góc đối diện bằng $31$ quân domino $2\times 1$ ?

Bắt đầu với năm số $1, 2, 3, 4, 5$ . Mỗi bước được cộng thêm $1$ vào hai số bất kỳ. Liệu cả năm số có thể trở nên bằng nhau không?

Một đơn biến nhận giá trị nguyên không âm $M(s) \in \mathbb{N}$ bắt đầu tại $M(s_0) = 42$ và thỏa $M(s') \le M(s) - 3$ ở mỗi bước hợp lệ. Số bước tối đa trước khi quá trình buộc phải dừng là bao nhiêu?

Khi thay hai số $a, b$ bởi $a + b + ab$ , đại lượng đại số nào giữ nguyên bất biến trên toàn danh sách?

Tài liệu tham khảo

Arthur Engel (1998). Problem-Solving Strategies · DOI:10.1007/b97682
Jessica Striker (2017). Dynamical Algebraic Combinatorics: Promotion, Rowmotion, and Resonance · DOI:10.1090/noti1539