2016 is absolutely awesome 6

We will prove that the game is fair exactly when $k$ is not a multiple of 3. The set $X = \{1, 2, \ldots , 2016\}$ is a union of the $672$ three element subsets $S_1 =\{1, 2, 3\}$ , $S_2 = \{4, 5, 6\}$ , ..., $S_{672} = \{2014, 2015, 2016\}$ .

Let $A$ be any subset of $X$ with $k$ elements, and let $[A]$ denote the remainder when we divide the sum of all the numbers in $A$ by 3.

If $k$ is not divisible by 3, then there must be an index $i$ with $A \cap S_i$ having $1$ or $2$ elements.

Let $i_0$ be the smallest such index, and define a function $f : X \rightarrow X$ by $f(n) = n$ , if $n \notin S_{i_0}$ , $f(n) = n + 1$ , if $n \in S_{i_0}$ and $n + 1 \in S_{i_0}$ , and $f(n) = n - 2$ , if $n \in S_{i_0}$ and $n + 1 \notin S_{i_0}$ .

The function $f$ is a bijection cyclically permutes the elements of $S_{i_0}$ , and leaves all the other elements of $X$ fixed.

Let $f(A)$ be the $k-$ element subset of $X$ obtained by applying $f$ to every element in $A$ .

Then $[A]$ , $[f(A)]$ , and $[f(f(A))]$ are distinct remainders, and $f(f(f(A))) = A$ .

We deduce that the function $f$ gives a $1-1$ correspondence between those $k-$ element subsets $A$ of $X$ with $[A] = 0$ (when Khang wins), those with $[A] = 1$ (when Calvin wins), and those with $[A] = 2$ (when Brian wins).The game is therefore fair.

Now suppose that $k = 3m$ is a multiple of $3$ .

Then the $k-$ element subsets $A$ such that $A \cap S_i$ has $1$ or $2$ elements for some $i$ can be partitioned into triples using the same function $f$ as above.

When $A$ is chosen at random among these subsets, the result is an equal number of winning games for each of the three players. There remain those $k-$ element subsets $A$ which are unions of $m$ $3-$ element subsets $S_i$ . Since all such subsets satisfy $[A] = 0$ , Khang will win if $A$ is chosen among those subsets. We deduce that the game is biased towards a win for Khang.

So the answer is $\boxed{1344}$ .

$\textbf{Lemma.}$

$\textit{If p is a prime number and}$ $a_0, a_1, ..., a_{p-1}$ are rational numbers satisfying $a_0 + a_1\varepsilon + a_2\varepsilon^2 + ... + a_{p-1}\varepsilon^{p-1} = 0,$ where $\varepsilon = e^{\frac{2\pi}{p}i},$ that is, the primitive root of unity, then $a_0 = a_1 = a_2 = ... = a_{p-1}.$

---

$\textbf{Proof:}$ Observe that $a_0 + a_1x + a_2x^2 + ... + a_{p-1}x^{p-1}$ and $1+x + x^2 + ... + x^{p-1}$ are not relatively prime since they have a common root. Since the latter is irreducible over $\mathbb{Q}$ , $1 + x + x^2 + ... + x^{p-1}$ must divide $a_0 + a_1x + ... + a_{p-1}x^{p-1}$ . which can only happen if $a_0 = a_1 = ... = a_{p-1}$ . We have proven the lemma.

---

Denote $a_i =$ number of subsets X of A such that $|X| = k$ and $m(X) \equiv i \text{ (mod 3)}$ .

Also denote $\varepsilon = e^{\frac{2\pi}{3}i}$ . It is clear that $\sum_{i = 0}^{2}a_i\varepsilon^{i} = \sum_{1 \leq c_1 \leq c_2 \leq ... \leq c_k \leq 2016}{\varepsilon^{c_1 + ... + c_k}}$

But this is just the $x^{2016 - k}$ coefficient of the polynomial

$\begin{aligned} (x+\varepsilon)(x + \varepsilon^2)...(x + \varepsilon^{2016}) & = \left[(x + \varepsilon)(x + \varepsilon^2)(x + 1)\right]^{672} \\ & = (x^3 + 1)^{672} \end{aligned}$

Notice that the only nonzero coefficients of this polynomial are when the exponent is divisible by 3. However, due to our lemma, in order for $a_0 = a_1 = a_2$ , we need the $x^{2016 - k}$ coefficient to be zero. This is only when $3 \nmid k$ .

The values for which this is true are $1,4, 7, ..., 2014$ and $2, 5, ..., 2015$ which is $\boxed{1344}$ values.

This solution just gives the upper limit of the answer (And coincidentally the upper limit is the answer ).

Let us define $f:A\rightarrow \{0,1,2\}$ by $f(n)=$ (remainder of $\frac{n}{3})$

We know that $P(wining)=\frac{Number of favorable outcomes}{Number of total possible outcomes}$ . For some particular $k$ the number of total possible outcomes (which is equal to number of distinct subsets of A that can be formed having $k$ elements.) is same for all the three players. So we just need some condition by which number of favorable outcomes becomes equal for all the three players.

In the subset of $k$ elements we can replace each element by $f(n)$ as it won't change the result (the remainder of the sum of all elements divided by 3 will still be the same.) Therefore we can write the sum of elements of the new sets as $a\times 2+b\times 1 +c\times 0$ where $a,b,c$ are whole numbers satisfying $a+b+c=k$ .

We can easily get the number of distinct triplets ( $a,b,c$ ) satisfying the above condition by using basic combinatorics. It is equal to $\frac{(k+2)!}{k!\times 2!}$ . For the number of outcomes to be in favor of the three players equally the number of distinct triplets must at least be divisible by 3.

We can easily see that if k is a multiple of 3 then $\frac{(k+2)!}{k!\times 2!}$ will not be divisible by 3(in all other cases $\frac{(k+2)!}{k!\times 2!}$ will be divisible by 3). Therefore total possible value of $k$ is $\frac{2016}{3}\times 2 =1344$ .

So we can see that the total number of $k$ cannot be more than $\boxed{1344}$ , but it is possible that the number of $k$ is less than the above figure because we haven't proved that all such $k$ will necessarily give equal probability to all three players.

Note:- Suggestions and improvements to the solutions are welcomed .