Puntos en la Plaza de la unidad

Question

Que $n$ puntos dados en la Plaza de la unidad. Cómo probar o refutar: los puntos pueden ser etiquetados $x_1,\ldots,x_n$ para satisfacer la desigualdad $$\|x_1-x_2\|^2 +\|x_2-x_3\|^2+\cdots+\|x_n-x_1\| ^2 \le 4,$$ where $\|\cdot\| ¿$ es la distancia euclidiana?

Answer 1

[He visto este problema antes, y supongo que en Matemática Gemas por Ross, pero no estoy muy seguro. Yo también soy perezoso con la notación, y estoy tratando como puntos, en lugar de coordenadas.]

Lema: Vamos a $ABC$ ser un triángulo rectángulo con $\angle ABC = 90^\circ$. Hay $n$ puntos en el triángulo. Entonces, es posible encontrar una secuencia de puntos tales que

$$|Ax_1^2 | + |x_1 x_2|^2 + \ldots + |x_k B|^2 + |Bx_{k+1}|^2 + \ldots + |x_nC|^2 \leq |AC|^2$$

Prueba: procedemos por inducción sobre el número de puntos.

Deje $BD$ ser la perpendicular al lado $AC$. Aplicar la hipótesis de inducción, para obtener

$$|Ax_1^2 | + |x_1 x_2|^2 + \ldots + |x_i D|^2 + |Dx_{i+1}|^2 + \ldots + |x_jB|^2 \leq |AB|^2$$

$$|Bx_{j+1}^2 | + |x_{j+1} x_{j+2}|^2 + \ldots + |x_k B|^2 + |Bx_{k+1}|^2 + \ldots + |x_nC|^2 \leq |BC|^2$$

Ahora, queda por demostrar que $|x_i D|^2 + |Dx_{i+1}|^2 \leq |x_ix_{i+1}|^2$, pero esto es evidente, porque $\angle x_i D x_{i+1}$ es en la mayoría de las $90^\circ$. Lo mismo para $|x_k D|^2 + |Dx_{k+1}|^2 \leq |x_k x_{k+1}|^2$.

Agregar hasta tanto las desigualdades y aplicar ese $|AB|^2 + |BC|^2 = |AC|^2$.

Nota: Hay un pequeño problema de al $ABD$ o $BCD$ está vacía, que nos impide aplicar la hipótesis de inducción. Sin embargo, lo que simplemente hacer es seguir recortando el derecho de triángulos hasta llegar a una división de los puntos.

Corolario: Su pregunta

Prueba:

Vamos a la plaza del ser $ABCD$. Tiro en puntos de $A, B, C, D$ si no están ya en la lista. Aplicar el Lema de triángulo $ABC$$BCD$, y hemos terminado. Usted tendrá que aplicar un paso de el Lema de la prueba a quitar el $A, B, C, D$ si es necesario.

Seguimiento: se Puede clasificar a todos la igualdad de los casos? Considere cómo el Lema es probada.

Answer 2

Edit: no me di cuenta de las plazas por encima de las normas. Con los que en su lugar, es cierto que no es una permutación de vértices tales que $$\|x_1-x_2\|^2 +\|x_2-x_3\|^2+\cdots+\|x_n-x_1\| ^2 \leq 4. \tag{$\spadesuit$}$$

La estrategia es crear un problema de instancia (es decir, un conjunto de puntos) que maximiza el menor (en el sentido de la desigualdad $(\spadesuit)$) del ciclo y el punto clave es la combinación de:

• Teorema de pitágoras: $a^2+b^2=c^2$ en cualquier ángulo recto de un triángulo,
• la hipotenusa de cualquier triángulo recto hace que el diámetro de la circunferencia circunscrita.

Considere las siguientes imágenes.

Cualquier punto que se encuentra en el círculo rojo (como $X$), se puede omitir lo que la duración del ciclo (se mantiene la misma si el punto se encuentra en el círculo, como $X'$). También, para cualquier punto que se encuentra más allá de la línea roja (como $Y$), el punto intermedio $B$ tal vez omitidos por la misma razón. En otras palabras, para cualquier problema instancia que maximiza el ciclo más corto, puede ser que no exista puntos como $X$ o como $Y$ (de lo contrario el ejemplo podría ser modificada para que el ciclo más corto podría ser más largo). Esto implica que para cualquier instancia con el ciclo más corto de longitud $L$, existe una instancia de $4$ vértices que ciclo más corto es por lo menos de la longitud de la $L$. Esto (voy a omitir los casos de $n < 4$ aquí) implica $(\spadesuit)$.

Espero que esta ayuda ;-)

Editar:

Algo más de explicación. Por ejemplo, el corolario de la segunda imagen es esta: vamos a $A$ ser un conjunto de puntos en cuestión y $x_1,x_2,\ldots,x_n$ una secuencia que es el ciclo más corto (en el sentido de la desigualdad $(\spadesuit)$). Entonces, si hay un $x_i$ tal que $|\angle x_{i-1}x_ix_{i+1}| > \frac{\pi}{2}$, $B = A \setminus \{x_i\}$ el ciclo más corto es más largo que el ciclo más corto de $A$.

Answer 3

He visto esto en un blog, con la idea de la solución. Aquí está.