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.