MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.]

share|cite|improve this question

closed as too localized by Felipe Voloch, Gerald Edgar, Chris Godsil, Igor Rivin, Kevin Walker May 29 '12 at 18:46

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

There is a puzzle problem much like this. But MO is not the place to ask about it. I would try the forum at perhaps. – Gerald Edgar May 29 '12 at 17:23
There is no need to (re)post it on the AoPS forum: – Daniel m3 May 29 '12 at 19:13
@Gerald, @Daniel: Thanks for the hints. – Someone May 30 '12 at 10:53
up vote 4 down vote accepted

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.

share|cite|improve this answer
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... – Igor Rivin May 29 '12 at 19:17
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 – Gerhard Paseman May 29 '12 at 19:27
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$. – Pietro Majer May 30 '12 at 5:36
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 – Someone May 30 '12 at 12:04
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). – js21 May 30 '12 at 12:26

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