1995 IMO Problems/Problem 6

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$?

Solution 1 (Partition)

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

B(1)+B(w)+B(w2)+B(wp1)p=p+p(2pp)+p+22(p1)(p)p2

But, we need to subtract $2$ because it counts the empty set and the set with size $2p$. This gives us

\[\boxed{\frac{\dbinom{2p}{p}+2p-2}{p}}\]

$\square$

Solution from this discussion: https://artofproblemsolving.com/community/c6t302107f6h15112_sum_of_whose_elements_is_divisible_by_p.

See Also

1995 IMO (Problems) • Resources
Preceded by
Problem 5
1 2 3 4 5 6 Followed by
Last Question
All IMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png