This is problem 6 form IMO 1995.There are two different solutions to it: The first is purely combinatorial: Tahe $ A = \{0..p - 1\}, B = \{p..2p - 1\}$. For a set $ S$ different from $ A$ and $ B$ denote $ C = S \bigcap A$ ,$ D = S \bigcap B$. Then the sets $ (C + x) \bigcap D$ form a group of $ p$ sets where all the residues appear. (The set $ A + x = \{(a + x) mod p| a \in A\}$) So we can couunt easily. The second uses multisection formula counting the coeff $ x^{pk} y^p$ at the polynomial $ (1 + y)(1 + xy)\cdots (1 + x^{2p - 1}y)$

Define $X: =\{ 1,2,...,p\},Y: =\{p+1,p+2,...,2p\}$. See $X$ and $Y$ as a representant system for $\mathbb{Z}/ p \mathbb{Z}$, since not more is necessary (so all identities concerning $X$ or $Y$ must be seen $\mod p$). For a subset $A \subset X$ and $z \in \mathbb{Z}/ p \mathbb{Z}$ define $A+z: =\{ a+z \in X| a \in A \}$ and similar for a subset $B \subset Y$. Call $A \subset X$ trivial iff $A=\emptyset$ or $A=X$, similar for $B \subset Y$ again. Now there are only $4$ subsets $P \subset (X \cup Y)$ such that both $P \cap X$ and $P \cap Y$ are trivial, so call these subsets trival from now on too. Then define for a nontrivial subset $P \subset (X \cup Y)$ a 'translation': if $P \cap X$ is nontrivial define $P+z : = ((P\cap X) +z) \cup (P \cap Y)$ and $P+z : = (P \cap X) \cup ((P\cap Y) +z)$ otherwise. Now it's easy to see that when $z$ goes through all possible residue classes, that also the sum of the elements of $P+z$ goes through all of them, so there is exactly one sum that is divisible by $p$. So the 'translation' divides the nontrivial subsets into equivalence classes of $p$ sets each, all sets of the same class having same number of elements. Since there are exactly $\binom{2p}{p}$ subsets of the desired order $p$ and $2$ of them are trivial, we get that there are $\frac{\binom{2p}{p}-2}{p}+2$ such subsets. (note that this technique trivially generalises to other types of subsets and all sets of type $\{1,2,...,kp\}$)

Thanks for nice work ZetaX (is it true ? )! It's a very famous problem ! It seems that there's another way to count this by using polynomial (or useing generator function) . Do you know who creat that nice solution? It's just my wondering about the exactly author of that nice solution which i saw on The Mathematics and Youth Magazine (Vietnam Magazine) in 1996!

can you write the second solution in a slightly way iura

Consider the polynomial $f(x,y)=(1+xy)(1+x^2y)\ldots(1+x^{2p-1}y)$, the $k$-th factor refering to whether $k$ is present in the set or not. Then the monomial $x^ky^l$ will refer to the set having $l$ elements and sum of elements $k$, so we need to compute the sum of coefficients of $x^{kp}y^p$ of $f$ to find the answer. To do this, we need to compute the sum of coefficients $x^{pk}y^{pl}$ and substract 2, since there are two terms for $l\neq 1$:$1, x^{p(2p-1)}y^{2p}$. To compute the sum of coefficients of $x^{pk}y^{pl}$ we use Multisection formula that says us that it equals $\frac{1}{p^2}\sum_{i,j}f(w^i,w^j)$($w$ is $p$th root of unity). Now if $w^i$ is not $1$, $f(w^i,w^j)=\prod(1+w^{ik}w^j)=\prod (1+w^k)^2$ (every $w^m$ will be written twice as $w^{ki}w^j$). This equals $\prod (-1-w^k)^2=g(-1)^2=((-1)^p-1)^2=4$ ($g(x)=x^p-1$ is the polynomial with roots $w^i$). Since there are $p-1$ choices for $w^i$, $p$ choices for $w^j$ we get $4p(p-1)$. Finally, if $w^i=1$, $f(1,w^j)=(1+w^j)^{2p}$. To evaluate $\sum_{j=0}^{p-1} (1+w^j)^{2p}$, note that it equals $p$ times the coefficients of $x^p$ in the polynomial $(1+x)^{2p}$ by the same multisection formula, so it equals $p\binom{2p}{p}$. So our total sum is $\frac 1{p^2} (4p(p-1)+p\binom{2p}{p}) =\frac{\binom{2p}{p}-2}p+4$. Substracting 2 we get the desired answer.

iura wrote: . To compute the sum of coefficients of $x^{pk}y^{pl}$ we use Multisection formula that says us that it equals $\frac{1}{p^2}\sum_{i,j}f(w^i,w^j)$($w$ is $p$th root of unity). . how can you prove that?What is miultisection formula?

