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)$.

$\endgroup$
5
  • 2
    $\begingroup$ cs.toronto.edu/~yuvalf/pm1%20Vectors%20Riddle.pdf $\endgroup$
    – user856
    Feb 1 '12 at 14:39
  • $\begingroup$ That was quick. Thanks!! $\endgroup$ Feb 1 '12 at 14:49
  • $\begingroup$ No problem. Yuval Filmus also happens to be a user here; perhaps he will see this question and post an answer! In the meantime, you should make your question title more descriptive. $\endgroup$
    – user856
    Feb 1 '12 at 14:59
  • 1
    $\begingroup$ Duplicate of mathoverflow.net/questions/7493/… $\endgroup$ Feb 2 '12 at 21:41
  • $\begingroup$ @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. $\endgroup$
    – user856
    Feb 3 '12 at 12:46
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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