AoPS Academy
.
different from 
and 
denote 
,
.
form a group of 
sets where all the residues appear. (The set 
)
at the polynomial
.
and 
as a representant system for 
, since not more is necessary (so all identities concerning or must be seen 
).
and 
define 
and similar for a subset 
. trivial iff 
or 
, similar for again.
subsets 
such that both 
and 
are trivial, so call these subsets trival from now on too. a 'translation': is nontrivial define 
and 
otherwise.
goes through all possible residue classes, that also the sum of the elements of 
goes through all of them, so there is exactly one sum that is divisible by 
. sets each, all sets of the same class having same number of elements.
subsets of the desired order and 
of them are trivial, we get that there are 
such subsets.
)
)!
, the 
-th factor refering to whether is present in the set or not.
will refer to the set having 
elements and sum of elements , so we need to compute the sum of coefficients of 
of 
to find the answer.
and substract 2, since there are two terms for 
:
. we use Multisection formula that says us that it equals
(
is th root of unity).
is not 
, 
(every 
will be written twice as 
). This equals 
(
is the polynomial with roots ). Since there are 
choices for , choices for 
we get 
.
, 
. To evaluate 
, note that it equals times the coefficients of 
in the polynomial 
by the same multisection formula, so it equals 
.
.
is a 
th root of unity then 
if 
and 
if 
. By using this result, we can prove the Multisection Formula (which holds also for polynomials of more variables) :
, then 
. Particularly
be the p-th root of unity.![\[ \prod_{k=1}^{2p} (x - w^k) = (x^p - 1)^2 = x^{2p} - 2x^p + 1. \]](http://latex.artofproblemsolving.com/5/1/4/514ceb2104b6145851a3884b2b6807282dcc339f.png)
![\[ t(w) = \sum_{1 \leq j_1 < j_2 < \ldots < j_p \leq 2p} w^{j_1}w^{j_2} \ldots w^{j_p}. \]](http://latex.artofproblemsolving.com/4/9/1/4916f7bd648286d8c29e84876f25b422eb5618a8.png)
. Besides, if we write 
, then 
represents the number of sub-sets 
of 
such that 
, and we can write :![\[ (a_0 - 2) + a_1w + \ldots + a_{p-1}w^{p-1} = 0. \]](http://latex.artofproblemsolving.com/4/7/7/477e6bb023ed7cfb7114a984eb26efad7335d973.png)
on ![$\mathbb{Q}[X]$](http://latex.artofproblemsolving.com/f/3/d/f3dc4b61f66a97c235268da5643f5bebbc69c9bd.png)
is 
, it follows that :![\[ a_0 - 2 = a_1 = a_2 = \ldots = a_{p-1}. \]](http://latex.artofproblemsolving.com/1/6/c/16c0afd9a753f9e9b4fcf134daca0f2aa2659877.png)
, we conclude immediately that :![\[ a_0 = \frac 1p \left\{\binom {2p}{p} - 2 \right \} + 2. \]](http://latex.artofproblemsolving.com/0/a/6/0a61ad8cfe65a9a2e50d89a566bbbf1b8b9ade1a.png)
be the p-th root of unity.. Besides, if we write , then represents the number of sub-sets of such that , and we can write : on is , it follows that :, we conclude immediately that :
with 
?
is the initial set, then the number of subsets with elements such that each sum of these subsets' elements is divisible by is
where 
is the Euler totient function.
is the initial set, then the number of subsets with elements such that each sum of these subsets' elements is divisible by iswhere is the Euler totient function.
where 
Clearly, it suffices to find sum of coefficients in the terms of the form 
So let 
be n-th primitive root of unity. By roots of unity filter it is sufficient to find the sum of coefficients in front of 
in 
Now, 
Now if we denote 
then 
is 
-th primitive root of unity. Hence 
Now it is clear that sequence 
passes through all divisors of and only through them. In the spirit of this, we have:
of the following has 
solutions in 
i.e 
which, since 
has solutions.
in 
then: 
Coefficient in front of is thus 
This holds for any divisor of and it appears for times, from Lemma. Hence, the answer is 
and 
. As usual 
denotes the sum of elements of set 
.-element sets 
, 
, such that 
, for a fixed 
is 
.. We will establish the desired bijection. Suppose . Then to each element of 
add a fixed constant 
so that 
. Here addition is defined in modulo . Anyway,we can choose so that 
is any desired residue mod . There are 
subsets in total. By our bijection between all residues we get subsets with .-element subsets with sum divisible by .
, then we choose all of 
. If we choose all of , then choose nothing from .
elements from . There are 
ways to do this. Then choose 
elements from with a fixed sum mod . There are 
ways to do so.
The last equality follows from the identity 
which can be proved by double counting the number of ways to choose elements from a 
-element set. So we are done.
, note that it equals times the coefficients of in the polynomial by the same multisection formula, so it equals .
, as you forgot to consider the first and last terms.
elements).![\[
f(x,y) = (1+xy)(1+x^2y)\cdots(1+x^{2p}y),
\]](http://latex.artofproblemsolving.com/f/8/b/f8b0f56ba29164ae695d1059f5a96c627998cad5.png)
and let 
be a primitive 
root of unity. We will consider this as a generating function in 
first, run the roots of unity computation, and read the result as a generating function in 
. Indeed, observe that 
while
Therefore the sum of all coefficients of associated to powers of is![\[
\frac{1}{p}\sum_{k=0}^{p-1}f(\zeta^k,y) = \frac{(p-1)(y^p + 1)^2 + (y+1)^{2p}}p.
\]](http://latex.artofproblemsolving.com/7/5/a/75a6e982b2662c42017cc9636dc6988aefba741e.png)
From this, we can read off the answer as the coefficient of 
in the above expression, or 
. whose sum of elements is divisible by equals 
when is not divisible by and equals when either 
or 
(as we would expect). Additionally, the total number of subsets over all sizes is 
, found by setting 
above.
be![\[(1+xy)(1+x^2y)\cdots (1+x^{2p}y).\]](http://latex.artofproblemsolving.com/8/9/6/896135e48c92a884c44076eb710724a50f7deb77.png)
, where is a positive integer.
. Note that the sum of the coefficients of 
is![\[\frac{\sum_{k=0}^{p-1} f(x, \omega^k)}{p}.\]](http://latex.artofproblemsolving.com/2/c/0/2c0e2a258ad4b28b2c721a6632591b802c87fd51.png)
and 
are clearly and 
, so the coeffient of is![\[\frac{\sum_{k=0}^{p-1} f(x, \omega^k)}{p} - x^{p(2p+1)} - 1.\]](http://latex.artofproblemsolving.com/a/8/5/a857f5542b6ea95656ce2b1de8dc5607708bcb80.png)
raised to a power of a multiple of , we once again apply the roots of unity filter. We desire the value of
![\[\{m+k, 2m+k, \cdots, pm+k\}\]](http://latex.artofproblemsolving.com/2/a/7/2a723ff19da833cbd8b30666d983dd1de0078a48.png)
![\[\{(p+1)m+k, (p+2)m+k, \cdots, 2pm+k\}\]](http://latex.artofproblemsolving.com/b/4/e/b4e1df91449b16c9eb436813fb2e2b4d9c730009.png)
of residues modulo when 
is not equal to 
. When 
, this set is just the number repeated times. Therefore,
![\[\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).\]](http://latex.artofproblemsolving.com/3/1/7/317376f911921bb1103b9d0d527b342ad3b78d8e.png)
![\[Q(x) = x^p-1\]](http://latex.artofproblemsolving.com/5/0/4/504483cbaa174678534c20cbe3dd2aaf798e83ca.png)
![\[(x-1)(x-\omega)(x-\omega^2)\cdots (x-\omega^{p-1}),\]](http://latex.artofproblemsolving.com/7/b/4/7b45946b33f4ac9434486e9ece739cab929e6c64.png)
![\[(1 + 1)(1 + \omega)\cdots(1 + \omega^{p-1}) = (-1)^pQ(-1) = 2\]](http://latex.artofproblemsolving.com/a/f/1/af1f9c320d533ceac0899cd1fd325163162e2612.png)
![\[p(p-1) \cdot \left((1 + 1)(1 + \omega)\cdots(1 + \omega^{p-1})\right)^2 = 4p(p-1).\]](http://latex.artofproblemsolving.com/f/9/4/f94f4c1771bd0892d11eebc7398dd99dc8a26a9f.png)
![\[\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)\]](http://latex.artofproblemsolving.com/5/f/5/5f533cd333a09eec14ea11a80661bd4e9af5ab6f.png)
. We will instead find the number of subsets such that divides 
and the sum of the elements of is also divisible by . Note that this is just the answer plus two (for the empty set and 
).
so the coefficient of 
represents the number of subsets with sum 
and 
elements. Then by a roots of unity filter we wish to find
where is a primitive th root of unity.
, then
Since 
and is odd, the last product on the above line is equal to 
. Thus we can write
To find the value of the inner summation, consider the sum of the 
coefficients of , which by another roots of unity filter is simply 
.
, so it follows that
Subtracting yields the desired answer. 
.
.
for 
integers 
. Then we make the trivial but important observation that we have that the sequence 
form a complete set of residues modulo . Hence if we were to count say, the number of subsets of elements for which they are 
, there would be such subsets. (For every subsets, there is only but one with sum divisible by ).
for integers 
. Similarly, this sequence of sets forms a complete set of residues modulo .
, then we may find a suitable 
so that 
, as both of the sequences 
and form a complete residue class modulo . Thus there are 
ways to choose these sets. Summing over all gives us 
. and . (Both of these sets have the property pertaining to them that the sum of their elements is divisible by and contain elements). Hence the total number of such element subsets becomes 
. 
for which the coefficient of the 
term denotes the number of -element subsets with sum . It suffices to find the coefficient of the 
term in this expansion for a multiple of , which is given via roots of unity filter by 
Notice that 
, and 
for any arbitrary th root of unity (necessarily primitive) denotes the coefficient of in 
which is just 2.
subsets.
![\[ F(x,y) = \prod_{i=0}^{2p}(1+x^iy).\]](http://latex.artofproblemsolving.com/c/7/a/c7a504e86e64af55143c1085048e6e314c21e0ac.png)
It suffices to find the sum of coefficients of all terms where the power of is a multiple of and the power of is equal to . Let 
Using roots of unity filter, the sum of coefficients of all terms where the power of is a multiple of 
is ![\[ \frac1p\sum_{i=0}^{p-1} F(\omega^i, y). \]](http://latex.artofproblemsolving.com/a/e/d/aedc9eed9957102d83c62de1e84595940be868a1.png)
The term when 
is equal to 
, for which the coefficient is 
. All other terms in this summation are equivalent to ![\[ \left(\prod_{i=0}^{p-1}(1+\omega^iy)\right)^2.\]](http://latex.artofproblemsolving.com/b/f/3/bf3498b0c2f00dcf181d173d889a60fc685a6afb.png)
The inside product is equivalent to evaluating the function with roots 
(namely 
) at , hence the entire term is equal to 
, with a coefficient of . Since there are such terms, the total contribution is 
. coefficients in the filter summation, which is equal to ![\[ \frac1p\left(\binom{2p}p+2(p-1)\right).\]](http://latex.artofproblemsolving.com/3/5/4/3546dde2aec63873d6cecc2efcff64198d5df49d.png)
![\[
\prod_{k=1}^{2p}(1+y^kx)=\cdots+f(y)x^p+\cdots.\tag{1}
\]](http://latex.artofproblemsolving.com/0/3/0/030a36e9e9fdb33c2b49b7626aa5e550022fd9b5.png)
Let 
denote the number of -element subsets of 
which has the sum of elements equal to . It follows that![\[
\sum_{n=0}^\infty a_ny^n=f(y).
\]](http://latex.artofproblemsolving.com/a/c/a/aca0f3065e3b7050f1664b8415ce2b7df5171247.png)
We also have![\[
\sum_{p\mid n}a_n=\frac{f(1)+f(\omega)+f(\omega^2)+\cdots+f(\omega^{p-1})}{p}
\]](http://latex.artofproblemsolving.com/0/5/0/0504705e49bcc5266c831b127746a52213fed3d7.png)
where 
. Plugging 
into (1) gives 
. By the binomial theorem, the coefficient of the term of is . Now, for 
, we have
so 
. Thus we have![\[
\sum_{p\mid n}a_n=\frac{2(p-1)+\binom{2p}{p}}{p}.\text{ }\square
\]](http://latex.artofproblemsolving.com/3/a/0/3a0282628478e2e287f575b5e8b762496b625a15.png)
; now, consider 
; do the similar thing for N. There are ways to choose some 
; in particular, summing over all possible k simplifies to ; but since we also need to add set M and N, there are 
many ways as our final answer. 
This generating function describes the subsets, where the exponent of is the sum of the elements and the exponent of is the size. Therefore, we want the sum of the coefficients of for positive integers . can be obtained by taking![\[
\frac{1}{p}\sum_{k=0}^{p-1}F(e^{\frac{ik\pi}{p}}x,y)
\]](http://latex.artofproblemsolving.com/6/3/7/63702db9b6e1eb30f1ee8432a61a855a3ffa6527.png)
and we want the sum of the terms with exponent when evaluated at 
. 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)
\]](http://latex.artofproblemsolving.com/8/b/8/8b85cd51b7d0bf328ec08413b372f5987c01b367.png)
Let 
be a monic polynomial in 
with roots 
for 
. When 
is a 
root of unity, 
Then, we find that 
Plugging in , 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*}](http://latex.artofproblemsolving.com/d/6/4/d640fd0e3948d6a87a9d1939c9796da2f2b398c7.png)
be the generating function![\[A(x,y) = (1+yx)(1+yx^2)\cdots(1+yx^{2p})\]](http://latex.artofproblemsolving.com/b/d/f/bdf5cfe2bc04baf7120b03bb18c52730d186d298.png)
We apply the roots of unity filter on 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}\]](http://latex.artofproblemsolving.com/b/9/0/b903e0b56df1f816fba4596940a00ea9c79958e0.png)
We call this function on , 
. Note that![\[(1+w)(1+w^2)\cdots(1+w^{p}) = 2\]](http://latex.artofproblemsolving.com/6/8/f/68f575ac21f319726af7523c916ec5030805d087.png)
Then, we apply the roots of unity filter on to get
But, we need to subtract because it counts the empty set and the set with size . This gives us![\[\boxed{\frac{\binom{2p}{p}+2p-2}{p}}\]](http://latex.artofproblemsolving.com/a/a/a/aaa2ab1d061116b992fd28c87995fa96d6e0c1ae.png)
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\]](http://latex.artofproblemsolving.com/f/9/0/f903b605f56e1e273b57b145db1c5487b9967e0c.png)
by roots of unity filter, with the 
coming from the empty set and 
being included in this count. We thus compute this!!!
, then the sequence 
contains each residue modulo twice. Thus 
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\]](http://latex.artofproblemsolving.com/4/c/7/4c759021b9297fefe18507982a97525826566ddb.png)
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\]](http://latex.artofproblemsolving.com/c/9/5/c95e2e8afe5907de7c9b3662c0cbe1c60f8c0a5a.png)
in 
.
, 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}\]](http://latex.artofproblemsolving.com/5/2/0/52024dcfda263149c0075c91ced7c0a2a0d2bcd8.png)
By roots of unity filter on , we get that the above sum is 
and subtraction is ![\[p\left(2+\binom{2p}{p}\right)+4p(p-1)=p\binom{2p}{p}+4p^2-2p\]](http://latex.artofproblemsolving.com/a/4/e/a4e02317bd4fced962dbea9b5b3827533939c211.png)
implying a final answer of ![\[\frac{p\binom{2p}{p}+4p^2-2p}{p^2}-2=\frac{\binom{2p}{p}-2}{p}+2.\]](http://latex.artofproblemsolving.com/9/a/e/9aeebc397d6079b6d99eb4bcd17e36a026494d9c.png)
, where the coefficient 
of 
represents the number of subsets 
where the sum of the elements of is , while 
. By considering how many numbers we extract from each individual residue class, it is not hard to find that
We will use a double roots of unity filter to add all coefficients where 
, then subtract to account for the cases when 
. Let 
. We want to evaluate 
. When 
, ![$f(\omega^r, \omega^s) = \left[\prod_{n = 0}^{p - 1} (1 + \omega^n) \right]^2 = 2^2 = 4$](http://latex.artofproblemsolving.com/5/6/a/56a8f587a16aeb65531a587c4bc5fdfe87932fc6.png)
. All cases belonging to the latter yield a total of 
. On the other hand, when 
, we have 
. Using the binomial theorem, only the terms when the exponent of is divisible by are left behind, and we obtain ![$p \left[\binom{2p}{p} + 2 \right]$](http://latex.artofproblemsolving.com/7/0/5/705721ab0d12b9a41156dd3b7ce25b987d396bdb.png)
. 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.$$](http://latex.artofproblemsolving.com/5/d/9/5d95834d490288f96883adc477d9da869f33e637.png)
in![\[(1 + xy)(1 + x^2y)\dots(1 + x^{2p}y)\text{.}\]](http://latex.artofproblemsolving.com/9/5/c/95ca0cd879ee7def26093ea4dcd1e8cd3fc61079.png)
First fix . Now let be a primitive -th root of unity, we want the coefficient of in![\[\frac{P(1) + P(\omega) + \dots + P(\omega^{p - 1})}{p} = \frac{(1 + y)^{2p} + (p - 1)(1 + y^p)^2}{p}\]](http://latex.artofproblemsolving.com/d/0/1/d010d9d006c116ec6ee71b5eb4b87d13c9183e61.png)
so the answer is![\[\frac1p\left(\binom{2p}{p} - 2\right) + 2\text{.}\]](http://latex.artofproblemsolving.com/e/d/5/ed5aff0e6db852986173ae9c8850c34ccb245c90.png)
Clearly, we want the sum of the coefficients of the terms with of degree divisible by and having degree 
Let 
Then by Roots of Unity Filter we have 
However, for 
clearly the set 
is a permutation of 
so 
Hence, our sum equals 
Now, we simply extract the coefficient of from here, and this is just 
be the 
-binomial coefficient and ![$\textstyle [n]_q=1+q+\dots+q^{n-1}=\frac{1-q^n}{1-q}$](http://latex.artofproblemsolving.com/f/1/0/f105d25482cfa1f59a3dcc2ea1f503175225de5a.png)
. 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.\]](http://latex.artofproblemsolving.com/c/6/1/c61c578e66e3da00179d1b9ada52854bd5ca76e5.png)
be a primitive 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}.\]](http://latex.artofproblemsolving.com/e/a/a/eaa23fd616fea729c628c01118cc80df074b0d65.png)
As we let 
, then the product cancels out, so we have 
.
, since 
and all other powers are primitive th roots of unity.
![\[P(x,y)=\prod_{n=1}^{2p}(x+y^n).\]](http://latex.artofproblemsolving.com/b/d/e/bdee663a78305829162c0c6d124e719b7ae96de5.png)
Note that if a subset 
has elements that sum to 
, the set will show up in the expansion of as 
.
. By roots of unity filter it suffices to find the coefficient 
of in the expansion of 
. But note that 
is equal to 
if 
and is equal to 
otherwise. Thus ![\[Q(x)=\frac{(x+1)^{2p}+(p-1)(x^p+1)^2}p,\]](http://latex.artofproblemsolving.com/6/6/c/66caef73f88bd8ac0015fda7ff95527d52a4a372.png)
from which extracting yields ![\[c_p=\boxed{\frac{\binom{2p}p+2(p-1)}p},\]](http://latex.artofproblemsolving.com/3/9/1/391193b5a2f254265d086497c0fbce28d93362a1.png)
which is our answer. 
where counts the number of elements we dont use and counts the exponent. We want to be a multiple of , and to be . To extract the first condition, take ROUF with a primitive th root . We get 
. Its obvious by binomial expansion that the answer from here is 
are there, the sum of whose elements is divisible by 
.
.
,
.
whose sum of elements is 
is 
.
.
.
in some order, so exactly one of them will be 
(call such subsets good). Suppose that it has 
elements in 
.
,
is 
is 
.
ways to choose ![\[\sum_{a=0}^{p-1}\frac{1}{p}\binom{p}{k}\frac{1}{p}\binom{p}{p-k}=\frac{1}{p}\binom{p}{k}^2.\]](http://latex.artofproblemsolving.com/1/7/d/17d9f8f8f04eb55cc52def0783ec02f352ddbef1.png)
![\[\sum_{k=1}^{p-1}\frac{1}{p}\binom{p}{k}^2=\frac{1}{p}\left[\sum_{k=0}^{p}\binom{p}{k}^2-\binom{p}{0}^2-\binom{p}{p}^2\right]=\frac{1}{p}\left[\binom{2p}{p}-2\right].\]](http://latex.artofproblemsolving.com/2/9/9/29919ad3c6b4ab26ce8ffbd2bc33cf34964f1ca3.png)
Adding back the two good subsets for 
.
elements from set 
Here, we need to think in two dimensions - that is, we need to have a generating function such that it gives us information on both how many elements participate in the sum and how much their sum is. To do this, we consider the two-variable function
and we are tasked with finding the sum of the coefficients in front of 
for any natural 
should have 
.
We remember that the roots of unity filter provides us with a function for which 
and 
otherwise, and that function is
where 
is the 
t
)
where 
and 
.
which we obtain from the identity
Here comes another roots of unity filter which, upon applying on the sum, solves the second case and we get that
The above means that only terms where 
survive:
or, for the sake of our solution (so subtracting 2 at the end), we obtain that the answer is