Exercício: (Generalização do Princípio de Dirichlet) Prove que, se colocarmos
objetos em
gavetas, então ao menos uma das gavetas conterá, no mínimo,
objetos.
Passo 1
O enunciado pede que a gente prove a seguinte afirmação: se colocarmos
objetos em
gavetas (com
e
inteiros positivos e
), então ao menos uma das gavetas conterá, no mínimo,
objetos.
Informações dadas que vamos usar explicitamente:
Informações dadas que vamos usar explicitamente:
Não foi dada nenhuma outra restrição sobre a distribuição: uma gaveta pode receber 0 objetos, mais de um objeto, etc.
Passo 2
Antes de provar, vamos entender bem a notação usada. Vou explicar o que significa
e também a relação com o teto
, porque isso facilita a compreensão do enunciado.
Definição de piso (floor): para qualquer número real
,
é o maior inteiro menor ou igual a
. Exemplos rápidos:
,
,
.
Definição de teto (ceil): para qualquer número real
,
é o menor inteiro maior ou igual a
. Ex.:
,
.
Uma identidade útil, para
inteiro e
inteiro positivo, é
Explicação rápida da identidade:
é o menor inteiro
tal que
. Se
, então
. Dividindo e rearranjando dá
, então
. Logo
. Isso só reforça que a expressão do enunciado é equivalente a dizer “ao menos uma gaveta tem pelo menos
objetos”, que é a forma clássica do princípio das gavetas.
Passo 3
Estratégia de prova (resumida): vou provar a afirmação por contradição — essa é a maneira mais direta aqui e é muito usada em provas relacionadas ao princípio de Dirichlet. A ideia é supor que nenhuma gaveta atinge o número pedido e mostrar que isso contradiz o total
.
Passo lógico inicial da contradição: suponha, para contradizer, que cada gaveta tenha no máximo
objetos. Vou mostrar que isso faz a soma total de objetos ser no máximo
, o que contradiz o fato de que há
objetos no total.
Passo 4
Formalizando a contradição:
Se cada uma das
gavetas contém, no máximo,
objetos, então a soma total de objetos está limitada por
Agora usamos uma propriedade do piso: para todo número real
vale
. Aplicando isso com
obtemos
Multiplicando ambos os lados por
(positivo) dá
Juntando com a desigualdade anterior, obtemos
Passo 5
Conclusão da contradição:
Mas sabemos que a soma total de objetos é exatamente
. A desigualdade encontrada diz que a soma total seria, no máximo,
. Isso é impossível. Portanto a hipótese inicial (de que todas as
gavetas têm no máximo
objetos) é falsa.
Logo, deve existir pelo menos uma gaveta que tem mais do que
objetos. Como o número de objetos em uma gaveta é inteiro, "mais do que
" significa "pelo menos
". Portanto existe uma gaveta com, no mínimo,
objetos, que é exatamente o que queríamos provar.
Passo 6
Um exemplo numérico para fixar a intuição:
Se
e
, então
A afirmação diz que ao menos uma das 3 gavetas tem pelo menos 4 objetos. Se tentássemos colocar no máximo 3 objetos em cada gaveta, o total máximo seria
, que é menor que
, impossível. Então realmente alguma gaveta precisa ter 4 ou mais.