The normal many-pile version of Nim is played as follows. There are n piles of stones, and two players take turns removing stones. On any turn, a player may remove as many stones as desired from a single pile. The player who cannot make a move loses.

A very nice and classical result is that a position a₁, a₂, ..., a_n is a losing position if and only if , where is the XOR operator. To prove this, we simply realize that from any losing position, if we change the value of one pile, the XOR will no longer be zero (thus a winning position). And from any winning position, we can look at the highest order bit which does not XOR to zero, pick a pile in which that bit is 1, change it to 0, and adjust the rest of the bits in that pile to make the XOR zero.

The variation in Problem D lies in the fact that a player may remove stones from up to k different piles on each turn rather than just a single one. As such, the winning and losing positions change. We begin by defining the operation b_i(x) which equals the i-th bit of x (always 0 or 1). Then define the p-XOR of the values a₁, a₂, ..., a_n to be

.

That is, for each digit in the binary expansion, we add up all the values and take the result modulo p. If we choose p = 2, for example, we get the sequence of bits resulting from the normal XOR of the values.

It turns out that in this variation of Nim, a position a₁, a₂, ..., a_n is a losing position if and only if is all zeros. The proof of this result is a little less nice, so I will just outline the idea. From any losing position, consider the highest order bit affected among any of the piles. This bit always goes from 1 to 0 (or else the pile is getting bigger). Since at most k piles are affected, the (k + 1)-XOR of that bit can no longer be 0, leaving us in a winning position.

From any winning position, we again look at the highest order bit which does not (k + 1)-XOR to 0. Let's say those bits add up to m modulo k + 1. Choose m piles which have that bit set to 1 and change them to 0, as well as zeroing out all of the lower order bits in those piles. Then move on to the next bit of lower order. If we can fix the (k + 1)-XOR of that bit using just the piles we have selected so far (by changing some 0's to 1's), then do so and move on. Otherwise, choose as many additional piles as necessary to change, noting that this will be at most k - m. If we continue this process we can set the (k + 1)-XOR of all bits to be 0 while choosing at most k piles.

It is useful to understand Nim and its variations very well because game problems often reduce to them. If you know what you're trying to reduce to, it can often be a lot easier to find the reduction. Then knowing how to solve a simple algorithmic game is all that's left!