DĨ BẤT BIẾN, ỨNG VẠN BIẾN

HÀ HUY KHOÁI

Đó là câu nói mà Chủ tịch Hồ Chí Minh dặn cụ Huỳnh Thúc Kháng trước khi lên đường sang Pháp năm 1946, giao trọng trách Quyền Chủ tịch nước cho Cụ Huỳnh. Bất biến ở đây là độc lập dân tộc, trên cơ sở đó mà tìm ra những chính sách mềm dẻo thích hợp với tình hình trong hoàn cảnh đất nước đang ngàn cân treo sợi tóc.

Câu nói trên cũng sẽ là cẩm nang cho chúng ta khi giải một lớp bài toán rời rạc, từ hình học đến số học, mà điều quan trọng nhất là tìm cho ra một “bất biến”. Trong rất nhiều bài toán, ta gặp tình huống sau đây: cho một quy luật biến đổi (một phép toán, một cách sắp xếp, một phép biến hình,…), hỏi khi lặp lại nhiều lần biến đổi đó, ta sẽ đi đến những tình huống nào? Bài toán tổng quát là: từ trạng thái ban đầu, sau hữu hạn lần thực hiện phép toán đã cho, ta có thế đi đến những trạng thái nào?

Ta xét vấn đề nêu trên thông qua một số ví dụ.

Ví dụ 1. Trên bảng đen, viết 2016 dấu cộng (+) và 2017 dấu trừ (-). Cho phép xoá hai dấu tuỳ ý và viết thay vào đó dấu cộng nếu hai dấu đã xoá là như nhau, và dấu trừ trong trường hợp ngược lại. Lặp lại phép toán đó 4032 lần, ta còn lại một dấu. Hỏi đó là dấu gì?

Ta hãy xem trong cả quá trình nói trên, có cái gì là bất biến hay không? Tất nhiên để làm toán thì con số vẫn dễ chịu hơn dấu rất nhiều. Ta viết số 1 thay cho mỗi dấu cộng, số -1 thay cho dấu trừ. Khi đó phép toán đã cho tương đương với việc thay hai số tuỳ ý bằng tích của chúng. Vấn đề bây giờ thật đơn giản. Phép toán của chúng ta không làm thay đổi tích các số đã cho trên bảng. Như vậy, tích các số còn lại trên bảng tại mỗi thời điểm là một bất biến. Ở trạng thái xuất phát, tích đó bằng -1, vậy dù ta thực hiện phép toán cho phép theo thứ tự thế nào, dấu cuối cùng còn lại trên bảng cũng là dấu trừ.

Trong bài toán trên đây, ta cũng có thể thay mỗi dấu cộng bằng số 0, mỗi dấu trừ bằng số 1. Khi thực hiện phép toán đã cho, tổng của hai số bị xoá cùng tính chẵn lẻ với số thay thế cho hai số đó. Như vậy, tính chẵn lẻ của tổng các số trên bảng trong mỗi thời điểm là một bất biến. Ở trạng thái xuất phát, tổng các số trên bảng là số lẻ. Như vậy, khi trên bảng còn lại một số thì số đó phải là số 1, tức là dấu còn lại chính là dấu trừ.

Cũng có thể giải bài toán trên đây theo cách sau: sau mỗi lần thực hiện phép toán, ta thấy số các dấu trừ hoặc không đổi (nếu xoá hai dấu cộng hoặc xoá hai dấu khác nhau), hoặc giảm đi 2 đơn vị (nếu xoá hai dấu trừ). Như vậy, tính chẵn lẻ của số các dấu trừ được viết tại mỗi thời điểm là một bất biến. Ở trạng thái ban đầu, số dấu trừ là số lẻ, vì thế khi chỉ còn lại một dấu thì đó là dấu trừ.

Trong ba cách giải trên đây, ta đều dựa vào một bất biến nào đó. Trong cách giải thứ nhất, đó là tính không đổi của tích các số đã viết, cách thứ hai dựa trên sự bất biến của tính chẵn lẻ của tổng các số, cách thứ ba dựa trên sự bất biến của tính chẵn lẻ của số các dấu trừ.

