Question

3. (a) Show that in a group of 6 people, there are either 3 either mutual friends or 3 mutual strangers. [3 marks) (b) Find the smallest number of people in a group such that there is actually about a probability of 50 that two of them have the same birthday. Justify. [3 marks]

Answer 1

a) This is an elementary result of Ramsey's Theorem.

This is a Graph Theory problem. Let vertices represent people and edges represent the connection between them. The connection can be of 2 'types': friends or strangers. Also note that is a complete graph with 6 vertices, i.e K6. Each vertex has a degree of 5. Let friends be connected by an edge of color red and strangers be connected by an edge of color blue. For any vertex v, its 5 neighbors are 01, 02, 03, 04, 05. Since there are only 2 colors, of the 5 edges incident to v, at least 3 of them have the same color. Without loss of generality, let's say v is connected to V1, V2, V3 with red edges. Now, if any of the edges among U1U2, U2 V3, V1 V3 is red (say, 02 03), then that edge forms a red triangle with the 2 edges between v and the edge's endpoints. That is, VU2, VU3, U2 Uz form a red triangle. If none of those edges is red, all the edges are blue and they (V1 V2, V2 V3, V1 V3 ) form a blue triangle. A red or a blue triangle always exists. Therefore, there exist at least 3 mutual friends or 3 mutual strangers.

b)

n = 23

For simplicity, ignore leap years. Then the probability that two people will share the same birthday out of n is i 365 x 364 x ... (366 – n) 365! 3651 (365 – n)!3651

min n such that this is greater or equal to 0.5

is n = 23