Bài toán nối điển trên hình chữ nhật

Bài toán nối điển trên hình chữ nhật

🧩 Đề bài:

Cho hình chữ nhật.
Có n điểm trên cạnh trên và $n$ điểm trên cạnh dưới của hình chữ nhật.
Không có hai điểm nào trùng hoành độ.

Chứng minh: Ta luôn có thể nối từng điểm phía trên với một điểm phía dưới bằng một đoạn thẳng sao cho:
🔹 Không có hai đoạn nào cắt nhau

---

✅ Phân tích ý tưởng

• Vì các điểm không trùng hoành độ, ta có thể gán hoành độ riêng biệt cho từng điểm.

• Gọi các điểm trên mép trên là A1,A2,...,An​
  và các điểm dưới là B1,B2,...,Bn​

• Mục tiêu: Nối mỗi Ai với một Bj​ sao cho các đoạn không cắt nhau.

👉 Ta sẽ sắp xếp các điểm theo thứ tự tăng hoành độ và ghép tương ứng từng cặp.

---

🧠 Chiến lược chứng minh: Matching theo thứ tự hoành độ

🔹 Bước 1: Sắp xếp các điểm

• Sắp xếp các điểm trên cạnh trên theo hoành độ tăng:
  A1,A2,...,An​ với hoành độ x1<x2<...<xn​

• Sắp xếp các điểm dưới theo hoành độ tăng:
  B1,B2,...,Bn​ với hoành độ y1<y2<...<yn​

🔹 Bước 2: Ghép nối tương ứng

• Nối A1↔B1​

• Nối A2↔B2​

• …

• Nối An↔Bn​

🔹 Bước 3: Chứng minh không cắt nhau

Giả sử tồn tại hai đoạn thẳng:

• AiBii​ và AjBj​ với $j$

Do:

• $)$

• $)$

⟹ Đoạn AiBi​ nằm bên trái so với đoạn AjBj​

⟹ Hai đoạn không thể cắt nhau vì thứ tự hoành độ đồng biến

---

✅ Kết luận

• Với mọi n≥1, nếu các điểm trên – dưới không trùng hoành độ, thì ta luôn có thể nối không cắt nhau.

• Chỉ cần sắp xếp đồng thời hai tập theo hoành độ tăng, rồi nối từng cặp tương ứng.

---

📌 Tổng kết mô hình