OBM 2019 - Nível 2 - P6

PROBLEMA 6. (enunciado corrigido)

No plano cartesiano, todos os pontos com ambas as coordenadas inteiras são pintados de azul. Dois pontos azuis são ditos mutuamente visíveis se o segmento de reta que os conecta não possui outros pontos azuis. Prove que não existe um conjunto de $5$ pontos azuis mutuamente visíveis dois a dois.

Solução de Gabriella Morgado.

Notemos que o ponto médio de dois pontos azuis $P_i$ e $P_j$ de coordenadas $(x_i,y_i)$ e $(x_j,y_j)$, respectivamente, não pode ser azul para que $P_i$ e $P_j$ sejam mutuamente visíveis. Portanto, como o ponto médio de $P_i$ e $P_j$ é dado por

$\left( \frac{x_i+x_j}{2},\frac{y_i+y_j}{2} \right)$

Segue que

$\left( \frac{x_i+x_j}{2} \right)$ ou $\left( \frac{y_i+y_j}{2} \right)$ não é inteiro.

Então, $x_i$ e $x_j$ ou $y_i$ e $y_j$ têm paridades diferentes.

Suponhamos que haja $5$ ou mais pontos azuis mutuamente visíveis dois a dois.

Mas, as opções de paridade para cada ponto são:

• $x_i$ ímpar e $y_i$ ímpar;
• $x_i$ ímpar e $y_i$ par;
• $x_i$ par e $y_i$ ímpar;
• $x_i$ par e $y_i$ par.

Pelo Princípio da Casa dos Pombos, há dois pontos com $x_A$ e $x_B$ e $y_A$ e $y_B$ de mesma paridade.

Então, esses pontos $P_A$ e $P_B$ não podem ser mutuamente visíveis: contradição!

Segue que não há um conjunto de $5$ pontos azuis mutuamente visíveis dois a dois. $\blacksquare$

Comentário: A banca organizadora da OBM decidiu por anular o problema 6 e comunicou que todos os estudantes ganharam os 50 pontos do problema. Provavelmente, o criador do problema queria propor um problema de combinatória geométrica que usasse o Teorema Chinês dos Restos. Com base nisso e na complexidade de um problema 6 de OBM Nível 2; sugerimos aos estudantes resolverem o seguinte problema:

Inglaterra 2014/15 Rodada 2:

Dados dois pontos $P$ e $Q$ com ambas coordenadas inteiras(lattice points), nós dizemos que $P$ enxerga o ponto $Q$ se o segmento $PQ$ não contém outros lattice points. Um $n$-loop é uma sequência de $n$ pontos $P_1, P_2,...,P_n$, cada um deles é um lattice point, tal que as seguintes condições são satisfeitas:

a) $P_i$ enxerga $P_{i+1}$ para todo $1\leq i\leq n-1$ e $P_n$ enxerga $P_1$;

b) Nenhum $P_i$ enxerga qualquer outro $P_j$, exceto os mencionados no item a);

c) Não há três pontos colineares.

Determine se existe um $100$-loop.