Problema 2:
Encontre o menor $$n$$ tal que qualquer conjunto de $$n$$ pontos do plano cartesiano, todos com coordenadas inteiras, contém dois cujo quadrado da distância é um múltiplo de $$2016$$.
Solução de Matheus Bezerra:
Afirmação: O menor valor possível de $$n$$ é $$14113$$.
Demonstração:
Sabemos que a distância entre dois pontos $$(x_1, y_1)$$ e $$(x_2, y_2)$$ do plano é dada por $$\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$$. Sendo assim, para que esses dois dois pontos tenham o quadrado de sua distância um múltiplo de $$2016$$, devemos ter $$(x_1-x_2)^2+(y_1-y_2)^2\equiv 0~(mod~2016)$$. Enunciemos então um fato útil para nossa solução:
Lema: Seja $$p$$ é um número primo da forma $$4k+3$$. Então
$$p\mid a^2+b^2\Leftrightarrow p\mid a$$ e $$p\mid b$$.
Prova: Suponha, por absurdo, que $$p\nmid a, b$$. Se $$a$$ ou $$b$$ é múltiplo de $$p$$, então o outro terá que ser múltiplo de $$p$$ também. Afinal, $$a^2+b^2 \equiv 0 ~(mod~p)$$ . Portanto, podemos supor que ambos não são $$0 ~(mod~p)$$ e agora, considerando a sequência de congruências no módulo $$p$$:
$$b^2\equiv -a^2$$
$$\implies (b^2)^{\dfrac{p-1}{2}}\equiv (-a^2)^{\dfrac{p-1}{2}}$$
$$\implies(b^{p-1})\equiv (-1)^{\dfrac{p-1}{2}} \cdot (a^2)^{\dfrac{p-1}{2}}$$
Lembrando que $$\dfrac{p-1}{2}$$ é ímpar pois $$p=4k+3$$, então $$(-1)^{\dfrac{p-1}{2}}= -1$$. Além disso, já que $$b$$ não é múltiplo de $$p$$, pelo Pequeno Teorema de Femat, $$b^{p-1}\equiv 1 ~(mod~p)$$. Logo:
$$\implies 1\equiv (-1) \cdot(a^{p-1}) \cdot ~(mod~p)\implies$$.
De novo por Fermat, temos:
$$1 \equiv (-1)\cdot 1~(mod~p)\implies$$
$$2\equiv 0 ~(mod~p)\implies p|2$$.
O que é um absurdo, uma vez que $$p$$ é maior que $$2$$. Portanto, segue o resultado $$\square$$
Como consequência do lema anterior, se $$p=4k+3$$ é um primo vale que $$a^2+b^2\equiv 0~(mod~p)\Leftrightarrow a^2+b^2\equiv 0~(mod~p^2)$$, já que $$p\mid a, b\implies p^2\mid a^2, b^2\implies p^2\mid a^2+b^2$$.
Perceba agora que a fatoração em primos é $$2016=2^5\cdot 3^2\cdot 7$$. Logo, queremos encontrar quando dois pontos do plano satisfazem $$(x_1-x_2)^2+(y_1-y_2)^2\equiv 0~(mod~3^2,~7,~32)$$.
Usando o resultado descrito acima, a congruência para o primeiro módulo $$3^2=(4\cdot 0 + 3)^2$$ é satisfeita se, e somente se, $$3\mid (x_1-x_2), (y_1-y_2)$$.
Novamente pelo Lema anterior: $$(x_1-x_2)^2+(y_1-y_2)^2\equiv 0~(mod~7)\Leftrightarrow 7\mid (x_1-x_2), (y_1-y_2)$$.
Agora, veremos para $$(mod~32)$$:
Veja que se $$a^2+b^2\equiv 0~(mod~32)$$, caso $$a$$ seja ímpar, $$b$$ também será e deveríamos ter $$a^2+b^2\equiv 2~(mod~4)$$ (já que todo quadrado de ímpar deixa resto $$1$$ na divisão por $$4$$). Porém isso é um absurdo, pois estamos supondo que $$ a^2+b^2 \equiv 0 ~(mod~4)$$, implicando que $$ a^2+b^2 \equiv~(mod~4)$$. Concluímos então que ambos são pares, ou seja: $$a=2a’$$ e $$b=2b’$$, gerando:$$4a’^2+4b’^2\equiv 0~(mod~32)\implies a’^2+b’^2\equiv 0~(mod~8)$$, e pelo mesmo argumento anterior temos $$a’=2a”$$ e $$b’=2b”$$, implicando agora em $$4a”^2+4b”^2\equiv 0~(mod~8)\implies a”^2+b”^2\equiv 0~(mod~2)$$, o que nos diz que $$a”$$ e $$b”$$ possuem a mesma paridade. Se ambos são pares, então: $$a, b\equiv 0~(mod~8)$$. Se forem ímpares: $$a, b\equiv 4~(mod~8)$$. Como $$a=(x_1-x_2)$$ e $$b=(y_1-y_2)$$, temos que $$8\mid (x_1-x_2), (y_1-y_2)$$ ou $$8\mid (x_1-x_2)+4, (y_1-y_2)+4$$.
De posse desses resultados, pelo Teorema Chinês dos Restos, isso ocorre nos casos em que $$(x_1-x_2)\equiv (y_1-y_2)\equiv 0~(mod~168=3\cdot 7\cdot 8)$$ ou $$(x_1-x_2)\equiv (y_1-y_2)\equiv 84~(mod~168)$$. Portanto, a primeira condição nos permite pegar no máximo $$168^2$$ pontos, com todas as possíveis combinações distintas de resíduos no módulo $$168$$ para as abscissa e ordenada do ponto. Dentre esses, a segunda condição nos restringe a podermos pegar no máximo metade, visto que se tomarmos um ponto $$(x, y)$$, não poderemos tomar os pontos $$(x\pm84, y\pm84)$$, que são equivalentes ao ponto único $$(x+84, y+84)$$ (com coordenadas no módulo $$168$$), já que $$84\equiv -84~(mod~168)$$. Portanto, conseguimos pegar no máximo metade de $$168^2$$ pontos do plano tais que o quadrado da distância deles não seja múltiplo de $$2016$$.
Aliás, agora mostra-se a importância de termos feitos todas as congruências em equivalências bilaterais, em vez de implicações. Tome o conjunto de pontos no plano: $$S=(x,y) | 0 \leq x \leq 83$$ e $$0 \leq y \leq 167$$, e suponha que hajam pontos $$(a,b)$$ e $$(c,d)$$ cujo quadrado distância é múltiplo de $$2016$$. Vimos que isso ocorre se e somente se: $$ a-c\equiv b-d \equiv 0~(mod~168)$$ ou $$a-c\equiv b-d \equiv 84~(mod~168)$$. Note que a diferença entre quaisquer duas abscissas está entre $$-83$$ e $$83$$. Logo, como $$84 \mid a-c$$ em ambos casos, $$a=c$$. Por outro lado, isso implica que estamos no caso em que: $$168 \mid b-d$$ e isso nos dá que $$b=d$$. Logo, os pares são o mesmo par. Isso conclui que este exemplo com $$84\times 168$$ pontos satisfaz não ter um par de pontos cujo quadrado da distância é $$2016$$.
Concluímos então que o menor $$n$$ tal que em quaisquer $$n$$ pontos de coordenadas inteiras no plano, dois deles possuem quadrado da distância múltiplo de $$2016$$ é, pelo Princípio das Casas dos Pombos, $$\dfrac{168^2}{2}+1=14113$$ $$\blacksquare$$