Difference between revisions of "1995 IMO Problems/Problem 6"
m (→See Also) |
m (→See Also) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 36: | Line 36: | ||
* [[IMO Problems and Solutions]] | * [[IMO Problems and Solutions]] | ||
| − | {{MAA | + | {{MAA Notice}} |
Latest revision as of 21:07, 18 January 2025
Problem
Let 
be an odd prime number. How many -element subsets 
of 
are there, the sum of whose elements is divisible by ?
Solution 1 (Partition)
Let 
be the generating function
![\[A(x,y) = (1+yx)(1+yx^2)\cdots(1+yx^{2p})\]](http://latex.artofproblemsolving.com/b/d/f/bdf5cfe2bc04baf7120b03bb18c52730d186d298.png)
We apply the roots of unity filter on 
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}\]](http://latex.artofproblemsolving.com/b/9/0/b903e0b56df1f816fba4596940a00ea9c79958e0.png)
We call this function on 
, 
. Note that
![\[(1+w)(1+w^2)\cdots(1+w^{p}) = 2\]](http://latex.artofproblemsolving.com/6/8/f/68f575ac21f319726af7523c916ec5030805d087.png)
Then, we apply the roots of unity filter on 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 
because it counts the empty set and the set with size 
. This gives us
![\[\boxed{\frac{\dbinom{2p}{p}+2p-2}{p}}\]](http://latex.artofproblemsolving.com/e/b/8/eb8d2e328aa699fd549335094106363000e03025.png)
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. 
