Valor máximo $c$ s.t. $\exists$ un subconjunto $S$ $\{z_1,z_2,\ldots,z_n\}$ s.t. $\left|\sum_{z\in S}z\right|\geq c$ ($\sum_{i=1}^{n}|z_i|=1$).

Question

La pregunta original es claro así que estoy completamente de reformuló la pregunta y siempre contexto completo:

Esta es la pregunta original (de la OCM 1986):

Deje $z_1,z_2,\cdots ,z_n$ ser números complejos satisfactoria $$|z_1|+|z_2|+\cdots +|z_n|=1.$$ Prove that there exists a subset $S$ of $\{z_1,z_2,\ldots,z_n\}$ such that $$\left|\sum_{z\in S}z\right|\geq\frac16.$$

Pero, obviamente, el límite inferior $\frac16$ es mucho menor que el óptimo. Por ejemplo, por el simple uso del principio del palomar y la desigualdad $|z|\leq\Re(z)+\Im(z)$ es fácil demostrar que para cada conjunto de números complejos $\{z_1,z_2,\ldots,z_n\}$ siempre existe $S$ tal que $\left|\sum_{z\in S}z\right|\geq\frac14$. Pero me pregunto cómo obtener el valor óptimo, es decir:

Deje $z_1,z_2,\cdots ,z_n$ ser números complejos satisfactoria $$|z_1|+|z_2|+\cdots +|z_n|=1.$$ Find the maximum value $c$ such that for every set of complex numbers $\{z_1,z_2,\ldots,z_n\}$ satisfying the condition above, there always exists a subset $S$ of $\{z_1,z_2,\ldots,z_n\}$ such that $$\left|\sum_{z\in S}z\right|\geq c.$$

He leído en el libro 101 Álgebra Problemas de la Formación de los Estados Unidos de la OMI Equipo (p85) que "el Uso de matemáticas avanzadas, el límite inferior puede ser mejorado a $\frac1{\pi}$." Pero, ¿exactamente cómo hago para obtener ese resultado?

Answer 1

Un poco de intuición para empezar: Nuestra idea básica aquí va a ser la de pensar de nuestros números complejos como vectores en $\mathbb{R}^2$ y el trabajo con las proyecciones, en lugar de longitudes, principalmente debido a que las proyecciones de trabajo que tan bien con respecto de la suma: La proyección de la suma es la suma de las proyecciones. Así que en lugar de intentar crear una cantidad grande de la norma, vamos a escoger una dirección y tratar de crear una suma con gran proyección/componente a lo largo de dicho vector.

Supongamos que me dio una dirección $v$ por adelantado, y todo lo que quería hacer era maximizar el componente de la suma a lo largo de $v$. A continuación, la elección de su subconjunto sería fácil: Se incluyen los vectores que apuntan "hacia" $v$ (positivos interior del producto), y excluir a los que el "punto" de $v$ (negativos producto interior).

Pero puesto que yo soy el uno de picking $v$, puede ser completamente fuera de suerte, tal vez te voy a dar un $v$ que se aleja de todos los de sus vectores, y el mejor componente que pude conseguir es $0$. Queremos recoger el "derecho" $v$, en cierto sentido, lo que nos da una gran proyección. Pero es difícil hacer que, sin conocer los vectores de antemano. Y, además, Han de Bruijn la respuesta sugiere que el caso extremo viene cuando todo es simétrico y que sólo podría elegir cualquier sentido alguno al azar.

Lo que esto sugiere es que debemos escoger una al azar la dirección, o para decirlo de otra manera, muestran que el promedio de $v$ nos da una gran proyección. Ahora, para el cálculo real de ...

---

Deje $v$ ser una unidad arbitraria de vectores. Como se sugiere en la intuición, dejen $S_v$ denotar los índices de $i$ que $z_i$ tiene un resultado positivo de producto interior con $v$, y definir $$x_v := \sum_{i \in S_v} z_i.$$ Podemos enlazado $|x_v|$, desde abajo, por su componente a lo largo de $v$: $$|x_v| \geq \langle x_v, v\rangle = \sum_{i \in S_v} \langle z_i, v \rangle = \sum_{i \in S_v} |z_i| \cos(\theta_{i,v}),$$ donde $\theta_{i,v}$ es el ángulo entre el$z_i$$v$. Podemos reescribir esto como $$|x_v| \geq \sum_{i=1}^n |z_i| \max\{0, \cos(\theta_{i,v})\},$$ ya que por definición los términos adicionales estamos incluyendo todo $0$.

