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

$\begin{aligned} \frac{B (1) + B (w) + B (w^{2}) + \dots B (w^{p - 1})}{p} & = \frac{p + p (\binom{2 p}{p}) + p + 2^{2} (p - 1) (p)}{p^{2}} \end{aligned}$

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.

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

Page

Toolbox

Search

1995 IMO Problems/Problem 6

Problem

Solution 1 (Partition)

See Also