1. 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á 15 executivos distribuídos entre 5 assistentes, de modo que cada executivo tem exatamente um assistente e nenhum assistente atende mais do que 4 executivos. Queremos mostrar que pelo menos 3 assistentes atendem 3 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 x_i o número de executivos atendidos pelo assistente i, para i=1,2,3,4,5. Então temos
\sum_{i=1}^{5} x_i = 15
e além disso
0 \le x_i \le 4
para todo i.

Passo 3

Suponha, por absurdo, que no máximo 2 assistentes atendam 3 ou mais executivos. Isso significa que pelo menos 3 assistentes atendem no máximo 2 executivos, ou seja, para eles x_i \le 2. Para maximizar a soma \sum x_i sob essa hipótese, damos o valor máximo permitido a cada classe:
  • Aos até 2 assistentes grandes atribuímos x_i=4.
  • Aos 3 assistentes pequenos atribuímos x_i=2.
    Assim o total máximo seria
2\cdot 4 \;+\; 3\cdot 2 \;=\; 8 + 6 \;=\; 14 < 15,
o que contradiz \sum_{i=1}^5 x_i=15.

Passo 4

A hipótese de que existem no máximo 2 assistentes com x_i\ge3 levou a uma soma máxima de 14, abaixo de 15. Logo essa hipótese é falsa e devemos ter pelo menos 3 assistentes com x_i\ge3.

Resposta

Pelo menos três assistentes trabalham para três ou mais executivos.

Exercícios relacionados