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?

  • 2
    $\begingroup$ 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$. $\endgroup$ – Gerry Myerson Feb 26 '13 at 11:21
  • $\begingroup$ @GerryMyerson, care to expand a bit for us less mathematically intuitive? $\endgroup$ – vonbrand Feb 26 '13 at 12:48
  • $\begingroup$ @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. $\endgroup$ – Gerry Myerson Feb 26 '13 at 22:48

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}


I remember an elegant complex number proof from an Olympiad book (apparently this solution was given by a Bulgarian contestant who won an award for creativity).

Let $\omega$ be a $p$-th root of unity. Consider the sum: $$F(\omega) = \sum_{1 \leq i_1 < i_2 ... < i_p \leq 2p} \omega^{i_1}\omega^{i_2}...\omega^{i_p}.$$

We observe that $\omega, \omega^{2}, ... , \omega^{2p}$ are the roots of $(x^p - 1)^2 = x^{2p} - 2x^p + 1$. By the relation between elementary symmetric functions of roots and coefficients, we get $F(\omega) = 2$.

But we can write $\omega^{i_1}\omega^{i_2}...\omega^{i_p} = \omega^{i_1+i_2+...+i_p}$ and read the powers of $\omega$ modulo $p$. So another way to write the sum is $$F(\omega) = \sum_{0 \leq k \leq p-1}a_k \omega ^k.$$

Therefore equating the two different ways of writing the sum, we get: $$(a_o - 2) + a_1 \omega + a_2 \omega^2 ... + a_{p-1} \omega^{p-1} = 0.$$

But this means $$a_0 - 2 = a_1 = a_2 = ... = a_{p-1}.$$ Clearly $\sum_k a_k$ counts the total number of terms in the summation $F(\omega)$ which is $\binom{2p}{p}$.

Therefore $$\binom{2p}{p} - 2 = (a_0 - 2) + a_1 + a_2 + ...+ a_{p-1} = p(a_0 - 2).$$

Thus we get $$a_0 = \frac{\binom{2p}{p} - 2}{p} + 2.$$

Note that this solves the problem since $a_0$ counts the number of terms in the sum with the property $i_1 + i_2 + ... + i_p = 0$ modulo $p$.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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