MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

There was a problem in an Olympiad selection test, which went as follows: Consider the set $\{1,2,\dots,3n \}$ and partition it into three sets A, B and C of size n each. Then, show that there exist x, y and z, one in each of the three sets, such that x + y = z.

This has a tricky-to-get but otherwise straightforward solution, that starts by assuming 1 to be in A, finding the smallest k not in A, assuming that to be in B, and then arguing that no two consecutive elements can be present in C (for that would give an infinite descent). Finally, cardinality considerations solve the problem.

I managed to prove a corresponding statement for 4n, namely: for $\{ 1,2,3, \dots, 4n \}$, partitioned into four sets of size n each, there exist x, y, z, and w, one in each set, such that x + y = z + w.

The question here is whether analogues of this hold for all m, with $m \ge 3$ and $n \ge 2$. In other words, if $\{ 1,2, \dots, mn \}$ is divided into $m$ sets of size $n$ each, can we always make a choice of one element in each set such that the sum of floor $m/2$ of the elements equals the sum of the remaining ceiling $m/2$ elements ($(m-1)/2$ and $(m + 1)/2$ for $m$ odd, $m/2$ each for $m$ even). Note we need $n \ge 2$ due to parity considerations when $m$ is congruent to $1$ or $2$ modulo $4$.

share|cite|improve this question
up vote 13 down vote accepted

This article is a nice survey of "Rainbow Ramsey theory". In this jargon what you are trying to prove is that the vector $(1,1,\dots,1,-1,-1,\dots,-1)$ is rainbow partition $m$-regular.

The case of $(1,1,-1,-1)$ being rainbow partition 4-regular, was proved in "Rainbow solutions for the sidon equation x+y=z+w", J. Fox, M. Mahdian, and R. Radoicic. They actually proved that as long as each of the four parts of $[n]$ has at least $(n+1)/6$ members then one can always find rainbow solutions to $x+y=z+w$ (i.e. each variable coming from a different partition.)

Though these results were mostly inspired from their monochromatic version (the 3 variable case dates back to Schur, and then R.Rado classified all linear equations that are partition regular), the analogy hasn't proven very faithful. The rainbow Hales-Jewett theorem is false, and so is the rainbow Van der Waerden theorem!

Another thing worth mentioning is that if we color $\mathbb{Z}/p\mathbb{Z}$ in $k$ colors with each color having at least $k$ elements, then the equation $\sum_{i=1}^k a_i x_i\equiv b\pmod{p}$ always has a rainbow solution given that not all $a_i$ are the same. A proof is in this article by D.Conlon.

share|cite|improve this answer
Thanks! "rainbow" is a very nice choice of term, though I'd never have guessed it! – Vipul Naik Jan 12 '10 at 23:27

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.