I recently heard this cute 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.
--Dan
* Dan Asimov <dasimov@earthlink.net> [Jun 23. 2012 07:47]:
I recently heard this cute 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.
--Dan
This will work only for some definition of "some": if the evil kid removes, for example, the j-th component in all but one vector then I cannot non-emptily sum to the 0 vector.
[...]
Huh? Taking n = 2, Stage 0: {++, +-, -+, --} Stage 1: {++, +0, -0, -0} Stage 2: {+0 -0} Sum = 0, yes? WFL On 6/23/12, Joerg Arndt <arndt@jjj.de> wrote:
* Dan Asimov <dasimov@earthlink.net> [Jun 23. 2012 07:47]:
I recently heard this cute 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.
--Dan
This will work only for some definition of "some": if the evil kid removes, for example, the j-th component in all but one vector then I cannot non-emptily sum to the 0 vector.
[...]
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
* Joerg Arndt <arndt@jjj.de> [Jun 23. 2012 17:06]:
* Dan Asimov <dasimov@earthlink.net> [Jun 23. 2012 07:47]:
[...]
This will work only for some definition of "some": if the evil kid removes, for example, the j-th component in all but one vector then I cannot non-emptily sum to the 0 vector.
Oh dear, I had to switch my computer back on, because: http://xkcd.com/386/ I'll think about it some more.
[...]
On 2012-06-23, at 6:37 AM, Joerg Arndt wrote:
* Dan Asimov <dasimov@earthlink.net> [Jun 23. 2012 07:47]:
I recently heard this cute 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.
--Dan
This will work only for some definition of "some": if the evil kid removes, for example, the j-th component in all but one vector then I cannot non-emptily sum to the 0 vector.
[...]
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 2012-06-23, at 6:37 AM, Joerg Arndt wrote:
* Dan Asimov <dasimov@earthlink.net> [Jun 23. 2012 07:47]:
I recently heard this cute 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.
--Dan
This will work only for some definition of "some": if the evil kid removes, for example, the j-th component in all but one vector then I cannot non-emptily sum to the 0 vector.
[...]
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Give the vectors back to your child, and tell them they can {play WII | have dessert} only after finding some vectors that add up to zero. Kids are smart (-: On Fri, Jun 22, 2012 at 5:03 PM, Dan Asimov <dasimov@earthlink.net> wrote:
I recently heard this cute 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.
--Dan
-- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com
Dan, I still don't have an answer, but am wondering if the right approach is to come up with a formula for the number of subsets of the resulting vectors which sum to 0, and then show that it's odd (or maybe non congruent to 0 modulo some other convenient integer). I could imagine using some clever trick involving interchanging summations. I also wonder how this generalizes to other finite groups: given a finite abelian group G, you can write down the matrix of all the group characters (which is what you've done with the group Z_2^n) -- the rows being the characters, and the columns the group elements. As long as G is not the trivial group, the rows sum to 0. So you can do the same thing -- change some arbitrary subset of the values of this matrix to 0, and ask if there is a non empty subset of the rows of the resulting matrix that sum to 0. Victor On Fri, Jun 22, 2012 at 5:03 PM, Dan Asimov <dasimov@earthlink.net> wrote:
I recently heard this cute 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.
--Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
An amendment: I realize that I was a bit too hasty with the modified problem. The original problem corresponds to the part of the matrix given by the columns of a set of generators of G. On Tue, Jun 26, 2012 at 11:34 AM, Victor Miller <victorsmiller@gmail.com>wrote:
Dan, I still don't have an answer, but am wondering if the right approach is to come up with a formula for the number of subsets of the resulting vectors which sum to 0, and then show that it's odd (or maybe non congruent to 0 modulo some other convenient integer). I could imagine using some clever trick involving interchanging summations. I also wonder how this generalizes to other finite groups: given a finite abelian group G, you can write down the matrix of all the group characters (which is what you've done with the group Z_2^n) -- the rows being the characters, and the columns the group elements. As long as G is not the trivial group, the rows sum to 0. So you can do the same thing -- change some arbitrary subset of the values of this matrix to 0, and ask if there is a non empty subset of the rows of the resulting matrix that sum to 0.
Victor
On Fri, Jun 22, 2012 at 5:03 PM, Dan Asimov <dasimov@earthlink.net> wrote:
I recently heard this cute 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.
--Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (6)
-
Dan Asimov -
Fred lunnon -
Joerg Arndt -
Robert Munafo -
Tom Karzes -
Victor Miller