Bài toán cắt nhau phương pháp chứng minh phản chứng

🧩 Bài toán cắt nhau phương pháp chứng minh phản chứng

Trên mặt phẳng, cho 2n điểm phân biệt, trong đó:

n điểm nằm trên đường thẳng d1

n điểm còn lại nằm trên đường thẳng d2 song song với d1

Không có ba điểm nào thẳng hàng, và không có hai điểm nào trùng nhau theo phương ngang.

Chứng minh rằng: Luôn có thể nối các điểm trên d1 với các điểm trên d2 (theo từng cặp) sao cho:

Mỗi điểm nối với đúng một điểm thuộc đường còn lại

Không có hai đoạn nối nào cắt nhau

🧠 Hướng dẫn tư duy giải – theo 3 bước:

✅ Bước 1. Xét tất cả các cách nối

Có cách nối 1–1 giữa n điểm trên d1 và n điểm trên d2.
Mỗi cách nối sinh ra n đoạn thẳng.
Ta chọn một cách nối tối ưu, ví dụ có tổng độ dài đoạn nối là nhỏ nhất.

Gọi cách nối này là .

✅ Bước 2. Giả sử tồn tại hai đoạn cắt nhau

Giả sử trong cách nối , tồn tại hai đoạn:

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

( thuộc d1, thuộc d2)

⟶ Do hai đoạn cắt nhau, tức là:

Thứ tự theo trục hoành ngược với thứ tự
Nói cách khác: cặp nối bị "chéo"

✅ Bước 3. Tạo cách nối mới và chứng minh mâu thuẫn

Thay vì nối như cũ, ta hoán đổi:

Dùng đoạn: $A_{2} B_{1}$

→ Về hình học:

Do các điểm và không trùng hoành độ, và nằm trên hai đường thẳng song song, thì:

Các đoạn và sẽ không cắt nhau
Và tổng độ dài mới sẽ nhỏ hơn tổng cũ (theo bất đẳng thức tam giác)

⟹ Mâu thuẫn với giả thiết rằng cách nối là tối ưu (có tổng độ dài nhỏ nhất).

✅ Kết luận:

⟹ Vậy nên tồn tại ít nhất một cách nối các điểm giữa hai đường song song mà không có hai đoạn nào cắt nhau.

📌 Bài học rút ra:

Khi có hai tập điểm phân biệt và cần ghép từng cặp sao cho không giao nhau, hãy thử:
1. Sắp xếp các điểm theo thứ tự
2. Áp dụng ghép tăng dần → sẽ tạo thành các đoạn không chéo nhau
3. Áp dụng nguyên lý cực trị + phản chứng nếu cần chứng minh sự tồn tại