292 6 Combinatorics and Probability
number, such that whenever the edges of a complete graph are colored red and blue,
there is either a complete subgraph withpvertices whose edges are all red, or a complete
subgraph withqvertices whose edges are all blue. (Recall that a complete graph is an
unoriented graph in which any two vertices are connected by an edge.)
Here is a simple problem in Ramsey theory.
Example.Show that if the points of the plane are colored black or white, then there exists
an equilateral triangle whose vertices are colored by the same color.
Solution.Suppose that there exists a configuration in which no monochromatic equilat-
eral triangle is formed.
Figure 40Start with two points of the same color, say black. Without loss of generality, we may
assume that they are( 1 , 0 )and(− 1 , 0 ). Then( 0 ,
√
3 )and( 0 ,−√
3 )must both be white.
Consequently,( 2 , 0 )is black, and so( 1 ,
√
3 )is white. Then on the one hand,( 1 , 2√
3 )
cannot be black, and on the other hand it cannot be white, a contradiction. Hence the
conclusion. This argument can be followed easily on Figure 40.
We now present a problem from the 2000 Belarus Mathematical Olympiad, which we
particularly liked because the solution contains a nice interplay between combinatorics
and number theory.
Example.LetM ={ 1 , 2 ,..., 40 }. Find the smallest positive integernfor which it
is possible to partitionMintondisjoint subsets such that whenevera,b, andc(not
necessarily distinct) are in the same subset,a =b+c.
Solution.We will show thatn=4. Assume first that it is possible to partitionMinto
three such setsX, Y, andZ. First trick: order the sets in decreasing order of their
cardinalities as|X|≥|Y|≥|Z|. Letx 1 ,x 2 ,...,x|X|be the elements ofXin increasing