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 […]

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 […]

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 n^2 quân domino 1×2 sao cho: Không có hai domino nào cắt nhau và Mỗi domino phủ đúng hai ô, và không chồng lấn Đây là một […]

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 […]

  Thuật toán tham lam (Greedy algorithm) là một trong những chiến lược thiết kế thuật toán cơ bản và mạnh mẽ trong khoa học máy tính và toán học tổ hợp. 🎯 Định nghĩa ngắn gọn Thuật toán tham lam (Greedy) là chiến lược giải quyết bài toán bằng cách: 👉 Ở mỗi bước, […]

🧩 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 […]

🎓 LÝ THUYẾT: Chứng minh bằng Nguyên lý cực tiểu – Thuật toán tham lam (Greedy) – Phản chứng 📍 1. Nguyên lý cực tiểu (Extremal Principle) Định nghĩa: Trong một tập hợp hữu hạn các cấu hình, ta xét một cấu hình tốt nhất (có giá trị cực tiểu hoặc cực đại theo một […]