Vtgyjfy

Interesting Question:

for any complex numbers $z_{1},z_{2},cdots,z_{n}$ such
$$begin{cases}
|z_{1}|^2+|z_{2}|^2+cdots+|z_{n}|^2=1\
|z_{i}|ledfrac{1}{10},i=1,2,cdots,n
end{cases}$$
show that the number of ordered $n$-tuples $(varepsilon_{1},varepsilon_{2},cdots,varepsilon_{n})$such this following inequality
$$|z_{1}varepsilon_{1}+z_{2}varepsilon_{1}+cdots+z_{n}varepsilon_{n}|ledfrac{1}{3}$$
at least $2^{n-100}$

where $varepsilon_{1},varepsilon_{2},cdots,varepsilon_{n}in {-1,1}$

This problem is from china 2014 omlypiad problem exisice it,and I find sometimes with this background:

(2004 Romania )Prove that for any complex numbers $z_{1},z_{2},cdots,z_{n}$ satisfying
$|z_{1}|^2+|z_{2}|^2+cdots+|z_{n}|^2=1$, one can selcet
$varepsilon_{1},varepsilon_{2},cdots,varepsilon_{n}in {-1,1}$ such that
$$left|sum_{k=1}^{n}varepsilon_{k}z_{k}right|le 1$$
then I found Nearest IMRE B´ AR´ ANY, BORIS reseacher these some problem:
see:http://arxiv.org/abs/1303.2877
and
http://arxiv.org/abs/1310.0910 these two paper have some new reslut,but I read find see can't solve my problem,can someone help.Thank you

Partition ${1,dots,n}$ into thirty sets $I_1,dots,I_{30}$ such that $sum_{iin I_j}|z_i|^2<tfrac1{30}+tfrac1{100}<tfrac4{90}$ for each $1leq jleq 30.$ This can be achieved by starting with empty sets and adding greedily: the only impediment to adding a value to some $I_j$ is that $sum_{iin I_j}|z_i|^2geq tfrac1{30},$ but if that holds for all the $j$ then all the values must already be assigned.

Assume these lemmas for now:

Lemma 1. For any positive integer $N$ and any values $z_1,dots,z_N$ with $sum_{i=1}^N |z_i|^2leq 4/90,$ there exist at least $2^N/10$ tuples $(epsilon_1,dots,epsilon_N)in{-1,1}^{N}$ such that $|sum_{i=1}^{N}epsilon_iz_i|^2leq 5/90$ and $epsilon_1=1.$

Lemma 2. Given values $z_1,dots,z_N$ such that $|z_i|^2leq 5/90$ for $1leq ileq N,$ there exist $epsilon_1,dots,epsilon_Nin{-1,1}$ such that $|sum_{i=1}^Nepsilon_iz_i|leq 1/3.$ (Actually we only need the case $N=30.$)

Combining the tuples given by applying Lemma 1 to each $I_j,$ there are at least $2^n10^{-30}=2^n1000^{-10}>2^n1024^{-10}=2^{n-100}$ tuples $(epsilon_1,dots,epsilon_n)in{-1,1}^n$ such that $|sum_{iin I_j} epsilon_iz_i|^2leq 5/90$ and $epsilon_{min(I_j)}=1$ for each $j.$
For each of these tuples, by Lemma 2, we can find $(theta_1,dots,theta_{30})in{-1,1}^{30}$ such that $|sum_{j=1}^{30}theta_j(sum_{iin I_j} epsilon_iz_i)|leq 1/3.$ This gives a new tuple defined by $epsilon'_i=epsilon_itheta_j$ for each $iin I_j$ and $1leq jleq 30.$ The resulting $2^{n-100}$ tuples $epsilon'$ are distinct and satisfy $|sum_{i=1}^{n}epsilon'_iz_i|leq 1/3$ as required.

Proof of Lemma 1:
$$sum_{epsilonin{-1,1}^N}sum_{i=1}^{N}|epsilon_iz_i|^2
=sum_{epsilonin{-1,1}^N}sum_{i=1}^{N}epsilon_iz_ioverline{sum_{j=1}^{N}epsilon_jz_j}
=2^Nsum_{i=1}^{N}|z_i|^2leqtfrac{4}{90}2^N$$ because the $z_iz_j$ terms cancel. So it is not possible for more than $tfrac45 2^{N}$ tuples $epsilon$ to satisfy $|sum_{i=1}^{N}epsilon_iz_i|^2>5/90.$ (This is a form of Markov's inequality.) So at least $tfrac15 2^{N}$ must have $|sum_{i=1}^{N}epsilon_iz_i|^2leq 5/90.$ Requiring $epsilon_1=1$ halves this to $tfrac1{10} 2^{N}.$

Proof of Lemma 2: Given any three complex values I claim there are always two $z,w$ such that $|z+w|$ or $|z-w|$ is at most $max(|z|,|w|).$ This follows from the fact that some two make an angle of at most $pi/3$ after possibly negating some values: assume one value $z$ lies on the real axis, then $z$ or $-z$ makes an angle of less than $pi/3$ which anything not in the region $arg win(pi/3,2pi/3)cup (4pi/3,5pi/3)$; but any two points in this region make an angle of at most $pi/6$ with each other after possibly negating one. In algebraic terms this means $2mathrm{Re}(zoverline w)geq tfrac12 |z||w|,$ giving $|z-w|^2=|z|^2+|w|^2-2mathrm{Re}(zoverline w)leqmax(|z|,|w|).$

This lets us reduce to the case $N=2.$ Without loss of generality $z_1$ is a positive real, and negating $z_2$ if necessary we can assume $mathrm{Re}(z_2)leq 0.$ This gives $|z_1+z_2|^2leq|z_1|^2+|z_2|^2leq 10/90$ as required.