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 , … , 2 0 1 6 } 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)?
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.
Lemma.
If p is a prime number and a 0 , a 1 , . . . , a p − 1 are rational numbers satisfying a 0 + a 1 ε + a 2 ε 2 + . . . + a p − 1 ε p − 1 = 0 , where ε = e p 2 π i , that is, the primitive root of unity, then a 0 = a 1 = a 2 = . . . = a p − 1 .
Proof: Observe that a 0 + a 1 x + a 2 x 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 Q , 1 + x + x 2 + . . . + x p − 1 must divide a 0 + a 1 x + . . . + 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 ) ≡ i (mod 3) .
Also denote ε = e 3 2 π i . It is clear that i = 0 ∑ 2 a i ε i = 1 ≤ c 1 ≤ c 2 ≤ . . . ≤ c k ≤ 2 0 1 6 ∑ ε c 1 + . . . + c k
But this is just the x 2 0 1 6 − k coefficient of the polynomial
( x + ε ) ( x + ε 2 ) . . . ( x + ε 2 0 1 6 ) = [ ( x + ε ) ( x + ε 2 ) ( x + 1 ) ] 6 7 2 = ( x 3 + 1 ) 6 7 2
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 2 0 1 6 − k coefficient to be zero. This is only when 3 ∤ k .
The values for which this is true are 1 , 4 , 7 , . . . , 2 0 1 4 and 2 , 5 , . . . , 2 0 1 5 which is 1 3 4 4 values.
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 } by f ( n ) = (remainder of 3 n )
We know that P ( w i n i n g ) = 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 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 . 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 × 2 + b × 1 + c × 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 k ! × 2 ! ( k + 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 ) ! will not be divisible by 3(in all other cases k ! × 2 ! ( k + 2 ) ! will be divisible by 3). Therefore total possible value of k is 3 2 0 1 6 × 2 = 1 3 4 4 .
So we can see that the total number of k cannot be more than 1 3 4 4 , 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 .
Problem Loading...
Note Loading...
Set Loading...
We will prove that the game is fair exactly when k is not a multiple of 3. The set X = { 1 , 2 , … , 2 0 1 6 } is a union of the 6 7 2 three element subsets S 1 = { 1 , 2 , 3 } , S 2 = { 4 , 5 , 6 } , ..., S 6 7 2 = { 2 0 1 4 , 2 0 1 5 , 2 0 1 6 } .
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 ∩ S i having 1 or 2 elements.
Let i 0 be the smallest such index, and define a function f : X → X by f ( n ) = n , if n ∈ / S i 0 , f ( n ) = n + 1 , if n ∈ S i 0 and n + 1 ∈ S i 0 , and f ( n ) = n − 2 , if n ∈ S i 0 and n + 1 ∈ / 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 = 3 m is a multiple of 3 .
Then the k − element subsets A such that A ∩ 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 1 3 4 4 .