a) Mostre que se sete números inteiros são selecionados a partir dos 10 primeiros números inteiros positivos, deverá haver pelo menos dois pares desses inteiros cuja soma seja igual a 11.
b) A conclusão do item (a) será verdadeira se seis inteiros, em vez de sete, forem selecionados?

Passo 1

O enunciado pede para selecionar inteiros de 1 a 10. No item (a) escolhemos 7 desses inteiros e queremos mostrar que entre eles há pelo menos dois pares cuja soma é 11. O conteúdo necessário é o Princípio da Casa dos Pombos (Pigeonhole Principle), usando os “pares complementares” que somam 11.

Passo 2

Identificamos os 5 pares disjuntos que somam 11:
(1,10),\;(2,9),\;(3,8),\;(4,7),\;(5,6).
Cada um desses pares será uma “gaveta”. Ao escolhermos alguns inteiros, cada inteiro cai exatamente numa gaveta, e numa gaveta podemos ter no máximo 2 elementos (o par completo).

Passo 3

Seja k o número de inteiros selecionados. Chamemos de s_i\in\{0,1,2\} a quantidade de inteiros escolhidos no i-ésimo par. Como existem 5 pares,
\sum_{i=1}^{5} s_i = k,\quad\text{com }0\le s_i\le2.
O número de pares completos (ou seja, com s_i=2) é no mínimo
\sum_{i=1}^{5}(s_i-1) = \Bigl(\sum_{i=1}^{5}s_i\Bigr) -5 = k-5,
pois cada par completo contribui com s_i-1=1, e os pares com s_i=0 ou 1 contribuem com valor não negativo.

Passo 4

No caso do item (a), k=7. Logo o número de pares completos é pelo menos
k-5 = 7 - 5 = 2.
Isto significa que obrigatoriamente existem pelo menos dois pares de inteiros escolhidos cuja soma é 11.

Passo 5

No caso de selecionar k=6 inteiros, o mesmo raciocínio dá
k-5 = 6 - 5 = 1.
Isso mostra que com 6 inteiros teremos garantido ao menos um par que soma 11, mas não dois.

Passo 6

Para ver que não asseguramos dois pares com 6 escolhas, basta o contraexemplo
\{1,2,3,4,5,6\}.
Dessa seleção só o par (5,6) soma 11, logo há exatamente um par e não dois.

Resposta

(a) Há sempre pelo menos dois pares cuja soma é 11.
(b) Não: com seis números selecionados podemos ter apenas um par que soma 11.

Exercícios relacionados