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.
$\begingroup$
$\endgroup$
6
-
$\begingroup$ 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. $\endgroup$– Gabriel BenamyCommented Dec 1, 2009 at 20:36
-
1$\begingroup$ How about the smpty subset? ;-) $\endgroup$– Kevin BuzzardCommented Dec 1, 2009 at 20:47
-
$\begingroup$ @buzzard: I took the liberty of inserting the non-empty word. $\endgroup$– Ilya NikokoshevCommented Dec 1, 2009 at 21:06
-
$\begingroup$ I hope for your sake the problem is correct with that modification :-) $\endgroup$– Kevin BuzzardCommented Dec 1, 2009 at 21:21
-
26$\begingroup$ "Someone comes and maliciously replaces some of the words by other words. Show that the problem still has a solution" $\endgroup$– Kevin BuzzardCommented Dec 1, 2009 at 21:22
|
Show 1 more comment
3 Answers
$\begingroup$
$\endgroup$
1
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.
-
1$\begingroup$ For the archive: The function in step 3 is the one that maps each minuend to the corresponding changed subtrahend. -- Great solution! $\endgroup$ Commented Jul 18, 2010 at 23:48
$\begingroup$
$\endgroup$
6
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.
-
$\begingroup$ But we're not asked about differences, are we? Just sums. $\endgroup$ Commented Dec 1, 2009 at 22:56
-
2$\begingroup$ 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. $\endgroup$ Commented Dec 1, 2009 at 23:38
-
$\begingroup$ 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. $\endgroup$ Commented Dec 2, 2009 at 0:06
-
$\begingroup$ 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... $\endgroup$ Commented Dec 2, 2009 at 5:43
-
$\begingroup$ 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. $\endgroup$ Commented Dec 2, 2009 at 17:29
$\begingroup$
$\endgroup$
One place where it showed up:
http://domino.research.ibm.com/comm/wwwr_ponder.nsf/challenges/February2003.html
