Prove que em qualquer conjunto
de 17 inteiros há um subconjunto
de 5 elementos com a seguinte propriedade: para qualquer par de elementos em S, a soma ou diferença deles é divisível por 7.
Passo 1
O enunciado pede que, dado qualquer conjunto
de
inteiros, mostremos que existe um subconjunto
com
tal que, para quaisquer
, ou
ou
é múltiplo de
.
Conteúdo: classes de resíduos módulo 7, princípio da casa dos pombos e construção de “grupos” que sejam cliques (isto é, qualquer par satisfaz a condição).
Conteúdo: classes de resíduos módulo 7, princípio da casa dos pombos e construção de “grupos” que sejam cliques (isto é, qualquer par satisfaz a condição).
Passo 2
Classificamos os elementos de
pelas suas classes de resto ao dividir por
. Para
definimos
Então
é a união disjunta dos
e
Passo 3
Note que se dois números estão na mesma classe
, digamos
, então
ou seja, a diferença é múltiplo de 7.
Além disso, se e
com
, então
Além disso, se
ou seja, a soma é múltiplo de 7.
Passo 4
Agrupamos as classes de forma a garantir que, dentro de cada grupo, qualquer par de elementos satisfaz uma das duas divisibilidades. Definimos quatro grupos:
Em cada
, se
estão na mesma subclasse de
então
é múltiplo de 7; se estão em subclasses complementares, então
é múltiplo de 7). Logo, cada
é um “clique” no grafo de adjacência definido pela condição do enunciado.
Passo 5
Temos
Pelo princípio da casa dos pombos, um desses quatro grupos tem tamanho pelo menos
Seja
esse grupo com
. Basta então escolher quaisquer 5 elementos de
para formar
.
Resposta
Escolhendo
como qualquer subconjunto de 5 elementos do grupo
com
, garantimos que, para todo par
, ou
ou
é múltiplo de 7, como desejado.