If $w$ is a $n$th root of unity then $\sum_{i=0}^{n-1} w^k=0$ if $w\neq 1$ and $\sum_{i=0}^{n-1} w^k=n$ if $w=1$. By using this result, we can prove the Multisection Formula (which holds also for polynomials of more variables) : $f(x)=\sum a_ix^i$, then $\sum_{i\equiv k\pmod m} a_ix^i=\frac 1n (\sum_{i=0}^{n-1} f(w^ix) w^{-ik})$. Particularly $\sum_{i \equiv k\pmod m} a_i=\frac 1n(\sum_{i=0}^{n-1}f(w^i)w^{-ik})$

thank,i understand it now

Another (wonderful) solution : We let $w$ be the p-th root of unity. We thus have : \[ \prod_{k=1}^{2p} (x - w^k) = (x^p - 1)^2 = x^{2p} - 2x^p + 1. \] We now define the quantity : \[ t(w) = \sum_{1 \leq j_1 < j_2 < \ldots < j_p \leq 2p} w^{j_1}w^{j_2} \ldots w^{j_p}. \] So we have $t(w) = 2$. Besides, if we write $t(w) = \sum a_jw^j$, then $a_j$ represents the number of sub-sets ${j_1, j_2, \ldots, j_p}$ of ${1, 2, \ldots, 2p}$ such that $j_1 + j_2 + \ldots + j_p \equiv j \pmod p$, and we can write : \[ (a_0 - 2) + a_1w + \ldots + a_{p-1}w^{p-1} = 0. \] Since the minimal polynomial of $w$ on $\mathbb{Q}[X]$ is $1 + x + \ldots + x^{p-1}$, it follows that : \[ a_0 - 2 = a_1 = a_2 = \ldots = a_{p-1}. \] Besides, $a_0 + a_1 + \ldots + a_{p-1} = \binom {2p}{p}$, we conclude immediately that : \[ a_0 = \frac 1p \left\{\binom {2p}{p} - 2 \right \} + 2. \]

mathmanman wrote: Another (wonderful) solution mathmanman is this the solution of Nikolai Nikolov from Bulgaria for which he get a special prize?

Yes, exactly.

iura wrote: $\frac 1{p^2} (4p(p-1)+p\binom{2p}{p}) =\frac{\binom{2p}{p}-2}p+4$. This is not true...$\frac 1{p^2} (4p(p-1)+p\binom{2p}{p}) =\frac{\binom{2p}{p}-4}p+4$.

iura wrote: Consider the polynomial $f(x,y)=(1+xy)(1+x^2y)\ldots(1+x^{2p-1}y)$, the $k$-th factor refering to whether $k$ is present in the set or not. I think that we have to consider the polynomial $f(x,y)=(1+xy)(1+x^2y)\ldots(1+x^{2p}y)$...am I right?

Sorry to bump this.... but when I solve it I keep getting $\left\lceil \frac{{2p \choose p}}{p}\right\rceil$, is this the same answer?

That's $1$ to small.

mathmanman wrote: Another (wonderful) solution : We let $w$ be the p-th root of unity. We thus have : \[ \prod_{k=1}^{2p} (x - w^k) = (x^p - 1)^2 = x^{2p} - 2x^p + 1. \] We now define the quantity : \[ t(w) = \sum_{1 \leq j_1 < j_2 < \ldots < j_p \leq 2p} w^{j_1}w^{j_2} \ldots w^{j_p}. \] So we have $t(w) = 2$. Besides, if we write $t(w) = \sum a_jw^j$, then $a_j$ represents the number of sub-sets ${j_1, j_2, \ldots, j_p}$ of ${1, 2, \ldots, 2p}$ such that $j_1 + j_2 + \ldots + j_p \equiv j \pmod p$, and we can write : \[ (a_0 - 2) + a_1w + \ldots + a_{p-1}w^{p-1} = 0. \] Since the minimal polynomial of $w$ on $\mathbb{Q}[X]$ is $1 + x + \ldots + x^{p-1}$, it follows that : \[ a_0 - 2 = a_1 = a_2 = \ldots = a_{p-1}. \] Besides, $a_0 + a_1 + \ldots + a_{p-1} = \binom {2p}{p}$, we conclude immediately that : \[ a_0 = \frac 1p \left\{\binom {2p}{p} - 2 \right \} + 2. \] I wonder that whether we can use this wonderful idea to solve the generation of this problem? I mean we replace $ 2p $ with $ n>p $?

Yes, we can. If $\{ 1,2,...,2n \}$ is the initial set, then the number of subsets with $n$ elements such that each sum of these subsets' elements is divisible by $n$ is $$\frac{(-1)^n}{n} \cdot \sum_{d|n} (-1)^d \varphi \bigg( \frac{n}{d} \bigg ) \binom {2d}{d} $$where $"\varphi"$ is the Euler totient function. $$\odot$$

