6
$\begingroup$

The following problem has been bothering me for a while, and I finally gave up to solve it on my own. However, I still would like to see a solution:

For an arbitrary integer $n$ consider a set of all n-vectors with coordinates $1$ and $-1$, e.g. for $n=2$:

$(1,1),\ (1,-1),\ (-1,1),\ (-1,-1)$

The sum of the vectors is obviously $0$ (zero-vector). Now, arbitrarily change some of the coordinates to 0 (it may be different coordinates in different vectors), e.g.:

$(0,1),\ (1,0),\ (-1,1),\ (-1,-1)$

Prove that there exists a non-empty subset of vectors whose sum is still $0$.

(In our case: $(0,1) + (1,0) + (-1,-1)=(0,0)$.

  • 0
    @Eric: *That's* where I'd seen it before! Thanks for pointing it out. Since there is no closing as duplicate of a MathOverflow question, I'll post the link to it as community wiki so the question can be marked as answered.2012-02-03

1 Answers 1

3

As Eric Naslund has pointed out in the comments, this question has been asked and answered before on MathOverflow: A riddle about zeros, ones and minus-ones. I quote Yuval Filmus's short answer below; he has also written a one-page explanation.

  • Write each original line as a difference of two $0$/$1$ vectors.
  • Adapt this representation to the modified lines by changing only the subtrahends.
  • You now have a function from $\{0,1\}^n$ to $\{0,1\}^n$. Find a cycle.

Darij Grinberg adds, "The function in step 3 is the one that maps each minuend to the corresponding changed subtrahend."