Where can I get 30 other people?

A game is played with 31 31 people.

First, each person is assigned a different integer between 0 0 and 30 30 inclusive. Also, an integer k k is selected such that 0 k 2015 0 \leq k \leq 2015 .

Then, a computer program chooses a random subset of { 1 , 2 , 3 , , 2015 } \{1, 2, 3, \dots, 2015 \} with k k elements. (For k = 0 k = 0 , the subset is the empty set.) Each subset is equally likely to be chosen. The sum S S of the numbers in this subset is calculated.

The winner of the game is the person whose assigned number is congruent to S S modulo 31 31 .

It is given that there is one person out of all 31 31 people that has a greater probability of winning than the other 30 30 people. Find the sum of all possible values of k k that satisfy this.


The answer is 66495.

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.

1 solution

Steven Yuan
May 5, 2015

Let a n a_n = the number of subsets with k k elements such that S n ( m o d 31 ) S \equiv n \pmod{31} . Also, let z = e 2 π i / 31 z = e^{2 \pi i/31} . We have

n = 0 30 a n z n = 1 d 1 < d 2 < < d k 2015 z d 1 + d 2 + + d k , \sum_{n = 0}^{30} a_n z^n = \sum_{1 \leq d_1 < d_2 < \cdots < d_k \leq 2015}^{} z^{d_1 + d_2 + \cdots + d_k},

where the d i d_i s are the elements of the subset. However, this is also the coefficient of x 2015 k x^{2015 - k} of

( x + z ) ( x + z 2 ) ( x + z 2015 ) . (x + z)(x + z^2)\cdots (x + z^{2015}).

The above expression can be simplified using z 31 = 1 z^{31} = 1 to get

( x + z ) ( x + z 2 ) ( x + z 2015 ) = [ ( x + 1 ) ( x + z ) ( x + z 30 ) ] 65 = ( x 31 + 1 ) 65 , \begin{aligned} (x + z)(x + z^2) \cdots (x + z^{2015}) &= [(x + 1)(x + z)\cdots (x + z^{30})]^{65} \\ &= (x^{31} + 1)^{65}, \end{aligned}

which, from binomial expansion, becomes

x 2015 + ( 65 1 ) x 1984 + + ( 65 64 ) x 31 + 1. x^{2015} + \binom{65}{1} x^{1984} + \cdots + \binom{65}{64} x^{31} + 1.

For k = 0 , 31 , 62 , , 2015 k = 0, 31, 62, \dots, 2015 , we get that n = 0 30 a n z n = c \sum_{n = 0}^{30} a_n z^n = c , where c > 0 c > 0 . We claim that a 0 c = a 1 = a 2 = = a 30 a_0 - c = a_1 = a_2 = \cdots = a_{30} , so a 0 a_0 is greater than the other a i a_i s. Since all subsets are chosen with equal probability, the person with the integer 0 0 has a greater chance of winning than the others. Thus, the sum of the possible k k is

0 + 31 + 62 + + 2015 = 31 ( 1 + 2 + + 65 ) = 31 ( 33 ) ( 65 ) = 66495 . 0 + 31 + 62 + \cdots + 2015 = 31(1 + 2 + \cdots + 65) = 31(33)(65) = \boxed{66495}.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...