746 Combinatorics and Probability
857.Yet another Olympiad problem related to Schur numbers. We can reformulate the
problem as follows:
Show that if the set{ 1 , 2 ,..., 1978 }is partitioned into six sets, then in one of these
sets there area, b, c (not necessarily distinct)such thata+b=c.
The germs of the solution have already been glimpsed in the Bielorussian problem
from the introduction. Observe that by the pigeonhole principle, one of the six sets, say
A, has at least^19786 + 1 =330 elements; call thema 1 <a 2 <···<a 330. If any of the
329 differences
b 1 =a 330 −a 329 ,b 2 =a 330 −a 328 ,...,b 329 =a 330 −a 1is inA, then we are done, becausea 330 −am=anmeansam+an=a 330. So let us
assume that none of these differences is inA. Then one of the remaining sets, sayB,
contains at least^3295 + 1 =66 of these differences. By eventually renumbering them,
we may assume that they areb 1 <b 2 <···<b 66. We repeat the argument for the
common differences
c 1 =b 66 −b 65 ,c 2 =b 66 −b 64 ,...,c 65 =b 66 −b 1.Note that
cj=b 66 −b 66 −j=(a 330 −am)−(a 330 −an)=an−am.So if one of thecj’s is inAorB, then we are done. Otherwise, there is a fourth set
D, which contains^654 + 1 =17 of thecj’s. We repeat the argument and conclude
that either one of the setsA, B, C, Dcontains a Schur triple, or there is a fifth setE
containing^173 + 1 =6 of the common differencesdk=c 17 −c 17 −k. Again either we
find a Schur triple inA,B,C,orD, or there is a setEcontaining^52 + 1 =3 of the five
differencesei=d 5 −d 5 −k. If any of the three differencese 2 −e 1 ,e 3 −e 2 ,e 3 −e 1 belongs
toA, B, C, D, E, then we have found a Schur triple in one of these sets. Otherwise, they
are all in the sixth setF, and we have found a Schur triple inF.
Remark.Look at the striking similarity with the proof of Ramsey’s theorem, which makes
the object of the previous problem. And indeed, Ramsey’s theorem can be used to prove
Schur’s theorem in the general case:S(n)is finite and is bounded above by thek-color
Ramsey numberR( 3 , 3 ,..., 3 ).
Here is how the proof runs. Think of the partition of the set of the firstNpositive
integers intonsubsets as a coloringc:{ 1 , 2 ,...,N}→{ 1 , 2 ,...,n}. Consider the
complete graph with vertices 1, 2 ,...,Nand color its edges so that fori>j,(i, j )is
colored byc(i−j).IfN≥R( 3 , 3 ,..., 3 )(thek-color Ramsey number), then there is a
monochromatic triangle. Ifi<j<kare the vertices of this triangle, then the numbers