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.