Welcome to MathOverflow

Question

16

10

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.

edited Dec 2 2009 at 1:14

Greg Kuperberg
36.4k●2●117●179

asked Dec 1 2009 at 20:00

Ehud Friedgut
315●7

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 2009 at 20:36

1

How about the smpty subset? ;-) – Kevin Buzzard Dec 1 2009 at 20:47

@buzzard: I took the liberty of inserting the non-empty word. – Ilya Nikokoshev Dec 1 2009 at 21:06

I hope for your sake the problem is correct with that modification :-) – Kevin Buzzard Dec 1 2009 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 2009 at 21:22

show 1 more comment

Yuval Filmus · Accepted Answer · 2010-07-18 23:23:34Z UTC

11

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.

answered Jul 18 2010 at 23:23

Yuval Filmus
698●6●11

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 2010 at 23:48

Alon Amit · Answer 2 · 2009-12-01 22:32:17Z UTC

15

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.

answered Dec 1 2009 at 22:32

Alon Amit
4,035●15●40

But we're not asked about differences, are we? Just sums. – Harald Hanche-Olsen Dec 1 2009 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 2009 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 2009 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 2009 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 2009 at 17:29

show 1 more comment

this · Answer 3 · 2011-01-26 01:46:22Z UTC

0

One place where it showed up:

http://domino.research.ibm.com/comm/wwwr_ponder.nsf/challenges/February2003.html

answered Jan 26 2011 at 1:46

this
1

A riddle about zeros, ones and minus-ones

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

3 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.