number of p element subsets whose sum is divisible by p

caffeinemachine

Well-known member
MHB Math Scholar
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$.

Attempt.

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]$. 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.

Opalg

MHB Oldtimer
Staff member
Unable to get anywhere with this, I did an internet search and found that this is a problem (an exceptionally difficult one) from the 1995 International Olympiad. There is a solution in a book by Ross Honsberger (Mathematical Chestnuts from Around the World, pp.220-223; if you search for the book, you will find it freely available online in DjVu format). The solution given there consists of a direct proof, using a generating function, that $|[K_0]| = \frac1p\Bigl\{{2p\choose p} + 2(p-1)\Bigr\}.$ It does not make use of your very elegant proof that all the other sets $[K_i]$ have the same size, and it gives no clue as to why $[K_0]$ should contain two extra elements.

caffeinemachine

Well-known member
MHB Math Scholar
Unable to get anywhere with this, I did an internet search and found that this is a problem (an exceptionally difficult one) from the 1995 International Olympiad. There is a solution in a book by Ross Honsberger (Mathematical Chestnuts from Around the World, pp.220-223; if you search for the book, you will find it freely available online in DjVu format). The solution given there consists of a direct proof, using a generating function, that $|[K_0]| = \frac1p\Bigl\{{2p\choose p} + 2(p-1)\Bigr\}.$ It does not make use of your very elegant proof that all the other sets $[K_i]$ have the same size, and it gives no clue as to why $[K_0]$ should contain two extra elements.
Thank You Opalg. Although the proof given in Honsberger uses a totally different approach, I myself tried a generating function approach and failed. So I am happy to see a proof using generating functions.

It does not make use of your very elegant proof that ...
*rubs eyes* Thank you so much for the compliment.