Kvant Math Problem 1530
Numbers $1,2,\dots,2p$ split into residue classes modulo $p$ as
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 9m31s
Source on kvant.digital
Problem
Let $p$ be an odd prime number. Find the number of subsets $A$ of the set ${1, 2, \ldots, 2p}$ such that
- $A$ contains exactly $p$ elements;
- the sum of all elements in $A$ is divisible by $p$.
International Mathematical Olympiad of School Students (XXXVI)
Exploration
Numbers $1,2,\dots,2p$ split into residue classes modulo $p$ as
$${1,p+1},{2,p+2},\dots,{p,2p},$$
so each residue class modulo $p$ contains exactly two elements.
A subset $A$ of size $p$ is determined by choosing exactly one or two elements from each pair, with total size constraint forcing a mixture of choices across pairs. The condition on the sum modulo $p$ depends only on residues, so the structure suggests a symmetric counting over the cyclic group $\mathbb{Z}_p$.
A naive expectation is that subsets are evenly distributed among residue classes of the sum, but the fixed size constraint $|A|=p$ introduces correlation, so uniformity fails. A root-of-unity filter or group action on residues is the natural mechanism.
The most delicate step is evaluating the contribution of nontrivial $p$th roots of unity in the generating function; this is where cancellations determine the final constant term.
Problem Understanding
The task is to count subsets $A \subseteq {1,2,\dots,2p}$ such that $|A|=p$ and
$$\sum_{a\in A} a \equiv 0 \pmod p,$$
where $p$ is an odd prime.
This is a Type A classification problem: we must compute an exact count.
The structure is governed by residues modulo $p$, where each residue appears exactly twice. The key difficulty is enforcing simultaneously a fixed subset size and a modular sum constraint.
The final answer will take the form of a closed expression in $p$.
Proof Architecture
Introduce a bivariate generating function tracking both subset size and sum modulo $p$.
Apply the root-of-unity filter to isolate subsets whose sum is divisible by $p$.
Compute the generating function at $z=1$ and at $p-1$ nontrivial $p$th roots of unity.
Evaluate the product $\prod_{r=1}^p (1+y\omega^r)$ using the identity for cyclotomic polynomials, then square it.
Extract the coefficient of $y^p$ in both cases.
Assemble contributions from the root-of-unity filter.
The most delicate lemma is the evaluation
$$\prod_{r=1}^p (1+y\omega^r)=1+y^p,$$
which drives the entire simplification.
Solution
Let $\omega = e^{2\pi i/p}$. For each integer $k \in {1,\dots,p}$, the numbers $k$ and $k+p$ both contribute residue $k \bmod p$. Introduce variables where selecting an element contributes a factor $y z^a$, where $y$ marks cardinality and $z$ marks the element modulo $p$.
The generating function over all subsets is
$$F(y,z)=\prod_{k=1}^p (1+y z^k)^2,$$
since each residue class $k$ contributes two independent choices.
We seek the number of subsets of size $p$ whose sum is divisible by $p$, which equals
$$\frac{1}{p}\sum_{j=0}^{p-1} [y^p] F(y,\omega^j).$$
For $j=0$, we obtain
$$F(y,1)=(1+y)^{2p},$$
so the contribution is
$$y^p^{2p}=\binom{2p}{p}.$$
For $j\neq 0$, multiplication by $j$ permutes the nonzero residues modulo $p$, hence
$$F(y,\omega^j)=\prod_{k=1}^p (1+y\omega^k)^2,$$
independent of $j \neq 0$.
Define
$$G(y)=\prod_{k=1}^p (1+y\omega^k).$$
Using $\prod_{k=1}^p (x-\omega^k)=x^p-1$, substitute $x=-1/y$ to obtain
$$\prod_{k=1}^p \left(-\frac{1}{y}-\omega^k\right)=\left(-\frac{1}{y}\right)^p-1.$$
Factor each term on the left as $(-1/y)(1+y\omega^k)$, giving
$$\left(-\frac{1}{y}\right)^p G(y)=\left(-\frac{1}{y}\right)^p-1.$$
Multiplying by $(-y)^p$ yields
$$G(y)=1-(-y)^p.$$
Since $p$ is odd, $(-y)^p=-y^p$, hence
$$G(y)=1+y^p.$$
Therefore
$$F(y,\omega^j)=G(y)^2=(1+y^p)^2=1+2y^p+y^{2p}.$$
Thus
$$[y^p]F(y,\omega^j)=2.$$
As there are $p-1$ nonzero values of $j$, the total number of desired subsets equals
$$\frac{1}{p}\left(\binom{2p}{p}+(p-1)\cdot 2\right).$$
Hence the required count is
$$\boxed{\frac{1}{p}\left(\binom{2p}{p}+2(p-1)\right)}.$$
Verification of Key Steps
The identity $\prod_{k=1}^p (x-\omega^k)=x^p-1$ holds because the $p$th roots of unity are precisely the roots of $x^p-1$, each appearing once, giving equality of monic polynomials of degree $p$.
The substitution $x=-1/y$ transforms the product into a form involving $\prod(1+y\omega^k)$ by factoring each term $-1/y-\omega^k=(-1/y)(1+y\omega^k)$, which introduces a global factor $(-1/y)^p$.
The simplification $1-(-y)^p=1+y^p$ uses the parity of $p$, ensuring $(-y)^p=-y^p$, and hence the coefficient of $y^p$ in $(1+y^p)^2$ is exactly $2$, with no other terms contributing at that degree.
Alternative Approaches
A group action approach on subsets via cyclic shifts of residue classes modulo $p$ leads to the same averaging over characters of $\mathbb{Z}_p$, effectively reproducing the root-of-unity filter without generating functions. This method emphasizes symmetry but requires similar evaluation of character sums, which ultimately reduces to the same cyclotomic identity used in the main solution.