mihaith wrote: Yes, we can. If $\{ 1,2,...,2n \}$ is the initial set, then the number of subsets with $n$ elements such that each sum of these subsets' elements is divisible by $n$ is $$\frac{(-1)^n}{n} \cdot \sum_{d|n} (-1)^d \varphi \bigg( \frac{n}{d} \bigg ) \binom {2d}{d} $$where $"\varphi"$ is the Euler totient function. $$\odot$$ Solution for generalization: Consider the generating function $f(x)=\prod_{i=1}^{2n}(1-x^iy)$ where $y>1.$ Clearly, it suffices to find sum of coefficients in the terms of the form $x^{kn}y^{n}.$ So let $\omega$ be n-th primitive root of unity. By roots of unity filter it is sufficient to find the sum of coefficients in front of $y^{n}$ in $$P=\frac{\sum_{i=0}^{n-1}f(\omega^{i})}{n}$$Now, $f(w^{i})=\prod_{j=1}^{2n}(1-\omega^{ij}y)=(\prod_{j=1}^{n}(1-\omega^{ij}y))^2.$ Now if we denote $\epsilon=\omega^{i},$ then $\epsilon$ is $\frac{n}{gcd(n,i)}$-th primitive root of unity. Hence $$f(w^{i})=(\prod_{j=0}^{\frac{n}{gcd(n,i)}-1}(1-\epsilon^{j}y))^2=(1-y^{\frac{n}{gcd(n,i)}})^{2gcd(n,i)}...(*)$$Now it is clear that sequence $(\frac{n}{gcd(n,j)})_{1 \le j \le n}$ passes through all divisors of $n$ and only through them. In the spirit of this, we have: Lemma: For any divisor $d$ of $n$ the following has $\varphi(d)$ solutions in $j: d=\frac{n}{gcd(n,j)}$ Proof: It is equivalent with $gcd(n,j)=\frac{n}{d}$ i.e $gcd(d,\frac{jd}{n})=1$ which, since $\frac{jd}{n} < d$ has $\varphi(d)$ solutions. So let $d=gcd(n,j)$ in $(*)$ then: $f(w^{i})=(1-y^\frac{n}{d})^{2d}.$ Coefficient in front of $y^{n}$ is thus $(-1)^d\binom{2d}{d}.$ This holds for any divisor $d$ of $n$ and it appears for $\varphi(d)$ times, from Lemma. Hence, the answer is $$\frac{\sum_{d|n} (-1)^d \varphi \bigg( \frac{n}{d} \bigg ) \binom {2d}{d}}{n} \blacksquare$$

Nice problem

how to get the formula in *

My solution is similar to CantonMathGuy's. Let $A = \{ 1,2, \dots, p \}$ and $B = \{ p+1, p+2, \dots ,2p \}$. As usual $\sigma(S)$ denotes the sum of elements of set $S$. Claim: The number of $k$-element sets $S_k \subset A$, $k<p$, such that $\sigma(S_k) \equiv \ell \mod p$, for a fixed $\ell$ is $\frac{1}{p} \binom{p}{k}$. Fix $k<p$. We will establish the desired bijection. Suppose $\sigma(S_k) \equiv \ell \mod p$. Then to each element of $S_k$ add a fixed constant $i$ so that $\sigma(S_k +i) \equiv \ell +ik \mod p$. Here addition is defined in modulo $p$. Anyway,we can choose $i$ so that $\ell +ik$ is any desired residue mod $p$. There are $\binom{p}{k}$ subsets in total. By our bijection between all residues we get $\frac{1}{p} \binom{p}{k}$ subsets with $\sigma(S_k) \equiv \ell \mod p$. Now we can directly count the number of $p$-element subsets with sum divisible by $p$. If we choose no elements from $A$, then we choose all of $B$. If we choose all of $A$, then choose nothing from $B$. Choose $1 \leq i \leq p-1$ elements from $A$. There are $\binom{p}{i}$ ways to do this. Then choose $p-i$ elements from $B$ with a fixed sum mod $p$. There are $\frac{1}{p} \binom{p}{p-i}$ ways to do so. So the number of ways is $$2 + \sum _{i=1} ^{p-1} \frac{1}{p} \binom{p}{i} \binom{p}{p-i} = \boxed{2 + \frac{\binom{2p}{p}-2}{p}}$$The last equality follows from the identity $\binom{2p}{p} = \sum_{i=0}^{p} \binom{p}{i} \binom{p}{p-i}$ which can be proved by double counting the number of ways to choose $p$ elements from a $2p$-element set. So we are done.

iura wrote: . To evaluate $\sum_{j=0}^{p-1} (1+w^j)^{2p}$, note that it equals $p$ times the coefficients of $x^p$ in the polynomial $(1+x)^{2p}$ by the same multisection formula, so it equals $p\binom{2p}{p}$. No, it equals $p\binom{2p}{p}+2p$ , as you forgot to consider the first and last terms. But anyways you got the final answer correct ,so maybe it was a typo.

