20. N6 (POL) ${ }^{\mathrm{IMO} 06}$ Let $p$ be an odd prime. Find the number of $p$-element subsets $A$ of $\{1,2, \ldots, 2 p\}$ such that the sum of all elements of $A$ is divisible by $p$.
20. We shall consider the set $M=\{0,1, \ldots, 2 p-1\}$ instead. Let $M_{1}=\{0,1, \ldots, p-1\}$ and $M_{2}=\{p, p+1, \ldots, 2 p-1\}$. We shall denote by $|A|$ and $\sigma(A)$ the number of elements and the sum of elements of the set $A$; also, let $C_{p}$ be the family of all $p$-element subsets of $M$. Define the mapping $T: C_{p} \rightarrow C_{p}$ as $T(A)=\left\{x+1 \mid x \in A \cap M_{1}\right\} \cup\left\{A \cap M_{2}\right\}$, the addition being modulo $p$. There are exactly two fixed points of $T$ : these are $M_{1}$ and $M_{2}$. Now if $A$ is any subset from $C_{p}$ distinct from $M_{1}, M_{2}$, and $k=\left|A \cap M_{1}\right|$ with $1 \leq k \leq p-1$, then for $i=0,1, \ldots, p-1$, $\sigma\left(T^{i}(A)\right)=\sigma(A)+i k(\bmod p)$. Hence subsets $A, T(A), \ldots, T^{p-1}(A)$ are distinct, and exactly one of them has sum of elements divisible by $p$. Since $\sigma\left(M_{1}\right), \sigma\left(M_{2}\right)$ are divisible by $p$ and $C_{p} \backslash\left\{M_{1}, M_{2}\right\}$ decomposes into families of the form $\left\{A, T(A), \ldots, T^{p-1}(A)\right\}$, we conclude that the required number is $\frac{1}{p}\left(\left|C_{p}\right|-2\right)+2=\frac{1}{p}\left(\binom{2 p}{p}-2\right)+2$. Second solution. Let $C_{k}$ be the family of all $k$-element subsets of $\{1,2, \ldots, 2 p\}$. Denote by $M_{k}(k=1,2, \ldots, p)$ the family of $p$-element multisets with $k$ distinct elements from $\{1,2, \ldots, 2 p\}$, exactly one of which appears more than once, that have sum of elements divisible by $p$. It is clear that every subset from $C_{k}, k<p$, can be complemented to a multiset from $M_{k} \cup M_{k+1}$ in exactly two ways, since the equation $(p-k) a \equiv 0(\bmod p)$ has exactly two solutions in $\{1,2, \ldots, 2 p\}$. On the other hand, every multiset from $M_{k}$ can be obtained by completing exactly one subset from $C_{k}$. Additionally, a multiset from $M_{k}$ can be obtained from exactly one subset from $C_{k-1}$ if $k<p$, and from exactly $p$ subsets from $C_{k-1}$ if $k=p$. Therefore $\left|M_{k}\right|+\left|M_{k+1}\right|=2\left|C_{k}\right|=2\binom{2 p}{k}$ for $k=1,2, \ldots, p-2$, and $\left|M_{p-1}\right|+p\left|M_{p}\right|=2\left|C_{p-1}\right|=2\binom{2 p}{p-1}$. Since $M_{1}=2 p$, it is not difficult to show using recursion that $\left|M_{p}\right|=\frac{1}{p}\left(\binom{2 p}{p}-2\right)+2$.  Third solution. Let $\omega=\cos \frac{2 \pi}{p}+i \sin \frac{2 \pi}{p}$. We have $\prod_{i=1}^{2 p}\left(x-\omega^{i}\right)=$ $\left(x^{p}-1\right)^{2}=x^{2 p}-2 x^{p}+1$; hence comparing the coefficients at $x^{p}$, we obtain $\sum \omega^{i_{1}+\cdots+i_{p}}=\sum_{i=0}^{p-1} a_{i} \omega^{i}=2$, where the first sum runs over all $p$-subsets $\left\{i_{1}, \ldots, i_{p}\right\}$ of $\{1, \ldots, 2 p\}$, and $a_{i}$ is the number of such subsets for which $i_{1}+\cdots+i_{p} \equiv i(\bmod p)$. Setting $q(x)=-2+\sum_{i=0}^{p-1} a_{i} x^{i}$, we obtain $q\left(\omega^{j}\right)=0$ for $j=1,2, \ldots, p-1$. Hence $1+x+\cdots+x^{p-1} \mid q(x)$, and since deg $q=p-1$, we have $q(x)=-2+\sum_{i=0}^{p-1} a_{i} x^{i}=c\left(1+x+\cdots+x^{p-1}\right)$ for some constant $c$. Thus $a_{0}-2=a_{1}=\cdots=a_{p-1}$, which together with $a_{0}+\cdots+a_{p-1}=\binom{2 p}{p}$ yields $a_{0}=\frac{1}{p}\left(\binom{2 p}{p}-2\right)+2$.