Balancing problem - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T06:37:28Z http://mathoverflow.net/feeds/question/11464 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/11464/balancing-problem Balancing problem Vipul Naik 2010-01-11T21:23:56Z 2010-01-12T08:30:53Z <p>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 <em>A</em>, <em>B</em> and <em>C</em> of size <em>n</em> each. Then, show that there exist <em>x</em>, <em>y</em> and <em>z</em>, one in each of the three sets, such that <em>x + y = z</em>.</p> <p>This has a tricky-to-get but otherwise straightforward solution, that starts by assuming 1 to be in <em>A</em>, finding the smallest <em>k</em> not in <em>A</em>, assuming that to be in <em>B</em>, and then arguing that no two consecutive elements can be present in <em>C</em> (for that would give an infinite descent). Finally, cardinality considerations solve the problem.</p> <p>I managed to prove a corresponding statement for <em>4n</em>, namely: for ${ 1,2,3, \dots, 4n }$, partitioned into four sets of size <em>n</em> each, there exist <em>x</em>, <em>y</em>, <em>z</em>, and <em>w</em>, one in each set, such that <em>x + y = z + w</em>.</p> <p>The question here is whether analogues of this hold for all <em>m</em>, 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$.</p> http://mathoverflow.net/questions/11464/balancing-problem/11512#11512 Answer by Gjergji Zaimi for Balancing problem Gjergji Zaimi 2010-01-12T08:30:53Z 2010-01-12T08:30:53Z <p><a href="http://www.emis.de/journals/INTEGERS/papers/a9int2003/a9int2003.pdf" rel="nofollow">This</a> 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.</p> <p>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.)</p> <p>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! </p> <p>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 <a href="http://www.dpmms.cam.ac.uk/~dc340/RE.pdf" rel="nofollow">this</a> article by D.Conlon.</p>