Of course, we can determine the number of such subsets for any fixed size of subset (not just those with $p$ elements). As in other solutions, let \[ f(x,y) = (1+xy)(1+x^2y)\cdots(1+x^{2p}y), \]and let $\zeta$ be a primitive $p^{\text{th}}$ root of unity. We will consider this as a generating function in $x$ first, run the roots of unity computation, and read the result as a generating function in $y$. Indeed, observe that $f(1,y) = (1+y)^{2p}$ while \begin{align*} f(\zeta^k,y) &= y^{2p}\Big((-y^{-1} - 1)(-y^{-1} - \zeta)\cdots (-y^{-1}-\zeta^{p-1})\Big)^2 \\&\hspace{2in}= y^{2p}(-(y^{-1})^p-1)^2 = (y^p + 1)^2. \end{align*}Therefore the sum of all coefficients of $x$ associated to powers of $p$ is \[ \frac{1}{p}\sum_{k=0}^{p-1}f(\zeta^k,y) = \frac{(p-1)(y^p + 1)^2 + (y+1)^{2p}}p. \]From this, we can read off the answer as the coefficient of $y^p$ in the above expression, or $\boxed{2 + \tfrac{\binom{2p}p - 2}p}$. In general, the number of subsets of size $k$ whose sum of elements is divisible by $p$ equals $\tfrac{1}{p}\textstyle\binom{2p}k$ when $k$ is not divisible by $p$ and equals $1$ when either $k=0$ or $k=2p$ (as we would expect). Additionally, the total number of subsets over all sizes is $4 + \tfrac{4^p-4}{p}$, found by setting $y = 1$ above.

Let $f(x, y)$ be \[(1+xy)(1+x^2y)\cdots (1+x^{2p}y).\] Then we desire the sum of the coefficients of terms of the form $x^{pk}y^p$, where $k$ is a positive integer. To get this value, we apply the roots of unity filter twice. Let $\omega = e^{\tfrac{2\pi i}{p}}$. Note that the sum of the coefficients of $y^0, y^p, y^{2p}$ is \[\frac{\sum_{k=0}^{p-1} f(x, \omega^k)}{p}.\] Then the coefficients of $y^0$ and $y^{2p}$ are clearly $1$ and $x^{p(2p+1)}$, so the coeffient of $y^p$ is \[\frac{\sum_{k=0}^{p-1} f(x, \omega^k)}{p} - x^{p(2p+1)} - 1.\] To find the sum of the coefficients of $x$ raised to a power of a multiple of $p$, we once again apply the roots of unity filter. We desire the value of \begin{align*} \frac{\sum_{m=0}^{p-1} \left(\frac{\sum_{k=0}^{p-1} f(\omega^m, \omega^k)}{p} - (\omega^m)^{p(2p+1)} - 1\right)}{p} & = \frac{ \frac{\sum_{m=0}^{p-1} \sum_{k=0}^{p-1} f(\omega^m, \omega^k)}{p} - p(\omega^m)^{p(2p+1)} - p}{p}\\ & = \frac{\frac{\sum_{m=0}^{p-1} \sum_{k=0}^{p-1} f(\omega^m, \omega^k)}{p} - p - p}{p}\\ & = \frac{\sum_{m=0}^{p-1} \sum_{k=0}^{p-1} (1 + \omega^m\omega^k)(1 + \omega^{2m}\omega^k)\cdots(1 + \omega^{2pm}\omega^k) - 2p^2}{p^2}. \end{align*} It's easy to see that the two sets \[\{m+k, 2m+k, \cdots, pm+k\}\] and \[\{(p+1)m+k, (p+2)m+k, \cdots, 2pm+k\}\] are equal to the set $\{0, 1, \cdots, p-1\}$ of residues modulo $p$ when $m$ is not equal to $0$. When $m=0$, this set is just the number $k$ repeated $p$ times. Therefore, \begin{align*} &\text{ }\sum_{m=0}^{p-1} \sum_{k=0}^{p-1} (1 + \omega^m\omega^k)(1 + \omega^{2m}\omega^k)\cdots(1 + \omega^{2pm}\omega^k)\\ = &\text{ }\sum_{k=0}^{p-1} (1+\omega^k)^{2p} + p(p-1) \cdot \left((1 + 1)(1 + \omega)\cdots(1 + \omega^{p-1})\right)^2. \end{align*} Then we note that, by expanding using the binomial theorem and summing, we get that \[\sum_{k=0}^{p-1} (1+\omega^k)^{2p} = p\cdot\binom{p}{0} + p\binom{2p}{p} + p\binom{p}{p} \omega^{kp} = p\left(\binom{2p}{p} + 2\right).\] Moreover, since the polynomial \[Q(x) = x^p-1\] factors as \[(x-1)(x-\omega)(x-\omega^2)\cdots (x-\omega^{p-1}),\] we get that \[(1 + 1)(1 + \omega)\cdots(1 + \omega^{p-1}) = (-1)^pQ(-1) = 2\] so that \[p(p-1) \cdot \left((1 + 1)(1 + \omega)\cdots(1 + \omega^{p-1})\right)^2 = 4p(p-1).\] Therefore, we have \[\sum_{m=0}^{p-1} \sum_{k=0}^{p-1} (1 + \omega^m\omega^k)(1 + \omega^{2m}\omega^k)\cdots(1 + \omega^{2pm}\omega^k) = p\left(\binom{2p}{p} + 2\right) + 4p(p-1)\] so our answer is \begin{align*} \frac{\sum_{m=0}^{p-1} \sum_{k=0}^{p-1} (1 + \omega^m\omega^k)(1 + \omega^{2m}\omega^k)\cdots(1 + \omega^{2pm}\omega^k) - 2p^2}{p^2} & = \frac{p\left(\binom{2p}{p} + 2\right) + 4p(p-1) - 2p^2}{p^2}\\ & = \boxed{\frac{1}{p}\left(\binom{2p}{p} - 2\right) + 2} \end{align*}

