Los puntos de "ver" el uno al otro en un bucle

Question

Para dos puntos de $P,Q$ con coordenadas enteras en $2$ dimensiones, podemos decir que $P$ "ve" $Q$ fib el segmento de $PQ$ no contiene otros puntos con coordenadas enteras. ¿Existen puntos de $P_1,\ldots,P_{100}$ tal que $P_i$ ve $P_{i+1}$ $i=1,2,\ldots,99$, $P_{100}$ ve $P_1$, no hay otro par de puntos que ve uno al otro, y no hay tres puntos son colineales?

(British Olimpíadas De Matemáticas 2014/15)

Si sólo necesitamos $4$ de los puntos, podemos utilizar $(-1,0),(0,1),(1,0),(0,-1)$. Cómo podemos generalizar a más puntos?

Answer 1

Esta es una construcción de la pregunta, así que piensa acerca de lo que las posibilidades de enfoque. Claramente, adelante inducción, inducción hacia atrás, algoritmo voraz son malos candidatos. Esto nos deja con la estructura avoider y el buscador de enfoque. (Vea el enlace para más detalles).

Reclamo: Punto de $(x_1, y_1), (x_2, y_2)$ ver entre sí, si y sólo si $\gcd ( x_1 - x_2 , y_1 - y_2 ) \neq 1$.

Esto es obvio. Prueba a ti mismo. Esta es la estructura que estamos tratando de encontrar / evitar.

---

Caso General 1: $k+2$ puntos, donde $k = p_2 - p_1$ es la diferencia de 2 números primos con $p_1 > k$.

Considere la posibilidad de la $k+1$ puntos de la forma $(n, n^2)$. A partir de lo anterior, desde la $\gcd (i-j, i^2 - j^2 ) = i-j$, por lo tanto, estos $k$ puntos son sólo visibles para sus vecinos, y no el de nadie más.

Deje que el último punto se denota por a $(x_0, y_0)$.
Observar que $\gcd( x_0 - i, y_0 - i^2 ) = \gcd( x_0 - i, y_0 - x_0 ^2 )$.
Nos pusimos $x_0 = p_2+1$. Esto nos da $x_0 - 1 = p_2$$x_0 - (k+1) = p_1$.
Por lo tanto, para satisfacer las condiciones, necesitamos $p_ 1 \not \mid y_0 - x_0^2 , p_ 2 \not \mid y_0- x_0^2$, pero $j \mid y_o - x_0^2$ todos los $p_1 < j < p_2$.
Este es satisfecho mediante la toma de $y_0 - x_0^2 = LCM ( j)$, ya que por la condición de $2p_1 > p_1 + k = p_2$ e lo $p_ 1 \not \mid LCM (j)$.

Ahora, aplicar esto a $k = 98, p_1 = 101, p_2 = 199$, y que el problema original se hace.

---

Caso General 2: $p+1$ puntos, donde $p$ es primo. No funciona por 100.
Esta realidad es similar a la primera, con la comprensión de la "$p_1 = -1$", y el trabajo en torno a las dificultades que surgen. De hecho, me ocurrió con este caso, primero, y luego trató de generalizar más allá.

Ahora, considere la posibilidad de la $p$ puntos de la forma $(n, n^2)$. A partir de lo anterior, desde la $\gcd (i-j, i^2 - j^2 ) = i-j$, por lo tanto, estos $p$ puntos son sólo visibles para sus vecinos, y no el de nadie más.

Deje que el último punto se denota por a $(x_0, y_0)$.
Observar que $\gcd( x_0 - i, y_0 - i^2 ) = \gcd( x_0 - i, y_0 - x_0 ^2 )$.
Vamos a recoger a $x_0 = p+1$, lo que nos da $\gcd ( p+1 - p, y_0 - p^2 ) = 1$ cualquier $y_0$.
Para$i = 2$$p-1$, necesitaremos $\gcd ( p+1 - i, y_0 - i^2 ) \neq 1$, o que $\gcd( p+1 - i, y_0 - (p+1)^2 ) \neq 1$. De hecho, vamos a $\gcd( p+1 - i, y_0 - (p+1) ^ 2 ) = p+1 - i$ sí. Esto nos da la opción de $y_0 - (p+1)^2 = K \times LCM ( 2, 3, \ldots, p-1)$.
Por último, debemos asegurarnos de que $\gcd(p, y_0 -1^2 ) = 1$, lo cual se logra con $K=1$, ya que el $y_0 - (p+1)^2$ no será un múltiplo de $p$.

---

Nota: El uso de puntos en el específico polinomio $f(n) = n^2$ no es necesario. Cualquier polinomio con coeficientes enteros en general funciona, pero también ha de satisfacer la condición de que no se entero 3 puntos son colineales. En particular, cuadráticas satisfacer esta trivialmente, y así elegí la más simple cuadrática.

Sospecho que esta declaración es verdadera para todos los $n$, pero no sé cómo demostrar que aún. Como se ve, los números primos, y el primer lagunas, son extremadamente importantes.