[math-fun] Asimov vector puzzle
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.
--Mentally pair each +-1 vector with its negation. If the child alters certain vectors V (converting to V'), then remove both V' and -V from the full set (admittedly you may not know what V is, but this proof is merely existential -- a way exists)... and then remaining vectors still will have a pairing as before hence still will sum to 0.
If, e.g., all vectors have been altered then this suggestion would lead to all vectors being removed, but the puzzle calls for a nonempty subset summing to 0. --Dan [Also, may I recommend not changing the Subject line unless one is genuinely changing the subject of the discussion.] << [I 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.
--Mentally pair each +-1 vector with its negation. If the child alters certain vectors V (converting to V'), then remove both V' and -V from the full set (admittedly you may not know what V is, but this proof is merely existential -- a way exists)... and then remaining vectors still will have a pairing as before hence still will sum to 0.
It's even worse than that, since both the altered vector and its paired vector are removed. So as few as half of the vectors being altered by the child could result in the empty subset (i.e., if only one vector in each pair is altered). For example, suppose all vectors whose initial element was originally +1 are altered to contain a zero element. Then all vectors would be removed and you'd end up with the disallowed empty subset. Tom Dan Asimov writes:
If, e.g., all vectors have been altered then this suggestion would lead to all vectors being removed, but the puzzle calls for a nonempty subset summing to 0.
--Dan
[Also, may I recommend not changing the Subject line unless one is genuinely changing the subject of the discussion.]
<< [I 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.
--Mentally pair each +-1 vector with its negation. If the child alters certain vectors V (converting to V'), then remove both V' and -V from the full set (admittedly you may not know what V is, but this proof is merely existential -- a way exists)... and then remaining vectors still will have a pairing as before hence still will sum to 0.
math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Yes, that was my reason for using an "e.g.". --Dan << On 2012-06-23, at 9:21 AM, Tom Karzes wrote:
It's even worse than that, since both the altered vector and its paired vector are removed. So as few as half of the vectors being altered by the child could result in the empty subset (i.e., if only one vector in each pair is altered). For example, suppose all vectors whose initial element was originally +1 are altered to contain a zero element. Then all vectors would be removed and you'd end up with the disallowed empty subset.
Tom
Dan Asimov writes:
If, e.g., all vectors have been altered then this suggestion would lead to all vectors being removed, but the puzzle calls for a nonempty subset summing to 0.
participants (3)
-
Dan Asimov -
Tom Karzes -
Warren Smith