0

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

Someone
  • 453
  • There is a puzzle problem much like this. But MO is not the place to ask about it. I would try the forum at http://www.artofproblemsolving.com/Forum/ perhaps. – Gerald Edgar May 29 '12 at 17:23
  • 2
    There is no need to (re)post it on the AoPS forum: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=386586 – Daniel m3 May 29 '12 at 19:13
  • @Gerald, @Daniel: Thanks for the hints. – Someone May 30 '12 at 10:53

1 Answers1

4

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.

Community
  • 1
js21
  • 7,199
  • 1
    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
  • 1
    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 05: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 http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=386586) – 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