(Insper-09) Em uma repartição pública, 112 pastas são guardadas em 15 arquivos, cada arquivo com capacidade para até 200 pastas. Considere a proposiçăo:
“algum arquivo tem n pastas” O maior valor de n, que toma essa proposição verdadeira, para qualquer distribuição das pastas é:
A) 2
B) 3
C) 6
D) 8
E) 9

Passo 1

O enunciado diz que temos 112 pastas distribuídas em 15 arquivos (caixas) e pergunta qual o maior n tal que, em qualquer distribuição, algum arquivo contenha pelo menos n pastas. Vamos usar o Princípio da Casa dos Pombos (Pigeonhole Principle).

Passo 2

O Princípio da Casa dos Pombos afirma que, ao distribuir m objetos em k caixas, existe pelo menos uma caixa contendo no mínimo
\left\lceil \frac{m}{k} \right\rceil
objetos.

Passo 3

Aqui temos m = 112 pastas e k = 15 arquivos. Calculamos
\left\lceil \frac{112}{15} \right\rceil = \left\lceil 7{,}466\ldots \right\rceil =8.
Portanto, em qualquer forma de distribuir as 112 pastas, haverá sempre algum arquivo com pelo menos 8 pastas.

Passo 4

Para confirmar que não podemos garantir n=9, basta exibir uma distribuição sem arquivo com 9 pastas. Por exemplo:
  • 8 arquivos com 7 pastas cada \;\Rightarrow\;8\times7=56
  • 7 arquivos com 8 pastas cada \;\Rightarrow\;7\times8=56
    Totaliza 56+56=112 pastas, e nenhum arquivo chega a 9 pastas. Logo, n=9 não está garantido.

Resposta

D) 8

Exercícios de Livros Relacionados