0
$\begingroup$

Let $z_i \in \mathbb{C}\:$ for $i=1,\dots, n\;$ be complex numbers, all with absolute value $|z_i|\le 1\;$.

Prove (or disprove) that there exists a choice of signs $s_i \in \{\pm 1\}$ such that $$\left|\sum_{i=1}^n s_i\cdot z_i\right| \le \sqrt{2}.$$

[My interest in this problem is purely for fun. I couldn't solve it a long time ago, forgot about it, but shortly ago it came back into my mind again.]

$\endgroup$
3

1 Answer 1

4
$\begingroup$

What follows is not an answer, but is too long for a comment.

This problem and its natural higher-dimensional generalization is connected with the recent MO questions Covering a unit ball with balls half the radius and covering disks with smaller disks : let $K_d$ be the smallest constant such that for any sequence $(z_i)_{i \geq 1}$ of vectors of $\mathbb{R}^d$ of (euclidean) norm at most one, there's some choice of signs $s_i = \pm 1$ such that the partial sums $\sum_{1 \leq i \leq n} s_i z_i$ are all bounded by $K_d$.

Now let $N_d$ be the minimal number of balls of radius $\frac{1}{2}$ needed to cover a ball of radius $1$ (in $\mathbb{R^d}$). I claim that $K_d \leq N_d$.

Proof : Let $K_{d,n}$ be the same constant as $K_d$, but for which we require only the first $n$ partial sums to be bounded by $K_{d,n}$. Then a straightforward averaging argument yields $K_{d,n} \leq \sqrt{n} \leq n$. Now let $n > N_d$. Fixing a covering of the unit ball with $N_d$ balls of radius $\frac{1}{2}$, then there must be two distinct $ i < j \leq N_d +1$ such that $z_i$ and $z_j$ lie in the same ball of radius $\frac{1}{2}$, and hence must satisfy $|| z_i - z_j || \leq 1$. If we replace $z_j$ by $z_j - z_i$, suppress $z_i$, and then use $K_{d,n-1}$, we get a sequence of signs which achieve $K_{d,n} \leq \max ( N_d, K_{d,n-1} ) $. But Kônig's lemma (for infinite binary trees) gives $K_d \leq \sup_{n} K_{d,n} $, hence the desired result.

$\endgroup$
5
  • 1
    $\begingroup$ A very nice answer! You might want to replicate it in the "covering a unit ball" question, since not too many people will look at this... $\endgroup$
    – Igor Rivin
    May 29, 2012 at 19:17
  • $\begingroup$ If you do follow Igor's suggestion, please use more letters so that n is not overloaded. It will make the argument easier to follow. Gerhard "Ask Me About System Design" Paseman, 2012.05.29 $\endgroup$ May 29, 2012 at 19:27
  • 1
    $\begingroup$ I thought a relevant number should be $M_n$ defined as the largest integer $m$ such that there are $m$ points $x_1,x_2,\dots,x_n$ on the unit sphere of $\mathbb{R}^n$ such that $\|x_i\pm x_j\|>1$ for all $i\neq j$ (that is, the max $m$ such that there are $2m$ points at a distance more than 1 from each other, arranged in $m$ antipodal pairs). Therefore, given $m >M_n$ points on the unit ball of $\mathbb{R}^n$, there are two of them such that either $\|x_i - x_j\|\le1$ or $\|x_i+ x_j\|\le1$ .This gives $\sqrt M_n$ as a bound for the generalized problem in $\mathbb{R}^n$. $\endgroup$ May 30, 2012 at 5:36
  • $\begingroup$ Thanks too all for the help! A very easy solution was given by mavropnevma on website linked by Daniel in his comment to the question (see artofproblemsolving.com/Forum/viewtopic.php?f=42&t=386586) $\endgroup$
    – Someone
    May 30, 2012 at 12:04
  • $\begingroup$ It seems I misread the question (I was bounding all partial sums rather than a single one). With the notations above, this gives a the better bound $\sqrt(N_d)$ (as Pietro Majer notes in the comment above). $\endgroup$
    – js21
    May 30, 2012 at 12:26

Not the answer you're looking for? Browse other questions tagged or ask your own question.