IBM Research | Ponder This | February 2003 challenges
Skip to main content

Ponder This

February 2003

<<January February March>>


Ponder This Challenge:

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 webmaster.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: webmster@us.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 webmaster.