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$$