Nguyên lí Dirichlet: đếm “ngăn–vật” để chứng minh tồn tại

🕊️ Nhiều vật hơn ngăn thì phải có chỗ trùng

Nếu phân n+1 vật vào n ngăn, ít nhất một ngăn chứa từ hai vật. Dạng tổng quát: phân N vật vào k ngăn thì có ít nhất một ngăn chứa không ít hơn ⌈N/k⌉ vật.

Ví dụ sinh nhật

Trong 13 người, coi mỗi người là một “vật”, 12 tháng là 12 “ngăn”. Vì 13>12, có ít nhất hai người sinh cùng tháng. Kết luận không phải họ cùng ngày sinh; muốn bảo đảm cùng ngày theo mô hình 366 ngày cần ít nhất 367 người.

Quy trình sử dụng

1. Chọn rõ đối tượng được phân và tiêu chí tạo ngăn.
2. Đếm N, k và tính ngưỡng ⌈N/k⌉.
3. Kiểm tra mỗi vật thuộc đúng một ngăn hoặc điều chỉnh phân hoạch.
4. Diễn giải “một ngăn đông” trở lại ngôn ngữ bài toán.

⚠️ Đây là chứng minh tồn tại

Nguyên lí thường không cho thuật toán tìm ngay đối tượng và không nói mọi ngăn đều đông. Nếu các ngăn chồng lấn hoặc có vật không được xếp, lập luận có thể sai. Phần khó thường nằm ở cách chọn ngăn có ý nghĩa.