IMO 1995 Problem 6
For small primes the structure can be tested directly.
Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 6m45s
Problem
Let $p$ be an odd prime number. How many $p$-element subsets $A$ of ${1,2,\ldots,2p}$ are there, the sum of whose elements is divisible by $p$?
Exploration
For small primes the structure can be tested directly. When $p=3$, the $3$-element subsets of ${1,2,3,4,5,6}$ can be enumerated and the sums modulo $3$ checked. A complete listing gives eight valid subsets whose sums are divisible by $3$, so the correct value at $p=3$ is $8$.
Any proposed closed form must reproduce this value. The earlier candidate $\frac{1}{p}\binom{2p-1}{p-1}$ already fails at $p=3$ since it equals $\frac{10}{3}$, so it cannot be correct. The expression $\frac{1}{p}\left(\binom{2p}{p}+2(p-1)\right)$ matches $8$ when $p=3$, so it remains consistent with the small case test.
The residue structure modulo $p$ shows that ${1,\dots,2p}$ consists of two copies of each residue class modulo $p$, which suggests a root-of-unity filter where nontrivial characters see a doubled cyclotomic product. No further simplification beyond this point is structurally justified without introducing a false cancellation.
Problem Understanding
The task is to count $p$-element subsets $A \subseteq {1,2,\dots,2p}$ such that
$\sum_{a\in A} a \equiv 0 \pmod p,$
where $p$ is an odd prime.
The selection size is exactly half of the ambient set, and the condition depends only on the sum modulo $p$. The multiset of residues modulo $p$ is perfectly balanced, with each residue appearing exactly twice, so Fourier methods over $\mathbb{Z}_p$ are naturally suited to the problem.
Key Observations
Each subset $A$ of size $p$ contributes a weight depending only on its residue-sum modulo $p$. The standard root-of-unity filter isolates the desired congruence class.
For $\omega = e^{2\pi i/p}$, orthogonality gives
$\frac{1}{p}\sum_{k=0}^{p-1} \omega^{k(\sum a - 0)}$
as the indicator of the condition $\sum a \equiv 0 \pmod p$.
The combinatorial generating function
$\prod_{i=1}^{2p}(1+x\omega^{ki})$
encodes weighted subsets, and the coefficient of $x^p$ extracts $p$-element subsets.
For $k \neq 0$, multiplication by $k$ permutes nonzero residues modulo $p$, and since each residue occurs twice in ${1,\dots,2p}$, the structure reduces to a squared cyclotomic product.
Solution
Let $\omega = e^{2\pi i/p}$. Define $N$ as the number of $p$-subsets $A \subseteq {1,\dots,2p}$ such that $\sum_{a\in A} a \equiv 0 \pmod p$.
Using the root-of-unity filter,
$$N = \frac{1}{p}\sum_{k=0}^{p-1} \sum_{\substack{A \subseteq {1,\dots,2p}\ |A|=p}} \omega^{k\sum_{a\in A} a}.$$
For fixed $k$, the inner sum is obtained as a coefficient:
$$\sum_{|A|=p} \omega^{k\sum a} = [x^p]\prod_{i=1}^{2p}(1+x\omega^{ki}).$$
Hence
$$N = \frac{1}{p}\sum_{k=0}^{p-1} [x^p]\prod_{i=1}^{2p}(1+x\omega^{ki}).$$
The case $k=0$
When $k=0$, every factor equals $(1+x)$, so
$$\prod_{i=1}^{2p}(1+x\omega^{0}) = (1+x)^{2p}.$$
Thus the contribution is
$$x^p^{2p} = \binom{2p}{p}.$$
The case $k \neq 0$
When $k \neq 0$, multiplication by $k$ permutes the nonzero residues modulo $p$. Among $1,\dots,2p$, each residue class modulo $p$ appears exactly twice, so
$$\prod_{i=1}^{2p}(1+x\omega^{ki}) = \prod_{r=0}^{p-1}(1+x\omega^r)^2.$$
Using the cyclotomic identity
$$\prod_{r=0}^{p-1}(1+x\omega^r) = 1+x^p,$$
we obtain
$$\prod_{i=1}^{2p}(1+x\omega^{ki}) = (1+x^p)^2 = 1 + 2x^p + x^{2p}.$$
Therefore,
$$x^p^2 = 2.$$
Since there are $p-1$ nonzero values of $k$, their total contribution is $2(p-1)$.
Final combination
Putting the $k=0$ and $k \neq 0$ parts together,
$$N = \frac{1}{p}\left(\binom{2p}{p} + 2(p-1)\right).$$
No further cancellation occurs, since the term $2(p-1)$ is a genuine contribution from the nontrivial characters in the root-of-unity filter and is not absorbed into the central binomial coefficient.
Thus the number of required subsets is
$$\boxed{,\frac{1}{p}\left(\binom{2p}{p} + 2(p-1)\right),}.$$
Verification of Key Steps
The root-of-unity filter is valid because it follows from orthogonality of characters of $\mathbb{Z}_p$, ensuring exact projection onto the residue class $0$ modulo $p$.
The generating function identity correctly encodes $p$-subsets via coefficient extraction, since each factor $(1+x\omega^{ki})$ represents independent inclusion or exclusion of the element $i$ with weight $\omega^{ki}$.
The reduction for $k \neq 0$ is justified because multiplication by $k$ permutes the nonzero residue classes modulo $p$, and each residue class occurs exactly twice in ${1,\dots,2p}$, producing a perfect square of the cyclotomic product.
The identity $\prod_{r=0}^{p-1}(1+x\omega^r)=1+x^p$ follows from the factorization of $x^p-1$ over $\mathbb{C}$ after substituting $x \mapsto -x$ and comparing roots.
The final summation over $k$ is valid because the root-of-unity filter averages over all characters, and no term cancels unless enforced by orthogonality, which does not eliminate the constant contribution $2(p-1)$.
Alternative Approaches
A purely combinatorial approach can be developed by grouping subsets according to how many elements they choose from each residue class modulo $p$, leading to a constrained integer partition problem with two copies of each residue. This ultimately reproduces the same Fourier decomposition in disguised form.
Another approach uses representation theory of the cyclic group $\mathbb{Z}_p$, decomposing the indicator space of subsets into irreducible characters and computing the multiplicity of the trivial character in the $p$-th exterior power of the permutation representation on two copies of each residue class.