Bài toán nối hình kinh điển - tổ hợp kinh điển

Cho 20 điểm phân biệt gồm 10 điểm màu xanh và 10 điểm màu đỏ trên mặt phẳng, trong đó không có 3 điểm nào thẳng hàng. Chứng minh rằng ta có thể dùng 10 đoạn thẳng nối mỗi điểm
xanh với một điểm đỏ tương ứng sao cho 10 đoạn thẳng này đôi một không có điểm chung

Đây là một bài toán hình học tổ hợp kinh điển, còn được gọi là bài toán kết ghép hai tập điểm khác màu bằng các đoạn thẳng không cắt nhau. Ta sẽ chứng minh rằng luôn tồn tại cách nối 10 điểm xanh với 10 điểm đỏ sao cho các đoạn nối không cắt nhau.

🧠 Tóm tắt đề bài

Có 20 điểm phân biệt trên mặt phẳng: 10 điểm xanh, 10 điểm đỏ.
Không có 3 điểm nào thẳng hàng.
Cần nối mỗi điểm xanh với một điểm đỏ duy nhất (ghép 1–1) sao cho 10 đoạn thẳng đôi một không cắt nhau.

✅ Chiến lược chứng minh

Chứng minh bằng nguyên lý cực tiểu – thuật toán tham lam (Greedy) – phản chứng.

🔷 Bước 1: Xét tất cả các phép ghép 1–1 giữa điểm xanh và điểm đỏ

Tổng số cách ghép là: $10!$ — rất nhiều.
Với mỗi cách ghép ta vẽ 10 đoạn thẳng nối điểm xanh với điểm đỏ.
Một cách ghép bất kỳ có thể sinh ra các đoạn thẳng cắt nhau.

🔷 Bước 2: Chọn cách ghép sao cho tổng độ dài các đoạn là nhỏ nhất

Gọi cách ghép này là tối ưu theo độ dài tổng, tức:

với là điểm xanh, là điểm đỏ.

🔷 Bước 3: Phản chứng – nếu tồn tại hai đoạn cắt nhau thì ta sẽ tìm được cách ghép có tổng độ dài nhỏ hơn ⇒ mâu thuẫn

Giả sử trong cách ghép tối ưu (tổng độ dài nhỏ nhất) có hai đoạn cắt nhau:

và cắt nhau tại một điểm trong mặt phẳng

Ta hoán đổi đầu mối, xét hai đoạn:

Khi hai đoạn và cắt nhau, thì ta có bất đẳng thức:

(Do định lý tam giác + tính chất hình học)

⟹ Tổng chiều dài của cặp đoạn mới nhỏ hơn cặp đoạn cũ.

Như vậy ta tạo được một ghép khác có tổng chiều dài nhỏ hơn ghép ban đầu — mâu thuẫn với giả thiết ban đầu là ghép tối ưu.

✅ Kết luận

⟹ Vậy nên cách ghép tối ưu theo tổng độ dài không thể có hai đoạn nào cắt nhau.⟹ Tồn tại một phép nối 10 đoạn thẳng đôi một không cắt nhau.

Ta thấy rằng khi nối mỗi điểm xanh với một điểm đỏ tương ứng, ta chỉ có hữu hạn cách nối (cụ thể là $10!$ cách). Giả sử rằng trong các cách nối đó có một cách nối $T$ mà tổng độ dài các đoạn thẳng là nhỏ nhất. Nếu ở cách nối $T$ này có hai đoạn thẳng cắt nhau:

(hình minh họa)

Như ở trên hình minh họa, các điểm màu đỏ và các điểm màu xanh sao cho cắt tại . Khi đó ta xét cách nối $^{'}$ được tạo thành từ việc giữ nguyên cách nối cho các điểm còn lại, ngoại trừ việc ta sẽ nối và :

(hình minh họa)

Rõ ràng theo bất đẳng thức tam giác thì

Do ngoài 4 điểm này, các điểm còn lại của cách nối được nối y hệt nên có tổng độ dài các đoạn thẳng nhỏ hơn (mâu thuẫn).
Vậy cách nối không thể có hai đoạn thẳng nào cắt nhau.