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é!
Làm đúng ngay lần đầu càng nhiều thì bé càng được nhiều sao.
Bắt đầu 6 bài tập