Question 16: A game of Nim is played with n heaps that have a_1, \ldo…

A game of Nim is played with $n$ heaps that have $a_1, \ldots, a_n$ stones (in other words, the $i$-th heap has $a_i$ stones). The rules of Nim are not relevant to this problem. We only note that the first player wins if and only if the bitwise xor $a_1 \oplus \cdots \oplus a_n$ is non-zero.

Alice and Bob are playing the following game. Both Alice and Bob have several boxes with heaps. In the first phase they pick exactly one heap from each box. In the second phase Alice chooses some nonempty subset of those heaps, and the regular Nim game starts on chosen heaps with Bob to move first.

Bob already knows which heaps Alice picked. Our goal is to help him to perform his picks so that he wins the game no matter which heaps Alice chooses during the second phase.

For example, suppose Alice has picked two heaps with one and two stones, and Bob has two boxes:

• The first box has two heaps of sizes one and three stones.
• The second box has two heaps of sizes two and four stones.

Then notice that no matter what Bob picks, Alice can always pick a subset whose XOR sum is zero:

• If Bob picks 1,2, Alice picks 1,2,1,2 (1,1 or 2,2 would also work)
• If Bob picks 1,4, Alice picks 1,1
• If Bob picks 3,2, Alice picks 2,2
• If Bob picks 3,4, Alice picks 1,2,3

However suppose Alice has picked one heap with one stone, and Bob has two boxes:

• The first box has two heaps of sizes three and five stones.
• The second box has two heaps of sizes seven and four stones.

Then Bob can pick the heap with three stones from the first box and seven stones from the second, and no matter which non-empty subset of heaps Alice picks from $(1, 3, 7)$, the XOR sum will be nonzero and Bob will win the game:

• $3 \oplus 2 \oplus 7 = 6$,
• $3 \oplus 2 = 1, 3 \oplus 7 = 4, 2 \oplus 7 = 5$,
• and singleton subsets are already nonzero.

Assume that all heap sizes are positive integers between $1$ and $2^{10}$.

Based on the above data, answer the given subquestions.

Suppose Bob has $b$ boxes. Let $S_i$ denote set of heap sizes in the $i$-th box. Let $S$ denote the set of heap sizes that Alice has. Interpret each heap size as a 10-length bit vector (adding leading zeroes as necessary) based on the binary representation of the number: for example, a heap of size $5$ would be $\langle 0, 0, 0, 0, 0, 0, 0, 1, 0, 1 \rangle$. Therefore, all heap sizes are elements of the vector space $\mathbb{F}_2^{10}$, where $\mathbb{F}_2$ is the field over two elements $\{0, 1\}$ with the operation being addition modulo two. If Bob selects heaps with sizes $h_i \in S_i$ and these choices guarantee a win for Bob, then the set $\{h_i \quad 1 \leqslant i \leq b\} \cup S$ is: