Argentine National Olympiad 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(\mathrm{mod}d)$ persists after each operation, while the desired "all zeros" final state requires $S\equiv 0(\mathrm{mod}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(\mathrm{mod}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(\mathrm{mod}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.