TheJerk wrote:

Wrong. It's a really nice problem, but I won't yet post a solution, to give others the pleasure to find one.

actually more is true: if the integers $1,2,...,n$ are colored with 3 colors with each color set receiving more than $n/4$ elements, then the equation $x =y+z$ has a solution with all $x,y,z$ receiving different colors.

Solution?

the version i stated is actually a problem in one of the Schweitzer competitions(i don't remember which).i had a solution (sometime ago) but it is a rather long and nasty one. maybe vess can give something shorter and smarter.

I'm quite sure to have post a solution of the Schweitzer one here, but I can't find it anymore Idem for the original one Pierre.

here is a solution for the problem in question(not the Schweitzer version):suppose not.then clearly $n \geq 2$.wlog $1 \in A$.consider $X=[3n] \setminus A$.since there is no solution to the equation $a=b+c$ with a,b,c in different sets, it follows that the elements of $X$ do not have consecutive elements in $B,C$ respectively.so X is partitioned(into B,C) and further B,C consist of unions of intervals(singleton sets are also regarded as intervals).suppose $[b_1,b_2] \subset B,[c_1,c_2] \subset C$ then there exists no element of $A$ of the form b-c.so if $b_2 < c_1$ then the interval $[c_1-b_2,c_2-b_1]$ is contained either in B or in C.starting with maximal such intervals of length $k,l$ respectively the length of the new interval is $c_2-c_1+b_2-b_1+1=(k-1)+(l-1)+1=k+l-1$.so if both $k,l \geq 2$ then this conradicts the choice of maximal intervals for both B and C. but if say $k=1$,i.e.B consists of isolated points only then $|A| \geq 2|B|-1 \Rightarrow |B| \leq 1$.contradiction.

Please, excuse me my stupid questions: 1. why do you say that $[c_1-b_2,c_2-b_1]$ is contained either in B or in C. maybe some parts is contained in B and some parts in C 2. your final contradiction "if B consists of isolated points then $|A|\geq 2|B|-1$" is unclear for me

Myth wrote: Please, excuse me my stupid questions: 1. why do you say that $[c_1-b_2,c_2-b_1]$ is contained either in B or in C. maybe some parts is contained in B and some parts in C 2. your final contradiction "if B consists of isolated points then $|A|\geq 2|B|-1$" is unclear for me sorry for the lack of clarity. 1)firstly, this interval cannot contain any element of A,so it is contained in $B\cup C$. now since $1 \in A$ we cannot have 2 consecutive elements of $X$ with one of them in B and the other in C.if the interval in question had points from both B and C then there would be consecutive elements with one of them in B and the other in C.(hope i am saying it clearly enough) 2)yah what i thought initially is not correct,since there can be strings of B's separated by the A's but i think it can be modified to still get the contradiction.the neighbors of the points of B cannot be points of C and so have to be points of A.so whenever the points of B occur they must occur in the form ABABA..BA,except if $3n \in B$ in which case that particular string contains equal number of A's and B's.now consider the strings ABAB..A as above.clearly each such string contains more elements of A than of B.Also,since there are elements of C present there have to be atleast 2 such strings and so $|A| >|B|$.(hopefullly this answers your questions)

Sorry, I was very tired last evening, and I was too lazy to think about your proof, so I wrote these stupid questions.

Yes!!! I found back the Schweitzer one : http://www.mathlinks.ro/Forum/viewtopic.php?highlight=contest&t=3781 Pierre.

I remember seeing the following generalization: Partition mn numbers (1,2,...,mn) to m sets such that each set has n elements, where m,n are arbitrary positive integers greater than 2. Show that it is possible to pick one element from every set such that sum of [m/2] of these chosen numbers equal to the sum of the rest m-[m/2].

Here is my solution : Supose prroblem is false.and 1,2,...,k-1 in A,k in B.k>=2. Let c in A => c-1 not in B. if c-1 in C we have c-ik,c-ik-1 in C .Exist such that c-ik <= k contraction. Since then c-1 in A.Let C={c_1,....,c_n} then A={c_i-1,i=1,2,...,n} .Wee have k-1 inA =>k in C (contraction

Did anybody understand it?

I think he means more or less the following, which is the solution we gave when we used the problem in our training : We will say that $(a,b,c) \in A \times B \times C$ is good if one of $a,b,c$ is the sum of the two others. Assume that there is no good triples. Wlog, we may assume that $1 \in A$ and that the least number which is not in $A$, say $k$, belongs to $B$. Let $x \in C$. We prove that $x-1 \in A$ : Clearly, since there is no good triple, $x-1 \notin B$. Suppose that $x-1 \in C$, and from the minimality of $k$, it follows that $x-1 > k$. Since none of the triples $(x-k,k,x)$ and $(k-1,x-k,x-1)$ is good, it follows that $x-k \notin A \cup B$. Similarly, using the triples $(x-k-1,k,x-1)$ and $(1,x-k-1,x-k)$ we deduce that $x-k-1 \notin A \cup B$. Thus both of them belong to $C$. By induction, it is now easy to prove that all the positive integers of the form $x-ik$ or $x-ik-1$ belong to $C$. But, for some $i$, one of the numbers $x-ik$ or $x-ik-1$ is positive and not greater than $k$, so that it belongs to $A \cup B$. A contradiction. It follows that, for all $x \in C$, we have $x-1 \in A$. Let $C = \{c_1, \cdots, c_n \}$. Thus each of the numbers $c_1-1, \cdots , c_n -1$ belongs to $A$. But these numbers are pairwise distincts and all are greater than $1$ (since they all the $c_i$'s are greater than $k$). Thus $|A| \geq n+1$, a contradiction. And we are done. Pierre.

Oh, it is so great to see nice solutions in the forum!