Bài toán kinh điển dây cao su và điểm

Bài toán kinh điển dây cao su và điểm

Dây cao su và điểm, một bài điển hình về matching theo thứ tự, rất thích hợp dùng trong các kỳ thi vào lớp chuyên Toán hoặc bài tập tổ hợp hình học.

---

🧩 Đề bài:

• Có n chiếc đinh nằm trên tường, xếp thành hàng ngang (trên cùng một đường thẳng), mỗi đinh có hoành độ khác nhau.

• Có $n$ điểm đất nằm bên dưới, cũng có hoành độ khác nhau.

• Nối mỗi đinh với một điểm đất bằng một dây cao su thẳng (đoạn thẳng nối).

Chứng minh rằng:
Luôn có cách nối sao cho không có hai dây nào cắt nhau.

---

✅ Phân tích và hướng tư duy

Ta cần tìm một matching 1–1 giữa hai tập điểm A={a1,...,an} (đinh) và B={b1,...,bn} (điểm đất), sao cho:

• Mỗi đoạn aibj là một đoạn thẳng

• Không có hai đoạn nào giao nhau (cắt nhau)

---

🧠 Chiến lược chứng minh – Matching theo thứ tự

🔷 Bước 1: Gán thứ tự tăng theo hoành độ

Vì hoành độ các điểm đều khác nhau, ta có thể:

• Sắp xếp đinh theo hoành độ tăng: a1<a2<⋯<an​

• Sắp xếp điểm đất theo hoành độ tăng: b1<b2<⋯<bn​

---

🔷 Bước 2: Matching thứ tự tương ứng

Gán từng cặp:

• Nối a1 với b1​

• Nối a2 với b2​

• …

• Nối an​ với bn​

Đây gọi là matching theo thứ tự tương ứng

---

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

Giả sử tồn tại hai đoạn nối:

• ai→bi​

• aj→bj​

với i<j

Vì ta đã sắp theo thứ tự hoành độ:

• ai<aj​

• bi<bj​

⟹ đoạn aibi nằm bên trái và thấp hơn so với đoạn ajbj​

⟹ Hai đoạn không thể cắt nhau

✅ Không có giao cắt!

---

✅ Kết luận

• Cách nối theo thứ tự hoành độ tăng đảm bảo không có đoạn nào cắt nhau

• Do vậy, với mọi n≥1, luôn tồn tại cách nối các đinh và điểm đất sao cho các đoạn thẳng đôi một không cắt nhau

---

📌 Tổng kết chiến lược

---

📚 Bài học rút ra

• Đây là một dạng bài rất quan trọng trong toán tổ hợp – hình học

• Tư duy cốt lõi: ghép thứ tự đồng nhất → loại bỏ khả năng giao cắt

• Bài toán tương đương với: dãy đồng biến không sinh nghịch biến