## February 2003

This month's puzzle was sent in by Michael Brand.

We have a collection of 2^{N} 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 2^{N} 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 i^{th} 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=2^{4} 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 2^{N} 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.