Let p be an odd prime number. How many p-element subsets A of {1, 2, ... , 2p} are there, the sum of whose elements is divisible by p?
Solution
Answer: 2 + (2pCp - 2)/p, where 2pCp is the binomial coefficient (2p)!/(p!p!).
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.
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.