Questão 7. Seja S um 677 - subconjunto do \{1,2, \ldots, 2022\}. Prove que é possível encontrar 2 elementos distintos em S , digamos \mathbf{a} e \mathbf{b}, tais que 6 \mid \mathbf{a}+\mathbf{b}.

Passo 1

Vou traduzir com calma o que o enunciado dá e o que pede.
  • Dado: S é um subconjunto de \{1,2,\ldots,2022\} com |S|=677.
  • Pedido: provar que existem dois elementos distintos a,b\in S tais que 6\mid a+b.
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 6.
Quando trabalhamos com divisibilidade por 6 é natural olhar os restos possíveis ao dividir por 6. Os restos possíveis são 0,1,2,3,4,5. Dizer que um número x está na classe r significa x\equiv r\pmod{6}. Dois números x,y satisfazem 6\mid x+y exatamente quando os restos de x e y somam 0 módulo 6. Por exemplo:
  • restos 0 e 0 somam 0 (pois 0+0\equiv0\pmod{6});
  • restos 1 e 5 somam 6\equiv0\pmod{6};
  • restos 2 e 4 somam 6\equiv0\pmod{6};
  • restos 3 e 3 somam 6\equiv0\pmod{6}.
Logo, pares de classes “problemáticas” (que dão soma múltipla de 6) são (0,0),(3,3),(1,5),(2,4).

Passo 3

Contagem de quantos números de \{1,\dots,2022\} há em cada classe de resto modulo 6.
Como 2022 é múltiplo de 6 — de fato 6\cdot337=2022 — cada resto r\in\{0,1,2,3,4,5\} aparece exatamente 337 vezes entre 1 e 2022. Uma forma de ver isso: os números congruentes a r são r, r+6, r+12,\dots até \le 2022; como 2022/6=337 não sobra resto, a sequência tem 337 termos para cada r.
Portanto, no universo \{1,\dots,2022\} cada classe de resto modulo 6 tem exatamente 337 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 S não existam dois elementos distintos cuja soma seja múltipla de 6. Vou ver qual é o máximo possível de elementos que S poderia ter sob essa hipótese; se esse máximo for menor que 677, teremos contradição, o que prova a existência do par procurado.

Passo 5

Impor as restrições que aparecem quando não queremos pares cuja soma seja múltipla de 6.
Pelo item de pares problemáticos:
  • Na classe 0 não podemos ter dois elementos, porque 0+0\equiv0. Logo, podemos ter no máximo 1 elemento de resto 0 em S.
  • Na classe 3 também não podemos ter dois elementos (pois 3+3\equiv0), logo no máximo 1 elemento de resto 3.
  • Entre as classes 1 e 5 não podemos ter números de ambas as classes ao mesmo tempo (qualquer um de resto 1 somado a qualquer um de resto 5 dá resto 0). Portanto, para evitar pares com soma múltipla de 6 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 1 não violam a condição).
  • De modo análogo, entre as classes 2 e 4 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 6":
  • no máximo 1 da classe 0;
  • no máximo 1 da classe 3;
  • ou se escolho da classe 1 então não escolho da 5, e vice-versa;
  • ou se escolho da classe 2 então não escolho da 4, e vice-versa.

Passo 6

Calcular o máximo possível de elementos em S respeitando essas restrições, lembrando que cada classe tem até 337 elementos disponíveis no universo \{1,\dots,2022\}.
  • Para o par \{1,5\} posso escolher, no máximo, todos os 337 elementos de uma das classes (por exemplo, escolho todos os de resto 1 e nenhum de resto 5), então contribui no máximo com 337.
  • Para o par \{2,4\} análogo, contribuição máxima 337.
  • Da classe 0 no máximo 1.
  • Da classe 3 no máximo 1.
Somando os máximos permitidos sob a hipótese:
337 \;+\; 337 \;+\; 1 \;+\; 1 \;=\; 674 \;+\; 2 \;=\; 676.
Portanto, qualquer subconjunto de \{1,\dots,2022\} que não contenha dois elementos cuja soma seja múltipla de 6 tem cardinalidade no máximo 676.

Passo 7

Conclusão por contradição.
Mas S tem |S|=677. Isso excede o máximo 676 compatível com a hipótese de que não existam dois elementos cuja soma seja múltipla de 6. Logo a hipótese é falsa. Portanto existem dois elementos distintos a,b\in S tais que 6\mid a+b.

Resposta

Existem dois elementos distintos a,b\in S tais que 6\mid a+b.

Exercícios relacionados