Prove que em qualquer conjunto R de 17 inteiros há um subconjunto S 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 R de 17 inteiros, mostremos que existe um subconjunto S\subseteq R com \lvert S\rvert=5 tal que, para quaisquer x,y\in S, ou x-y ou x+y é múltiplo de 7.
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 R pelas suas classes de resto ao dividir por 7. Para i=0,1,\dots,6 definimos
R_i = \{\,x\in R : x\equiv i\pmod{7}\}.
Então R é a união disjunta dos R_i e
\sum_{i=0}^6 |R_i| = 17.

Passo 3

Note que se dois números estão na mesma classe R_i, digamos x,y\in R_i, então
x-y\equiv 0\pmod7,
ou seja, a diferença é múltiplo de 7.
Além disso, se x\in R_i e y\in R_j com i+j\equiv0\pmod7, então
x+y\equiv i+j\equiv0\pmod7,
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:
G_0 = R_0, \qquad G_1 = R_1\cup R_6, \qquad G_2 = R_2\cup R_5, \qquad G_3 = R_3\cup R_4.
Em cada G_k, se x,y estão na mesma subclasse de G_k então x-y é múltiplo de 7; se estão em subclasses complementares, então x+y é múltiplo de 7). Logo, cada G_k é um “clique” no grafo de adjacência definido pela condição do enunciado.

Passo 5

Temos
|G_0| + |G_1| + |G_2| + |G_3| = \sum_{i=0}^6 |R_i| = 17.
Pelo princípio da casa dos pombos, um desses quatro grupos tem tamanho pelo menos
\bigl\lceil 17/4\bigr\rceil = 5.
Seja G_k esse grupo com |G_k|\ge5. Basta então escolher quaisquer 5 elementos de G_k para formar S.

Resposta

Escolhendo S como qualquer subconjunto de 5 elementos do grupo G_k com |G_k|\ge5, garantimos que, para todo par x,y\in S, ou x-y ou x+y é múltiplo de 7, como desejado.

Exercícios relacionados