OBM 2016 - Nível 3 - P2

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$