Description
Exercise 7.1
In this question, R(m, n) denotes the Ramsey number and we assume that in a group of people, any two people
are either friends or enemies.
i) Show that in a group of five people there are not necessarily either three mutual enemies or three mutual
friends. Hence, R(3, 3) > 5.
(2 Marks)
ii) Show that in a group of 10 people there are either three mutual friends or four mutual enemies, and there
are either three mutual enemies or four mutual friends. This implies R(4, 3) ≤ 10.
(2 Marks)
iii) Use ii) to show that among any group of 20 people there are either four mutual friends or four mutual
enemies. (Actually, R(4, 4) = 18, so this result is not optimal.)1
(2 Marks)
iv) Show that R(2, n) = n for n ∈ N, n ≥ 2.
(1 Mark)
v) Show that R(m, n) ≤ R(m − 1, n) + R(m, n − 1). Hence R(4, 3) ≤ 10.
(2 Marks)
vi) Prove that R(4, 3) ≤ 9 as follows: In a party of size 9, every person has at least four enemies or at least
four friends (by the generalized pigeonhole principle). Consider first the case where there is one person
with four friends and then the case where no one has four friends, i.e., everyone has five or more enemies.
(2 Marks)
vii) Show that R(4, 3) > 8 by giving a suitable example of an 8-member party. Conclude R(4, 3) = 9.
(2 Marks)
Exercise 7.2
At a given party of at least two people, any two participants are either mutual friends or not. Show that there
are two people at such a party that have the same number of friends.
(2 Marks)
Exercise 7.3
Show that if k, n ∈ N with 1 ≤ k ≤ n, then
(
n
k
)
≤
n
k
2
k−1
(2 Marks)
1From http://www.cut-the-knot.org/arithmetic/combinatorics/Ramsey44.shtml: Noga Alon and Michael Krivelevich [The
Princeton Companion to Mathematics, p. 562] present a story of the Ramsey number R(4, 4):
“In the course of an examination of friendship between children some fifty years ago, the Hungarian sociologist Sandor
Szalai observed that among any group of about twenty children he checked he could always find four children any
two of whom were friends, or else four children no two of whom were friends. Despite the temptation to try to draw
sociological conclusions, Szalai realized that this might well be a mathematical phenomenon rather than a sociological
one. Indeed, a brief discussion with the mathematicians Erd¨os, Tur´an, and S´os convinced him this was the case.”
Exercise 7.4
Show that if A and B are events and P is a probability function, then P[A ∩ B] ≥ P[A] + P[B] − 1. This is
known as Bonferroni’s inequality.
(2 Marks)
Exercise 7.5
Use induction to prove the probabilistic inclusion-exclusion principle: Let S be a sample space and A1, . . . , An ⊂
S. Then
P[A1 ∪ A2 ∪ · · · ∪ An] = ∑
1≤i≤n
P(Ai) −
∑
1≤i
