IBM Ponder This #058 · 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 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=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.

Solution

Best opened after a real attempt

To be added.