- Um grupo de 15 executivos usará os serviços de cinco assistentes. Cada executivo tem exatamente um assistente e nenhum assistente trabalha para mais de quatro executivos. Mostre que pelo menos três assistentes trabalham para três ou mais executivos.
Passo 1
O enunciado diz que há
executivos distribuídos entre
assistentes, de modo que cada executivo tem exatamente um assistente e nenhum assistente atende mais do que
executivos. Queremos mostrar que pelo menos
assistentes atendem
ou mais executivos. O conteúdo aqui é argumentar por contradição usando limites na soma de inteiros (princípio da casa dos pombos).
Passo 2
Seja
o número de executivos atendidos pelo assistente
, para
. Então temos
e além disso
para todo
.
Passo 3
Suponha, por absurdo, que no máximo
assistentes atendam
ou mais executivos. Isso significa que pelo menos
assistentes atendem no máximo
executivos, ou seja, para eles
. Para maximizar a soma
sob essa hipótese, damos o valor máximo permitido a cada classe:
- Aos até
assistentes grandes atribuímos . - Aos
assistentes pequenos atribuímos .
Assim o total máximo seria
o que contradiz
.
Passo 4
A hipótese de que existem no máximo
assistentes com
levou a uma soma máxima de
, abaixo de
. Logo essa hipótese é falsa e devemos ter pelo menos
assistentes com
.
Resposta
Pelo menos três assistentes trabalham para três ou mais executivos.