Khang, Calvin, and Brian play the following game. Given a fixed positive integer $k$ which is at most 2016, they randomly choose a subset A of $\{1, 2, \ldots, 2016\}$ with $k$ elements.

The winner is Khang, Calvin, or Brian, respectively, if the sum of the numbers in $A$ leaves a remainder of 0, 1, or 2 when divided by 3.

How many values of $k$ for which this game is fair (i.e., such that the three possible outcomes are equally likely)?

The answer is 1344.

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

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}$ .