The answer is $\frac{1}{p}\left(\binom{2p}{p}-2\right)+2$. We will instead find the number of subsets $A$ such that $p$ divides $|A|$ and the sum of the elements of $A$ is also divisible by $p$. Note that this is just the answer plus two (for the empty set and $A=\{1,\ldots,2p\}$). Consider the generating function $$F(x,y)=(1+x^1y)(1+x^2y)\ldots (1+x^{2p}y),$$so the coefficient of $x^ay^b$ represents the number of subsets with sum $a$ and $b$ elements. Then by a roots of unity filter we wish to find $$\frac{1}{p^2}\sum_{i=0}^{p-1}\sum_{j=0}^{p-1}F(z^i,z^j),$$where $z$ is a primitive $p$th root of unity. Note that if $p \nmid i$, then $$F(z^i,z^j)=(1+z^{1i+j})\ldots(1+z^{2pi+j})=(1+z^0)^2(1+z^1)^2\ldots(1+z^{p-1})^2.$$Since $(x-z^0)\ldots(x-z^{p-1})=x^p-1$ and $p$ is odd, the last product on the above line is equal to $(1^p+1)^2=4$. Thus we can write $$\frac{1}{p^2}\sum_{i=0}^{p-1}\sum_{j=0}^{p-1}F(z^i,z^j)=\frac{1}{p^2}\left(4p(p-1)+\sum_{j=0}^{p-1}F(1,z^j)\right)=\frac{1}{p^2}\left(4p(p-1)+\sum_{j=0}^{p-1}(1+z^j)^{2p}\right).$$To find the value of the inner summation, consider the sum of the $x^{kp}$ coefficients of $(1+x)^{2p}$, which by another roots of unity filter is simply $\frac{1}{p}\sum_{j=0}^{p-1}(1+z^j)^{2p}$. On the other hand by direct computation this quantity is equal to $\binom{2p}{p}+2$, so it follows that $$\frac{1}{p^2}\left(4p(p-1)+\sum_{j=0}^{p-1}(1+z^j)^{2p}\right)=\frac{1}{p^2}\left(4p(p-1)+p\left(\binom{2p}{p}+2\right)\right)=\frac{1}{p}\left(4p-4+\binom{2p}{p}+2\right)=\frac{1}{p}\left(\binom{2p}{p}-2\right)+4.$$Subtracting $2$ yields the desired answer. $\blacksquare$

This problem took me so long. The idea is to partition $\{1, 2, \dots, 2p\} = \{1, 2, \dots, p\} \cup \{p + 1, p + 2, \dots, 2p\} = A \cup B$. $\bold{Lemma}:$ $\binom{2p}{p} = \sum_{k = 0}^{p} \binom{p}{k} \binom{p}{p - k} = 2 + \sum_{k = 1}^{p - 1} \binom{p}{k} \binom{p}{p - k}$.

Consider the set $A_{\ell} = \{a_1 + \ell, a_2 + \ell, \dots, a_k + \ell\}$ for $k \neq p$ integers $a_1, a_2, \dots, a_k \in A$. Then we make the trivial but important observation that we have that the sequence $A_0, A_1, \dots A_{p - 1}$ form a complete set of residues modulo $p$. Hence if we were to count say, the number of subsets of $k$ elements for which they are $0 \pmod p$, there would be $\frac{1}{p} \binom{p}{k}$ such subsets. (For every $p$ subsets, there is only but one with sum divisible by $p$). Consider then the set $B_{\ell'} = \{b_1 + \ell', b_2 + \ell', \dots, b_k + \ell'\}$ for $k \neq p$ integers $b_1, b_2, \dots, b_k \in B$. Similarly, this sequence of sets forms a complete set of residues modulo $p$. Now if the set $A_i \equiv x \pmod p$, then we may find a suitable $B_j$ so that $B_j \equiv p - x \pmod p$, as both of the sequences $A_i$ and $B_j$ form a complete residue class modulo $p$. Thus there are $p \left (\frac{1}{p} \binom{p}{k} \frac{1}{p} \binom{p}{p - k} \right) = \frac{1}{p} \binom{p}{k} \binom{p}{p - k}$ ways to choose these sets. Summing over all $k$ gives us $\frac{1}{p} \left(\binom{2p}{p} - 2 \right)$. Now we also have the original sets $A$ and $B$. (Both of these sets have the property pertaining to them that the sum of their elements is divisible by $p$ and contain $p$ elements). Hence the total number of such $p$ element subsets becomes $\boxed{2 + \frac{1}{p} \left(\binom{2p}{p} - 2 \right)}$. $\blacksquare$

