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<j≤n
P[Ai ∩ Aj ] + ∑
1≤i<j<k≤n
P[Ai ∩ Aj ∩ Ak]
− + . . . + (−1)n+1P[A1 ∩ A2 ∩ · · · ∩ An]
(3 Marks)
Exercise 7.6
Devise a Monte Carlo algorithm that determines whether a permutation of the integers 1 through n has already
been sorted (that is, in increasing order), or, instead, is a random permutation. A step of the algorithm should
answer “true” if it determines the list is not sorted and “unknown” otherwise. After k steps the algorithm
decides that the numbers are sorted if the answer is “unknown” in each step. Estimate the probability that the
algorithm produces an incorrect answer as a function of k and n.
Hint: For each step, whether two randomly selected elements are in the correct order. Make sure these tests
are independent!
(4 Marks)
Exercise 7.7
Let n ∈ N \ {0} such that n − 1 = 2s
t for s ∈ N and t = 2k + 1 for some k ∈ N. We say that n passes Miller’s
test for the base b if either b
t ≡ 1 mod n or b
2
j
t ≡ −1 mod n for some j with o ≤ j ≤ s − 1. It can be shown
that a composite integer passes Miller’s test for fewer than n/4 bases b with 1 < b < n. A composite integer
that passes Miller’s test to the base b is called a strong pseudoprime to the base b
i) Show that if n is prime and b ∈ N \ {0} with b ∤ n, then n passes Miller’s test for the base b.
(3 Marks)
ii) Show that 2047 passes Miller’s test to the base 2, but that it is composite.
(1 Mark)