Ahora, supongamos que yo fuera a recoger un $v$ uniformemente al azar de la unidad de círculo. A continuación, el ángulo de $\theta_{i,v}$ sería uniforme en $[0,2 \pi)$, y el valor esperado de la $i^{th}$ término en el lado derecho sería $$\frac{1}{2 \pi} \int_0^{2\pi} |z_i| \max\{0, \cos \theta\} \, d\theta = \frac{1}{\pi} |z_i|.$$ Sumando sobre todos los $i$, tenemos $$E(|x_v|) \geq \frac{1}{\pi} \sum_{i=1}^n |z_i| = \frac{1}{\pi}$$ Aquí $E(|x_v|)$ denota el valor esperado (o promedio) de $|x_v|$ de los que tomaron más de un elegida al azar,$v$.

El punto clave aquí (lo que a veces se denomina "Erdős magia" después de que Paul Erdős): Si tenemos una colección de vectores, donde el promedio de duración es de $\frac{1}{\pi}$, lo que significa que debe ser un vector de la colección cuya longitud es al menos $\frac{1}{\pi}$, por lo que ganamos. Que $\frac{1}{\pi}$ es la mejor posible puede ser mostrado usando el conjunto de puntos de Han de Bruijn la respuesta.

---

Este problema es una especie de viejos castaños, y el argumento aquí no es el mío. Pero yo en realidad no se conoce la fuente original. Me encantaría que si alguien que sepa un poco más de su historia podría comentar.

Answer 2

Caso especial el primero. Se supone que el valor máximo $\,c\,$ es alcanzado por uniformemente distribuidas $\{z_0,z_1,\ldots,z_{n-1}\}$ . Esto significa que $$ z_k = \frac{1}{n} e^{i\cdot k\,2\pi/n} \quad \Longrightarrow \quad |z_0|+|z_1|+\cdots +|z_{n-1}|=1 $$ Fácil que se obtienen los resultados (por mano) por $n=1,2,3,4$: $$ \begin{cases} n=1 \quad \Longrightarrow \quad S = \{1\} & \mbox{and} & \left|\sum_{z\in S} z\right|\geq 1 > 1/\pi \\ n=2 \quad \Longrightarrow \quad S = \{1/2\} & \mbox{and} & \left|\sum_{z\in S} z\right|\geq 1/2 > 1/\pi \\ n=3 \quad \Longrightarrow \quad S = \{1/3,(-1-i\sqrt{3})/6\} & \mbox{and} & \left|\sum_{z\in S} z\right|\geq 1/3 > 1/\pi\\ n=4 \quad \Longrightarrow \quad S = \{1/4,i/4\} & \mbox{and} & \left|\sum_{z\in S} z\right|\geq \sqrt{2}/4 > 1/\pi \end{casos} $$ Esto ya mejora los límites $1/6$ $1/4$ como se da en la pregunta (en el mejor de $n=3$).
De orden superior de los resultados se obtienen con la ayuda de un programa de ordenador. Las líneas de dar $n$ , $\left|\sum_{z\in S} z\right|$ y $1/\pi$ se alternan con las líneas de dar a los índices de $\,k\,$ de los términos de $\,z_k\,$ en la suma de $\,\left|\sum_{z\in S} z\right|$ .
Está demostrado que las sumas de hecho, parecen converger a la conjetura valor de $1/\pi$ . Y no hay un patrón en los subconjuntos que hacer el trabajo.

 1 1.00000000000000 E+0000 > 3.18309886183791 E-0001
0 
 2 5.00000000000000 E-0001 > 3.18309886183791 E-0001
0 
 3 3.33333333333333 E-0001 > 3.18309886183791 E-0001
0 2 
 4 3.53553390593274 E-0001 > 3.18309886183791 E-0001
