Let S=\{ 1, 2, \ldots , 2p\}, where p is an odd prime. Find the number of p-element subsets of S the sum of whose elements is divisible by p.


Let \mathcal{K} be the set of all the p element subsets of S. Let \sigma(K) denote the sum of the elements of a member K of \mathcal{K}. Define a relation R on \mathcal{K} as: ARB if \sigma(A) \equiv \sigma(B) (\mod p), for A,B \in \mathcal{K}. Its clear that R is an equivalence relation. Choose K_0,K_1, \ldots , K_{p-1} \in \mathcal{K} such that \sigma(K_i) \equiv i (\mod p). Let [K_i] denote the equivalence class of K_i under R.

Claim: |[K_i]|=|[K_j]| whenever 2p>i,j>0

Proof. Let x \in \{ 1, \ldots , p-1\} be such that ix \equiv j (\mod p) (Such an x exists).

If x is odd put y=x else put y=p+x.

So in any case y is odd and 0<y<2p.

Now let K_i = \{ a_1, \ldots , a_p \}.

Consider a set K^{*}=\{ ya_1, \ldots , ya_p\}, where each element of K^{*} is reduced mod 2p if necessary.

One can easily show that ya_i's are all distinct, thus K^{*} \in \mathcal{K}.

Also \sigma(K^{*}) \equiv iy \equiv ix \equiv j (\mod p)), thus K^{*} \in [K_j].

So from each element of [K_i] we can produce one element of [K_j].

Also, since gcd(y,2p)=1, it follows that two distinct elements of [K_i] don't match to a same element of [K_j].

Replacing j with i in the above, the claim follows.

To arrive at the required answer I just need to show that |[K_0]|=|[K_1]|+2. But here I am stuck.