For any set $A=\{a_1,a_2,\cdots,a_m\}$, let $P(A)=a_1a_2\cdots a_m$. Let $n={2010\choose99}$, and let $A_1, A_2,\cdots,A_n$ be all $99$-element subsets of $\{1,2,\cdots,2010\}$. Prove that $2010|\sum^{n}_{i=1}P(A_i)$.
Problem
Source: 2010 China South East Mathematical Olympiad
Tags: algebra, polynomial, modular arithmetic, LaTeX, number theory, number theory unsolved
20.07.2011 02:17
Consider the polynomial $f(X) = (X-1)(X-2)\cdots (X-2010)$. We have to prove that the coefficient of $X^{2010-99} = X^{1911}$ is divisible by $2010 = 2\cdot 3\cdot 5\cdot 67$. It therefore suffices to consider our polynomial modulo 2, 3, 5 and 67. First note that if $p$ is a prime divisor of $k\in\mathbb{Z}_{>0}$, then mod $p$ we have \[(X-1)(X-2)\cdots (X-k) \equiv \left[X(X-1)\cdots (X-(p-1))\right]^{k/p} \equiv \left[X^p-X\right]^{k/p},\]where the last equivalence is a well-known fact: the polynomial $X^p-X$ has distinct roots $0,1,2,\ldots,p-1$ (Fermat's little theorem) in $\mathbb{Z}_p$, and since this is a field, we get $X^p-X = X(X-1)\cdots (X-(p-1))$ over $\mathbb{Z}_p$. Hence, to prove that the coefficient of $X^{1911}$ in $f(X)$ is divisible by $p\in\{2,3,5,67\}$, we need to prove that the coefficient of $X^{1911}$ in \[\left(X^p-X\right)^{2010/p} = \sum_{j=0}^{k/p} X^{jp}(-X)^{\frac{2010}{p}-j}\binom{2010/p}{j}\]is divisible by $p$. This coefficient is precisely $(-1)^{\frac{2010}{p}-j}\binom{2010/p}{j}$, where $j\in\{0,1,\ldots,2010/p\}$ is such that $jp+\frac{2010}{p}-j = 1911$. For $p$ odd, such a $j$ can not exist, by considering this equation mod 2. Hence, the coefficient of $X^{1911}$ is zero mod 3, 5 and 67. Finally, consider the case $p = 2$: then this coefficient is $\binom{1005}{906}$, which is easily seen to be even. We are done!
21.12.2011 14:29
An easier approach: for each 99-element subset $A=\{a_1,...,a_{99}\}$ define $A'=\{2011-a_1,...,2011-a_{99}\}$. Looking at $P(A)+P(A')$ modulo 2010, since 99 is odd and every element of $A$ is the negative modulo its corresponding element in $A'$, we obtain $P(A)+P(A')\equiv 0$. Suppose for some subset $A=A'$. Then for each element x in $A$, 2011-x is also in $A$. Since $2011-x\neq x$ for all x, we must have an even number of elements, contradiction. Hence every $A$ maps to a unique $A'$. Now biject every subset to its $A'$. It clearly follows that $2010|\sum^{n}_{i=1}P(A_{i})$.
21.12.2011 14:43
tobash_co wrote: ... and every element of $A$ is the negative modulo its corresponding element in $A'$, we obtain $P(A)+P(A')\equiv 0$.$.[/quote] I guess that means $ a_i \equiv a_i - 2011 \pmod {2010}$ , which is wrong ?? (what happened to latex?)
21.12.2011 17:27
Let $\mathcal{U=} \sum_{ 2010 \in A_i }^{{}} P(A_i) $, , $\mathcal{V =} \sum_{2010 \notin A_i , 1005 \notin A_i }^{{}}P(A_i) $ , and $\mathcal{W =} \sum_{2010 \notin A_i , 1005 \in A_i}^{{}}P(A_i) $. So $ \sum_{i=1}^{n}P(A_i) = \mathcal{U+V+W} $ We say $A \in \mathcal{U}$ if the set $A$ is appearing in product summation in $\mathcal{U}$. Obviously $\mathcal{U} \equiv 0 \pmod {2010}$. Lets look at $\mathcal{V}$. Let $A_i \in \mathcal{V}$ and $A_i = \left \{ a_1, a_2, \cdots , a_{99} \right \}$. Let $A_j = \left \{2010- a_1, 2010 -a_2, \cdots , 2010 -a_{99} \right \}$, so $A_j \in \mathcal{V}$. Since the number of elements in $A_i$ or in $A_j$ is odd, (and they does not contain $1005$) $A_i \ne A_j$. Since $a_t \equiv a_t - 2010 \pmod{2010}$ for all $1 \le t \le 99$, multiplying those modular relations , we get $P(A_i) + P(A_j) \equiv \pmod {2010}$ So $ \mathcal{V =} \sum_{2010 \notin A_i , 1005 \notin A_i }^{{}}P(A_i) = \sum_{2010 \notin A_i,A_j , 1005 \notin A_i,A_j }^{{}} P(A_i) + P(A_j) \equiv \pmod {2010}$ Now look at $\mathcal{W}$.Let $\mathcal{W = P+Q} $. If $A_i , A_j \in \mathcal{W}$ , $A_i = \left \{ a_1, a_2, \cdots , a_{99} \right \}$. Let $A_j = \left \{2010- a_1, 2010 -a_2, \cdots , 2010 -a_{99} \right \}$, and $A_i \ne A_j$, then let those pair of sets $A_i,A_j$ belong to $\mathcal{P}$. We can show as before that $\mathcal{P} \equiv 0 \pmod {2010}$. But if $A_i \in \mathcal{W}$, and $A_i = \left \{ a_1, a_2, \cdots , a_{99} \right \}$. Let $A_j = \left \{2010- a_1, 2010 -a_2, \cdots , 2010 -a_{99} \right \}$, but $A_i = A_j$, then let this type of pair less set belong to $Q$ . Let $\mathcal{Q= R+ S}$. Where $A_i \in \mathcal{R}$ if it contains any even number. (and to $\mathcal{S}$ if it doesn't contain any even number). Since $A_i \in \mathcal{R}$ also contains $1005$, we have $\mathcal{R} \equiv 0 \pmod{2010}$. We can easily see that if $A_i \in \mathcal{Q}$, then $A_i$ must be of the form $\left \{ 1005, (a_1,b_1), (a_2,b_2), \cdots , (a_{49},b_{49}) \right \} $. Where each of the $49$ pair of odd numbers ${a_i,b_i}$ belongs to the set of $502$ pairs of odd numbers : $\left \{ (1,2009), (3,2007), \cdots , (1003, 1007) \right \}$. So there are $\binom{502}{49}$, sets appearing in the product sum $\mathcal{R}$. We easily see that $1005 \mid \mathcal{R}$ .Since all the summands are odd , and they are being summed up $\binom{502}{49}$ times $2 \mid \mathcal{R}$ iff $\binom{502}{49}$ is even. Which is found to be true. (Using Legrendes formula $v_2(\binom{502}{49}) = 1$). So $2010 \mid \mathcal{R}$. So $\sum_{i=1}^{n}P(A_i) = \mathcal{U+V+P + R+ S} \equiv 0 \pmod {2010} $. qed
22.03.2020 12:33
The statement of this problem is wrong. The correct version is to show that $2011|\sum^{n}_{i=1}P(A_i)$, which is much easier.