OBM 2016 - Nível 3 - P4

Problema 4

Qual é a maior quantidade de inteiros positivos menores ou iguais a $2016$ que podemos escolher de modo que não haja dois números cuja diferença é $1$, $2$ ou $6$?

Solução de Matheus Bezerra:

Afirmação: Em cada conjunto de $7$ inteiros consecutivos conseguimos escolher no máximo dois deles.

Demonstração: Suponha, por absurdo, que consigamos tomar $3$ inteiros e considere aquele que está entre os outros dois. A distância entre ele e cada um dos outros é pelo menos $3$, visto que, segundo o enunciado, não podemos selecionar dois números cuja distância seja $1$ ou $2$. Mas, isso indica que os dois números das pontas devem ser o menor e o maior números dentre os $7$ consecutivos, o que os faria ter distância $6$ um do outro. $\blacksquare$

Como há $288$ grupos de $7$ números consecutivos de $1$ a $2016$, têm-se que podemos escolher no máximo: $2\times288$ números. Um exemplo é obtido selecionando os números que deixam restos $1$ ou $4$ na divisão por $7$. A diferença entre quaisquer dois deles deixa restos $0$, $3$ ou $4$ na divisão por 7, assim não pode ser $1$, $2$ ou $6$.

1 2 3 4 5 6 7

8 9 10 11 12 13 14

15 16 17 18 19 20 21

22 23 24 25 26 27 28 ....

2010 2011 2012 2013 2014 2015 2016

Assim, provamos que a resposta é: $576$. $\blacksquare$