Suppose $a_1, a_2, ..., a_r$ are integers with $a_i \geq 2$ for all $i$ such that $a_1 + a_2 + ... + a_r = 2010$. Prove that the set $\{1,2,3,...,2010\}$ can be partitioned in $r$ subsets $A_1, A_2, ..., A_r$ each with $a_1, a_2, ..., a_r$ elements respectively, such that the sum of the numbers on each subset is divisible by $2011$. Decide whether this property still holds if we replace $2010$ by $2011$ and $2011$ by $2012$ (that is, if the set to be partitioned is $\{1,2,3,...,2011\}$).
Problem
Source:
Tags: algebra, polynomial, induction, combinatorics unsolved, combinatorics
Batominovski
03.05.2010 09:27
I'm proving a generalization (note that $2011$ is a prime): Let $p$ be an odd prime number. Suppose $a_k$, $k=1,2,\ldots,r$, are integers greater than $1$ such that \[\sum_{k=1}^r a_r = p-1\,.\] Then, there exists a partition $\mathcal{A}:=\big\{A_1,A_2,\ldots,A_r\big\}$ of $\mathbb{F}_p^\times=\{1,2,\ldots,p-1\}$ such that $\big|A_k\big|=a_k$ for all $k=1,2,\ldots,r$, and the sum of elements in each $A_k$ is zero in $\mathbb{F}_p$.
WLOG, let $a_1 \geq a_2 \geq \ldots \geq a_r$. When $a_1=2$, the assertion is trivial. Now, assume that $a_1>2$. Thus, we must have $r \leq \frac{p-3}{2}$. Define a polynomial $f\left(x_1,x_2,\ldots,x_{p-1}\right)$ in $\mathbb{F}_p\left[x_1,x_2,\ldots,x_{p-1}\right]$ as follows:
\[f\left(x_1,x_2,\ldots,x_{p-1}\right) := \left(\prod_{i=1}^{p-1} x_i\right)\left(\prod_{1\leq{i}<j\leq{p-1}}\left(x_i-x_j\right)\right)\prod_{k=1}^r\left(1-\left(\sum_{i=b_{k-1}+1}^{b_k}x_i\right)^{p-1}\right)\,,\]
where $b_0:=0$ and $b_k:=a_k+b_{k-1}$ for $k>0$.
The total degree of $f$ is
\[(p-1)+\binom{p-1}{2}+(p-1)r\,.\]
The next part is tricky. Note that the only nonvanishing terms of $\prod_{1\leq{i}<j\leq{p-1}}\left(x_i-x_j\right)$ are $U:=x_1^{u_1}x_2^{u_2}\cdots x_{p-1}^{u_{p-1}}$, where $\left(u_1,u_2,\ldots,u_n\right)$ is a permutation of $(0,1,\ldots,p-2)$. This is because $\prod_{1\leq{i}<j\leq{p-1}}\left(x_i-x_j\right)$ is the Vandermonde polynomial (corresponding to the Vandermonde determinant). We need to find a particular $U$ and try to use the Combinatorial Nullstellensatz.
We now consider a nonvanishing term
\[V:=\prod_{k=1}^rx_{b_{k-1}+1}^{p-1-k}x_{b_{k-1}+2}^{k}\]
from $\prod_{k=1}^r\left(1-\left(\sum_{i=b_{k-1}+1}^{b_k}x_i\right)^{p-1}\right)$. We see that this monomial $V$, when multiplied by $U$ that is in the form
\[x_1^{0}x_2^{p-3}x_3^{p-2}x_4^{u_4}x_5^{u_5}\cdots x_{b_1}^{u_{b_1}} \cdot \left(\prod_{k=2}^r\left(x_{b_{k-1}+1}^{k-1}x_{b_{k-1}+2}^{p-k-2} x_{b_{k-1}+3}^{u_{b_{k-1}+3}}\cdots x_{b_k}^{u_{b_k}}\right)\right)
\,,\]
will become a monomial $W:=x_1^{w_1}x_2^{w_2}\cdots x_{p-1}^{w_{p-1}}$ which has $w_i \leq p-2$ for all $i$. (The fact that $r \leq \frac{p-3}{2}$ ensures that no exponents are repeated in $U$. Also, the unspecified exponents can be taken arbitrarily, as long as $U$ has all the exponents from $0$ to $p-2$.) Therefore, the coefficient of $M:=x_1x_2\cdots x_{p-1}\cdot W$ is nonzero in $f\left(x_1,x_2,\ldots,x_{p-1}\right)$. Since the degree of each variable in $M$ is at most $p-1$ and the total degree of $M$ is the same as that of $f$, due to the Combinatorial Nullstellensatz, $f$ must be nonzero at some point $\big(X_1,X_2,\ldots,X_{p-1}\big) \in \mathbb{F}_p^{p-1}$. Take $A_k:=\big\{X_{b_{k-1}+1},X_{b_{k-1}+2},\ldots,X_{b_k}\big\}$, and we obtain a desired partition (why?).
PS: Please post a nonalgebraic solution if you have one. Without my previous knowledge of alg. combi., I would have no idea how to attack the problem.
uglysolutions
03.05.2010 18:33
For the second part, one could just say that $1+2+...+2011 = 1006 \cdot 2011$ is not divisible by $2012$, and hence such a division is never possible.
Batominovski
03.05.2010 19:20
According to your proof for $2012$, it rules out all even numbers. Do you think my assertion is true for any odd integer $p$?
mcampo
07.05.2010 19:58
I have a solution in the case $3|p-1$. If $a_k$ is even for all $k$ then you can get the partition by taking $a$ and $p-a$ in the same subset. Now, we can get a partition of $\{1,2 \ldots p-1\}$ into subsets of three elements such that the sum on each subset is divisible by $p$ and if $\{a_1, a_2, a_3\}$ is one of our subsets then $\{p-a_1, p-a_2, p-a_3\}$ is another. Once we have this partition we put a triple in each $A_k$ with odd $a_k$, as there is an even number off odd $a_k$'s we can do this in a way that if we put ${a_1, a_2, a_3}$ in one subset then we put ${p-a_1, p-a_2, p-a_3}$ in another. Now we can fill all the $A_i$'s by adding pairs ${a, p-a}$. To get the partition of $\{1,2 \ldots p-1\}$ into triples pick a primitive root $\alpha$ modulo $p$, and take the triples $\{{\alpha}^{k},{\alpha}^{\frac{p-1}{3}+k},{\alpha}^{\frac{2(p-1)}{3}+k}\}$. The sum of each triple is ${\alpha}^{k}.\frac{{\alpha}^{p-1}-1}{{\alpha}^{\frac{p-1}{3}} - 1}$ which is divisible by $p$, and the opposite of $\{{\alpha}^{k},{\alpha}^{\frac{p-1}{3}+k},{\alpha}^{\frac{2(p-1)}{3}+k}\}$ is $\{{\alpha}^{k+\frac{p-1}{2}},{\alpha}^{\frac{p-1}{3}+k+\frac{p-1}{2}},{\alpha}^{\frac{2(p-1)}{3}+k+\frac{p-1}{2}}\}$.
jlucascsa
30.04.2011 01:36
Batominovski wrote: PS: Please post a nonalgebraic solution if you have one. Without my previous knowledge of alg. combi., I would have no idea how to attack the problem.
We use reverse induction. Suppose $ a_{1}\geq a_{2}\geq\ldots\geq a_{r} $. If $ a_{1}\geq 4 $, the problem holds for $ a_{1}-2, 2, a_{2}, a_{3}, \ldots, a_{n} $, so we just put the sets with sizes $a_{1}-2$ and $2$ together and get the result inductively.
So, we just need to analyse the initial cases, which are the ones with $ a_{i}\leq3$ for every $i$.
Suppose $r=770$ and $a_{1}=a_{2}=\ldots=a_{r}=3$.
An easy solution for this case comes with the sets
$A_{i}=\{i,1005+i,1006-2i\}$ for every $1\leqq\leq335$
and
$B_{i}=\{2011-i,1006-i,1005+2i\}$ for every $1\leqq\leq335$
which I will not verify here.
Now suppose $a_{k}=3$ and $a_{k+1}=2$. Then we have $ k$ $3's$ and $r-k$ $2's$ among those numbers, which means $k$ is even and $r-k$ is a multiple of 3. Clearly, we can convert sets $A_{j}$ and $B_{j}$ into three sets of sum multiple of 2011, for every j. So, just do that for each $1\leq j\leq\frac{2k}{3}$.
Our induction is complete.
Batominovski, can you tell how you learnt those algebraic methods? They're impressive.
Batominovski
30.04.2011 02:54
jlucascsa wrote: $A_{i}=\{i,1005+i,1006-2i\}$ for every $1\leqq\leq335$ $B_{i}=\{2011-i,1006-i,1005+2i\}$ for every $1\leqq\leq335$ I think $A_1$ and $B_2$ are not disjoint, are they? They both contain $1004$. jlucascsa wrote: Batominovski, can you tell how you learnt those algebraic methods? I took an algebraic combinatoric course when I was an undergraduate. But you can also learn the nullstellensatz from this very useful paper too: http://www.tau.ac.il/~nogaa/PDFS/null2.pdf.
trenkialabautroj
05.03.2012 14:30
is there any elementary solution ?
v_Enhance
11.04.2012 21:53
Sorry to revive... I have a silly question about the CN solution.
Batominovski wrote:
Therefore, the coefficient of $M:=x_1x_2\cdots x_{p-1}\cdot W$ is nonzero in $f\left(x_1,x_2,\ldots,x_{p-1}\right)$.
As I'm interpreting your solution, you've constructed $M$ as a product of certain monomials in the expression for $f$. How do you know that this is the only way to construct $M$? (As a simple example, the coefficient of $xy$ in $(x+y)(x-y) = x^2-y^2$ is zero, even though there were $xy$ terms in the expansion.)
Batominovski
11.04.2012 22:13
v_Enhance wrote: Batominovski wrote: Therefore, the coefficient of $M:=x_1x_2\cdots x_{p-1}\cdot W$ is nonzero in $f\left(x_1,x_2,\ldots,x_{p-1}\right)$. As I'm interpreting your solution, you've constructed $M$ as a product of certain monomials in the expression for $f$. How do you know that this is the only way to construct $M$? (As a simple example, the coefficient of $xy$ in $(x+y)(x-y) = x^2-y^2$ is zero, even though there were $xy$ terms in the expansion.) There is a reference to the Vandermonde polynomials for a reason. Reread my solution, please.
v_Enhance
11.04.2012 23:31
I did read the part about Vandermonde polynomials, but I'm not seeing why that implies it's the unique way to write that particular term. Maybe I am not being clear what my question is, so let me give an example:
Take $p=7$ and $a_1=a_2=3$. The polynomial, (well, ignoring the $\prod x_i$ at the beginning) can be written as
\[ V_6 ( (x_1+x_2+x_3)^6 - 1))((x_4+x_5+x_6)^6-1) \] where $V_6$ is the Vandermonde polynomial we care about.
But now both, say, \[(x_1^0 x_2^4 \cdot x_4^1x_5^3 \cdot x_3^2x_6^5)(x_1^5x_2^1)(x_4^4x_3^2) \] and \[ (x_1^1x_2^3 \cdot x_4^0x_5^4 \cdot x_3^2x_6^5)(x_1^4x_2^2)(x_4^5x_5^1) \] are both terms that appear in the expansion.
How does $V_6$ being the Vandermonde polynomial ensure that these do not cancel out? Does it involve the sign of the permutation?
Batominovski
13.04.2012 19:04
v_Enhance wrote: I did read the part about Vandermonde polynomials, but I'm not seeing why that implies it's the unique way to write that particular term. Maybe I am not being clear what my question is, so let me give an example: Start to see your point. I may indeed have presented an incomplete solution. I will try to fix it if that is possible. Thank you very much.