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$.


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.

  • $\begingroup$ Thanks! "rainbow" is a very nice choice of term, though I'd never have guessed it! $\endgroup$ – Vipul Naik Jan 12 '10 at 23:27

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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