most recent 30 from http://mathoverflow.net 2013-05-24T21:49:20Z http://mathoverflow.net/feeds/question/7493 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/7493/a-riddle-about-zeros-ones-and-minus-ones Ehud Friedgut 2009-12-01T20:00:07Z 2011-01-26T01:46:22Z

<p>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. </p>

http://mathoverflow.net/questions/7493/a-riddle-about-zeros-ones-and-minus-ones/7518#7518 Alon Amit 2009-12-01T22:32:17Z 2009-12-01T22:32:17Z

<p>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. </p>

http://mathoverflow.net/questions/7493/a-riddle-about-zeros-ones-and-minus-ones/32425#32425 Yuval Filmus 2010-07-18T23:23:34Z 2010-07-18T23:23:34Z

<p>Another answer (I guess they must be equivalent):</p> <ul> <li>Write each <em>original</em> line as a difference of two 0/1 vectors.</li> <li>Adapt this representation to the modified lines by changing <em>only the subtrahends</em>.</li> <li>You now have a function from {0,1}^n to {0,1}^n. Find a cycle.</li> </ul>

http://mathoverflow.net/questions/7493/a-riddle-about-zeros-ones-and-minus-ones/53309#53309 this 2011-01-26T01:46:22Z 2011-01-26T01:46:22Z

<p>One place where it showed up:</p> <p><a href="http://domino.research.ibm.com/comm/wwwr_ponder.nsf/challenges/February2003.html" rel="nofollow">http://domino.research.ibm.com/comm/wwwr_ponder.nsf/challenges/February2003.html</a></p>