Christof wrote: << So we have n x 2^n numbers and the child sets any *arbitrary* (not necessarily small) subset of those to zero, correct? regarding the puzzle: << For some integer n > 0 you have all 2^n vectors of dimension n whose entries are +1 or -1. Of course the sum of all 2^n of these vectors is the 0 vector. Then your three-year-old child changes some of the entries of some of these vectors to 0. Show that there is still a nonempty subset of the new set of 2^n vectors that sums to the 0 vector.
Yes, exactly. Any subset of the n(2^n) components of the original 2^n vectors may be changed to 0's. The problem is to show there is always some nonempty subset of the resulting set of 2^n vectors that sums to the 0 vector. --Dan ________________________________________________________________________________________ It goes without saying that .
I've been thinking about this, and I like the problem, but I don't know the answer yet. It feels like there should be some inductive approach. If you consider the half of the vectors that ended in a 1 (before your kid vandalized them), covering up their last coordinate gives you an instance of the (n-1)-dimensional problem, which by induction has a solution. Likewise for all the vectors that ended in -1. Uncovering the last coordinates of the two lower-dimensional solutions gives you two n-dimensional vectors that are all 0's except for in their final coordinates -- but of course there's no reason these two final coordinates would be equal up to sign. But that was just looking at one pair of codimension-1 problems embedded in the n-dimensional problem. Actually there are *tons* of ways to recurse: for each of the 2^(n-1) pairs of vectors that were the same (before vandalization) up to their last coordinate, you can pick one of the two to be in projection A and the other one in projection B, and by induction, each of A and B have a solution-except-for-the-nth-coordinate. That's 2^(2^(n-1)-1) different ways to partition those pairs and recurse. Does something guarantee that one of them will give you an n-dimensional solution when you uncover the last coordinate? Great problem, Dan! Where did you get it? --Michael On Mon, Jun 25, 2012 at 9:14 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Christof wrote:
<< So we have n x 2^n numbers and the child sets any *arbitrary* (not necessarily small) subset of those to zero, correct?
regarding the puzzle: << For some integer n > 0 you have all 2^n vectors of dimension n whose entries are +1 or -1. Of course the sum of all 2^n of these vectors is the 0 vector.
Then your three-year-old child changes some of the entries of some of these vectors to 0.
Show that there is still a nonempty subset of the new set of 2^n vectors that sums to the 0 vector.
Yes, exactly. Any subset of the n(2^n) components of the original 2^n vectors may be changed to 0's. The problem is to show there is always some nonempty subset of the resulting set of 2^n vectors that sums to the 0 vector.
--Dan
________________________________________________________________________________________ It goes without saying that .
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Forewarned is worth an octopus in the bush.
I heard it from Peter Winkler, who said he heard it independently from each of Noga Alon and Ehud Friedgut. (So it's not clear who composed the problem in the first place.) --Dan On 2012-06-25, at 6:35 PM, Michael Kleber wrote:
Great problem, Dan! Where did you get it?
On Mon, Jun 25, 2012 at 10:28 PM, Dan Asimov <dasimov@earthlink.net> wrote:
I heard it from Peter Winkler, who said he heard it independently from each of Noga Alon and Ehud Friedgut. (So it's not clear who composed the problem in the first place.)
--Dan
More history of the vector puzzle: The vector puzzle was posted as a card problem at this IBM Research site in 2003 http://domino.research.ibm.com/comm/wwwr_ponder.nsf/challenges/February2003.... and a solution was posted the same day. The problem was "sent in" by Michael Brand. The solution was not credited to anyone as far as I can see. I found that link in a Mathoverflow discussion of the same problem in 2009 here: http://mathoverflow.net/questions/7493/a-riddle-about-zeros-ones-and-minus-o...
In a story about an Olympic trial footrace in which the third-place finisher was too close to call, even with photos of the tape being taken every 1/3000 of a second, the NY Times photo caption of the finish of the race reads: "Jeneba Tarmoh (1) and Allyson Felix (2) crossed the finish line at exactly the same time." Amusing. --Dan
participants (3)
-
Dan Asimov -
Michael Kleber -
W. Edwin Clark