Trong ví dụ trên đây, việc tìm ra bất biến để giải bài toán là khá dễ dàng. Tuy nhiên, không phải bao giờ cũng có thể làm được như vậy.

Ví dụ 2. Viết vào mỗi ô của một bảng 4×4 một dấu cộng hoặc dấu trừ như trong hình vẽ. Mỗi lần, cho phép đảo ngược tất cả các dấu trong cùng một hàng, trong cùng một cột, hoặc nằm trên một đường bất kỳ song song với một trong hai đường chéo của bảng (đặc biệt, có thể đổi dấu trong các ô ở góc). Có thể hay không, bằng cách thực hiện phép toán trên đây, đưa bảng ban đầu về bảng chỉ gồm các dấu cộng?

Cũng như trước, ta thay các dấu cộng bởi số 1, dấu trừ bởi số -1. Rõ ràng tích tất cả các số đã viết, tính chẵn lẻ của số các dấu trừ, tính chẵn lẻ của tổng các số (khi thay dấu cộng bởi số 0, dấu trừ bởi số 1) đều không phải là một bất biến của quá trình thực hiện phép toán. Nhận xét rằng, mặc dù tích của tất cả các số trong bảng không phải là một bất biến, nhưng rất có thể tích các số nằm trong một nhóm ô cố định nào đó là một bất biến. Để tìm các ô như vậy, ta cần tìm một tập hợp các ô mà khi thực hiện phép toán cho phép, số ô có thể đổi dấu trong tập hợp này phải là số chẵn. Nói cách khác, mỗi hàng, mỗi cột, mỗi đường song song với một trong hai đường chéo đều chứa một số chẵn các ô của tập hợp đó. Ý tưởng đó dễ dàng đưa đến việc chọn các ô sau đây:

Trong trạng thái xuất phát, tích các số viết trong các ô đã chọn là -1. Vì tích này là một bất biến nên rõ ràng bảng đã cho không thể đưa về trạng thái mà trong ô nào cũng là dấu cộng.

Ví dụ 3. Bài toán như trong ví dụ 2, nhưng bảng đã cho được thay bằng các bảng sau đây:

Cũng với ý tưởng như trong Ví dụ 2, ta tìm một tập hợp chứa một số chẵn các ô trên mỗi hàng, mỗi cột, mỗi đường song song với đường chéo của bảng; đồng thời, tập hợp đó, ở trạng thái ban đầu, chứa một số lẻ các ô có dấu trừ.

Nhận xét: Với cách làm như trên, bạn có thể đặt ra những bài toán tương tự cho các bảng khác nhau. Trong các bài toán trên, chỉ có một số vị trí nào đó của dấu trừ là quan trọng.

Ví dụ 4. Viết lên bảng một số các số 0, 1 và 2. Lấy hai số khác nhau tuỳ ý, xoá hai số đó và viết số còn lại (ví dụ, xoá số 0, 1 và viết số 2). Có một người thực hiện liên tiếp phép toán này và cuối cùng chỉ còn một số trên bảng. Chứng minh rằng số còn lại trên bảng không phụ thuộc quá trình thực hiện phép toán đã cho.

Dĩ nhiên, không phải cách thực hiện phép toán đã cho như thế nào cũng đưa đến kết quả chỉ còn một số trên bảng (có thể xẩy ra trạng thái mọi số trên bảng bằng nhau). Trong bài này, ta giả thiết là có một cách thực hiện việc đó. Vấn đề là cần chứng minh rằng, đối với những cách thực hiện phép toán mà trạng thái cuối cùng là còn lại một số thì số đó không phụ thuộc cách thực hiện.

Giả sử x₀, x₁, x₂ lần lượt là số các số 0, 1, 2 đã được viết. Mỗi lần thực hiện phép toán, mỗi số x_i, i = 0,1,2, hoặc tăng, hoặc giảm một đơn vị, tức là thay đổi tính chẵn lẻ. Khi chỉ còn một số cuối cùng trên bảng, hai trong các số x₀, x₁, x₂ trở thành 0, số kia trở thành 1. Vậy, ở trạng thái xuất phát, hai trong các số đó cùng tính chẵn lẻ, số kia khác tính chẵn lẻ với chúng. Do đó, không phụ thuộc quá trình thực hiện phép toán, chỉ có một trong ba số x₀, x₁, x₂ trở thành 1; đó là số mà ở trạng thái ban đầu, tính chẵn lẻ của nó khác với tính chẵn lẻ của hai số còn lại.

