Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
    
That was quick. Thanks!! –  malenkiy_scot Feb 1 '12 at 14:49
    
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. –  Rahul Feb 1 '12 at 14:59
1  
Duplicate of mathoverflow.net/questions/7493/… –  Eric Naslund Feb 2 '12 at 21:41
    
@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. –  Rahul Feb 3 '12 at 12:46

1 Answer 1

up vote 3 down vote accepted

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 Greenberg adds, "The function in step 3 is the one that maps each minuend to the corresponding changed subtrahend."

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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