A game is played with people.
First, each person is assigned a different integer between and inclusive. Also, an integer is selected such that .
Then, a computer program chooses a random subset of with elements. (For , the subset is the empty set.) Each subset is equally likely to be chosen. The sum of the numbers in this subset is calculated.
The winner of the game is the person whose assigned number is congruent to modulo .
It is given that there is one person out of all people that has a greater probability of winning than the other people. Find the sum of all possible values of that satisfy this.
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.
Let a n = the number of subsets with k elements such that S ≡ n ( m o d 3 1 ) . Also, let z = e 2 π i / 3 1 . We have
n = 0 ∑ 3 0 a n z n = 1 ≤ d 1 < d 2 < ⋯ < d k ≤ 2 0 1 5 ∑ z d 1 + d 2 + ⋯ + d k ,
where the d i s are the elements of the subset. However, this is also the coefficient of x 2 0 1 5 − k of
( x + z ) ( x + z 2 ) ⋯ ( x + z 2 0 1 5 ) .
The above expression can be simplified using z 3 1 = 1 to get
( x + z ) ( x + z 2 ) ⋯ ( x + z 2 0 1 5 ) = [ ( x + 1 ) ( x + z ) ⋯ ( x + z 3 0 ) ] 6 5 = ( x 3 1 + 1 ) 6 5 ,
which, from binomial expansion, becomes
x 2 0 1 5 + ( 1 6 5 ) x 1 9 8 4 + ⋯ + ( 6 4 6 5 ) x 3 1 + 1 .
For k = 0 , 3 1 , 6 2 , … , 2 0 1 5 , we get that ∑ n = 0 3 0 a n z n = c , where c > 0 . We claim that a 0 − c = a 1 = a 2 = ⋯ = a 3 0 , so a 0 is greater than the other a i s. Since all subsets are chosen with equal probability, the person with the integer 0 has a greater chance of winning than the others. Thus, the sum of the possible k is
0 + 3 1 + 6 2 + ⋯ + 2 0 1 5 = 3 1 ( 1 + 2 + ⋯ + 6 5 ) = 3 1 ( 3 3 ) ( 6 5 ) = 6 6 4 9 5 .