Lời giải trên đây cũng cho thấy rằng, khi ba số x₀, x₁, x₂ có cùng tính chẵn lẻ thì bằng cách thực hiện phép toán trên đây, không thể đi đến trạng thái chỉ còn một số trên bảng. Tuy nhiên, lời giải trên đây không chỉ ra rằng, điều đó luôn luôn có thể làm được nếu trong ba số x₀, x₁, x₂ có đúng hai số cùng tính chẵn lẻ.

Bây giờ, giả sử ta thay đổi phép toán trong Ví dụ 4: mỗi lần đòi hỏi xoá 4 số, gồm 2 cặp số khác nhau, mỗi cặp gồm 2 số cùng loại, và thay vào đó một số thuộc loại còn lại (ví dụ xoá hai số 0, hai số 1, thay vào đó một số 2). Giả sử sau một số lần thực hiện phép toán như vậy, chỉ còn một số trên bảng. Nếu biết số các số 0, 1, 2 tại thời điểm xuất phát, có thể nói gì về số còn lại trên bảng?

Trong trường hợp này, việc xét tính chẵn lẻ như trước kia không đưa đến kết quả, bởi vì một trong các số x₀, x₁, x₂ thay đổi tính chẵn lẻ sau khi thực hiện phép toán, trong khi hai số kia giữ nguyên tính chẵn lẻ. Do đó, các số ban đầu có tính chẵn lẻ khác nhau có thể sẽ có tính chẵn lẻ như nhau sau một số lần thực hiện phép toán. Để giải bài toán, ta cần tìm một bất biến khác.

Để ý rằng, khi xét tính chẵn lẻ, ta đã xét đồng dư theo modulo 2, tức là dùng đồng dư trong trường hợp đơn giản nhất. Khi việc đó không còn có ích nữa, lẽ tự nhiên là ta tính đến đồng dư tiếp theo: đồng dư theo modulo 3. Rõ ràng, các lớp đồng dư theo modulo 3 của các số x₁ – x₂, x₁ – x₀, x₂ – x₀ bất biến trong quá trình thực hiện phép toán. Như vậy, nếu sau khi thực hiện một số lần phép toán đã cho mà trên bảng còn lại đúng một số thì khi xuất phát, phải có đúng hai số trong các số x₀, x₁, x₂ đồng dư với nhau theo modulo 3. Dễ suy ra số cuối cùng còn lại trên bảng, đó chính là số i mà x_i không đồng dư với hai số còn lại theo modulo 3.

Ví dụ 5. Cho bảng ô vuông 8×8 , trong mỗi ô ta viết một số nguyên. Chọn tuỳ ý một bảng con kích thước 3×3 hoặc 4×4 rồi cộng thêm 1 vào mỗi số trong các ô của bảng con đã chọn. Xuất phát từ một bảng tuỳ ý, với việc thực hiện liên tiếp phép toán đó, ta có thể nhận được hay không một bảng mà tất cả các số viết trong các ô đều chia hết cho 3?

Ta dự đoán rằng, phải tồn tại những bảng mà không có cách nào để đưa về bảng thoả mãn yêu cầu của bài toán. Vì điều kiện duy nhất ở đây là chia hết cho 3 nên ta cần tìm một tập hợp nào đó các ô mà tổng các số viết tại các ô của tập hợp này có thặng dư modulo 3 bất biến trong quá trình thực hiện phép toán. Nếu tồn tại tập hợp như vậy, ta chỉ cần ghi vào bảng xuất phát các số sao cho tổng các số trong tập đã chọn không chia hết cho 3.

Tập con A các ô sẽ thoả mãn yêu cầu đặt ra trên đây nếu mỗi bảng con 3×3 hoặc 4×4 chứa 0, 3, 6, 9, 12 hoặc 15 ô của tập hợp A. Từ ý tưởng đó, dễ thấy cách chọn sau thoả mãn (A là tập các ô được đánh dấu).

