Nguyên lý Dirichlet, còn gọi là nguyên lý chuồng bồ câu, phát biểu rất đơn giản: nhốt nhiều thỏ hơn số chuồng thì chắc chắn có chuồng chứa từ hai con trở lên.
🐰🐰🐰🐰🏠🏠🏠
Chìa khoá: nghĩ tới trường hợp xui nhất
Câu hỏi “lấy ít nhất bao nhiêu để chắc chắn...” luôn được giải theo hai bước: hình dung tình huống xui nhất có thể xảy ra, rồi cộng thêm 1.
Ví dụ
Trong hộp có 5 bi đỏ, 5 bi xanh và 5 bi vàng. Không nhìn vào hộp, phải lấy ít nhất bao nhiêu viên để chắc chắn có 2 viên cùng màu?
- 1Trường hợp xui nhất: lấy được 3 viên khác màu hoàn toàn — mỗi màu một viên.
- 2Lúc này vẫn chưa có hai viên cùng màu.
- 3Lấy thêm 1 viên nữa thì viên đó bắt buộc trùng màu với một viên đã có.
Đáp số: 4 viên
Công thức tổng quát
- Muốn chắc chắn có 2 vật cùng loại, với n loại: lấy n + 1 vật.
- Muốn chắc chắn có k vật cùng loại, với n loại: lấy n × (k − 1) + 1 vật.
- Chia m vật vào n nhóm thì luôn có nhóm chứa ít nhất m ÷ n vật (làm tròn lên).
Dễ nhầm chỗ này
Đừng nhầm “chắc chắn” với “có thể”. Câu hỏi “có thể lấy được 2 viên cùng màu không” chỉ cần 2 viên; câu hỏi “chắc chắn” thì phải tính trường hợp xui nhất.
Đọc xong rồi, mình làm bài nhé!
Bắt đầu 6 bài tập