Ponder This

February 2003

<<January February March>>

We will build a sequence of cards from our collection. We will maintain a "position" S[t] (after t steps), namely a vector of N integers from {0,+1}. Initially S[0]=[0,0,...,0].

At each step, use the "position" to select the next card in the sequence, as follows. Convert the "position" to a "tag" by changing each +1 to -1 and changing each 0 to +1. So a position of [0,1,1,0] determines a tag of [+1,-1,-1,+1]. For our next card in the sequence, select the unique card with this tag. (Our first selected card will have tag [+1,+1,...,+1], obtained from our initial position of [0,0,...,0].)

When we add the "value" of the chosen card to the "position", we obtain a new "position" whose entries are still in {0,+1}. To see this: if the i^th entry in the old position was 0, then that entry in the tag of the chosen card will have +1, and its value will be either +1 or 0; adding that to the entry in the old position, the entry in the new position will be +1 or 0. Similarly, if the i^th entry in the old position was +1, then the tag of the chosen card will have -1, and its value will be either -1 or 0; adding that to entry in the old position, the entry in the new position will be 0 or +1.

Let us continue selecting more such cards through the same procedure: at each step, the position is always in {0,1}^N, so it can always be mapped into a card. We add the resultant card into the sequence to continue the sequence.

If we reach all-zeros, we're done. If we go through all 2^N sets, and don't reach zero, we must have reached the same position twice (there are only2^N possible positions, so, barring all-zeros, we have more sets than positions). Supposing we reached the same position both in step X and in step Y. Then difference set {X+1,X+2,...,Y-1,Y} is the desired set, since

0 = S[Y] - S[X] = V[X+1] + V[X+2] + ... + V[Y-1] + V[Y].

We can, therefore, stop the process as soon a we hit the same position twice, and we don't need to finish building all 2^N.

What if we're not able to put the right card into the set, because we've already used it before? Since the mapping from positions to cards is one-to-one, the only way for us to need the same card twice is if we've reached the same position twice. However, as we've already seen, if that happens we merely need to take the subtraction set in order to find the solution.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com