The University of Melbourne — School of Mathematics and Statistics
MAST30012 Discrete Mathematics — Semester 2, 2021
Practice Class 4: Pigeon Holes and Ramsey Numbers – Answers
Q1: (a) Taking into account the number of days in each month and the fact that 28 days
equals 4 weeks we find that the 13th day of each month corresponds to days of the week
as
Jan $ 0,Feb $ 3,Mar $ 3,Apr $ 6,May $ 1, Jun $ 4,
Jul $ 6,Aug $ 2, Sep $ 5,Oct $ 0,Nov $ 3,Dec $ 5.
(b) There is at least one and no more than three months with the 13th day any given
type. So there must be at least one, and no more than 3, Friday the 13ths in any one
year.
Q2: In each case there is n people and n� 1 possible number of friends.
Q3: Divide the circle into 6 sectors of equal size and choose one of the boundaries to pass
through one the points. Each sector contains an equilateral triangle and it follows that
two points inside a sector are at most a unit distance apart. Then apply the PHP.
Q4: (a) Number of games:
�
10
2
�
= 45.
(b) Number of draws is at least 45⇥ 0.7 = 31.5 so not less than 32.
(c) By the generalised pigeonhole principle there are at least 5 players with a positive
score or at least 5 players with a negative score.
(d) Suppose at least 5 players have positive scores which are all di↵erent. Then there
must be a minimum of 1 + 2 + 3 + 4 + 5 = 15 wins. This contradicts the result from (ii).
Q5: R(a, b) is the minimum number of points, which when connected with red or blue lines,
will always produce a complete graph Ka in red or a complete graph Kb in blue.
Q6: Identify sending a message about relationship gossip as ‘friend’ and sending a message
about what’s on next week as ‘stranger’ and use R(3, 3) = 6.
Q7: (a) After singling out person 1 there are 9 people to distribute too the pigeonholes ‘friend
of 1’ or ‘stranger to 1’. Hence one or the other contains at least 5 people.
(b) Suppose 5 or more mutual strangers to person 1. If 4 or more of these are mutual
friends we are done. Otherwise there must be at least one pair of mutual strangers.
Combining such a pair with person 1 produces a group of 3 mutual strangers.
(c) The above argument still holds with 4 mutual strangers to person 1.
(d) There are 6 or more mutual friends of person 1. In any group of 6 people there are
at least 3 mutual friends or 3 mutual strangers. In the latter case we are done, while in
the former case combining with person 1 we have a group of 4 mutual friends.
Q8: (a) K9 consists of 9 points (vertices) each connected to all the other points by an edge.
(b) The number of edges is
�
9
2
�
= 36.
(c) The number of possible colourings is 236.
(d) We know that R(3, 4) = 9. This means that in any two-colouring of K9 there must
be a K3 in one of the colours or a K4 in the other colour.
It is not true for K8.