Chuồng bồ câu: Nguyên lý Dirichlet

Có những điều ta chứng minh được là chắc chắn đúng mà không cần thử hết mọi cách, chỉ cần đếm số lượng. Nguyên lý Dirichlet là công cụ đơn giản để chứng minh 1 điều chắc chắn phải xảy ra, dù không biết trước nó xảy ra ở đâu.

Nếu có nhiều con bồ câu hơn số chuồng thì dù nhốt kiểu gì, luôn có ít nhất 1 chuồng chứa từ 2 con trở lên. Điều này nghe hiển nhiên nhưng giúp giải được nhiều bài toán khó. Chọn số chuồng và số bồ câu, rồi thử xếp sao cho mỗi chuồng có tối đa 1 con.

Từ khóa: chứng minh, tổ hợp, câu đố