Se N objetos são distribuídos entre k caixas e N > k·m, o que o Princípio da Casa dos Pombos garante?

Que existe pelo menos uma caixa com ≥ m+1 objetos.

Em geral, se houvesse no máximo m objetos em cada uma das k caixas, o total seria ≤ \(k\cdot m\). Como \(N>k\cdot m\), isso é impossível; logo alguma caixa contém pelo menos \(m+1\) objetos. Equivalentemente, existe uma caixa com pelo menos \( \lceil N/k\rceil \) objetos.

exemplo: distribuir 23 maçãs em 4 cestos.
Calcule: \(23/4=5{,}75\), então \( \lceil 23/4\rceil=6\).
Se cada cesto tivesse no máximo 5 maçãs, o total seria ≤ \(4\cdot5=20<23\), contradição; portanto, algum cesto tem pelo menos 6 maçãs.