🐦 Câu 2 · 1 điểm
Nguyên lý Chuồng Bồ Câu
Dirichlet
Dễ ăn trọn 1 điểm nếu nhớ đúng công thức và trình bày đủ bước. Bẫy chính: nhầm "thỏ" và "lồng".
Nguyên lý Dirichlet
Dạng cơ bản
Nếu có $n$ vật vào $k$ hộp ($n > k$)
thì có ít nhất 1 hộp chứa $\geq 2$ vật.
thì có ít nhất 1 hộp chứa $\geq 2$ vật.
Dạng mở rộng
$$\left\lceil \frac{n}{k} \right\rceil$$
Số vật tối thiểu trong hộp chứa nhiều nhất (khi chia $n$ vật vào $k$ hộp)
Công thức tính nhanh
Tìm số vật nhỏ nhất để đảm bảo có $m$ vật trong cùng 1 hộp
Công thức
$$n_{\min} = k(m-1) + 1$$
$k$ = số hộp | $m$ = số vật cần có trong cùng hộp
Ý nghĩa công thức
Trường hợp xấu nhất: mỗi hộp chứa đúng $(m-1)$ vật rồi vẫn chưa có hộp nào có $m$ vật. Vậy tổng = $k(m-1)$. Thêm 1 vật nữa chắc chắn phải rơi vào một hộp đã có $(m-1)$ vật.
📋 Template trình bày chuẩn
Bước 1: Xác định và gọi tên "lồng" (hộp/loại/nhóm).
Số lồng k = [...]
Bước 2: Xác định "vật" (đối tượng cần xếp vào lồng).
Số vật n = [...]
Bước 3: Áp dụng nguyên lý Dirichlet:
"Vì n = [...] > k = [...],
theo nguyên lý chuồng bồ câu,
tồn tại ít nhất một [lồng] chứa ít nhất
⌈n/k⌉ = [...] [vật]."
Kết luận: Vậy nhất định tồn tại [phát biểu kết luận cụ thể]. □
⚡ Mẹo xác định "lồng" và "vật"
Cách nhận biết nhanh:
• Vật = thứ cần phân loại (người, số, vật phẩm...)
• Lồng = tiêu chí phân loại (quê quán, tháng sinh, chữ số đầu, số dư khi chia...)
Hay nhầm: "10 người sinh trong 4 mùa" → Vật = người (10), Lồng = mùa (4), KHÔNG phải ngược lại!
• Vật = thứ cần phân loại (người, số, vật phẩm...)
• Lồng = tiêu chí phân loại (quê quán, tháng sinh, chữ số đầu, số dư khi chia...)
Hay nhầm: "10 người sinh trong 4 mùa" → Vật = người (10), Lồng = mùa (4), KHÔNG phải ngược lại!
✏️ Ví dụ mẫu 1: Sinh viên cùng quê
Đề bài
Lớp học có sinh viên đến từ 5 tỉnh thành. Hỏi lớp cần có tối thiểu bao nhiêu sinh viên để chắc chắn có ít nhất 3 bạn cùng quê?
Bài giải chuẩn
- Gọi "lồng" = 5 tỉnh thành → $k = 5$Xác định lồng
- Gọi "vật" = sinh viên → cần tìm $n_{\min}$Xác định vật
- Cần: có ít nhất 3 bạn cùng quê → $m = 3$Đọc yêu cầu
$n_{\min} = k(m-1)+1 = 5 \cdot (3-1) + 1 = 11$Công thức Dirichlet mở rộng
Theo nguyên lý chuồng bồ câu, với 11 sinh viên chia vào 5 tỉnh, tồn tại ít nhất 1 tỉnh có ≥ $\lceil11/5\rceil = 3$ sinh viên.
Kết luận
→ Cần tối thiểu 11 sinh viên □
✏️ Ví dụ mẫu 2: Số nguyên cùng số dư
Đề bài
Trong $n$ số nguyên bất kỳ, hỏi $n$ tối thiểu là bao nhiêu để chắc chắn tìm được 2 số có cùng số dư khi chia cho 7?
Bài giải
- "Lồng" = các số dư khi chia cho 7: $\{0,1,2,3,4,5,6\}$ → $k=7$Xác định lồng
- "Vật" = các số nguyên, cần $m=2$ số cùng lồngXác định vật
$n_{\min} = 7(2-1)+1 = 8$Công thức
Với 8 số nguyên bất kỳ, theo nguyên lý Dirichlet, tồn tại 2 số có cùng số dư khi chia cho 7. ✓Kết luận
Các dạng bài thường gặp
| Dạng đề | Vật | Lồng | k |
|---|---|---|---|
| SV cùng quê, có $r$ tỉnh | Sinh viên | Tỉnh thành | $r$ |
| SV cùng mức điểm (thang 10) | Sinh viên | Mức điểm nguyên 0–10 | $11$ |
| Số nguyên cùng số dư ÷ $m$ | Số nguyên | Số dư $\{0,1,...,m-1\}$ | $m$ |
| Ngày sinh cùng tháng | Người | Tháng 1–12 | $12$ |
| Chữ số đầu giống nhau | Số tự nhiên | Chữ số đầu 1–9 | $9$ |
Bẫy kinh điển
"Chứng minh tồn tại $m$ vật trong cùng 1 hộp" khác với "chứng minh tồn tại $m$ vật bất kỳ".
Phải đọc kỹ: cùng quê, cùng điểm, cùng số dư... là clue để tìm "lồng".