Here's a somewhat shorter solution. Consider the generating function $$F(k) = \prod_{i=1}^{2p} (1+k^i X)$$for which the coefficient of the $X^a k^b$ term denotes the number of $a$-element subsets with sum $B$. It suffices to find the coefficient of the $X^p$ term in this expansion for $a$ a multiple of $p$, which is given via roots of unity filter by $$\sum_{\omega^p = 1} f(\omega) = f(1) + \sum_{\omega^p =1, \omega \neq 1} f(\omega).$$Notice that $f(1) ={2p \choose p}$, and $f(\omega)$ for any arbitrary $p$th root of unity (necessarily primitive) denotes the coefficient of $X^p$ in $$\prod_{i=1}^{2p}(1+\omega^i X) = (-1)^{2p} \prod_{i=1}^{2p} (-1-\omega^i X) = (-1-X^p)^2 = (1+X^p)^2,$$which is just 2. Thus, the answer is $$\frac{{2p \choose p} + 2(p-1)}p = \frac{{2p \choose p} - 2}p + 2$$subsets.

Consider the generating function \[ F(x,y) = \prod_{i=0}^{2p}(1+x^iy).\]It suffices to find the sum of coefficients of all terms where the power of $x$ is a multiple of $p$ and the power of $y$ is equal to $p$. Let $\omega = e^{\frac{2\pi i}{p}}.$ Using roots of unity filter, the sum of coefficients of all terms where the power of $x$ is a multiple of $P$ is \[ \frac1p\sum_{i=0}^{p-1} F(\omega^i, y). \]The term when $y=0$ is equal to $(1+y)^{2p}$, for which the $y^p$ coefficient is $\binom{2p}p$. All other terms in this summation are equivalent to \[ \left(\prod_{i=0}^{p-1}(1+\omega^iy)\right)^2.\]The inside product is equivalent to evaluating the function with roots $\omega^iy$ (namely $x^p+y^p$) at $1$, hence the entire term is equal to $(1+y^p)^2$, with a $y^p$ coefficient of $2$. Since there are $p-1$ such terms, the total contribution is $2(p-1)$. Our desired answer is the sum of the $y^p$ coefficients in the filter summation, which is equal to \[ \frac1p\left(\binom{2p}p+2(p-1)\right).\]

Consider \[ \prod_{k=1}^{2p}(1+y^kx)=\cdots+f(y)x^p+\cdots.\tag{1} \]Let $a_i$ denote the number of $p$-element subsets of $\{1,2,\ldots,2p\}$ which has the sum of elements equal to $i$. It follows that \[ \sum_{n=0}^\infty a_ny^n=f(y). \]We also have \[ \sum_{p\mid n}a_n=\frac{f(1)+f(\omega)+f(\omega^2)+\cdots+f(\omega^{p-1})}{p} \]where $\omega=e^\frac{2\pi i}{k}$. Plugging $y=1$ into (1) gives $(1+x)^{2p}=\cdots+f(1)x^p+\cdots$. By the binomial theorem, the coefficient of the $x^p$ term of $(1+x)^{2p}$ is $\binom{2p}{p}$. Now, for $1\leq j\leq p-1$, we have \begin{align*} \cdots+f(\omega^j)x^p+\cdots&=\prod_{k=1}^{2p}(1+\omega^{jk}x)\\ &=\prod_{k=1}^{2p}(1+\omega^kx)\\ &=\left(\prod_{k=1}^{p}(1+\omega^kx)\right)^2\\ &=(x^p+1)^2\\ &=x^{2p}+2x^p+1 \end{align*}so $f(\omega^j)=2$. Thus we have \[ \sum_{p\mid n}a_n=\frac{2(p-1)+\binom{2p}{p}}{p}.\text{ }\square \]

Ha! The answer confirmation's so simple I knew there had to be a combinatorial way! So I'm not going to post some rouf solution. By intuition we feel like our answer would be close to 1/p(2pCp) since it's around that expected value 1 in p subsets to be divisible by p; but since there are TWO elements same mod p, it kind of messes things up, while one distinct of each would help greatly. So we partition the sets into $\{1, 2, \dots, 2p\} = \{1, 2, \dots, p\} \cup \{p + 1, p + 2, \dots, 2p\} = M\cup N$; now, consider $M_k=\{m_1+k,m_2+k,...,m_m+k\}\forall k\ne p,m_1,m_2,...,m_m\in M$; do the similar thing for N. There are $p \left (\frac{1}{p} \binom{p}{k} \frac{1}{p} \binom{p}{p - k} \right) = \frac{1}{p} \binom{p}{k} \binom{p}{p - k}$ ways to choose some $N_i\equiv p-M_j\pmod p$; in particular, summing over all possible k simplifies to $\frac{1}{p} \left(\binom{2p}{p} - 2 \right)$; but since we also need to add set M and N, there are $2 + \frac{1}{p} \left(\binom{2p}{p} - 2 \right)$ many ways as our final answer. $\blacksquare$

