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
n = \sum_{t\in T} \bigl\lvert f^{-1}(t)\bigr\rvert \;\le\; \sum_{t\in T}(m-1) \;=\; k\,(m-1).

Passo 4

Mas das desigualdades de Passo 2 sabemos que k(m-1) < n. Logo chegamos a
n \le k(m-1) < n,
que é impossível. Essa contradição mostra que nossa suposição estava errada. Portanto, existe algum t\in T tal que
\bigl\lvert f^{-1}(t)\bigr\rvert \ge m.
Basta então escolher m elementos distintos s_{1},\dots,s_{m} em f^{-1}(t) para concluir.

Resposta

Existem s_{1},s_{2},\dots,s_{m} distintos em S tais que
f(s_{1}) = f(s_{2}) = \cdots = f(s_{m}).

Exercícios relacionados