February 2003
This month's puzzle was sent in by Michael Brand.
We have a collection of 2N cards. Each card C[c] has two vectors of N integers each: a "tag" T[c] and a "value" V[c]. The "tag" consists of N integers chosen from {-1,+1}, and each of the 2N such possible vectors is used as a tag for exactly one card. The "value" of each card is a vector with entries from {-1,0,+1}, whose nonzero entries agree with the entries of the card's "tag". That is, in the ith position, V[c]i is either T[c]i or 0. The "tags" are fixed, and the "values" are chosen by an outsider before we begin; both are known to us.
Given a nonempty set of cards, the "total value" is a vector of N integers obtained by summing the vector "values" of the various cards. For example, if N=4, among the 16=24 cards we select three with "tags" and "values" given respectively by
T[1]= [-1,-1,+1,+1] V[1] = [-1,-1, 0,+1 ]
T[2]= [+1,-1,+1,+1] V[2] = [+1, 0,+1, 0 ]
T[3]= [+1,+1,-1,+1] V[3] = [ 0,+1,-1,+1 ]
The "total value" in this case is [0,0,0,2].
Given such a collection of 2N cards, show that there is a nonempty subset of them whose "total value" is the vector of all zeroes, [0,0,...,0]. Show how to find such a subset.
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com
Challenge:
02/03/2003 @ 10:40 AM EST
Solution:
02/03/2003 @ 10:40 AM EST
List Updated:
02/03/2003 @ 10:40 AM EST
People who answered correctly:
John G. Fletcher (02.10.2003@11:39:10PM EST)
Trevor Graffa (02.11.2003@09:26:30AM EST)
Airat Chanyshev (02.13.2003@06:35:09PM EST)
Peter Johansson (02.19.2003@11:18:07PM EST)
Steve Horvath (02.27.2003@01:36:05PM EST)
Stephen Martin (02.27.2003@01:36:05PM EST)
Swastik Kopparty (02.28.2003@02:15:47AM EST)
Klaus Hoffmann (03.01.2003@03:52:15AM EST)
Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.