Goofy gen func rouf Consider a generating function $$F(x,y) = (1+xy)(1+x^2y)(1+x^3y)\dots (1+x^{2p}y)$$This generating function describes the subsets, where the exponent of $x$ is the sum of the elements and the exponent of $y$ is the size. Therefore, we want the sum of the coefficients of $x^{kp}y^p$ for positive integers $k$. We now apply a Roots of Unity Filter. The generating function containing only the terms $x^{kp}$ can be obtained by taking \[ \frac{1}{p}\sum_{k=0}^{p-1}F(e^{\frac{ik\pi}{p}}x,y) \]and we want the sum of the terms with exponent $y^p$ when evaluated at $x=1$. We write \[ (1+xy)(1+x^2y)\dots (1+x^{2p}y) = y^{2p}\left(-\frac1y-x\right)\left(-\frac1y-x^2\right)\left(-\frac1y-x^3\right)\dots \left(-\frac1y-x^{2p}\right) \]Let $P_x(t)$ be a monic polynomial in $t$ with roots $x^i$ for $i=1,2,\dots 2p$. When $x\neq 1$ is a $p^\text{th}$ root of unity, $P_x(t) = (t^p-1)^2$ Then, we find that $$F(x,y) = y^{2p}P_x\left(-\frac1y\right)$$Plugging in $x=1$, we calculate that \begin{align*} [y^p]\frac{1}{p}\sum_{k=0}^{p-1}F(e^{\frac{ik\pi}{p}},y) &= [y^p]\frac{y^{2p}}{p}P_{e^\frac{ik\pi}{p}}\left(-\frac1y\right)\\ &= [y^p]\frac{y^{2p}}{p}\left((p-1)\left(\frac{-1}{y^p}-1\right)^2+\left(1+\frac{1}{y}\right)^{2p}\right)\\ &= [y^p]\frac{1}{p}\left((p-1)(y^p+1)^2 + (y+1)^{2p}\right)\\ &= \boxed{\frac{1}{p}\left(2(p-1)+\binom{2p}{p}\right)} \end{align*}

Let $A(x,y)$ be the generating function \[A(x,y) = (1+yx)(1+yx^2)\cdots(1+yx^{2p})\]We apply the roots of unity filter on $x$ to get \[\frac{A(1,y)+A(w,y)+\cdots+A(w^{p-1},y)}{p} = \frac{(1+y)^{2p}+(p-1)(1+yw)\cdots(1+yw^{2p})}{p}\]We call this function on $y$, $B(y)$. Note that \[(1+w)(1+w^2)\cdots(1+w^{p}) = 2\]Then, we apply the roots of unity filter on $y$ to get \begin{align*} \frac{B(1)+B(w)+B(w^2)+\cdots B(w^{p-1})}{p} &= \frac{p+p\binom{2p}{p}+p+2^{2}(p-1)(p)}{p^2} \end{align*}But, we need to subtract $2$ because it counts the empty set and the set with size $2p$. This gives us \[\boxed{\frac{\binom{2p}{p}+2p-2}{p}}\]

Let $F(x,y)=\prod_{i=1}^{2p}(1+yx^i)$ be the gen func representing sums of subsets and their number of elements. Note that the answer is equal to \[\frac{1}{p^2}\left(\sum_{k=1}^p \sum_{k=1}^p F\left(e^{2\pi ij/p},e^{2\pi i k/p}\right)\right)-2\]by roots of unity filter, with the $-2$ coming from the empty set and $\{1,2,\dots,2p\}$ being included in this count. We thus compute this!!! First, if $j=1,2,\dots,p-1$, then the sequence $j,2j,\dots, 2pj$ contains each residue modulo $p$ twice. Thus $j+k,2j+k,\dots, 2pj+k$ contains each residue twice. herefore, \[\sum_{k=1}^{p}F\left(e^{2\pi ij/p},e^{2\pi i k/p}\right)=p\prod_{k=1}^p \left(1+e^{2\pi i k/p}\right)^2=4p\]As \[\prod_{k=1}^p \left(1+e^{2\pi i k/p}\right)^2=\prod_{k=1}^p \left(-1-e^{2\pi i k/p}\right)^2=P(-1)^2=4\]in $P(x)=x^p-1$. If $j=p$, then \[\sum_{k=1}^{p}F\left(1,e^{2\pi i k/p}\right)=p\sum_{k=1}^{p}F\left(1+e^{2\pi i k/p}\right)^{2p}\]By roots of unity filter on $(1+x)^{2p}$, we get that the above sum is $p\left(2+\binom{2p}{p}\right).$ Thus the total sum ignoring the division by $p^2$ and subtraction is \[p\left(2+\binom{2p}{p}\right)+4p(p-1)=p\binom{2p}{p}+4p^2-2p\]implying a final answer of \[\frac{p\binom{2p}{p}+4p^2-2p}{p^2}-2=\frac{\binom{2p}{p}-2}{p}+2.\] Remark: N6 is crazy lol