Nhận xét: Số 8 trong bài toán có thể thay bởi 4n, n > 1.

Ví dụ 6. Với điều kiện như trong Ví dụ 5, xuất phát từ một bảng tuỳ ý, có thể thu được một bảng gồm toàn số lẻ hay không?

Trong bài toán này, ta chỉ quan tâm đến tính chẵn lẻ; vì thế, ta cần tìm một tập hợp nào đó các ô mà tính chẵn lẻ của tổng các số viết tại các ô của nó là một bất biến trong quá trình thực hiện phép toán. Nều tồn tại tập hợp như vậy, ta chỉ cần ghi vào bảng xuất phát các số sao cho tổng các số trong các ô đã chọn là một số chẵn.

Như vậy, chỉ cần chọn tập A mà mỗi bảng con 3×3 hoặc 4×4 chứa một số chẵn các ô của

A. Ý tưởng đó giúp ta dễ dàng tìm được tập A (gồm các ô đánh dấu) như sau:

Nhận xét: Lời giải trên đây đúng cho bảng n x m tuỳ ý.

Ví dụ 7. Có 2017 xe ô tô đua xuất phát cùng một lúc từ các vị trí khác nhau dọc theo một đường đua khép kín, và chạy theo cùng một hướng. Theo quy tắc của cuộc đua, các xe có thể vượt nhau, và trong mỗi lần vượt, chỉ có một xe vượt và xe này vượt đúng một xe đang chạy ngay trước nó. Sau một thời gian, các xe trở về vị trí xuất phát của chúng cùng một lúc. Chứng minh rằng trong quá trình chạy, số lần các xe vượt nhau là một số chẵn.

Ở bài toán này, ta phải dùng một phương pháp rất quen thuộc khi giải bài toán rời rạc mà ban đầu các đối tượng là “bình đẳng” (không phân biệt): cần “đánh dấu” một đối tượng nào đó, để căn cứ vào đó mà lý luận! Trong bài toán trên, do đường đua khép kín nên vị trí của các xe là hoàn toàn bình đẳng. Trước khi các xe xuất phát, ta chọn một xe và “sơn màu vàng” cho nó (để tránh bị chủ xe phản đối, chỉ sơn trong tưởng tượng thôi). Các xe còn lại, lần lượt theo thứ tự đứng sau xe màu vàng, được gán các số 1, 2,…, 2016. Giả sử có một quan sát viên luôn xem xe màu vàng là xe chạy đầu tiên và ghi lại thứ tự các xe chạy sau nó. Mỗi lần có một xe nào đó vượt xe khác, hai số nào đó sẽ đổi chỗ cho nhau. Giả sử tại thời điểm nào đó, có một xe vượt xe màu vàng. Nếu thứ tự các xe (không vàng) trước khi vượt là a₁,a₂,…,a₂₀₁₆ thì sau khi vượt, thứ tự sẽ là a₂,a₃,…,a₂₀₁₆,a₁. Phép thế này có thể nhận được nhờ 2015 phép dịch chuyển sau:

Nếu xe màu vàng vượt xe khác thì a₁,a₂,…,a₂₀₁₆ trở thành a₂₀₁₆,a₁,….,a₂₀₁₅.

Dễ thấy rằng, phép thế này cũng có thể nhận được nhờ việc thực hiện 2015 phép dịch chuyển.

Tóm lại, bất kỳ một lần vượt nhau nào của hai xe tuỳ ý cũng tương ứng với một số lẻ các phép dịch chuyển. Tại thời điểm cuối cùng, thứ tự các xe trùng với thứ tự xuất phát, nên tổng số phép dịch chuyển phải là số chẵn (điều này không hiển nhiên, và dành để độc giả tự kiểm tra). Từ đó suy ra số lần các xe vượt nhau phải là số chẵn.

Trong cách giải trên đây, ta đã dựa vào bất biến sau: tính chẵn lẻ của số phép dịch chuyển ứng với mỗi lần hai xe vượt nhau. Một số ví dụ trên đây cho chúng ta làm quen với phương châm “Dĩ bất biến, ứng vạn biến” khi giải một số bài toán rời rạc.