Quantos números devem ser selecionados a partir do conjunto \{1,3,5,7,9,11,13,15\} para garantir que pelo menos um par desses números some 16 ?

Passo 1

O enunciado pede o número mínimo de elementos a escolher do conjunto \{1,3,5,7,9,11,13,15\} para garantir que existam dois cuja soma seja 16. O conteúdo envolvido é o Princípio da Casa dos Pombos (pigeonhole).

Passo 2

Observamos que os únicos pares que somam 16 são:
(1,15),\;(3,13),\;(5,11),\;(7,9).
Estes formam 4 pares disjuntos que cobrem todo o conjunto.

Passo 3

Para evitar qualquer par com soma 16, podemos escolher no máximo um elemento de cada par, totalizando 4 escolhas sem criar soma 16.

Passo 4

Pelo Princípio da Casa dos Pombos, ao escolher mais que 4 elementos, isto é, 4+1=5, obrigatoriamente teremos os dois elementos de algum par, somando 16.

Resposta

5

Exercícios relacionados