Dưới đây là một số bài toán tương tự dạng hình học tổ hợp, áp dụng nguyên lý cực tiểu – thuật toán tham lam (Greedy) – phản chứng như bài 10 đoạn không cắt nhau, rất thích hợp cho ôn luyện HSG hoặc các đề thi logic tư duy toán học:
🧩 Bài toán 1: Nối điểm trên đường tròn
Cho 2n điểm phân biệt trên một đường tròn (không có ba điểm đồng quy).
Chứng minh rằng ta luôn có thể nối n đoạn thẳng giữa các cặp điểm (ghép đôi từng cặp), sao cho:
Không có hai đoạn nào cắt nhau bên trong đường tròn.
🔍 Hướng dẫn gợi ý:
-
Gọi các điểm là P1,P2,…,P2n theo thứ tự trên đường tròn.
-
Chứng minh tồn tại perfect matching không giao nhau bằng quy hoạch động hoặc nguyên lý cực trị.
-
Chứng minh rằng trong matching cực trị, nếu có cắt nhau thì có thể đổi cặp để giảm chiều dài (tổng độ dài cung hoặc đoạn) ⟶ mâu thuẫn.
✅ Áp dụng hoàn hảo bộ ba: Greedy + cực tiểu + phản chứng
🧩 Bài toán 2: Lát hình chữ nhật bằng domino
Cho hình chữ nhật kích thước 2n×2n, chia thành các ô vuông đơn vị.
Chứng minh rằng có thể lát kín hình này bằng 2n^2 quân domino 1×2 sao cho:
Không có hai domino nào cắt nhau
Mỗi domino phủ đúng hai ô, và không chồng lấn
🔍 Gợi ý:
-
Gán màu caro trắng–đen
-
Mỗi domino luôn che đúng 1 ô trắng và 1 ô đen
-
Bài toán chuyển về matching trên đồ thị lưỡng phân
-
Matching cực đại không thể có "giao nhau" theo nghĩa hình học
✅ Dẫn dắt về matching cực trị + lý do tại sao không thể chồng lấn
🧩 Bài toán 3: Dây cao su và điểm
Có n chiếc đinh đóng trên tường thành hàng ngang (tọa độ x khác nhau).
Có n điểm nằm dưới đất (tọa độ x khác nhau).
Ta nối mỗi đinh với một điểm đất bằng một dây cao su thẳng.
Chứng minh: Luôn tồn tại cách nối không chéo (không có dây nào cắt nhau).
🔍 Gợi ý:
-
Gán thứ tự các điểm trên trục hoành
-
Sắp xếp đinh theo hoành độ tăng, rồi nối với điểm đất theo thứ tự tăng hoành độ
-
Các đoạn sẽ không bao giờ cắt nhau ⟶ matching theo thứ tự tương ứng
✅ Bài điển hình về matching theo thứ tự – có thể dùng cho thi vào chuyên
🧩 Bài toán 4: Nối đoạn không cắt nhau trong hình chữ nhật
Trong hình chữ nhật, cho n điểm ở mép trên và n điểm ở mép dưới, các điểm không trùng phương ngang.
Chứng minh rằng ta có thể nối từng điểm trên với một điểm dưới sao cho không có hai đoạn cắt nhau.
🔍 Gợi ý:
-
Gán thứ tự trái → phải cho các điểm
-
Matching theo thứ tự tăng (ghép điểm trên vị trí i với điểm dưới vị trí i) → không bao giờ cắt
✅ Dẫn chứng bằng tranh minh họa rất trực quan