0 1 
 5 3.23606797749979 E-0001 > 3.18309886183791 E-0001
0 1 2 
 6 3.33333333333333 E-0001 > 3.18309886183791 E-0001
0 4 5 
 7 3.20997086245352 E-0001 > 3.18309886183791 E-0001
0 1 2 
 8 3.26640741219094 E-0001 > 3.18309886183791 E-0001
0 1 2 3 
 9 3.19931693507980 E-0001 > 3.18309886183791 E-0001
5 6 7 8 
 10 3.23606797749979 E-0001 > 3.18309886183791 E-0001
3 4 5 6 7 
 11 3.19394281060558 E-0001 > 3.18309886183791 E-0001
4 5 6 7 8 9 
 12 3.21975275429689 E-0001 > 3.18309886183791 E-0001
1 2 3 4 5 6 
 13 3.19085761944568 E-0001 > 3.18309886183791 E-0001
3 4 5 6 7 8 
 14 3.20997086245352 E-0001 > 3.18309886183791 E-0001
0 1 2 3 4 5 6 
 15 3.18892407783521 E-0001 > 3.18309886183791 E-0001
0 1 2 3 11 12 13 14 
 16 3.20364430967688 E-0001 > 3.18309886183791 E-0001
0 1 2 3 4 13 14 15 
 17 3.18763277866454 E-0001 > 3.18309886183791 E-0001
5 6 7 8 9 10 11 12 
 18 3.19931693507980 E-0001 > 3.18309886183791 E-0001
2 3 4 5 6 7 8 9 10 
 19 3.18672778564237 E-0001 > 3.18309886183791 E-0001
2 3 4 5 6 7 8 9 10 
 20 3.19622661074983 E-0001 > 3.18309886183791 E-0001
3 4 5 6 7 8 9 10 11 12 
 21 3.18606904753685 E-0001 > 3.18309886183791 E-0001
0 1 2 3 15 16 17 18 19 20 
 22 3.19394281060558 E-0001 > 3.18309886183791 E-0001
0 1 2 3 4 5 6 7 8 9 10 
 23 3.18557468338846 E-0001 > 3.18309886183791 E-0001
7 8 9 10 11 12 13 14 15 16 17 
 24 3.19220732314183 E-0001 > 3.18309886183791 E-0001
4 5 6 7 8 9 10 11 12 13 14 15 

Dos instantáneas debe aclarar el patrón en los subconjuntos que hacer el trabajo:

Así que parece que, sin demasiada pérdida de generalidad, podemos suponer que: $$ \left|\sum_{z\in S} z\right| = \left|\sum_{k=0}^{n/2-1} \frac{1}{n} e^{i\cdot k\,2\pi/n}\right| $$ La suma de una serie geométrica es reconocido en el presente documento: $$ \sum_{z\in S} z = \frac{1}{n} \frac{1-r^{n/2}}{1-r} \quad \mbox{con} \quad r = e^{i\cdot 2\pi/n} $$ Por lo tanto: $$ \left|\sum_{z\in S} z\right| = \frac{1}{n} \left|\frac{1-e^{i\cdot 2\pi/n\cdot n/2}}{1-e^{i\cdot 2\pi/n}}\right| = \frac{1}{n} \left|\frac{2\cdot i}{e^{i\cdot \pi/n}\left(e^{-i\cdot \pi/n}-e^{i\cdot \pi/n}\right)\cdot i}\right| = \frac{\pi/n}{\sin(\pi/n)}\frac{1}{\pi} $$ Y una conocida límite nos dice que $$ \lim_{n\to\infty} \left|\sum_{z\in S} z\right| = \frac{1}{\pi} $$ en concordancia con los experimentos numéricos.
No me malinterpreten. El de arriba es sólo un boceto de una prueba. Bastante algunos aspectos técnicos permanecen para ser rellenado. La parte principal de probar es: ¿por qué este caso muy especial de ser relevante para el caso general de arbitrario $\,z_k$ ? (Aunque no es infrecuente que las soluciones de alta simetría son relevantes para encontrar los valores extremos de una forma más general de la configuración)