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

Latest revision as of 22: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 2: / Line 2: @@
 Let <math>p</math> be an odd prime number. How many <math>p</math>-element subsets <math>A</math> of <math>{1,2,\ldots,2p}</math> are there, the sum of whose elements is divisible by <math>p</math>?
-==Solution==
+==Solution 1 (Partition)==
-{{solution}}
+Let <math>A(x,y)</math> be the generating function
+<cmath>A(x,y) = (1+yx)(1+yx^2)\cdots(1+yx^{2p})</cmath>
+We apply the roots of unity filter on <math>x</math> to get
+<cmath>\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}</cmath>
+We call this function on <math>y</math>, <math>B(y)</math>. Note that
+<cmath>(1+w)(1+w^2)\cdots(1+w^{p}) = 2</cmath>
+Then, we apply the roots of unity filter on <math>y</math> 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 <math>2</math> because it counts the empty set and the set with size <math>2p</math>. This gives us
+<cmath>\boxed{\frac{\dbinom{2p}{p}+2p-2}{p}}</cmath>
+<math>\square</math>
+Solution from this discussion: https://artofproblemsolving.com/community/c6t302107f6h15112_sum_of_whose_elements_is_divisible_by_p.
 ==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