Mostre que se f for uma função de S para T, em que S e T são conjuntos finitos e m=\lceil|S| /|T|\rceil, então pelo menos m elementos de S têm a mesma imagem em T. Ou seja, mostre que há elementos distintos s_{1}, s_{2}, \ldots, s_{m} de S tal que f\left(s_{1}\right)=f\left(s_{2}\right)=\cdots=f\left(s_{m}\right).
Passo 1
O enunciado afirma que temos uma função f\colon S\to T entre dois conjuntos finitos, com \lvert S\rvert elementos em S e \lvert T\rvert em T. Definimos
m = \Bigl\lceil \frac{\lvert S\rvert}{\lvert T\rvert}\Bigr\rceil.
Queremos mostrar que existe algum t\in T tal que pelo menos m elementos de S sejam enviados para t, isto é, existem distintos s_{1},\dots,s_{m} em S com
f(s_{1}) = f(s_{2}) = \cdots = f(s_{m}).
O conteúdo aqui é um caso clássico do Princípio da Casa dos Pombos (Pigeonhole Principle).
Passo 2
Sejam
n = \lvert S\rvert \quad\text{e}\quad k = \lvert T\rvert.
Pelo modo como m foi definido, vale
m-1 < \frac{n}{k} \le m.
Multiplicando por k, obtemos
k(m-1) < n \le k\,m.
Passo 3
Suponha, para fins de contradição, que nenhum valor em T tenha m ou mais pré-imagens; isto é, para todo t\in T, \lvert f^{-1}(t)\rvert \le m-1.
Como os conjuntos f^{-1}(t) para t\in T particionam S, temos