About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
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.