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?
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
a
. No item (a) escolhemos
desses inteiros e queremos mostrar que entre eles há pelo menos dois pares cuja soma é
. O conteúdo necessário é o Princípio da Casa dos Pombos (Pigeonhole Principle), usando os “pares complementares” que somam
.
Passo 2
Identificamos os
pares disjuntos que somam
:
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
elementos (o par completo).
Passo 3
Seja
o número de inteiros selecionados. Chamemos de
a quantidade de inteiros escolhidos no
-ésimo par. Como existem
pares,
O número de pares completos (ou seja, com
) é no mínimo
pois cada par completo contribui com
, e os pares com
ou
contribuem com valor não negativo.
Passo 4
No caso do item (a),
. Logo o número de pares completos é pelo menos
Isto significa que obrigatoriamente existem pelo menos dois pares de inteiros escolhidos cuja soma é
.
Passo 5
No caso de selecionar
inteiros, o mesmo raciocínio dá
Isso mostra que com
inteiros teremos garantido ao menos um par que soma
, mas não dois.
Passo 6
Para ver que não asseguramos dois pares com
escolhas, basta o contraexemplo
Dessa seleção só o par
soma
, logo há exatamente um par e não dois.
Resposta
(a) Há sempre pelo menos dois pares cuja soma é
.
(b) Não: com seis números selecionados podemos ter apenas um par que soma .
(b) Não: com seis números selecionados podemos ter apenas um par que soma