Olimpiadas de Matemáticas
Página de preparación y problemas

Solución. La respuesta es que sí es posible y para justificarlo daremos una forma de colorearlo. Dado un punto de coordenadas $(x,y)$,

• Lo pintamos de color A si las coordenadas $x,y$ tienen distinta paridad.
• Lo pintamos de color B si $x$ e $y$ son pares.
• Lo pintamos de color C si $x$ e $y$ son impares.

De esta manera, los colores A y B aparecen infinitas veces en las rectas de la forma $y=2k$ y los colores A y C aparecen infinitas veces en las rectas de la forma $y=2k+1$. Queda ver que cualquier recta $r$ contiene puntos de a lo sumo dos colores. Está claro que podemos suponer que la recta $r$ contiene al menos dos puntos de coordenadas enteras $P_1=(x_1,y_1)$ y $P_2=(x_2,y_2)$ y podemos suponer que no hay puntos de coordenadas enteras en el interior del segmento $P_1P_2$, luego el vector director $\vec{v}=(x_2-x_1,y_2-y_1)$ es tal que los puntos de $r$ de coordenadas enteras son los de la forma $P_1+n\vec{v}$ con $n\in\mathbb{Z}$. Distingamos varios casos:

• Si las dos coordenadas de $v$ son impares, entonces todos los puntos de $r$ son o bien todos de color A (cuando $x_1$ e $y_1$ tienen distinta paridad) o bien alternan entre colores B y C (cuando $x_1$ e $y_1$ tienen la misma paridad).
• Si la primera coordenada de $v$ es impar y la segunda par, entonces los puntos de $r$ o bien alternan entre colores A y B o entre colores A y C (dependiendo de la paridad de $y_1$). Análogamente ocurre cuando la primera coordenada de $v$ es par y la segunda impar.
• No puede ocurrir que las dos coordenadas de $v$ sean pares ya que en tal caso el punto medio $P_1+\frac{1}{2}\vec{v}$ también tendría coordenadas enteras y estaría en el interior del segmento $P_1P_2$.

Nota. Una dificultad de este problema es que la intuición parece decirnos que la coloración no puede existir ya que hay demasiadas rectas posibles. Sin embargo, si nos ponemos en que sí puede existir y pensamos en que en cada recta con al menos dos colores estos alternan, es fácil llegar a la solución propuesta.