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


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

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

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

If $\displaystyle x$ is odd put $\displaystyle y=x$ else put $\displaystyle y=p+x$.

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

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

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

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

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

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

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

Replacing $\displaystyle j$ with $\displaystyle i$ in the above, the claim follows.

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