, 2016

The winning values of $k$ are the numbers in $\{1, ..., 1000\}$ that are coprime with $1001$, i.e., not divisible by $7$, $11$ or $13$.

Despite the repetitions in Bibi's collection $B$ for brevity we call it a set in the solution and denote the number of its elements by $|B|$. The allowed operation is choosing a $k$-element subset of $B$ and increasing each of its elements by $1$ modulo $1001$.

Let us show that a winning number $k$ is coprime with $1001$. Assume on the contrary that $\text{gcd}(k,1001) = d > 1$ and consider any set $B$ chosen by Bibi. Let the elements of $B$ have sum $S$. Suppose Alex chooses $k$ numbers from $B$ of which $m$ are $1000$. Then the operation increases $S$ by $(k - m) - 1000m = k - 1001m$, a number divisible by $d$ in view of $\text{gcd}(k,1001) = d$. Hence the operation does not change $S$ modulo $d$, for any choice of $B$. Let $B$ contain one number $1$ and $|B|-1$ zeros. Then $S \equiv 1 \pmod{d}$ persists after each operation, while the desired "all zeros" final state requires $S \equiv 0 \pmod{d}$. The contradiction proves that $\text{gcd}(k,1001) = 1$ is a necessary condition for $k$ to be winning.

Conversely, $\text{gcd}(k, 1001) = 1$ is sufficient. For a proof consider the unique integer $l$ in $\{1, ..., 1000\}$ such that $kl \equiv 1 \pmod{1001}$. Let $B$ any set chosen by Bibi and $b \in B$ an arbitrary element. It is enough to show that there is a sequence of operations that adds $1$ modulo $1001$ to $b$ without affecting the remaining numbers in $B$.

Take a $(k + 1)$-element subset $C$ of $B$ that contains $b$. This is possible as $|B| > k$. Apply the operation $l$ times to each $k$-element subset of $C$. Each element of $C$ is contained in exactly $k$ such subsets, so the procedure increases it $kl$ times modulo $1001$. Because $kl \equiv 1 \pmod{1001}$, the result is that each element of $C$ is increased by $1$ modulo $1001$. Now take the $k$-element subset $C \setminus \{b\}$ of $C$ and apply the operation $1000$ times. After all described operations each element of $C \setminus \{b\}$ is increased by $1+1000=1001$ modulo $1001$ with respect to its initial state, meaning that the operations do not change it. Clearly the elements of $B \setminus C$ do not change either. The only change concerns $b$ which is increased by $1$ modulo $1001$, as needed. Hence $\text{gcd}(k, 1001) = 1$ is a sufficient condition, and the solution is complete.