Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I was asked this years ago, but I don't remember by whom, and have never managed to solve it. Consider the $2^n \times n$ matrix of all vectors in {-1,1}$^n$. Someone comes and maliciously replaces some of the entries by zeros. Show that there still remains a non-empty subset of rows that add up to the all zero vector.

share|improve this question
    
To see if I understand your situation properly, you're taking 2^n vectors of n elements such that each element in the matrix is a -1 or a 1, and no two vectors are the same? I would think that a proof for such would use induction, but I'm not sure how it would work. –  Gabriel Benamy Dec 1 '09 at 20:36
1  
How about the smpty subset? ;-) –  Kevin Buzzard Dec 1 '09 at 20:47
    
@buzzard: I took the liberty of inserting the non-empty word. –  Ilya Nikokoshev Dec 1 '09 at 21:06
    
I hope for your sake the problem is correct with that modification :-) –  Kevin Buzzard Dec 1 '09 at 21:21
26  
"Someone comes and maliciously replaces some of the words by other words. Show that the problem still has a solution" –  Kevin Buzzard Dec 1 '09 at 21:22
show 1 more comment

3 Answers 3

up vote 12 down vote accepted

Another answer (I guess they must be equivalent):

  • 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.
share|improve this answer
1  
For the archive: The function in step 3 is the one that maps each minuend to the corresponding changed subtrahend. -- Great solution! –  darij grinberg Jul 18 '10 at 23:48
add comment

Hint: starting with the empty set, add vectors one by one and ensure you never get a negative entry in the partial sum. During the process, either you can find a suitable vector (the one which originally had 1's where your current sum has 0's), or you've hit upon a partial sum previously seen - which means the difference is 0.

share|improve this answer
    
But we're not asked about differences, are we? Just sums. –  Harald Hanche-Olsen Dec 1 '09 at 22:56
2  
Harald: The difference between the previous and current partial sums being zero is the same thing as the sum of the vectors you added between then and now being zero. –  David Eppstein Dec 1 '09 at 23:38
    
Oh, duh; thanks. I had one more objection, which was how we could tell that we have the same partial sum again if we stopped. The point being that we must always keep every component of the partial sums in {0,1}, as the particular choice suggested in the answer ensures. (Well, he did call it a hint, did he not?) So that's +1 from me, then. –  Harald Hanche-Olsen Dec 2 '09 at 0:06
    
Great, thanks Alon. I've been haunted by this silly question for a long time. BTW, I believe it used to be used as a question in job interviews for Hi-Tech companies in Israel. I am sure every single candidate started by trying induction. The nice thing about your solution is that it is almost dimension-free... –  Ehud Friedgut Dec 2 '09 at 5:43
    
Glad I could help :) I wouldn't call this a silly question, I actually think it's quite hard despite the solution being fairly simple. I also think it's completely unsuitable for job interviews, but I know a lot of companies do this kind of stuff. If a person is unable to solve this on the spot, you really learn very little about them. –  Alon Amit Dec 2 '09 at 17:29
show 1 more comment

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.