2016 is absolutely awesome 6

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

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

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


This is a part of the Set .


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.

3 solutions

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

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

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

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

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

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

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

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

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

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

When A 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 k- element subsets A A which are unions of m m 3 3- element subsets S i S_i . Since all such subsets satisfy [ A ] = 0 [A] = 0 , Khang will win if A A is chosen among those subsets. We deduce that the game is biased towards a win for Khang.

So the answer is 1344 \boxed{1344} .

Alan Yan
Dec 19, 2015

Lemma. \textbf{Lemma.}

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


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


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

Also denote ε = e 2 π 3 i \varepsilon = e^{\frac{2\pi}{3}i} . It is clear that i = 0 2 a i ε i = 1 c 1 c 2 . . . c k 2016 ε c 1 + . . . + c k \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 x^{2016 - k} coefficient of the polynomial

( x + ε ) ( x + ε 2 ) . . . ( x + ε 2016 ) = [ ( x + ε ) ( x + ε 2 ) ( x + 1 ) ] 672 = ( x 3 + 1 ) 672 \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 a_0 = a_1 = a_2 , we need the x 2016 k x^{2016 - k} coefficient to be zero. This is only when 3 k 3 \nmid k .

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

Dhiraj Agarwalla
Dec 19, 2015

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

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

We know that P ( w i n i n g ) = N u m b e r o f f a v o r a b l e o u t c o m e s N u m b e r o f t o t a l p o s s i b l e o u t c o m e s P(wining)=\frac{Number of favorable outcomes}{Number of total possible outcomes} . For some particular k k the number of total possible outcomes (which is equal to number of distinct subsets of A that can be formed having k 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 k elements we can replace each element by f ( n ) 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 × 2 + b × 1 + c × 0 a\times 2+b\times 1 +c\times 0 where a , b , c a,b,c are whole numbers satisfying a + b + c = k a+b+c=k .

We can easily get the number of distinct triplets ( a , b , c a,b,c ) satisfying the above condition by using basic combinatorics. It is equal to ( k + 2 ) ! k ! × 2 ! \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 ( k + 2 ) ! k ! × 2 ! \frac{(k+2)!}{k!\times 2!} will not be divisible by 3(in all other cases ( k + 2 ) ! k ! × 2 ! \frac{(k+2)!}{k!\times 2!} will be divisible by 3). Therefore total possible value of k k is 2016 3 × 2 = 1344 \frac{2016}{3}\times 2 =1344 .

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

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

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...