Nguyên Lý Chuồng Bồ Câu trong Toán Rời Rạc

1. Nguyên lý cơ bản

Phiên bản cơ bản: Nếu có n+1 con bồ câu thả vào n cái chuồng, thì chắc chắn có một chuồng chứa ít nhất 2 con.

Bản tổng quát: Nếu phân N đối tượng vào m nhóm, thì tồn tại một nhóm có ít nhất ⌈N/m⌉ đối tượng.

2. Ví dụ dễ

• Tất trùng màu: Lấy 3 chiếc tất từ ngăn có 2 màu (đen, trắng) → chắc chắn có 2 chiếc cùng màu.
• 13 người & tháng sinh: Trong 13 người → có 2 người trùng tháng sinh (12 tháng).
• 26 học sinh chia 5 tổ: Có tổ có ít nhất 6 học sinh.

3. Ví dụ trung bình

• Phần dư modulo: Trong 8 số bất kỳ → luôn có 2 số cùng dư khi chia 7 → hiệu chia hết cho 7.
• Cặp tổng 101: Chọn 51 số trong {1,…,100} → luôn có cặp cộng lại bằng 101.
• 5 điểm trong hình vuông: Có 2 điểm cách nhau ≤ √2/2.

4. Ví dụ khó

• Đồ thị: Trong đồ thị n đỉnh → tồn tại 2 đỉnh cùng bậc.
• Tổng con chia hết cho n: Cho n số nguyên, luôn có tập con không rỗng có tổng chia hết cho n.
• Tập {1,…,2n}: Trong n+1 số bất kỳ, tồn tại cặp mà một số chia hết cho số kia.

5. Ví dụ nâng cao

• Xấp xỉ Diophantine: Với mọi số thực α, tồn tại phân số p/q (1 ≤ q ≤ N) sao cho |α – p/q| < 1/(qN).
• Ramsey R(3,3)=6: Trong 6 người, luôn có 3 người quen nhau đôi một hoặc 3 người xa lạ đôi một.

6. Bài tập luyện

• Trong 21 số nguyên, có 2 số hiệu chia hết cho 20.
• Chọn 51 số trong {1,…,100}, chứng minh tồn tại cặp mà một số chia hết cho số kia.
• Đặt 10 điểm trong hình vuông 1×1, chứng minh có 2 điểm cách nhau ≤ √2/3.
• Cho n số nguyên, luôn tồn tại tập con có tổng chia hết cho n.

7. Kết luận & mẹo

Nguyên lý Chuồng Bồ Câu là công cụ đơn giản nhưng mạnh mẽ trong toán rời rạc và chứng minh tổ hợp. Bí quyết áp dụng:

• Xác định rõ “bồ câu” và “chuồng”.
• Dùng công thức ⌈N/m⌉ để ước lượng.
• Các “chuồng” phổ biến: phần dư modulo, cặp bù, ô hình học, khoảng đều.