Balancing problem

2010-01-11T21:23:56Z

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

Answer by Gjergji Zaimi for Balancing problem

2010-01-12T08:30:53Z

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.

Balancing problem - MathOverflow

Balancing problem

Answer by Gjergji Zaimi for Balancing problem