Bất biến và đơn biến là hai ý tưởng quan trọng trong các bài toán thao tác, trò chơi, tô màu và biến đổi trạng thái. Thay vì theo dõi toàn bộ quá trình, ta tìm một đại lượng không đổi hoặc chỉ biến thiên theo một chiều.
Phạm vi: Đây là nội dung Toán THCS nâng cao, phù hợp học sinh khá giỏi, ôn HSG và thi vào lớp 10 chuyên; không phải toàn bộ kiến thức trong bài đều thuộc yêu cầu chính khóa.
1. Bất biến là gì?
Một đại lượng là bất biến nếu nó giữ nguyên sau mỗi phép biến đổi hợp lệ. Nếu trạng thái đầu và trạng thái đích có giá trị bất biến khác nhau thì trạng thái đích không thể đạt được.
Các bất biến thường gặp ở THCS:
- tổng hoặc hiệu của các số;
- tính chẵn lẻ;
- số dư modulo \(m\);
- màu của ô trên bảng;
- một đại lượng hình học như tổng góc hoặc diện tích trong một phép cắt ghép phù hợp.
2. Ví dụ 1: tổng không đổi
Cho cặp số \((a,b)\). Mỗi bước được phép thay \((a,b)\) bởi \((a+1,b-1)\). Khi đó tổng
\(a+b\)
không đổi. Vì vậy nếu trạng thái ban đầu có tổng bằng 20 thì không thể đi tới một trạng thái có tổng bằng 21, dù thực hiện bao nhiêu bước.
Đây là mẫu đơn giản nhất: tính đại lượng trước và sau một thao tác rồi so sánh.
3. Ví dụ 2: bất biến theo modulo
Nếu một thao tác luôn làm tổng tăng thêm 3 thì số dư của tổng khi chia cho 3 không đổi. Ta không cần biết tổng cụ thể sau hàng trăm bước; chỉ cần biết lớp dư modulo 3.
Ví dụ trạng thái đầu có tổng \(S\equiv 1\pmod{3}\), thì mọi trạng thái đạt được cũng phải có tổng \(\equiv 1\pmod{3}\).
4. Ví dụ 3: tô màu bàn cờ
Tô bàn cờ \(8\times8\) theo hai màu xen kẽ như bàn cờ vua. Mỗi quân domino \(1\times2\) luôn phủ đúng một ô đen và một ô trắng. Vì vậy mọi miền được lát hoàn toàn bằng domino phải có số ô đen bằng số ô trắng.
Nếu bỏ đi hai góc cùng màu của bàn cờ, miền còn lại có số ô hai màu không bằng nhau. Do đó không thể lát kín miền còn lại bằng domino \(1\times2\).
Ở đây “chênh lệch số ô đen và trắng” là đại lượng giúp phát hiện điều không thể.
5. Đơn biến là gì?
Một đại lượng là đơn biến nếu sau mỗi bước nó luôn tăng hoặc luôn giảm. Nếu đại lượng là số nguyên không âm và luôn giảm ít nhất 1 sau mỗi bước thì quá trình buộc phải dừng sau hữu hạn bước.
Đơn biến thường dùng để chứng minh:
- một thuật toán hoặc trò chơi chắc chắn kết thúc;
- không thể quay lại trạng thái cũ;
- không thể tồn tại chu trình.
6. Ví dụ 4: quá trình chắc chắn dừng
Bắt đầu từ một số nguyên dương \(n\). Mỗi bước được phép thay \(n\) bằng một số nguyên dương nhỏ hơn nó. Khi đó \(n\) là một đại lượng đơn biến giảm. Vì không có dãy số nguyên dương giảm vô hạn, quá trình phải dừng.
7. Cách tìm bất biến
- Viết rõ một thao tác làm thay đổi trạng thái thế nào.
- Thử các đại lượng đơn giản: tổng, hiệu, tích, chẵn lẻ, số dư.
- Nếu bài có bàn cờ hoặc lưới, thử tô màu theo 2, 3 hoặc 4 lớp.
- So sánh giá trị ở trạng thái đầu và trạng thái cần đạt.
Không phải cứ “không đổi” về mặt trực giác là bất biến; cần kiểm tra sau mọi thao tác hợp lệ.
8. Bài tập tự luyện
- Mỗi bước cộng 4 vào một số nguyên. Chứng minh số dư modulo 4 không đổi.
- Một cặp \((a,b)\) được biến đổi thành \((a+2,b-2)\). Tìm một bất biến.
- Giải thích vì sao bàn cờ \(8\times8\) bỏ hai góc đối diện không thể lát bằng domino \(1\times2\).
- Một số nguyên dương được thay bằng một ước dương nhỏ hơn nó ở mỗi bước. Chứng minh quá trình kết thúc.
Đáp án ngắn: bài 1 dùng lớp dư modulo 4; bài 2 dùng tổng \(a+b\); bài 3 dùng tô hai màu; bài 4 dùng đại lượng đơn biến là giá trị của số.