Encontrar el mínimo posible perímetro de un convexo $n$-gon con vértices en los puntos con coordenadas enteras. El polígono debe tener ángulos interiores de menos de $180$ grados.
Se garantiza que $n$ es incluso. Para $n = 4$ el resultado debería ser $4$.
Lo mejor es hacer un cuadrado con lado de longitud $1$ en esta prueba.
Para $n = 10$ el resultado debería ser $14.12899$.
.
Este es un ejemplo de un convexo $10$de lados del polígono con el mínimo perímetro (con vértices en coordenadas enteras). Tiene cuatro lados de longitud $1$, cuatro lados de longitud $\sqrt{2}$, y los dos lados de longitud $\sqrt{5}$, para un total de alrededor de $14.12899$. ¿Cuál es la fórmula?
Respuestas
¿Demasiados anuncios?
JiminyCricket
Puntos
143
Cada eje corresponde a un punto en $\mathbb Z^2\setminus\{0\}$. (Para visualizar esto, escoja una orientación, atravesar el polígono y para cada borde, el cambio inicial de vértice en el origen y marca el final de vértice con un punto.)
La contribución de un borde para el perímetro es la distancia del punto correspondiente en el $\mathbb Z^2\setminus\{0\}$ desde el origen. Usted no puede utilizar el mismo punto dos veces (ya que se produciría un "ángulo de $\pi$" que la pregunta no permite). Tan solo añadir la distancia desde el origen hasta la próxima $n$$\mathbb Z$.
Anthony Cramp
Puntos
126
comentario
Espero que el OP no importa si hablamos de $n$ impares así.
Llame a los puntos en joriki a responder a la orilla de los vectores. Al $n$ es extraño, tal vez no podemos elegir el $n$ puntos más cercana al origen visible desde el origen como el borde de los vectores, ya que no puede agregar a $(0,0)$.
Podemos obtener el menor perímetro por elegir el más cercano a $n-1$ puntos y, a continuación, utilizando el último punto para obtener la suma de $(0,0)$? No, al$n=5$, $4$ más cercano los puntos ya tiene suma cero. De modo que podemos tener en la mayoría de las $3$ borde vectores de longitud $1$.
Tal vez que no funciona para $n=11$. De todos modos, aquí es una $11$-gon con perímetro $4+4\sqrt{2}+2\sqrt{5}+\sqrt{10}$:
Es que el mínimo para $n=11$? El borde de los vectores de $$ (1, 0) , (2, 1) , (1, 1) , (0, 1) , (-1, 2) , (-1, 1) , (-1, 0) , (-1, -1) , (-1, -3) , (0, -1) , (1, -1) $$ Es claro que para el mínimo perímetro debemos usar todo el borde de vectores de longitud $1$ y todo el borde de vectores de longitud $\sqrt{2}$?
Es claro que, en general, que una configuración mínima con $n$ impar no puede utilizar el borde de vectores $(2,0)$ pero no $(1,0)$?
Permítanme añadir $n=6$ $n=8$ según joriki del método, según lo solicitado por la luna.
