Questão 7. Seja S um 677 - subconjunto do
. Prove que é possível encontrar 2 elementos distintos em S , digamos
e
, tais que
.
Passo 1
Vou traduzir com calma o que o enunciado dá e o que pede.
- Dado:
é um subconjunto de com . - Pedido: provar que existem dois elementos distintos
tais que .
Anotação: não se resolve nada ainda; só listei os dados e o que precisa ser mostrado.
Passo 2
Conceito útil — classes de resto módulo
.
Quando trabalhamos com divisibilidade por é natural olhar os restos possíveis ao dividir por
. Os restos possíveis são
. Dizer que um número
está na classe
significa
. Dois números
satisfazem
exatamente quando os restos de
e
somam
módulo
. Por exemplo:
Quando trabalhamos com divisibilidade por
- restos
e somam (pois ); - restos
e somam ; - restos
e somam ; - restos
e somam .
Logo, pares de classes “problemáticas” (que dão soma múltipla de
) são
.
Passo 3
Contagem de quantos números de
há em cada classe de resto modulo
.
Como é múltiplo de
— de fato
— cada resto
aparece exatamente
vezes entre
e
. Uma forma de ver isso: os números congruentes a
são
até
; como
não sobra resto, a sequência tem
termos para cada
.
Como
Portanto, no universo
cada classe de resto modulo
tem exatamente
elementos.
Passo 4
Estratégia do argumento (princípio da casa dos pombos / contagem por exclusão).
Vamos provar por contradição: suponha que em não existam dois elementos distintos cuja soma seja múltipla de
. Vou ver qual é o máximo possível de elementos que
poderia ter sob essa hipótese; se esse máximo for menor que
, teremos contradição, o que prova a existência do par procurado.
Vamos provar por contradição: suponha que em
Passo 5
Impor as restrições que aparecem quando não queremos pares cuja soma seja múltipla de
.
Pelo item de pares problemáticos:
Pelo item de pares problemáticos:
- Na classe
não podemos ter dois elementos, porque . Logo, podemos ter no máximo elemento de resto em . - Na classe
também não podemos ter dois elementos (pois ), logo no máximo elemento de resto . - Entre as classes
e não podemos ter números de ambas as classes ao mesmo tempo (qualquer um de resto somado a qualquer um de resto dá resto ). Portanto, para evitar pares com soma múltipla de devemos escolher elementos de, no máximo, uma dessas duas classes; podemos, porém, ter muitos elementos todos da mesma classe (por exemplo, vários elementos todos congruentes a não violam a condição). - De modo análogo, entre as classes
e não podemos ter elementos de ambas as classes; podemos escolher elementos de, no máximo, uma delas.
Resumo das restrições sob a hipótese "nenhum par soma múltiplo de
":
- no máximo
da classe ; - no máximo
da classe ; - ou se escolho da classe
então não escolho da , e vice-versa; - ou se escolho da classe
então não escolho da , e vice-versa.
Passo 6
Calcular o máximo possível de elementos em
respeitando essas restrições, lembrando que cada classe tem até
elementos disponíveis no universo
.
- Para o par
posso escolher, no máximo, todos os elementos de uma das classes (por exemplo, escolho todos os de resto e nenhum de resto ), então contribui no máximo com . - Para o par
análogo, contribuição máxima . - Da classe
no máximo . - Da classe
no máximo .
Somando os máximos permitidos sob a hipótese:
Portanto, qualquer subconjunto de
que não contenha dois elementos cuja soma seja múltipla de
tem cardinalidade no máximo
.
Passo 7
Conclusão por contradição.
Mas tem
. Isso excede o máximo
compatível com a hipótese de que não existam dois elementos cuja soma seja múltipla de
. Logo a hipótese é falsa. Portanto existem dois elementos distintos
tais que
.
Mas
Resposta
Existem dois elementos distintos
tais que
.