294 6 Combinatorics and Probability
such that for any partition of{ 1 , 2 ,...,S(n)}intonsets one of the sets will contain a
Schur triple. No general formula forS(n)exists although upper and lower bounds have
been found. Our problem proves thatS( 4 )>40. In fact,S( 4 )=45.
854.What is the largest number of vertices that a complete graph can have so that its
edges can be colored by two colors in such a way that no monochromatic triangle
is formed?
855.For the Ramsey numbers defined above, prove thatR(p, q)≤ R(p− 1 ,q)+
R(p, q− 1 ). Conclude that forp, q≥2,
R(p, q)≤(
p+q− 2
p− 1)
.
856.The edges of a complete graph withk!e+1 edges are colored bykcolors. Prove
that there is a triangle whose edges are colored by the same color.
857.An international society has members from six different countries. The list of
members contains 1978 names, numbered 1, 2 ,...,1978. Prove that there exists at
least one member whose number is the sum of the numbers of two members from
his/her own country, or twice as large as the number of one member from his/her
country.
858.Letnbe a positive integer satisfying the following property: Ifndominoes are
placed on a 6×6 chessboard with each domino covering exactly two unit squares,
then one can always place one more domino on the board without moving any other
dominoes. Determine the maximum value ofn.
6.2 Binomial Coefficients and Counting Methods
6.2.1 Combinatorial Identities
The binomial coefficient
(n
k)
counts the number of ways one can choosekobjects from
givenn. Binomial coefficients show up in Newton’s binomial expansion
(x+ 1 )n=(
n
0)
xn+(
n
1)
xn−^1 +···+(
n
n− 1)
x+(
n
n)
.
Explicitly,
(
n
k
)
=
n!
k!(n−k)!=
n(n− 1 )···(n−k+ 1 )
k!if 0≤k≤n.The recurrence relation