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?
Respuestas
¿Demasiados anuncios?
[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.
dtldarek
Puntos
23441
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$.
