"Nói một cách tổng quát, một đại lượng bất biến của một thuật toán là đại lượng không thay đổi sau mỗi bước của thuật toán đó." Trong topic này, ta sẽ thảo luận những ứng dụng của bất biến trong việc giải toán tổ hợp. Cho $a,b,c$ là các số thực. Ta xét tổng $S=a+b+c$. Nếu ta đổi chỗ $a$ cho $b$, $b$ cho $c$ hoặc $c$ cho $a$ thì $S$ vẫn không thay đổi. Khi đó $S$ được gọi là bất biến đối với việc thay đổi vị trí của $a,b,c$. Bài toán sau trình bày một ví dụ phức tạp hơn về đại lượng bất biến. $\boxed{\text{Bài toán 1}}$ Người nông dân trồng được một cây khế thần có $99$ quả chưa chín màu xanh và $100$ quả chín màu vàng. Một con Quạ đến ăn mỗi ngày hai quả khế và nói với người nông dân: "Ăn một quả khế, trả một cục vàng, may túi ba gang, mang đi mà đựng". Quạ đến ăn hai quả khế bất kì không phân biệt quả xanh và quả vàng. Nếu Quạ ăn một quả xanh và một quả vàng thì cây khế lại sinh ra một quả xanh. Nếu Quạ ăn hai quả xanh hoặc hai quả vàng thì cây khế lại sinh ra một quả vàng. Hỏi quả khế cuối cùng trên cây có màu gì? Spoiler: Lời giải Ta kí hiệu quả khế xanh là $X$, quả khế vàng là $V$. Theo cách sinh ra quả mới của cây khế, ta có thể viết ngắn gọn bài toán thành \begin{align*} V+V\rightarrow V,\ X+X\rightarrow V,\ X+V\rightarrow X. \end{align*} Quan sát thấy rằng số quả xanh trên cây sẽ giảm đi $2$ hoặc giữ nguyên sau mỗi lần Quạ ăn. Mà ban đầu có $99$ quả xanh nên khi trên cây còn lại một quả thì quả đó cũng là quả xanh. Vậy quả cuối cùng còn lại trên cây là quả xanh. Tính bất biến trong bài toán này là dù cách ăn của Quạ là gì đi nữa thì số quả xanh trên cây luôn bảo toàn hoặc giảm đi $2$. Đại lượng bất biến này kết hợp với giả thiết của bài toán đưa ta đến lời giải. Do đó việc tìm ra đại lượng bất biến trong một bài toán là rất quan trọng. Những ví dụ sau sẽ trình bày một số đại lượng bất biến thường gặp trong các bài toán tổ hợp. $\boxed{\text{Ví dụ 1}}$ Trên bảng ta viết $10$ dấu cộng và $15$ dấu trừ tại các vị trí bất kì. Ta thực hiện xóa hai dấu bất kì trong đó và viết vào đó một dấu cộng nếu hai dấu bị xóa đi giống nhau và viết vào đó một dấu trừ nếu hai dấu bị xóa đi khác nhau. Hỏi trên bảng còn lại dấu gì sau khi thực hiện thao tác trên $24$ lần? Spoiler: Lời giải Cách 1: Thao tác thực hiện xóa hai dấu và viết lại bởi một dấu theo đề bài được viết lại là \begin{align*} \left\{+,+\right\}\rightarrow +,\ \left\{-,-\right\}\rightarrow +,\ \left\{+,-\right\}\rightarrow -. \end{align*} Quan sát thấy số dấu trừ luôn giữ nguyên hoặc giảm đi $2$ sau mỗi bước. Mà ban đầu có $15$ dấu trừ nên số dấu trừ trên bảng luôn là một số lẻ, tức không thể bằng $0$. Do đó khi trên bảng chỉ còn một dấu thì dấu đó không thể là dấu cộng. Vậy, dấu cuối cùng là dấu trừ. Cách 2: Ta thay mỗi dấu cộng bằng số $1$, mỗi dấu trừ bằng số $-1$. Thao tác thực hiện xóa hai số và viết lại bởi một số theo đề bài được viết lại là \begin{align*} \left\{1,1\right\}\rightarrow 1,\ \left\{-1,-1\right\}\rightarrow 1,\ \left\{1,-1\right\}\rightarrow -1. \end{align*} Đây chính là việc thay hai số bởi tích của chúng. Do đó tích của tất cả các số trên bảng sẽ không đổi. Ban đầu, tích của tất cả các số trên bảng là $-1$ nên khi chỉ còn một số trên bảng thì số đó là $-1,$ tức dấu cuối cùng là dấu trừ. Cách 3: Ta thay mỗi dấu cộng bằng số $0$ và dấu trừ bởi số $1$. Thao tác thực hiện xóa hai số và viết lại bởi một số theo đề bài được viết lại là \begin{align*} \left\{0,0\right\}\rightarrow 0,\ \left\{1,1\right\}\rightarrow 0,\ \left\{0,1\right\}\rightarrow 1. \end{align*} Đây chính là việc thay hai số bởi số $0$ nếu tổng của chúng là một số chẵn và bởi số $1$ nếu tổng của chúng là một số lẻ. Do đó tính chẵn lẻ của tổng các số trên bảng luôn không đổi. Ban đầu, tổng của các số trên bảng là một số lẻ ($15$) nên khi trên bảng còn lại một số thì số đó là $1$, tức dấu cuối cùng là dấu trừ. $\boxed{\text{Ví dụ 2}}$ Bốn kí tự $X$ và năm kí tự $O$ được viết xung quanh một hình tròn theo một thứ tự bất kì. Nếu hai kí tự cạnh nhau là như nhau thì ta viết thêm vào giữa chúng chữ $X$ mới, ngược lại ta viết thêm vào chúng chữ $O$ mới và xóa những kí tự cũ đi. Liệu ta có thể thu được chín kí tự $O$ trên đường tròn hay không? Spoiler: Lời giải Nếu ta đặt $X$ là $1$ và $O$ là $-1$ thì việc thay hai kí tự cạnh nhau theo quy tắc của đề bài chính là việc lấy tích của hai số cạnh nhau. Gọi $P$ là tích của tất cả các số trên đường tròn thì sau mỗi lần thay đổi, $P$ mới sẽ bằng bình phương của $P$ cũ. Do đó $P$ luôn bằng $1$ sau khi thực hiện lần thay đổi đầu tiên. Việc thu được chín kí tự $O$ trên đường tròn kéo theo $P=-1$ (không xảy ra). Vậy ta không thể thu được chín kí tự $O$ trên đường tròn.
$\boxed{\text{Bài toán 1}}$ Trên bảng viết các số nguyên dương $1,2,\ldots,4n-1$. Trong mỗi bước, ta có thể thay thế hai số trên bảng bởi hiệu hai số đó. Chứng minh rằng còn lại một số chẵn sau $4n-2$ bước. Spoiler: “Lời giải” Trong một lượt di chuyển, số lượng các số nguyên trên bảng giảm đi một. Sau $4n-2$ bước, chỉ còn lại một số nguyên dương trên bảng. Ban đầu có $2n$ số lẻ. Số các số lẻ trên bảng sẽ giảm đi $2$ nếu hai số bị xóa là hai số lẻ, giữ nguyên nếu hai số bị xóa là hai số chẵn hoặc một số chẵn một số lẻ. Do đó số các số lẻ trên bảng luôn mà một số chẵn. Do đó, khi chỉ còn một số trên bảng thì số đó phải là số chẵn. $\boxed{\text{Bài toán 2}}$ Cho tập hợp $A=\left\{3,4,12\right\}$. Trong mỗi bước, ta có thể chọn số $a,b$ trong $A$ và thay chúng bởi $0.6a-0.8b$ và $0.8a+0.6b$. Liệu ta có thể đạt được các trạng thái sau đây sau hữu hạn bước lặp hay không? a) $\left\{4,6,12\right\}.$ b) $\left\{x,y,z\right\}$ với $|x-4|,|y-6|,|z-12|$ đều nhỏ hơn $1/\sqrt{3}.$ Spoiler: “Lời giải” $(0.6a-0.8b)^2+(0.8a+0.6b)^2=a^2+b^2.$ Vì $a^2+b^2+c^2=3^2+4^2+12^2=13^2$ nên điểm $(a,b,c)$ trong không gian luôn cách gốc tọa độ $13$ đơn vị. Vì $4^2+6^2+12^2=14^2$ nên ta không thể đưa về trạng thái $\left\{4,6,12\right\}$ sau hữu hạn đơn vị. a) Tương tự câu a), vì $(x-4)^2+(y-6)^2+(z-12)^2<1$ nên ta cũng không thể đạt được trạng thái này. $\boxed{\text{Bài toán 3}}$ Cho một bàn cờ $8\times 8$ được tô màu như bình thường. Ta có thể đổi màu tất cả các ô vuông cùng hàng hoặc cùng cột trong bảng. Liệu có thể đạt được trạng thái chỉ có một ô vuông đen hay không? Spoiler: “Lời giải” Tô lại một hàng hoặc một cột có $b$ ô đen và $8-b$ ô trắng sẽ thu được $8-b$ ô đen và $b$ ô trắng. Khi đó số ô đen thay đổi là $|(8-b)-b|=|8-2b|,$ là một số chẵn. Do đó không thể thu được trạng thái chỉ còn một ô vuông đen trên bảng. $\boxed{\text{Bài toán 4}}$ Cho cặp số $(a,b)$ với $a,b$ là các số nguyên dương. Ta áp dụng thuật toán sau $$\text{while }a>0,\text{ do if } a<b\text{ then }(a,b)\leftarrow (2a,b-a)\text{ else }(a,b)\leftarrow (a-b,2b).$$ Với những vị trí bắt đầu nào thì thuật toán sẽ kết thúc? Trong trường hợp thuật toán kết thúc thì nó cần bao nhiêu bước? Spoiler: “Lời giải” Sau đây là lời giải của bài toán cho số tự nhiên, số hữu tỉ và số vô tỉ. Với bất biến $a+b=n$, thuật toán có thể được biến đổi lại thành như sau: Nếu $a<\dfrac{n}{2},$ thay $a$ bởi $2a$. Nếu $a\ge \dfrac{n}{2},$ thay $a$ bởi $a-b=a-(n-a)=2a-n\equiv 2a\text{ (mod n)}$. Do đó, nhân với $a$ liên tiếp theo modulo $n$, ta được dãy \begin{align*} a,2a,2^2a,\ldots\text{ (mod n) (1)}. \end{align*} Chia $a$ cho $n$ trong hệ cơ số hai, ta có ba trường hợp sau. Trường hợp 1. $\dfrac{a}{n}=0d_1d_2\ldots d_k,d_i\in\left\{0,1\right\}.$ Khi đó $2^k\equiv 0\text{ (mod n)}$ nhưng $2^i$ không chia hết cho $n$ với $i<k$. Do đó thuật toán kết thúc sau $k$ bước. Trường hợp 2. $\dfrac{a}{n}=0a_1a_2\ldots a_p0d_1d_2\ldots d_k0d_1d_2\ldots d_k\ldots$ Khi đó thuật toán sẽ không bao giờ kết thúc nhưng dãy (1) có chu kì $k$. Trường hợp 3. $\dfrac{a}{n}=0d_1d_2\ldots d_k\ldots$. Trong trường hợp này, thuật toán không kết thúc và dãy (1) không có chu kì. $\boxed{\text{Bài toán 5}}$ Có ba đống sỏi màu xanh, đỏ, vàng có lần lượt $a,b,c$ viên. Trong mỗi bước, ta bỏ đi hai viên sỏi khác màu nhau và thêm vào một viên sỏi có màu còn lại. Nếu chỉ còn một viên sỏi ở trên bàn, với điều kiện nào để viên sỏi ấy không phụ thuộc vào cách bỏ đi và thêm sỏi vào trong từng bước?
$\boxed{\text{Bài toán 6}}$ Có ba đống sỏi màu xanh, đỏ, vàng có lần lượt $a,b,c$ viên. Trong mỗi bước, ta bỏ đi hai viên sỏi khác màu nhau và thêm vào hai viên sỏi có màu còn lại. Tìm điều kiện để tất cả các viên sỏi trở nên cùng màu sau hữu hạn bước lặp. Giả sử ban đầu ta có $13$ sỏi xanh, $15$ sỏi đỏ và $17$ sỏi vàng. Liệu có thể thu được tất cả sỏi cùng màu sau hữu hạn bước lặp hay không? Những trạng thái nào có thể thu được từ những viên sỏi như vậy? Spoiler: “Lời giải” $(a,b,c)$ sẽ được biến đổi thành $(a+2,b-1,c-1)$ hoặc $(a-1,b+2,c-1)$ hoặc $(a-1,b-1,c+2)$. Trong tất cả những trường hợp này $a-b,b-c,c-a$ theo modulo $3$ là các đại lượng bất biến. Khi đó $a-b\equiv 0\text\{ (mod 3)}$ và $a+b+c\equiv 0\text\{ (mod 3)}$ là điều kiện để thu được yêu cầu bài toán. $\boxed{\text{Bài toán 7}}$ Trong một bảng chữ nhật $m\times n$, ta viết lên mỗi ô vuông đơn vị một số nguyên dương. Trong mỗi lượt, ta có thể nhân đôi mỗi số trong cùng một hàng hoặc trừ mỗi số trong cùng một cột đi một đơn vị. Chứng minh rằng ta có thể đưa bảng về tất cả các giá trị bằng $0$ sau hữu hạn lần thao tác. Spoiler: “Lời giải” Nếu tồn tại các số $1$ trong hàng đầu tiên, ta nhân đôi các hàng tương ứng với các số đó và trừ tất cả các số trên cột đầu tiên đi $1$. Thao tác này sẽ giảm tổng của các số trong cột đầu tiên cho đến khi ta nhận được cột toàn số $1$. Trừ tất cả các phần tử trên cột này đi $1$, ta nhận được cột $0$. Làm tiếp tục đối với các cột tiếp theo. $\boxed{\text{Bài toán 8}}$ Các đỉnh của một $n-$ giác được đánh số bởi các số thực $x_1,\ldots,x_n$. Đặt $a,b,c,d$ là bốn số tự nhiên đứng cạnh nhau trên đa giác đó. Nếu $(a-d)(b-c)<0$ thì ta có thể đổi chỗ $b$ cho $c$. Chứng minh rằng việc đổi chỗ này có thể được thực hiện vô hạn lần. Spoiler: “Lời giải” $(a-d)(b-c)<0$ tương đương với $ab+cd<ac+bd.$ Gọi $S$ là tổng của các tích hai số đứng cạnh nhau trên đa giác. Trong bài toán này, $ab+bc+cd$ được thay thế bởi $ac+cb+bd$. Vì $ab+cd<ac+bd$ nên $S$ sẽ tăng sau mỗi bước lặp. Tuy nhiên $S$ có thể chỉ nhận hữu hạn giá trị nên việc thay đổi vị trí sẽ dừng lại sau hữu hạn thao tác. $\boxed{\text{Bài toán 9}}$ Trong hình sau, ta có thể thay đổi dấu của các số trên cùng một hàng, một cộ, hoặc các đường chéo song song với đường chéo chính và đường chéo phụ. Chứng minh rằng trên bảng luôn tồn tại ít nhất một số $-1$. Spoiler: “Lời giải” Xét $S$ là tích của các số trên biên (trừ bốn góc). Khi đó tích này là không đổi sau mỗi lần thao tác. Do đó $S$ luôn bằng $-1,$ tức trên bảng luôn tồn tại ít nhất một số $-1$. $\boxed{\text{Bài toán 10}}$ Cho $1000$ số tự nhiên được sắp trên một hàng ngang. Hàng thứ hai được xây dựng như sau: dưới mỗi số $a$ trên hàng thứ nhất, ta viết tương ứng $f(a)$ là số lần xuất hiện của $a$ trên hàng thứ nhất. Tương tự, ta xây dựng hàng thứ $3$, thứ $4,\ \ldots$ Chứng minh rằng tồn tại hai hàng trong số những hàng đó có tất cả các giá trị tương ứng bằng nhau. Spoiler: “Lời giải” Các số bắt đầu từ hàng thứ hai là một dãy các số nguyên tăng và bị chặn trên.
