329 views
3 votes
3 votes
Let p be an odd prime number. Find the number of subsets A of the set {1, 2, …, 2p} such that

(i) A has exactly p elements, and

(ii) the sum of all the elements in A is divisible by p.

1 Answer

Best answer
1 votes
1 votes

Solution:

Answer: 2 + ( 2pCp - 2) / p, where 2pCp is the binomial coefficient (2p)! / (p!p!).

(i) A has exactly p elements:

Let A be a subset other than {1, 2, ... , p} and {p+1, p+2, ... , 2p}.

Consider the elements of A in {1, 2, ... , p}.

The number r satisfies 0 < r < p. We can change these elements to another set of r elements of {1, 2, ... , p} by adding 1 to each element (and reducing mod p if necessary).

We can repeat this process and get p sets in all. For example, if p = 7 and the original subset of {1, 2, ... , 7} was {3 , 5}, we get:

  {3 , 5}, {4, 6}, {5, 7}, {6, 1}, {7, 2}, {1, 3}, {2, 4}.

The sum of the elements in the set is increased by r each time. So, since p is prime, the sums must form a complete set of residues mod p. In particular, they must all be distinct and hence all the subsets must be different.

(ii) the sum of all the elements in A is divisible by p:

Now consider the sets A which have a given intersection with {p+1, ... , n}.

Suppose the elements in this intersection sum to k mod p. The sets can be partitioned into groups of p by the process described above, so that exactly one member of each group will have the sum -k mod p for its elements in {1, 2, ... , p}. In other words, exactly one member of each group will have the sum of all its elements divisible by p.

There are 2pCp subsets of {1, 2, ... , 2p} of size p.

Excluding {1, 2, ... , p} and {p+1, ... , 2p} leaves (2pCp - 2). We have just shown that (2pCp - 2)/p of these have sum divisible by p.

The two excluded subsets also have sum divisible by p, so there are 2 + (2pCp - 2)/p subsets in all having sum divisible by p.

selected by

Related questions

0 votes
0 votes
1 answer
2
0 votes
0 votes
0 answers
3
codingo1234 asked Dec 10, 2018
305 views
Difference between getting closed form of generating function and closed form of the given sequence ,pls someone explain with an example
1 votes
1 votes
3 answers
4
srestha asked Dec 3, 2018
1,658 views
What will be solution of this function for coefficient of $x^{100}$?$$\frac{1}{\left ( 1-x^{10} \right )(1-x^{20})(1-x^{50})}$$