Difference between revisions of "1995 IMO Problems/Problem 6"

Latest revision as of 21:07, 18 January 2025

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

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{align*} \frac{B(1)+B(w)+B(w^2)+\cdots B(w^{p-1})}{p} &= \frac{p+p\binom{2p}{p}+p+2^{2}(p-1)(p)}{p^2} \end{align*}

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$

@@ Line 19: / Line 19: @@
 \begin{align*}
-    \frac{B(1)+B(w)+B(w^2)+\cdots B(w^{p-1})}{p} &= \frac{p+p\binom{2p}{p}+p+2^{2}(p-1)(p)}{p^2}
+\frac{B(1)+B(w)+B(w^2)+\cdots B(w^{p-1})}{p} &= \frac{p+p\binom{2p}{p}+p+2^{2}(p-1)(p)}{p^2}
 \end{align*}
@@ Line 32: / Line 32: @@
 ==See Also==
 {{IMO box|year=1995|num-b=5|after=Last Question}}
+* [[1995 IMO]]
+* [[IMO Problems and Solutions]]
+{{MAA Notice}}

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