Exercício: (Generalização do Princípio de Dirichlet) Prove que, se colocarmos n objetos em k gavetas, então ao menos uma das gavetas conterá, no mínimo,
\left\lfloor\frac{n-1}{k}\right\rfloor+1
objetos.

Passo 1

O enunciado pede que a gente prove a seguinte afirmação: se colocarmos n objetos em k gavetas (com n e k inteiros positivos e k\ge1), então ao menos uma das gavetas conterá, no mínimo,
\left\lfloor\frac{n-1}{k}\right\rfloor+1
objetos.
Informações dadas que vamos usar explicitamente:
\text{temos }n\text{ objetos no total, distribuídos em }k\text{ gavetas.}í
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 \left\lfloor x\right\rfloor e também a relação com o teto \lceil x\rceil, porque isso facilita a compreensão do enunciado.
Definição de piso (floor): para qualquer número real x, \left\lfloor x\right\rfloor é o maior inteiro menor ou igual a x. Exemplos rápidos: \left\lfloor 2,7\right\rfloor=2, \left\lfloor 3\right\rfloor=3, \left\lfloor -1,2\right\rfloor=-2.
Definição de teto (ceil): para qualquer número real x, \lceil x\rceil é o menor inteiro maior ou igual a x. Ex.: \lceil 2,1\rceil=3, \lceil 3\rceil=3.
Uma identidade útil, para n inteiro e k inteiro positivo, é
\left\lfloor\frac{n-1}{k}\right\rfloor+1=\left\lceil\frac{n}{k}\right\rceil.
Explicação rápida da identidade: \lceil n/k\rceil é o menor inteiro \alpha tal que \alpha\ge n/k. Se \alpha=\lceil n/k\rceil, então \alpha-1< n/k\le\alpha. Dividindo e rearranjando dá \alpha-1\le (n-1)/k<\alpha, então \alpha-1=\left\lfloor (n-1)/k\right\rfloor. Logo \alpha=\left\lfloor (n-1)/k\right\rfloor+1. Isso só reforça que a expressão do enunciado é equivalente a dizer “ao menos uma gaveta tem pelo menos \lceil n/k\rceil 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 n.
Passo lógico inicial da contradição: suponha, para contradizer, que cada gaveta tenha no máximo
\left\lfloor\frac{n-1}{k}\right\rfloor
objetos. Vou mostrar que isso faz a soma total de objetos ser no máximo n-1, o que contradiz o fato de que há n objetos no total.

Passo 4

Formalizando a contradição:
Se cada uma das k gavetas contém, no máximo, \left\lfloor\frac{n-1}{k}\right\rfloor objetos, então a soma total de objetos está limitada por
\text{soma total} \le k\cdot\left\lfloor\frac{n-1}{k}\right\rfloor.
Agora usamos uma propriedade do piso: para todo número real x vale \left\lfloor x\right\rfloor\le x. Aplicando isso com x=(n-1)/k obtemos
\left\lfloor\frac{n-1}{k}\right\rfloor \le \frac{n-1}{k}.
Multiplicando ambos os lados por k (positivo) dá
k\cdot\left\lfloor\frac{n-1}{k}\right\rfloor \le n-1.
Juntando com a desigualdade anterior, obtemos
\text{soma total} \le k\cdot\left\lfloor\frac{n-1}{k}\right\rfloor \le n-1.

Passo 5

Conclusão da contradição:
Mas sabemos que a soma total de objetos é exatamente n. A desigualdade encontrada diz que a soma total seria, no máximo, n-1. Isso é impossível. Portanto a hipótese inicial (de que todas as k gavetas têm no máximo \left\lfloor\frac{n-1}{k}\right\rfloor objetos) é falsa.
Logo, deve existir pelo menos uma gaveta que tem mais do que \left\lfloor\frac{n-1}{k}\right\rfloor objetos. Como o número de objetos em uma gaveta é inteiro, "mais do que \left\lfloor\frac{n-1}{k}\right\rfloor" significa "pelo menos \left\lfloor\frac{n-1}{k}\right\rfloor+1". Portanto existe uma gaveta com, no mínimo,
\left\lfloor\frac{n-1}{k}\right\rfloor+1
objetos, que é exatamente o que queríamos provar.

Passo 6

Um exemplo numérico para fixar a intuição:
Se n=10 e k=3, então
\left\lfloor\frac{10-1}{3}\right\rfloor+1=\left\lfloor\frac{9}{3}\right\rfloor+1=3+1=4.
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 3\cdot 3=9, que é menor que 10, impossível. Então realmente alguma gaveta precisa ter 4 ou mais.

Resposta

\left\lfloor\frac{n-1}{k}\right\rfloor+1

Exercícios relacionados