# Combinatorics/Schur's Theorem

Schur's theorem states that for every positive integer *r*, there exists a positive integer *S*, such that for every partition of the integers {1, ..., *S*} into *r* parts, one of the parts contains integers *x*, *y* and *z* with

*x*+*y*=*z*.

**Proof:** Let *n* = *R*(3, ..., 3) where *R*(3, ..., 3) denotes the Ramsey number on *r* colors. Now take *S* to be *n* and partition the integers {1, ..., *n*} into *r* parts, which we denote by *colors*. That is, the integers in the first part are said to be *colored* c_{1}, the integers in the second part are said to be colored c_{2} and so on till color c_{r}. We also then say that {1, ..., *S*} has been *r-colored*. This terminology is common in Ramsey theory.

Now color the edges of K_{n} as follows: An edge *xy* (this denotes an edge which joins vertices *x* and *y*) is given color *c* if |*x* - *y*| was colored *c* in the partitioning. Now K_{n} will definitely contain a monochromatic triangle, say built out of the vertices *i* > *j*> *k*. Suppose the triangle is colored c_{m}. Now *i* - *j*, *i* - *k* and *j* - *k* will also be colored c_{m}, i.e. will belong to the same part in the partition. It only remains to take *x* = *i* - *j*, *y* = *j* - *k* and *z* = *i* - *k* to complete the proof.