We will create a generating function $f(x, y)$, where the coefficient $c_{i, j}$ of $x^i y^j$ represents the number of subsets $A \subseteq \{1, 2, \dots, 2p \}$ where the sum of the elements of $A$ is $i$, while $|A| = j$. By considering how many numbers we extract from each individual residue class, it is not hard to find that $$f(x, y) = \prod_{n = 0}^{p - 1} (1 + 2x^ny + x^{2n}y^2) = \prod_{n = 0}^{p - 1} (1 + x^ny)^2.$$We will use a double roots of unity filter to add all coefficients $c_{i, j}$ where $p \mid i, j$, then subtract $2$ to account for the cases when $j = 0, 2p$. Let $\omega = e^{2 \pi i / p}$. We want to evaluate $\frac{1}{p^2} \sum_{r = 0}^{p - 1} \sum_{s = 0}^{p - 1} f(\omega^r, \omega^s)$. When $r \ne 0$, $f(\omega^r, \omega^s) = \left[\prod_{n = 0}^{p - 1} (1 + \omega^n) \right]^2 = 2^2 = 4$. All cases belonging to the latter yield a total of $4p(p - 1)$. On the other hand, when $r = 0$, we have $\sum_{s = 0}^{p - 1} f(1, \omega^s) = \sum_{s = 0}^{p - 1} (1 + \omega^s)^{2p}$. Using the binomial theorem, only the terms when the exponent of $\omega$ is divisible by $p$ are left behind, and we obtain $p \left[\binom{2p}{p} + 2 \right]$. Our final answer is $$\frac{4p(p - 1) + p \left[\binom{2p}{p} + 2 \right]}{p^2} - 2 = \frac{\binom{2p}{p} - 2}{p} + 2.$$

I think you only need one filter! We want to find the sum of the coefficients of $x^0y^p,x^py^p,x^{2p}y^p,\dots$ in \[(1 + xy)(1 + x^2y)\dots(1 + x^{2p}y)\text{.}\]First fix $y$. Now let $\omega$ be a primitive $p$-th root of unity, we want the coefficient of $y^p$ in \[\frac{P(1) + P(\omega) + \dots + P(\omega^{p - 1})}{p} = \frac{(1 + y)^{2p} + (p - 1)(1 + y^p)^2}{p}\]so the answer is \[\frac1p\left(\binom{2p}{p} - 2\right) + 2\text{.}\]

$ $

niceee Let $A(x, y) = (1+xy)(1+x^2y)(\cdots)(1+x^{2p}y).$ Clearly, we want the sum of the coefficients of the terms with $x$ of degree divisible by $p$ and $y$ having degree $p.$ Let $z=e^{2\pi i/p}.$ Then by Roots of Unity Filter we have $$\frac{1}{p} \sum^{p-1}_{k=0}A(z^k, y).$$However, for $k = 1, 2, \cdots, p-1,$ clearly the set $\{1, z, z^2, \cdots z^{p-1}\}$ is a permutation of $\{ z^k, z^{2k}, \cdots z^{pk} \},$ so $$A(z^k, y) = \left( \prod_{k=0}^{p-1} (1+z^ky) \right)^2 = \left( y^{2p} \prod_{k=0}^{p-1} (\frac{1}{y}+z^k) \right)^2 = y^{2p} \cdot \left( -\frac{1}{y^p}-1 \right)^2 = (y^p+1)^2.$$Hence, our sum equals $$\frac{1}{p} \left((p-1)(y^p+1)^2+(y+1)^{2p} \right).$$Now, we simply extract the coefficient of $y^p$ from here, and this is just $$\boxed{\frac{2p-2+\binom{2p}{p}}{p}}.$$

Here's the other genfunc solution. Let $\textstyle\binom{n}{k}_q$ be the $q$-binomial coefficient and $\textstyle [n]_q=1+q+\dots+q^{n-1}=\frac{1-q^n}{1-q}$. Then it is well-known that \[\sum_{\substack{S\subseteq\{1,2,\dots,2p\}\\|S|=p}}q^{\sum S}=q^{p(2p+1)}\binom{2p}{p}_q.\] Let $\omega$ be a primitive $p$th root of unity. Then we have \[\binom{2p}{p}_q=\frac{[2p]_q[2p-1]_q\dots[p+1]_q}{[p]_q[p-1]_q\dots[1]_q}=(1+q^p)\frac{[2p-1]_q\dots[p+1]_q}{[p-1]_q\dots[1]_q}.\]As we let $q\rightarrow\omega$, then the product cancels out, so we have $\textstyle\binom{2p}{p}_\omega=1+\omega^p=2$. Hence by roots of unity filter, the desired result is $\textstyle\frac{1}{p}\sum_{i=0}^{n-1}\binom{n}{k}_{\omega^i}=\frac{\binom{2p}{p}-2}{p}+2$, since $\omega^0=1$ and all other powers are primitive $p$th roots of unity.