🎓 LÝ THUYẾT: Chứng minh bằng Nguyên lý cực tiểu – Thuật toán tham lam (Greedy) – Phản chứng
📍 1. Nguyên lý cực tiểu (Extremal Principle)
Định nghĩa:
Trong một tập hợp hữu hạn các cấu hình, ta xét một cấu hình tốt nhất (có giá trị cực tiểu hoặc cực đại theo một tiêu chí nhất định).
Sau đó dùng tính chất của cấu hình này để chứng minh điều mong muốn hoặc dẫn đến mâu thuẫn.
✅ Ứng dụng: Khi không dễ xét tất cả các khả năng, ta xét trường hợp “đẹp nhất”, rồi phân tích đặc điểm của nó.
📍 2. Thuật toán tham lam (Greedy Method)
Định nghĩa:
Thuật toán chọn từng bước một phương án tối ưu cục bộ, với kỳ vọng rằng ta sẽ đạt được tối ưu toàn cục.
Trong chứng minh toán học, Greedy thường là:
-
Chọn tổng độ dài nhỏ nhất
-
Chọn cấu hình ít giao cắt nhất
-
Chọn cấu hình đơn giản nhất, cân bằng nhất,…
Vai trò: Cho ta một cách chọn cụ thể để sử dụng nguyên lý cực trị.
📍 3. Phản chứng (Proof by Contradiction)
Định nghĩa:
Giả sử mệnh đề cần chứng minh là sai, sau đó từ giả thiết và suy luận logic, ta đi đến mâu thuẫn với giả thiết ban đầu hoặc một định lý đã biết → mệnh đề ban đầu phải đúng.
Kết hợp với nguyên lý cực tiểu:
-
Giả sử tồn tại cấu hình tốt nhất nhưng vi phạm yêu cầu
-
Dùng Greedy để tạo cấu hình tốt hơn (mâu thuẫn với “tốt nhất”)
⟶ Phản chứng thành công.
✅ TỔNG HỢP QUY TRÌNH 3 BƯỚC:
| Bước | Ý nghĩa | Ví dụ điển hình |
|---|---|---|
| 1. Chọn cấu hình cực trị | Chọn cách nối/tổ hợp có tổng nhỏ nhất, ít giao cắt nhất,… | Cách nối có tổng độ dài nhỏ nhất |
| 2. Phân tích nếu cấu hình vi phạm | Giả sử vẫn còn đoạn cắt nhau / nghịch lý trong cấu hình tốt nhất | Có 2 đoạn cắt nhau |
| 3. Dùng Greedy để tạo cấu hình tốt hơn → mâu thuẫn | Đổi cặp nối → tổng độ dài nhỏ hơn → mâu thuẫn với cực trị | Áp dụng bất đẳng thức tam giác |
🔎 Ví dụ minh họa ứng dụng lý thuyết:
Bài toán: Có 10 điểm xanh, 10 điểm đỏ. Nối từng điểm xanh với một điểm đỏ sao cho các đoạn thẳng không cắt nhau.
Áp dụng lý thuyết:
-
Cực tiểu: Chọn phép nối 1–1 sao cho tổng độ dài nhỏ nhất.
-
Phản chứng: Giả sử có 2 đoạn cắt nhau.
-
Greedy: Đổi cặp nối → tổng độ dài giảm → mâu thuẫn với giả thiết.
⟶ Mâu thuẫn xảy ra → Cách nối cực trị phải không có đoạn nào cắt nhau.
🎁 Ghi nhớ ngắn gọn:
Cực trị + Tham lam + Phản chứng = Vũ khí lợi hại trong toán tổ hợp – hình học – giải tích.
Chỉ cần: Chọn cấu hình tốt nhất → nếu còn vi phạm thì chỉnh lại tốt hơn → mâu thuẫn!
