Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Since there are $2p$ elements in the set, there are exactly $p$ distinct remainders (including $0$) when divided by $p$. We can write it as :

$1$ and $p+1 \equiv 1 \pmod{p}$

$2$ and $p+2 \equiv 2 \pmod{p}$

$3$ and $p+3 \equiv 3 \pmod{p}$

$.$

$.$

$p-1$ and $2p-1 \equiv p - 1 \pmod{p}$

$p$ and $2p \equiv 0 \pmod{p}$

I noticed that we can make $p$-element subsets considering each from same remainder set

for eg: Subsets can be = ($1,2,3,...p$), ($p+1,p+2,3,5,..2p$).

Therefore, number of ways choosing such $p$-element subsets is $2^p$. And I believe there are few more. Hope someone could help?

share|improve this question
2  
The number of $p$-element subsets is $N={2p\choose p}$. I expect the number with sum a multiple of $p$ to be very close to $N/p$. –  Gerry Myerson Feb 26 '13 at 11:21
    
@GerryMyerson, care to expand a bit for us less mathematically intuitive? –  vonbrand Feb 26 '13 at 12:48
    
@vonbrand, given a $p$-element subset, the remainder on division of its sum by $p$ could be any one of $p$ different numbers, and the default assumption is that all $p$ are equally likely. I'm happy to see that Ivan has confirmed my expectation with rigorous mathematics. –  Gerry Myerson Feb 26 '13 at 22:48

1 Answer 1

up vote 11 down vote accepted

This is IMO 1995 Q6.

I shall provide 2 solutions, one using only standard number theory and another using generating functions.

Solution 1: Clearly $\{1, 2, \ldots , p\}$ and $\{p+1, p+2, \ldots , 2p\}$ are 2 such $p$-element subsets with sum of elements divisible by $p$.

Consider all other $p$-element subsets of $\{1, 2, \ldots , 2p\}$. There are $\dbinom{2p}{p}-2$ of them. For a subset with $k$ elements in $\{1, 2, \ldots , p\}$ and $p-k$ elements in $\{p+1, p+2, \ldots , 2p\}$, where $1 \leq k \leq p-1$, we can take any $1 \leq i \leq p-1$, add $i$ to each of the $k$ elements in $\{1, 2, \ldots , p\}$, then take the resulting $k$ numbers $\pmod{p}$ to keep them in $\{1, 2, \ldots, p\}$. This gives us $(p-1)$ more $p$-element subsets, so that we have $p$ $p$-element subsets with sum of elements giving different remainder $\pmod{p}$.

It is now clear that the $\dbinom{2p}{p}-2$ subsets can be partitioned into groups of $p$ subsets, where each group has exactly one subset with sum of elements divisible by $p$. This gives $\dfrac{\dbinom{2p}{p}-2}{p}$.

Finally, combining gives the total number as $2+\dfrac{\dbinom{2p}{p}-2}{p}$.

Solution 2: We proceed using generating functions. Consider the generating function $f(x, y)=\prod\limits_{m=1}^{2p}{(1+x^my)}$. In its expansion, the coefficient of $x^ay^b$ is the number of $b$-element subsets with sum of elements equal to $a$.

Suppose we sum all the coefficients of the terms where the power of $x$ and the power of $y$ are both divisible by $p$. This will give the number of $kp$ element subsets with sum of elements divisible by $p$. To get the number of $p$-element subsets with sum divisible by $p$, we would have to subtract the number of $0$-element subsets and $2p$-element subset with sum divisible by $p$, which is $2$.

To get the required sum, we average over all $p$th roots of unity for both $x, y$ (and subtract $2$ to get the final answer):

\begin{align} &-2+\frac{1}{p^2}\sum_{k=0}^{p-1}{\sum_{j=0}^{p-1}{f(e^{\frac{2i\pi j}{p}}, e^{\frac{2i\pi k}{p})}}} \\ = &-2+\frac{1}{p^2}\sum_{k=0}^{p-1}{\sum_{j=0}^{p-1}{\prod_{m=1}^{2p}{(1+(e^{\frac{2i\pi j}{p}})^m(e^{\frac{2i\pi k}{p}}))}}} \\ = &-2+\frac{1}{p^2}\sum_{k=0}^{p-1}{\left((1+e^{\frac{2i\pi k}{p}})^{2p}+\sum_{j=1}^{p-1}{\prod_{m=1}^{2p}{(1+(e^{\frac{2i\pi j}{p}})^m(e^{\frac{2i\pi k}{p}}))}}\right)} \\ = &-2+\frac{1}{p^2}\sum_{k=0}^{p-1}{\left((1+e^{\frac{2i\pi k}{p}})^{2p}+(p-1)\prod_{m=1}^{2p}{(1+e^{\frac{2i\pi m}{p}})}\right)} \\ = &-2+\frac{1}{p^2}\sum_{k=0}^{p-1}{\left((1+e^{\frac{2i\pi k}{p}})^{2p}\right)}+\frac{1}{p}\left((p-1)\prod_{m=1}^{2p}{(1+e^{\frac{2i\pi m}{p}})}\right) \\ = &-2+\frac{1}{p}\left(2+\binom{2p}{p}\right)+\frac{1}{p}\left((p-1)[(-1)^p((-1)^p-1)]^2\right) \\ = & \frac{\dbinom{2p}{p}+2p-2}{p} \end{align}

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.