Let $Z\subset \mathbb{C}$ be a set of $n$ complex numbers, $n\geqslant 2.$ Prove that for any positive integer $m$ satisfying $m\leqslant n/2$ there exists a subset $U$ of $Z$ with $m$ elements such that\[\Bigg|\sum_{z\in U}z\Bigg|\leqslant\Bigg|\sum_{z\in Z\setminus U}z\Bigg|.\]Vasile Pop
Problem
Source: Romania National Olympiad 2022
Tags: complex numbers, algebra, romania
21.04.2022 10:50
Denote $S$ the sum of all $z$ ∈ $Z$. Then, $\sum_{z\in Z\setminus U}z = S - \sum_{z\in U}z$ We assume that there exists a positive integer $m$, $m\leq n/2$, for which any subset $U$ with $m$ elements has the property: $\Bigg|\sum_{z\in U}z\Bigg| \nleq \Bigg|S-\sum_{z\in U}z\Bigg|$$\quad \Rightarrow \quad$$\Bigg|\sum_{z\in U}z\Bigg|^2>\Bigg|S-\sum_{z\in U}z\Bigg|^2$$\Rightarrow$ $\Rightarrow$ $|S|^2<S (\overline{\sum_{z\in U}z})$$+\overline{S}(\sum_{z\in U}z) \quad \star$ There are $\left(\begin{array}{c} n \\ m \end{array}\right)$ ways of choosing $U$ from $Z$. Any random complex number $z \in Z$ appears in exactly $\left(\begin{array}{c} n-1 \\ m-1 \end{array}\right)$ of these subsets. Adding all $\star$ together for every subset of $Z$ with $m$ elements, we obtain: $\left(\begin{array}{c} n \\ m \end{array}\right)|S|^2<\left(\begin{array}{c} n-1 \\ m-1 \end{array}\right)S\overline{S}+\left(\begin{array}{c} n-1 \\ m-1 \end{array}\right)\overline{S}S\quad \Rightarrow$ $\left(\begin{array}{c} n \\ m \end{array}\right)|S|^2<2\left(\begin{array}{c} n-1 \\ m-1 \end{array}\right)|S|^2\quad \Rightarrow$ $\frac n{m}|S|^2<2|S|^2 \quad \Rightarrow \quad \frac n{m}<2$, false. Then, our assumption is proven wrong, so for any positive integer $m$, $m \leq n/2$, there exists a subset $U$ of $Z$ with $m$ elements, such that $\Bigg|\sum_{z\in U}z\Bigg|\leqslant\Bigg|\sum_{z\in Z\setminus U}z\Bigg|$
22.04.2022 12:28
My approach is more complicated, but it gives a much stronger lower bound on the number of $U\subset Z$ with the desired property. Firstly observe that instead of solving the problem for $Z,$ it is enough to solve it for some $Z_\theta:=Z\cdot e^{i\theta}=\{z\cdot e^{i\theta}:z\in Z\}.$ This is because $Z_\theta$ is simply $Z$ rotated by $\theta$ degrees with respect to the origin, so no modulus is changed. This does allow us, however, to impose some conditions and efficiently find several $U$ satisfying the desired properties. In what follows, by $\Sigma(S)$ we will denote the sum of the elements of the set $S.$ We informally define $\Sigma(\emptyset)=0.$ Finally, for any complex number $z,$ we will denote by $P_z$ the point in the plane corresponding to $z.$ Then, the following lemma follows: Lemma: There exists a subset $V\subset Z$ with $n-2m$ elements such that, upon a proper rotation, $P_{\Sigma(Z)}$ and $P_{\Sigma(V)}$ can both be sent in the top-right quadrant of the plane. In other words, upon a proper rotation, $P_{\Sigma(Z)}$ and $P_{\Sigma(V)}$ will both have non-negative $x$ and $y$ coordinates. Proof: If $n-2m=0$ then $V=\emptyset$ so $P_{\Sigma(V)}=(0,0).$ Regardless of what rotation we apply, $P_{\Sigma(V)}$ will remain unchanged and it does lie in the desired quadrant, as it is the origin itself. Therefore, we just have to apply a proper rotation to send $P_{\Sigma(Z)}$ in the desired quadrant as well and we finish. If $\Sigma(Z)=0$ then we are left with the exact same situation as above. Regardless of what rotation we apply, $P_{\Sigma(Z)}$ remains the origin, so it will always lie in the desired quadrant. Just choose a random $V\subset Z$ with $n-2m$ elements and rotate it by some adequate $\theta$ to finish in this case as well. Assume that $n-2m\neq 0$ and that $\Sigma(Z)\neq 0.$ Choose some $V\subset Z$ with $n-2m$ elements. Then, there exists a rotation $\theta$ which sends $P_{\Sigma(Z)}$ and $P_{\Sigma(V)}$ in the desired quadrant if and only if $\angle P_{\Sigma(V)}OP_{\Sigma(Z)}\leq 90^\circ$ (our assumptions guarantee that this angle is not degenerated). Let's assume that the lemma is false, so for every $V\subset Z$ with $n-2m$ elements, we have $\angle P_{\Sigma(V)}OP_{\Sigma(Z)}> 90^\circ.$ Looking at this from a geometrical point of view, if we trace the line $\ell$ perpendicular to $OP_{\Sigma(Z)}$ in $O$, then all of $P_{\Sigma(V)}$ will be in the half-plane determined by $\ell$ not containing $P_{\Sigma(Z)}$ as shown in the figure below[asy][asy] import olympiad;import geometry; size(5cm);defaultpen(fontsize(10pt)); pair A,B,C,D,E,A1,D1; A=dir(60);B=dir(150);C=dir(330);D=dir(280); A1=A*2/3; D1=D*4/7; E=C*5/6; draw(B--C); draw((0,0)--A1); dot("$P_{\Sigma(Z)}$",A1,dir(A1)); label("$\ell$",E,dir(A)); dot("$P_{\Sigma(V)}$",D1,dir(A1)); dot("$O$",(0,0),dir(20)); [/asy][/asy]Let $V_1,V_2,\ldots, V_k$ be all the $n-2m$ element subsets of $Z.$ Then, since all of $P_{\Sigma(V_i)}$ lie in the lower half-plane, then so does $P_{\Sigma(V_1)+\cdots+\Sigma(V_k)}$ (adding complex numbers is basically adding vectors). However, a simple double counting yields that\[\sum_{i=1}^k\Sigma(V_i)=\binom{n-1}{n-2m-1}\sum_{z\in Z}z=\binom{n-1}{n-2m-1}\Sigma(Z).\]Thus, $\Sigma(V_1)+\cdots+\Sigma(V_k)=k\Sigma(Z)$ for some $k\in\mathbb{N}.$ We got that $P_{k\Sigma(Z)}=P_{\Sigma(V_1)+\cdots+\Sigma(V_k)}$ and $P_{\Sigma(Z)}$ lie in different half-planes, which is a clear contradiction, as a homothety of factor $k>0$ with pole $O$ sends the former into the latter. Hence our assumption is wrong and the lemma holds. $\blacksquare$ Coming back to the original problem, choose $V\subset Z$ and $\theta$ as per our lemma. Using our observation, we will, instead, solve the problem for $Z_\theta.$ In other words, we will solve the problem assuming that $\Sigma(Z)=a+ib$ with $a,b\geq 0$ and that there exists $V\subset Z$ with $n-2m$ elements so that $\Sigma(V)=x+iy$ with $x,y\geq 0.$ Consider two sets $U_1$ and $U_2$ such that $|U_1|=|U_2|=m$ and $U_1\cup U_2=Z\setminus V.$ Assume that the problem doesn't hold for both $U_1$ and $U_2.$ Then, for any $j\in\{1,2\}$ we have the following\begin{align*}\Bigg|\sum_{z\in U_j}z\Bigg|>\Bigg|\sum_{z\in Z\setminus U_j}z\Bigg|=\Bigg|\Sigma(Z)-\sum_{z\in U_j}z\Bigg|\implies \Sigma(Z)\overline{\sum_{z\in U_j}z}+\overline{\Sigma(Z)}\sum_{z\in U_j}z>|\Sigma(Z)|^2.\end{align*}By summing the latter over $j=1,2$ and using the fact that $U_1\cup U_2=Z\setminus V$ we finally get the following inequality\[\Sigma(Z)\overline{\sum_{z\in Z\setminus V}z}+\overline{\Sigma(Z)}\sum_{z\in Z\setminus V}z>2|\Sigma(Z)|^2.\]However, the sum of all $z\in Z\setminus V$ is precisely $\Sigma(Z)-\Sigma(V).$ Plugging this above and using the fact that $\Sigma(Z)=a+ib$ with $a,b\geq 0$ and that $\Sigma(V)=x+iy$ with $x,y\geq 0$ we ultimately get \[(a+ib)(a-x-i(b-y))+(a-ib)(a-x+i(b-y))>2(a^2+b^2)\]which, after reducing the common terms, rewrites as $2a(a-x)+2b(b-y)>2(a^2+b^2).$ This is an obvious contradiction, as $a,b,x,y\geq 0$ so $2a(a-x)+2b(b-y)\leq 2a^2+2b^2.$ Therefore the problem cannot fail for both of $U_1$ and $U_2$ whenever $|U_1|=|U_2|=m$ and $U_1\cup U_2=Z\setminus V.$ It follows there are at least \[\frac{1}{2}\binom{2m}{m}\]sets $U$ which satisfy the desired condition. As a remark, this bound achieves equality when $n=2m$ and it looks asymptotically accurate. I am very curious to see whether this bound is actually optimal or not in general.