Nguyên lý Dirichlet (nguyên lý chuồng bồ câu)

Phát biểu

Nếu $n+1$ vật trở lên được đặt vào $n$ hộp, thì có ít nhất một hộp chứa từ hai vật trở lên. Tổng quát hơn, nếu $kn+1$ vật được đặt vào $n$ hộp, thì có một hộp chứa ít nhất $k+1$ vật.

Vì sao đúng?

Bạn không thể nhét nhiều bồ câu vào tổ hơn số tổ cho phép mà không có tổ nào chứa từ hai con trở lên: nếu số vật nhiều hơn hẳn số hộp, thì ít nhất một hộp phải chứa nhiều hơn một vật. Nghe có vẻ hiển nhiên, nhưng việc ép ra một sự lặp lại hay va chạm chỉ từ một chênh lệch đếm đơn giản lại là một kỹ thuật chứng minh mạnh đến bất ngờ.

Chủ đề chứa định lý này

Định lý liên quan

Chứng minh từng bước

Chưa có chứng minh từng bước cho định lý này.